2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 74, 75, 76, 77, 78, 79, 80 ... 88  След.
 
 Re: Factorials
Сообщение01.05.2013, 21:50 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #718444 писал(а):
Интересно ещё то, что оптимальное решение для 6652800 имеет 9 шагов.
Но при построении решения 36! используется решение для 6652800 из 11 шагов, на 2 шага больше оптимального.

Ну, это уже не удивительно.
Число 4200 имеет оптимальное решение в 7 шагов; однако в построении решения для 22! используются решения для числа 4200 в 9 шагов, на 2 шага больше оптимального.

-- Ср май 01, 2013 22:53:43 --

whitefox в сообщении #718462 писал(а):
Nataly-Mak в сообщении #718459 писал(а):
А почему нельзя использовать, например, такое решение в 10 шагов:

Число 6652800 нужно не само по себе, а как часть решения для 36!

Это мне понятно :-)
Цитата:
Кстати Ваша последовательность тоже отвечает эвристике делителей.

Она не моя, она ваша; просто я выбросила из неё не нужное число 899, которое в составлении числа 6652800 совсем не участвует.
Если я буду строить все решения в 10 шагов, в них будут все решения: и отвечающие, и не отвечающее эвристике делителей.

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 22:01 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #718465 писал(а):
Ну, это уже не удивительно.
Число 4200 имеет оптимальное решение в 7 шагов; однако в построении решения для 22! используются решения для числа 4200 в 9 шагов, на 2 шага больше оптимального.

Вы правы.
Вспомнил об этом когда уже написал сообщение, но исправлять не стал. :-)

-- 01 май 2013, 23:08 --

Nataly-Mak в сообщении #718465 писал(а):
Если я буду строить все решения в 10 шагов, в них будут все решения: и отвечающие, и не отвечающее эвристике делителей.

Проверено, всех решений менее тысячи.
Но ни одно из них не продолжается до решения 39970374732288000 в 13 шагов. Решение в 14 шагов существует (приведено выше), но чтобы получить его нужно исходную последовательность расширить на 4 шага.

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 22:27 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Я тоже проверила.
Решений в 10 шагов для числа 6652800 безо всяких эвристик найдено 924
(мой тихоход справился с этой задачей за 23 мин. 20 сек.; работала самая последняя версия программы mertz.)

Цитата:
Но ни одно из них не продолжается до решения 39970374732288000 в 13 шагов. Решение в 14 шагов существует (приведено выше), но чтобы получить его нужно исходную последовательность расширить на 4 шага.

Не поняла. Так всё-таки решение можно найти от всех начальных последовательностей в 10 шагов?
Я думаю, что можно, так как выброшенное число 899 - оно же легко порождается решением в 10 шагов. Какая разница --- было ли это число до числа 6652800 или оно будет после него?
У вас следующий этап вот эта последовательность:

Код:
1, 2, 4, 6, 36, 35, 216, 220, 864, 899, 30240, 6652800, 6683040, 44460928512000, 39970374732288000

Ну и что? Разве от всех решений в 10 шагов нельзя найти число 39970374732288000 за 4 шага? Уверена, что можно.
Просто от вашей последовательности это число составляется за 3 шага, но у вас и последовательность на 1 шаг длиннее моих последовательностей.
У меня решение будет выглядеть, например, так:

Код:
1, 2, 4, 6, 36, 35, 216, 220, 864, 30240, 6652800, 899, 6683040, 44460928512000, 39970374732288000

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 22:41 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Сейчас программа Эда ищет расширение на 4 шага для 39970374732288000 от всех 10-шаговых последовательностей для 6652800.
За 36 минут выполнено 80% работы, найдено 3 решения:
Код:
found 3 solutions for 39970374732288000 in 14 steps
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,44460928512000,39970374732288000
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,5980867200,39970374732288000
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,6008052960,39970374732288000

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 22:46 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ага, и у меня ищет :D
Так мы с вами после конкурса найдём все оптимальные решения :wink:

Ну вот, как я и сказала, решения есть, и не могло не быть.
Зато искать решения в 10 шагов можно безо всяких эвристик, и на это уходят считанные минуты; у меня всего 23 минуты потребовалось. У вас будет ещё меньше, а у Эда вообще за секунды это выполнится.

Код:
found 3 solutions for 39970374732288000 in 14 steps
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,44460928512000,39970374732288000

Вот и решение я угадала :D Прорицательница? :wink:

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 22:54 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Изображение

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 22:56 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
У вас слова кончились? :D
Прекрасно, я и картинки понимаю :wink:

Тэк-с, почти 44 минуты программа работала, найдено 3 решения.
Отличный результат эксперимента :roll:

Мне прервать что ли программу или пусть отработает до конца?
Сравним время работы.

А у меня программа работает 23 минуты, выполнено 7% и... три решения уже найдены!
Вот как быстро они найдены.
Ну, не буду зря мучить машину, прерву программу.
Вот три решения:

Код:
found 3 solutions for 39970374732288000 in 14 steps
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,44460928512000,39970374732288000
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,5980867200,39970374732288000
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,6008052960,39970374732288000

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 23:01 
Заслуженный участник
Аватара пользователя


19/12/10
1546
От трёх предыдущих последовательностей мгновенно получено:
Код:
found 1 solutions for 1398918654701568000 in 16 steps
1,2,4,6,36,35,216,220,864,30240,6652800,899,6683040,44460928512000,39970374732288000,1398963115630080000,1398918654701568000

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 23:04 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ну и? Вывод какой? Нужна эвристика с делителями N! :?:
И в этом примере прекрасно обошлись без неё, и даже без эвристики для чётных чисел.

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 23:09 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Эвристика для чётных чисел это решение не нашла бы, так как в нём присутствуют нечётные.

А эвристика делителей N! позволила бы существенно сократить время поиска.

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 23:15 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #718511 писал(а):
Эвристика для чётных чисел это решение не нашла бы, так как в нём присутствуют нечётные.

Вот ёлки-палки!
Да не нужны вообще никакие эвристики при поиске решений в 10 шагов!
Эти решения без эвристик находятся за считанные минуты.

Цитата:
А эвристика делителей N! позволила бы существенно сократить время поиска.

А вот в этом нисколько не уверена.
Писала уже своё мнение на этот счёт. Ещё не факт, что эвристика позволит сократить время поиска.
Вот когда докажете это экспериментально, тогда соглашусь :D
Вот на этом примере и докажите.

Ещё раз повторю: пусть мы ищем решения для числа 6652800 в 10 шагов.
Включаем эвристику в вашем понимании, то есть в решениях не должно быть чисел, не являющихся делителями 36!
Я правильно ваше требование поняла?
Так значит, программа должна проверять все члены последовательностей на соответствие этому условию. На это надо время, между прочим.
Итак, решения для числа 6652800 в 10 шагов безо всяких эвристик мной найдены за 23 минуты (924 решения).
Где ваша программа, которая ищет решения с этой эвристикой? Давайте её мне.
Буду экспериментировать :-)

Да, ещё немаловажно. В программе Эда решения строятся от базовых последовательностей, состоящих из 7 членов (6 шагов). Это должно быть соблюдено.

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 23:28 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Изображение

-- 02 май 2013, 00:31 --

Ускорение в 37 раз.

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 23:32 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox
но... ведь здесь проверяются не делители 36!, а делители числа 39970374732288000
(вроде Эд ещё не добавил ваше требование по этой эвристике ?)
Это не совсем одно и то же.

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 23:39 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #718515 писал(а):
Так значит, программа должна проверять все члены последовательностей на соответствие этому условию. На это надо время, между прочим.

Время обработки одного узла возрастает.
Но общее число обрабатываемых узлов сокращается в значительно большей степени за счёт обрезания большинства ветвей.

-- 02 май 2013, 00:45 --

Nataly-Mak в сообщении #718531 писал(а):
но... ведь здесь проверяются не делители 36!, а делители числа 39970374732288000
(вроде Эд ещё не добавил ваше требование по этой эвристике ?)
Это не совсем одно и то же.

Любой делитель числа 39970374732288000 является и делителем 36!

Здесь нам повезло, что числа 899, 6683040, 44460928512000 являются делителями 39970374732288000.
Иначе бы решение мы не получили.

Конечно число делителей 36! больше числа делителей 39970374732288000, но не думаю чтобы время обработки одного узла возрасло из-за этого очень сильно.

 Профиль  
                  
 
 Re: Factorials
Сообщение01.05.2013, 23:57 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #718528 писал(а):
Ускорение в 37 раз.

Ну вот, можем и время сравнить, у меня с этой эвристикой программа отработала за 9 мин. 12 сек.

Теперь ещё раз и последний.
Это похоже на мышиную возню: мышка, у которой хвост обрезан, быстрее бегает и поворачивается, нежели мышка с длинным хвостом :D
Меня не устраивает сама концепция такого поиска.
Вот берём некоторое разложение (откуда мы его берём? какой-то добрый волшебник нам сделал все эти разложения :-) ).
Так, берём разложение... и начинаем строить решения --- сначала для первого числа (в 7-10 шагов), потом для второго числа, потом для третьего числа.
Это очень примитивный поиск, как я уже писала. Много так не проверить.
Да, Эд сделал очень хорошую программу! Я это уже не раз отмечала.
Но это не решатель в полном смысле этого слова, это только инструмент, помогающий искать решения. Инструмент отличный, да. Отдадим должное Эду!

Так, в рассмотренном выше примере какая разница мне, нашлось ли решение за полчаса или оно нашлось за 5 минут? Абсолютно никакой разницы. Мне надо проделать ряд ручных процедур с автоматическим их исполнением, но не с автоматическим выполнением всего поиска в целом!
Эд пытался автоматизировать одну из парадигм:

$N! = A^2B$
Вроде это у него получилось, он прислал мне решение для 25!, найденное по этому алгоритму.
Больше никаких автоматизаций я не видела.

А wanderers, между прочим, писал именно об автоматизации поиска по парадигмам.
Правда, он не раскрыл свой способ автоматизации, только намекнул о построении таблиц.
Как раз такие таблицы строил и Эд при автоматизации поиска решений по приведённой выше парадигме (о чём я рассказала выше).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1 ... 74, 75, 76, 77, 78, 79, 80 ... 88  След.

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



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

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


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

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