Создание массивов чисел с заданной суммой элментов

[upgrade]

прошел месяц перебора 30 слагаемых для суммы 100, ждать надоело/вырубилось электричество/выгнали из-за компа/надо срочно посчитать другую задачу ...
1. как остановить не потеряв уже обработанные данные?
2. как затем возобновить не с самого начала, чтобы снова месяц не считать?
без сохранения определенным образом полученных результатов - никак.

[iifat]

Дык заранее ж писать рассчитанную на такой режим программу. А что, там реально месяц вырисовывается? $C_{71}^{30}$ комбинаций?

[upgrade]

iifat в сообщении #1023560 писал(а):

Дык заранее ж писать рассчитанную на такой режим программу.

для останова - угу.
а для возобновления?
посчитали только $4$ тройки из $6$ для суммы $5$.
как возобновить не пересчитывая по-новой?

iifat в сообщении #1023560 писал(а):

А что, там реально месяц вырисовывается? комбинаций?

а как реализовать выбор только тех слагаемых , которые могут участвовать в переборе, например, как отбросить участие в переборе комбинации $4+4+4$, не проверяя что она должна быть отброшена?
для $10$-ти разрядных слагаемых - $10^n$ , где $n$ - количество слагаемых

-- 05.06.2015, 10:16 --

я считаю поразрядно - сперва посчитали для $2$-х разрядов, запомнили в массивчик, затем из этого массивчика дергаем слагаемые (которые каждое состоит из двух уже посчитанных) и перебираем их с новыми - снова в массивчик и так далее.

[aa_dav]

upgrade в сообщении #1023564 писал(а):

как возобновить не пересчитывая по-новой?

Уже же было продемонстрировано, что алгоритм может продолжить вычислять следующие последовательности зная текущую.

[upgrade]

aa_dav в сообщении #1023565 писал(а):

upgrade в сообщении #1023564 писал(а):

как возобновить не пересчитывая по-новой?

Уже же было продемонстрировано, что алгоритм может продолжить вычислять следующие последовательности зная текущую.

да, видел. я дополнил, что Ваши вычисления поячеечные (у меня они - "поразрядные") надо сохранять и при расчете следующих комбинаций перебирать значения в новой ячейке (в новом разряде) с сохраненными.
считывать уже полученные данные с комбинациями слагаемых и только эти комбинации включать в перебор с новыми.

-- 05.06.2015, 10:32 --

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

[whitefox]

upgrade в сообщении #1023556 писал(а):

прошел месяц перебора 30 слагаемых для суммы 100, ждать надоело/вырубилось электричество/выгнали из-за компа/надо срочно посчитать другую задачу ...
1. как остановить не потеряв уже обработанные данные?
2. как затем возобновить не с самого начала, чтобы снова месяц не считать?
без сохранения определенным образом полученных результатов - никак.

Перечисляйте представления в лексикографическом порядке, например так. Предусмотрите возможность запуска программы с любого представления. Организуйте периодический сброс буферов вывода на диск, например каждые 10 минут. А если программа никаких результатов на диске не сохраняет, то организуйте периодический, например каждые 10 минут, вывод на диск (со сбросом на диск буфера вывода) последнего найденного представления (с перезаписью файла).

В этом случае максимальная потеря при прерывании программы — 10 минут работы.

[iifat]

upgrade в сообщении #1023564 писал(а):

как реализовать выбор только тех слагаемых , которые могут участвовать в переборе

Одним из способов. Уверяю вас, перебирать 30 чисел от 1 до 100, проверяя каждый раз сумму — не единственный метод.

[upgrade]

whitefox в сообщении #1023569 писал(а):

Перечисляйте представления в лексикографическом порядке, например так.

я не очень понял идею получения комбинаций, каким образом можно комбинации увидеть?
допустим два массива один длиной $20$, с суммой для комбинаций $100$,
а второй длиной $80$ с суммой для комбинаций $100$
я правильно понимаю, что второй массив будет посчитан быстрее первого?

[whitefox]

upgrade в сообщении #1023575 писал(а):

допустим два массива один длиной $20$, с суммой для комбинаций $100$,
а второй длиной $80$ с суммой для комбинаций $100$
я правильно понимаю, что второй массив будет посчитан быстрее первого?

Перебор представлений для первого массива можно выполнить за реальное время, а перебор для второго — практически неосуществим.

upgrade в сообщении #1023575 писал(а):

я не очень понял идею, каким образом можно комбинации увидеть?

Пожалуйста, поподробнее, что именно не понятно?

[upgrade]

whitefox в сообщении #1023552 писал(а):

Для удобства перейдём к эквивалентной задаче — перечислить в лексикографическом порядке все представления числа $p=m-n$ в виде суммы целых неотрицательных чисел.
Для обратного перехода к исходной задаче нужно будет каждый элемент найденного представления увеличить на $1$.

каким образом, узнав комбинации для числа $p$, я узнаю комбинации для числа $m$?
допустим $m=3$, $n=2$ тогда $p=1$, элементы массива длиной $n$ принимают значения $1,2,3,4,5$
как я "увижу" комбинации
$1,2$
$2,1$
или похуже $m=20$, $n=2$ тогда $p=18$, но элементы массива длиной $n$ принимают значения только $9,10,11$
как увидеть комбинации
$10,10$
$9,11$
$11,9$
?

[grizzly]

(upgrade)

В отличие от Вас, whitefox точно сформулировал в своих сообщениях, какую постановку задачи он рассматривает. Если постановка задачи ТС и допускает различные интерпретации, то вряд ли Ваша более правдоподобна.

[whitefox]

upgrade в сообщении #1023589 писал(а):

каким образом, узнав комбинации для числа $p$, я узнаю комбинации для числа $m$?

Нужно просто каждый элемент представления для $p$ в целых неотрицательных числах увеличить на 1, и получим представление для $m$ в целых положительных числах.
Возьмём пример стартового поста темы:

ilya_msu в сообщении #1023465 писал(а):

То есть для массива из 3 чисел, с заданной суммой 5, необходимо вывести что-то типа этого
1 1 3
1 2 2
2 1 2
1 3 1
2 2 1
3 1 1

Здесь $n=3,\;m=5$ и $p=2.$ Соответствующие представления для $p$ будут:
0 0 2
0 1 1
1 0 0
0 1 0
1 1 0
2 0 0

Или в лексикографическом порядке:
0 0 2
0 1 1
0 2 0
1 0 1
1 1 0
2 0 0

Что соответствует представлениям для $m:$
1 1 3
1 2 2
1 3 1
2 1 2
2 2 1
3 1 1

[upgrade]

(Оффтоп)

grizzly в сообщении #1023595 писал(а):

В отличие от Вас, whitefox точно сформулировал в своих сообщениях, какую постановку задачи он рассматривает. Если постановка задачи ТС и допускает различные интерпретации, то вряд ли Ваша более правдоподобна.

я пытаюсь понять, как получаем комбинации по методу whitefox.

[aa_dav]

upgrade в сообщении #1023598 писал(а):

я пытаюсь понять, как получаем комбинации по методу whitefox.

обратите внимание как у него первая колонка последовательно проходит значения 1,2,3
внутри этого цикла вторая колонка последовательно проходит значения 1,2,3
внутри этих циклов последняя колонка "вынуждена" становится конкретным значением.
еще раз посмотрите на например моё описание рекурсивного алгоритма.

[upgrade]

whitefox в сообщении #1023597 писал(а):

Здесь $n=3$, $m=5$ и $p=2$ Соответствующие представления для будут

спасибо, понял. количество переборов практически не меняется.

-- 05.06.2015, 12:08 --

aa_dav в сообщении #1023601 писал(а):

еще раз посмотрите на например моё описание рекурсивного алгоритма.

рекурсию компы не тянут - памяти не хватает, а так то, с тем что Вы написали, я и работаю, только в память сохраняю результаты шага рекурсии. 20 шагов (длина массива)- это максимум.