Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Получить все комбинации..
|
|||
|---|---|---|---|
|
#18+
Народ, срочно понадобилась такая задача (вернее, ее решение :) ): есть натуральные числа 1,2,3..n. Необходимо получить всевозможные последовательности этих чисел, к-е в сумме дают n, причем последовательности "1,2,3" и "3,2,1" считать разными - т.е. местоположение числа играет свою роль.. Очень важно получить именно ВСЕ последовательности. Хочу подчеркнуть, что эта задачка не является школьным/университетским заданием, а входит как некоторая часть в большую задачу.. Пожалуйста, помогите - я зашел в тупик. З.Ы. А если еще и реализацию покажет на любом языке - благодарности моей не будет предела.. :) Для корабля, который не знает куда плыть, нет попутного ветра... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2004, 03:09 |
|
||
|
Получить все комбинации..
|
|||
|---|---|---|---|
|
#18+
/topic/56272 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2004, 07:55 |
|
||
|
Получить все комбинации..
|
|||
|---|---|---|---|
|
#18+
2 aleks2 Это не совсем задача о рюкзаке , потому что исходное мн-во слишком особенное: 1,2,3..n. тут похожие задачи можно найти: http://pascal.city.tomsk.net/task/pereb.htm На первой странице даже уже что-то такое есть : 8-ая задача.. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2004, 08:35 |
|
||
|
Получить все комбинации..
|
|||
|---|---|---|---|
|
#18+
restart: > # получить все наборы n_1...n_k: sum(n_i) = n > > f:=proc(x::list,i::integer) > local y::list, k::integer; > if (i=1) then > y[1]:=x[1]+x[2]: > for k from 2 to nops(x)-1 do y[k]:=x[k+1] od: > elif (i=nops(x)-1) then > for k to nops(x)-1 do y[k]:=x[k] od: > y :=x+x[nops(x)]: > else > for k to i-1 do y[k]:=x[k] od: > y:=x+x[i+1]: > for k from i+1 to nops(x)-1 do y[k]:=x[k+1] od: > fi: > seq(y[k],k=1..nops(x)-1); > end proc: > > n:=6; # к примеру > for i to n-1 do N:={} od: > N[1]:={[seq(1,k=1..n)]}: > N[2]:=N[2] union {seq([f(N[1][1],k)],k=1..n-1)}: > > for i from 3 to n-1 do > for j to nops(N[i-1]) do > N:=N union {seq([f(N[i-1][j],k)],k=1..n-i+1)} od od: > > for i to n-1 do N;nops(N); od; > M:=N[1]: > for i from 2 to n-1 do > for k to nops(N) do > M:=M union {N[k]} od od: > '____________________________'; > M; > nops(M); комментарий 1) написано на maple7 - устраивает? 2) код, я полагаю, читабелен... намного по командам maple: list - тип данных, вроде array nops - количество элементов, типа длина массива union - объединение множеств (set) в принципе, все это можно перенести на любой общеисп. яз. прогр. по алгоритму: легко понять, что различных наборов, удовлетворяющих усл, будет ровно (2^n) -1. (можно проверить вручную, можно откр учебник по комбинаторике) строим наборы: первый = (1,1...1,1) = ровно n едениц второй и послед наборы строятся так в пред наборе последовательно суммируем каждые соседние элементы и тд пример: n=4 (1,1,1,1) -> (2,1,1),(1,2,1),(1,1,2) -> (3,1),(2,2),(1,3) всё естественно, будет много повторов - используем тип "множество" - все повторы как рукой снимет. пример ответа: {[1, 2, 1, 2], [2, 1, 2, 1], [2, 1, 1, 2], [1, 3, 1, 1], [1, 2, 2, 1], [1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1], [1, 2, 1, 1, 1], [1, 1, 2, 1, 1], [1, 1, 1, 2, 1], [1, 1, 1, 1, 2], [3, 1, 1, 1], [2, 2, 1, 1], [4, 2], [2, 4], [5, 1], [2, 2, 2], [4, 1, 1], [1, 4, 1], [3, 1, 2], [1, 3, 2], [1, 2, 3], [3, 2, 1], [2, 3, 1], [2, 1, 3], [1, 1, 3, 1], [1, 1, 2, 2], [1, 1, 1, 3], [1, 5], [3, 3], [1, 1, 4]} при n = 6 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.04.2004, 08:47 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=32477027&tid=1348478]: |
0ms |
get settings: |
9ms |
get forum list: |
12ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
28ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
50ms |
get tp. blocked users: |
2ms |
| others: | 288ms |
| total: | 413ms |
| 0 / 0 |
