|
|
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
Добрый день, столкнулся с такой задачкой - есть некое кол-во чисел (до 200)- нужно перебрать все варианты сумм этих чисел, например есть 800 600 500 400 800+600+500+400 800+500+400 800+600 800+500 800+400 800+600+500 800+600+400 600+500+400 600+500 600+400 500+400 800 600 500 400 чувствую что рекурсия, но как? Олег ПС Задачка явно студенческая, да я в другой области работаю, не могу сообразить ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 18:05:23 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
olegsng, Странная задача: 2^200 это очень много. А перебор нужно делать без рекурсии - каждае число лбо входит в сумму, либо нет - просто цикл от 0 (все числа не входят) до 2^(кол-во чисел). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 18:12:41 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
x1ca4064, да число большое, но это очень грубая постановка для простоты объяснения, оценки верхнего предела вычислений и получаемых результатов. Поставлю компьютер на просчет и пусть считает, все равно на работе я его не выключаю никогда. На самом деле числа будут разбиваться на группы, скажем по 50 шт по определенному соотношению "больших" и "маленьких" значений и к ним будет применяться этот же алгоритм 4 раза для 200 (4*50=200) чисел. Если результат в группе подобен всему множеству - то и будем бить на группы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 18:31:05 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
x1ca4064olegsng, Странная задача: 2^200 это очень много. А перебор нужно делать без рекурсии - каждае число лбо входит в сумму, либо нет - просто цикл от 0 (все числа не входят) до 2^(кол-во чисел). Из 200 чисел получится 200 + 199 + ... + 2 + 1 = 20100 сумм, т.е. (N + 1) * N / 2, а не 2^N olegsng Если есть числа от 1 до 5, то список всех сумм будет: 1, 1+2, 1+3, 1+4, 1+5, 2, 2+3, 2+4, 2+5, 3, 3+4, 3+5, 4, 4+5, 5 Где ж тут рекурсия? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 19:38:15 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
olegsngНа самом деле числа будут разбиваться на группы Не обязательно, если конечно в этом нет иной необходимости. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 19:41:08 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
Edd.Dragon Если есть числа от 1 до 5, то список всех сумм будет: 1, 1+2, 1+3, 1+4, 1+5, 2, 2+3, 2+4, 2+5, 3, 3+4, 3+5, 4, 4+5, 5 Где ж тут рекурсия? Ой прогнал Ща ))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 19:41:51 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
внешний цикл от 0 до 199, внутренний от i до 199, где i - номер итерации первого во внутреннем цикле числа суммируются от i-го элемента до последнего на каждой итерации внутреннего цикла получаем новую сумму на каждой итерации внешнего цикла сумму нужно обнулить ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 19:47:53 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
Количество вариантов: (см. картинку) Вот как можно разложить рекурсию и перебрать циклами: Код: plaintext 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. Ща попробую алгоритм накатать... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 20:33:41 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
Edd.Dragon Из 200 чисел получится 200 + 199 + ... + 2 + 1 = 20100 сумм, т.е. (N + 1) * N / 2, а не 2^N Категорически не согласен: начальная постановка "нужно перебрать все варианты сумм этих чисел". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 20:37:31 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
Правда так вывод будет вперемешку. Лучше по отдельности перебирать сначала все комбинации с 1 слагаемым, потом с 2-мя, потом с 3-мя ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 20:38:29 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
x1ca4064Edd.Dragon Из 200 чисел получится 200 + 199 + ... + 2 + 1 = 20100 сумм, т.е. (N + 1) * N / 2, а не 2^N Категорически не согласен: начальная постановка "нужно перебрать все варианты сумм этих чисел". Уже поправился )) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 20:38:45 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
600+200 = 500+300 причем это будет фигурировать много где. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 20:41:40 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
Edd.DragonПравда так вывод будет вперемешку. Это не важно."Нужная" сумма определяется и фиксируется "нужная" комбинация ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 20:55:07 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
Edd.DragonКоличество вариантов: (см. картинку) Вот как можно разложить рекурсию и перебрать циклами: Код: plaintext 1. 2. 3. 4. 5. 6. Ща попробую алгоритм накатать... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 21:41:12 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
искомые суммы можно представить как где, - числа из множества исходного набора чисел ( ), - количество чисел во множестве тогда выражение(строку) можно рассматривать как представление разрядного 2-ич. числа. значит, количество " все варианты сумм этих чисел " равно (исключая 0) при не выполнении условия ( ) потребуется некоторая модификация... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 21:54:22 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
avb1003Edd.DragonКоличество вариантов: (см. картинку) Правильно, для 4-х чисел 15 вариантов, в постановке задачи оно так и показано Ща попробую алгоритм накатать... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 21:55:01 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
"x1ca4064" прав ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.10.2010, 21:56:14 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
Сорри, пришлось отвлечься С циклами сломал себе мозг. Выше схемка, которую приводил - это как раз под рекурсию: Код: plaintext 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. Кстати, обнаружил, что вывод endl в поток сильно тормозит процесс. При просчете комбинаций из 20 чисел, если записывать их в столбик по одному, т.е. Код: plaintext avb1003 Ага, пока тестил, заметил эти магические числа :( Так что, olegsngНа самом деле числа будут разбиваться на группы, скажем по 50 шт не вариант. При 20 числах получаем 1 миллион вариантов. Если держать их в оперативке, то на такой массив потребуется 4 Мб памяти, в файле как у меня (по 10 знакомест на 1 число) - 10 Мб файл. При 30 числах - в 1024 раза больше требования: 4 Гб в оперативке (32-битная винда уже не выдаст приложению столько) или 10 Гб на винт. При 40 числах - еще в 1024 больше: 4 Тб в оперативке или 10 Тб на винт. При 50 - еще в 1024 раза больше... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2010, 03:47:18 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
* Переменная count в программе - для проверки, так то считать кол-во не надо - известно заранее. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2010, 03:49:16 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
Edd.Dragon void stepIn(int pos, int sum) { for(int i = pos; i < n; i++) { int new_sum = sum + nums[i]; outfile << setw(10) << new_sum; count++; if(i < n - 1) stepIn(i + 1, new_sum); } } Ага, похоже function SearchProfile(Data: PProfileArray; FromIndex, ProfileLen...): Integer; var ... begin for i := FromIndex to Data^.Size-1 do begin Yield; M := SearchProfile(Data, i+1, ProfileLen-Data^.Values[i].ProfPartLen, ProfileNumber); if M = нужное то ...... end; SearchProfile := ....; end; При 80 числах - я не дождался результата, при 40 реальных данных - 5-20 сек на моем стареньком Core2 первого выпуска. Сильно зависит сколько "маленьких" чисел, результат определяется как остаток (ProfileLen-Data^.Values[i].ProfPartLen) от некоего начального значения, если числа "маленькие", то их "больше" в начальном значении. Результат - отличный при 40, так что 200 буду бить на 5 интервалов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2010, 21:33:25 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
Раз вам хранить все варианты сразу не нужно, то конечно проще. Можно варьировать. авторПри 80 числах - я не дождался результата, при 40 реальных данных - 5-20 сек Ну вот для 50-ти было бы порядка 5-20 тыс. сек Для 60 - 5-20 млн. сек. (~ пол года) Для 70 - 5-20 млрд. сек. Для 80 - 5-20 триллионов сек (пол миллиона лет) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2010, 22:26:21 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
x1ca4064А перебор нужно делать без рекурсии - каждае число лбо входит в сумму, либо нет - просто цикл от 0 (все числа не входят) до 2^(кол-во чисел). +1 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2010, 23:15:29 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
Edd.Dragon Для 80 - 5-20 триллионов сек (пол миллиона лет) Да уж, мужики бы не дождались, 80 чисел - это 40 изделий в производство, задание на полдня. Работа не бей лежачего - полдня один раз в полмиллиона лет. Впрочем, как говорил мой один знакомый - если разработанный нами алгоритм не тянет компьютер, то мы купим новый соответствующий компьютер. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2010, 23:28:12 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
olegsng Впрочем, как говорил мой один знакомый - если разработанный нами алгоритм не тянет компьютер, то мы купим новый соответствующий компьютер. а компьютеры он из Топ500 выбирает? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.10.2010, 23:36:45 |
|
||
|
Перебор вариантов сумм
|
|||
|---|---|---|---|
|
#18+
ZyK_BotaN а компьютеры он из Топ500 выбирает? думаю, что какой нибудь современный бытовой граф акселератор с массово параллельными процессорами (сколько их там сейчас в АТИ - 1000 потоковых процессоров?) такую задачку расщелкает быстро ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.10.2010, 00:45:33 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=36878664&tid=1343419]: |
0ms |
get settings: |
11ms |
get forum list: |
16ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
200ms |
get topic data: |
12ms |
get forum data: |
3ms |
get page messages: |
83ms |
get tp. blocked users: |
1ms |
| others: | 254ms |
| total: | 588ms |

| 0 / 0 |
