2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4, 5  След.
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 20:42 
Аватара пользователя
aa_dav в сообщении #1023739 писал(а):
Есть ли способ избежать без кодов Грея?

Кнут о таком способе не пишет. А это почти стопроцентная гарантия, что другого способа просто нет.

Впрочем, алгоритм, реализованный в программе ewert, показывает, что для данной задачи лексикографический порядок тоже является неким кодом Грея. :D

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение05.06.2015, 23:17 
А блин, да, возврат из рекурсии - тоже операция (и еще какая).
Так что да, я фигню спорол в предыдущем сообщении.

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение06.06.2015, 00:19 
aa_dav в сообщении #1023821 писал(а):
А блин, да, возврат из рекурсии - тоже операция (и еще какая).

Да маленькая. Там проблема в другом: если рекурсия на каждом шаге, то стек засоряется.

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение06.06.2015, 00:56 
ewert в сообщении #1023826 писал(а):
Да маленькая. Там проблема в другом: если рекурсия на каждом шаге, то стек засоряется.


Да млин что за мифология вокруг стека возникла вообще???
То у одного он не могёт, то у другого засоряется...
Оценки чем обоснованы?
По сабжевому алгоритму в чём они выражаются?

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение06.06.2015, 01:06 
aa_dav в сообщении #1023832 писал(а):
Да млин что за мифология вокруг стека возникла вообще???

Не мифология. Стек как класс требует для себя выделения памяти ваще; увы, это его характеристическое свойство.

И если для его хранения требуется память, хотя бы сопоставимая с памятью машины -- то это уже крайне нехорошо.

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение06.06.2015, 01:20 
ewert в сообщении #1023833 писал(а):
И если для его хранения требуется память, хотя бы сопоставимая с памятью машины -- то это уже крайне нехорошо.


Согласен - если автор топика перебирает массив из миллиона элементов, то нехорошо для стека совсем, да. Как и для перебора.

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение06.06.2015, 01:27 
aa_dav в сообщении #1023836 писал(а):
если автор топика перебирает массив из миллиона элементов, то нехорошо для стека совсем, да.

А эти две вещи меж собой, кстати, никак не связаны. Да и мульён -- не так уж и много (хоть это и не в тему)

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение06.06.2015, 08:42 
arseniiv в сообщении #1023682 писал(а):
А на двойку-то зачем уменьшать?

Чтобы понять суть. Это экспериментальное уменьшение на двойку. Можно увеличить на единицу. А можно попробовать умножить.
Пытаюсь понять что дает эта методика, уменьшение - еще одна операция.

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение06.06.2015, 09:48 
ewert в сообщении #1023838 писал(а):
Да и мульён -- не так уж и много (хоть это и не в тему)


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

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение06.06.2015, 10:02 
Аватара пользователя
upgrade в сообщении #1023875 писал(а):
Пытаюсь понять что дает эта методика, уменьшение - еще одна операция.

Да никакая это не методика. Просто "внутренне представление" данных в алгоритме не обязано совпадать с "внешним представлением". Совершенно без разницы какими символами мы будем обозначать те или иные "цифры" внутреннего представления. Так в примере ewert для кодирования "слов" внутреннего представления использованы "цифры" $\{0,1,2,3,4\}.$ С равным успехом мог быть использован "алфавит" $\{a,b,c,d,e\},$ и, если Вам угодно, $\{1,2,3,4,5\}.$ Со всеми этими внутренними представлениями алгоритм будет работать одинаково, если только "цифры" алфавита линейно упорядочены.

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение06.06.2015, 11:43 
aa_dav в сообщении #1023886 писал(а):
Я не думаю что автора интересуют вырожденные случаи как и случаи перебор которых займёт больше миллиарда лет, так что стека тут за глаза.

Разбиение числа 25 на 15 слагаемых выдаёт 50 с чем-то миллионов комбинаций где-то за пару минут и создаёт файл в полтора гигабайта с лишком. Вот и прикиньте -- что выйдет, если загнать весь этот массив в стек, да ещё и со всеми локальными переменными.

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение06.06.2015, 12:07 
whitefox в сообщении #1023735 писал(а):
Д.Кнут Искусство программирования т.4А.
Спасибо!

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение06.06.2015, 13:57 
ewert в сообщении #1023910 писал(а):
Вот и прикиньте -- что выйдет, если загнать весь этот массив в стек


А зачем его весь загонять в стек? =) Рекурсивный алгоритм "входит в стек" на величину $n$ максимум.

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение06.06.2015, 22:28 
whitefox в сообщении #1023889 писал(а):
Да никакая это не методика

Как то одним словом надо было назвать. Алгоритм видимо правильнее.
whitefox в сообщении #1023889 писал(а):
Просто "внутренне представление" данных в алгоритме не обязано совпадать с "внешним представлением".

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

-- 06.06.2015, 22:31 --

aa_dav в сообщении #1023955 писал(а):
Рекурсивный алгоритм "входит в стек" на величину $n$ максимум.

Каждая $n$ - это набор комбинаций, не вычислив комбинации для $n=4$ не получить комбинации для $n=5$.

 
 
 
 Re: Создание массивов чисел с заданной суммой элментов
Сообщение06.06.2015, 22:35 
upgrade в сообщении #1024162 писал(а):
Каждая $n$ - это набор комбинаций, не вычислив комбинации для $n=4$ не получить комбинации для $n=5$.
Ну и бросьте вы эту затею. Вам так жутко надо параллелить получение комбинаций? Если нет, и хватает просто их перечисления, лучше описанного не найти.

 
 
 [ Сообщений: 68 ]  На страницу Пред.  1, 2, 3, 4, 5  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group