2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5  След.
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 09:41 


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

 Профиль  
                  
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 10:05 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 10:14 


07/08/14
4231
iifat в сообщении #1023560 писал(а):
Дык заранее ж писать рассчитанную на такой режим программу.

для останова - угу.
а для возобновления?
посчитали только $4$ тройки из $6$ для суммы $5$.
как возобновить не пересчитывая по-новой?
iifat в сообщении #1023560 писал(а):
А что, там реально месяц вырисовывается? комбинаций?

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

-- 05.06.2015, 10:16 --

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

 Профиль  
                  
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 10:20 


11/12/14
893
upgrade в сообщении #1023564 писал(а):
как возобновить не пересчитывая по-новой?


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

 Профиль  
                  
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 10:27 


07/08/14
4231
aa_dav в сообщении #1023565 писал(а):
upgrade в сообщении #1023564 писал(а):
как возобновить не пересчитывая по-новой?


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

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

-- 05.06.2015, 10:32 --

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

 Профиль  
                  
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 10:43 
Заслуженный участник
Аватара пользователя


19/12/10
1546
upgrade в сообщении #1023556 писал(а):
прошел месяц перебора 30 слагаемых для суммы 100, ждать надоело/вырубилось электричество/выгнали из-за компа/надо срочно посчитать другую задачу ...
1. как остановить не потеряв уже обработанные данные?
2. как затем возобновить не с самого начала, чтобы снова месяц не считать?
без сохранения определенным образом полученных результатов - никак.

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

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

 Профиль  
                  
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 10:44 
Заслуженный участник


16/02/13
4105
Владивосток
upgrade в сообщении #1023564 писал(а):
как реализовать выбор только тех слагаемых , которые могут участвовать в переборе
Одним из способов. Уверяю вас, перебирать 30 чисел от 1 до 100, проверяя каждый раз сумму — не единственный метод.

 Профиль  
                  
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 11:02 


07/08/14
4231
whitefox в сообщении #1023569 писал(а):
Перечисляйте представления в лексикографическом порядке, например так.

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

 Профиль  
                  
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 11:10 
Заслуженный участник
Аватара пользователя


19/12/10
1546
upgrade в сообщении #1023575 писал(а):
допустим два массива один длиной $20$, с суммой для комбинаций $100$,
а второй длиной $80$ с суммой для комбинаций $100$
я правильно понимаю, что второй массив будет посчитан быстрее первого?

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

upgrade в сообщении #1023575 писал(а):
я не очень понял идею, каким образом можно комбинации увидеть?

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

 Профиль  
                  
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 11:26 


07/08/14
4231
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$
?

 Профиль  
                  
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 11:36 
Заслуженный участник
Аватара пользователя


09/09/14
6328

(upgrade)

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

 Профиль  
                  
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 11:43 
Заслуженный участник
Аватара пользователя


19/12/10
1546
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

 Профиль  
                  
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 11:44 


07/08/14
4231

(Оффтоп)

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

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

 Профиль  
                  
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 11:52 


11/12/14
893
upgrade в сообщении #1023598 писал(а):
я пытаюсь понять, как получаем комбинации по методу whitefox.


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

 Профиль  
                  
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 12:02 


07/08/14
4231
whitefox в сообщении #1023597 писал(а):
Здесь $n=3$, $m=5$ и $p=2$ Соответствующие представления для будут

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

-- 05.06.2015, 12:08 --

aa_dav в сообщении #1023601 писал(а):
еще раз посмотрите на например моё описание рекурсивного алгоритма.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 68 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group