Функция перебора по разу

@jamki · Регистрация: 04.09.2021

Author24 — интернет-сервис помощи студентам

Есть QVector<double> max, есть сумма double s, есть QVector<double> otvet с таким же размером как у max.

Пример: ( для быстрого набора пишу круглые скобки вместо корректных {} )
max=(3,3,3), s =4, нужно распределить всевозможно сумму на ячейки. При этом учитывать, что вектор max показывает максимальный размер ячейки.
Итоговые варианты:
3 1 0
3 0 1
2 2 0
2 1 1
2 0 2
1 3 0
1 2 1
1 1 2
1 0 3
0 3 1
0 2 2
0 1 3

Необходимо написать функцию которая меняет содержимое ячейки на следующий вариант. То есть (смотрим данные из примера) если в векторе ответ было 1 3 0, то 1 2 1.

Возможно нужна рекурсия с выходом изменения.

Логика выстраивалась (можно в любом порядке: возрастание, убывание):
Смотрим сумма элементов Макс<=s, тогда можно распределять

В первую ячейку положим максимально возможное число. Если s<max[0], то в первую ячейку ответа записываем s и остальные ячейки заполняем нулями. Иначе в первую ячейку заполняем max[0], а вторую *Если размер ответа равен 2 ячейкам. S-otvet[0]
Потом надо как—то перебирать первую ячейку от max[0] до 0, но при этом учитывать, про возможный размер 2 ячейки.

Те сначала нужно продумать логику как заполнять 2 ячейки. А потом нарастить функцию, чтобы она рассматривала 1 ячейку как 1 ячейку, а остальное как 2 ячейку. Тут возможна рекурсия.

Желательно как—то проработать еще шаг step. То есть перекидывать не 1, а другое число.. допустим только двойками…

Возможно нужно сделать эту функцию эффективной и работать с указателями. Планируется нереально часто ей пользоваться. Важно, чтобы она меняла ответ по 1 разу. Накапливать и хранить варианты нельзя.

Добавлено через 1 час 44 минуты
Уверена что тут логика сломана в самом запросе. Я сама не очень понимаю как это делать. Возможно нужна функция которая на вход возьмет вектор ответ и обновит его. Наверно нужно сделать упор на шаг переброса числа.

@pupitan · 12.10.2023, 11:26

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
int main() {
   
 
    int row_size = 5;   // число ячеек
    int max = 7;        // нужное число
 
    int* arr = new int[3];
 
 
    for (int i = 0; i < row_size; i++)
        arr[i] = 0;
 
    arr[0]       = max; //
 
    int count   = 0;   //для \n
 
    int num     = 0;
 
    int counter = 0;
 
    for (int lim = 0; lim < 18; lim++) {
        
        int sum = 0;
        
        for (int i = 0; i < lim; i++) {
            
            for (int a = 0; a < row_size; a++)
                    sum += arr[a];
                    
                if(sum == max) {
 
                    arr[num] -= 1;
                
                    if (i + 1 <= row_size) {
                        arr[counter] += 1;
                        counter ++;
                   }
                   
                    if(counter == row_size)
                
                        counter = num+1;
                        
                        
                    if(arr[num] == 0)
                                    num ++;
 
                       }
 
        }
 
        for (int i = 0; i < row_size; i++) {
 
            cout << arr[i];
            
            count++;
            
            if (count % row_size == 0)
                cout << '\n';
 
        }
 
    }
    
    
    delete [] arr;
}

@jamki · 12.10.2023, 23:59 **[ТС]**

Не так.
Есть сумма s. Нужно перебрать все сочетания = разложить на заданное кол-во ячеек. При этом учесть, что в каждой ячейке есть ограничение, те нельзя в ячейку записать число больше.

Для суммы s = 5 на 3 ячейки
Могли быть следующие варианты
5 0 0
4 1 0
4 0 1
3 2 0
3 1 1 тд
Но так как стоит ограничение m = (3,3,3) -> в первой ячейке не больше 3, во второй ячейке не больше трех, в третей ячейке не больше трех,
то варианты :
3 2 0
3 1 1 тд
1 4 0 - нельзя

Задача функции пример:
При данных сумме s=12, ограничения на i ячейки m=(6 4 8 2) шаг_переброса step = 1 и векторе otvet = (6 2 2 2)
Запустить функцию и она обновит вектор otvet на (6 1 5 0)

Пояснение:
Если установить правило, что в первую ячейку записать максимально возможное число, во вторую максимально возможное число..
То первый вариант будет 6 4 2 0 далее
6 4 2 0
6 4 1 1
6 4 0 2
6 3 3 0
6 3 2 1
6 3 1 2
6 2 4 0
6 2 3 1
6 2 2 2
6 1 5 0
6 1 4 1
и тд

Возможно тут подойдет рекурсия
Которая перебрасывает шаг step из a в b : (a₁ b₁)
А общая картина (a₂ (b₂)), где b₂ = (a₁ b₁)...

Функция должна выдать 1 следующий вариант, возможно в самой рекурсии делать проверку: дошли до последнего числа в ответе, то больше ни чего не делай и выходи.

Шаг желательно сделать, так как это сократит варианты.... Функцию нужно запускать в цикле, пока функция не сможет выдавать следующий вариант = переберет всё.
Если функция не может выдать вариант, то должен измениться признак. Допустим есть переменная int stop = 1;

Работать в double

- на вход функции передавать указатели и работать напрямую, чтобы сократить время работы программы
- не запоминать все варианты забивая память
- шаг может быть любой 1 2 0.5

Новые блоги и статьи Все статьи Все блоги /
Что нового в C# 14 UnmanagedCoder 10.03.2025 Предстоящая версия C# 14 обещает принести изменения, которые сделают разработку еще более приятной и эффективной. Что стоит отметить, так это влияние сообщества разработчиков на формирование новых. . .	Формулы поворота Igor3D 10.03.2025 Добрый день Тема Эти формулы приводятся во множестве тьюториалов, часто под видом "матрица вращения на плоскости". x' = x * cos(a) - y * sin(a) y' = y * cos(a) + x * sin(a) Как бы Вы их. . .	Что нового в .NET 10 UnmanagedCoder 10.03.2025 . NET 10 выходит как релиз с длительной поддержкой (LTS), включающей три года обновлений. В этом обновлении Microsoft сфокусировались на нескольких направлениях: производительность, оптимизация. . .	Отложенное высвобождение, RCU и Hazard Pointer в C++26 NullReferenced 09.03.2025 Многопоточное программирование стало важной частью современной разработки. Когда несколько потоков одновременно работают с общими данными, возникает целый ряд проблем, связанных с синхронизацией и. . .	Неблокирующийся стек на C++26 NullReferenced 09.03.2025 Традиционные способы синхронизации в многопоточном программировании — мьютексы, семафоры, условные переменные — часто превращаются в узкое место в плане производительности. При этом неблокирующиеся. . .
Обработка строк в C++26: Новые возможности string и string_view NullReferenced 09.03.2025 Новый стандарт C++26 предлагает много улучшений для работы с привычными string и относительно новыми string_view. string_view - это невладеющая ссылка на последовательность символов, появившаяся в. . .	Мой первый аддон для Blender 3D, с помощью нейронки (не зная даже азов пайтона, но это не значит что так и с остальным). Hrethgir 09.03.2025 Потратил весь день. Пол-дня мне хватило, чтобы понять что с версией с 14B мне не одолеть написание функционального кода, на языке с которым я вообще никак не знаком - пайтон. Версия 22B от другого. . .	Einstein@Home сегодня исполняется двадцать лет! Programma_Boinc 09.03.2025 Einstein@Home сегодня исполняется двадцать лет! Отправлено 19 февраля 2025 года в 17:20:21 UTC Я хочу поздравить всех наших волонтеров, разработчиков и ученых из Einstein@Home. Мы официально. . .	Заполнители и расширенный набор символов в C++26 NullReferenced 09.03.2025 C++26 представляет два важных обновления: заполнители и расширенный набор символов. Заполнители (placeholders) решают давнюю проблему лаконичности кода в шаблонных выражениях и лямбда-функциях. Они. . .	Контракты в C++26 NullReferenced 09.03.2025 Контракты – это механизм, позволяющий указывать предусловия, постусловия и инварианты для функций в коде. Эта функциональность должна была стать частью C++20, но была исключена на встрече комитета. . .

@jamki 0 / 0 / 0 Регистрация: 04.09.2021 Сообщений: 15
		1
	Функция перебора по разу 11.10.2023, 18:35. Показов 2733. Ответов 2 Метки перебор чисел, рекурсивная функция, с++, шаг (Все метки) Есть QVector<double> max, есть сумма double s, есть QVector<double> otvet с таким же размером как у max. Пример: ( для быстрого набора пишу круглые скобки вместо корректных {} ) max=(3,3,3), s =4, нужно распределить всевозможно сумму на ячейки. При этом учитывать, что вектор max показывает максимальный размер ячейки. Итоговые варианты: 3 1 0 3 0 1 2 2 0 2 1 1 2 0 2 1 3 0 1 2 1 1 1 2 1 0 3 0 3 1 0 2 2 0 1 3 Необходимо написать функцию которая меняет содержимое ячейки на следующий вариант. То есть (смотрим данные из примера) если в векторе ответ было 1 3 0, то 1 2 1. Возможно нужна рекурсия с выходом изменения. Логика выстраивалась (можно в любом порядке: возрастание, убывание): Смотрим сумма элементов Макс<=s, тогда можно распределять В первую ячейку положим максимально возможное число. Если s<max[0], то в первую ячейку ответа записываем s и остальные ячейки заполняем нулями. Иначе в первую ячейку заполняем max[0], а вторую Если размер ответа равен 2 ячейкам. S-otvet[0] Потом надо как—то перебирать первую ячейку от max[0] до 0, но при этом учитывать, про возможный размер 2 ячейки. Те сначала нужно продумать логику как заполнять 2 ячейки. А потом нарастить функцию, чтобы она рассматривала 1 ячейку как 1 ячейку, а остальное как 2 ячейку. Тут возможна рекурсия. Желательно как—то проработать еще шаг step. То есть перекидывать не 1, а другое число.. допустим только двойками… Возможно нужно сделать эту функцию эффективной и работать с указателями. Планируется нереально часто ей пользоваться. Важно, чтобы она меняла ответ по 1 разу. Накапливать и хранить варианты нельзя. Добавлено через 1 час 44 минуты* Уверена что тут логика сломана в самом запросе. Я сама не очень понимаю как это делать. Возможно нужна функция которая на вход возьмет вектор ответ и обновит его. Наверно нужно сделать упор на шаг переброса числа. 0

@jamki 0 / 0 / 0 Регистрация: 04.09.2021 Сообщений: 15
	12.10.2023, 23:59 [ТС]	3
	Не так. Есть сумма s. Нужно перебрать все сочетания = разложить на заданное кол-во ячеек. При этом учесть, что в каждой ячейке есть ограничение, те нельзя в ячейку записать число больше. Для суммы s = 5 на 3 ячейки Могли быть следующие варианты 5 0 0 4 1 0 4 0 1 3 2 0 3 1 1 тд Но так как стоит ограничение m = (3,3,3) -> в первой ячейке не больше 3, во второй ячейке не больше трех, в третей ячейке не больше трех, то варианты : 3 2 0 3 1 1 тд 1 4 0 - нельзя Задача функции пример: При данных сумме s=12, ограничения на i ячейки m=(6 4 8 2) шаг_переброса step = 1 и векторе otvet = (6 2 2 2) Запустить функцию и она обновит вектор otvet на (6 1 5 0) Пояснение: Если установить правило, что в первую ячейку записать максимально возможное число, во вторую максимально возможное число.. То первый вариант будет 6 4 2 0 далее 6 4 2 0 6 4 1 1 6 4 0 2 6 3 3 0 6 3 2 1 6 3 1 2 6 2 4 0 6 2 3 1 6 2 2 2 6 1 5 0 6 1 4 1 и тд Возможно тут подойдет рекурсия Которая перебрасывает шаг step из a в b : (a₁ b₁) А общая картина (a₂ (b₂)), где b₂ = (a₁ b₁)... Функция должна выдать 1 следующий вариант, возможно в самой рекурсии делать проверку: дошли до последнего числа в ответе, то больше ни чего не делай и выходи. Шаг желательно сделать, так как это сократит варианты.... Функцию нужно запускать в цикле, пока функция не сможет выдавать следующий вариант = переберет всё. Если функция не может выдать вариант, то должен измениться признак. Допустим есть переменная int stop = 1; Работать в double - на вход функции передавать указатели и работать напрямую, чтобы сократить время работы программы - не запоминать все варианты забивая память - шаг может быть любой 1 2 0.5 0