2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 37, 38, 39, 40, 41, 42, 43 ... 88  След.
 
 Re: Factorials
Сообщение18.03.2013, 08:24 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов

(Оффтоп)

А-а-а, поняла. Не смотрю я ведь мультики :-)

 Профиль  
                  
 
 Re: Factorials
Сообщение18.03.2013, 19:18 
Аватара пользователя


10/11/12
121
Бобруйск
Pavlovsky в сообщении #697450 писал(а):
... Умеет очень высоко прыгать!

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

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


22/03/08

7154
Саратов
Ну, вы уже вошли в зону 22+, что совсем не плохо.
Прорваться в десятку очень сложно, соперники чересчур сильные.
Те, кто в начале конкурса был в лидерах, сейчас уже вытеснены из десятки, например, Valentin Dobrota, который довольно долго был на первом месте.
Наблюдаю за dimkadimon, пока держится в десятке, но очень трудно. Был на границе (10-ое место), потом поднялся на 7-ое, сейчас опять оттеснили на 9-ое. Острая борьба в десятке.

В моей команде тоже пока всё застопорилось. Ищем новые идеи. Я со своим ручным подходом выдохлась давно.
Хотя... что-то всё-таки продолжаю делать.

Интересно решение для 29!
Берём оптимальное решение для 26!, остаётся умножить на 27*28*29=21924 (тривиальная эвристика :D ).
Начинаю составлять число 21924 вручную, сначала это удаётся мне за 5 операций, что даёт решение в 21 шаг, не интересно, такое решение у меня уже было.
Думаю дальше, удалось составить за 4 шага, это уже дало решение в 20 шагов, есть улучшение.
Наконец, подключаю программу mertz. Программа находит представление числа 21924 за 3 шага! И таким образом получаю решение в 19 шагов. Конечно, до оптимального ещё 2 шага, но и то хлеб :D

-- Вт мар 19, 2013 05:23:22 --

(Оффтоп)

Pavlovsky
очень понравился ваш аватар :wink:
dimkadimon
а вы не добавите аватар?

Может быть, мне сменить аватар к грядущему юбилею (5 лет на форуме)?
Не наскучила коллегам моя физиономия? :D

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


22/03/08

7154
Саратов
Это полином для 29! по решению, о котором рассказано в предыдущем посте (19 шагов):

f(x)=$64 x^{19}-576 x^{18}-23664 x^{17}-237664 x^{16}-1276608 x^{15}-4265952 x^{14}-9250760x^{13}-12777744 x^{12}-10066692 x^{11}-2557220 x^{10}+2079969 x^9+1302762 x^8-112640 x^7-88800 x^6$
$f(36)=29!$

Упаковка, предложенная Вольфрамом:

$x^5 (x+2) (2 x+5)^2 (2 x (x+2)+1) (2 (x-28) (x+2) x+x) ((x+2) (2 x (x+2)+1)-6)^2$

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

Как уже писала, мне очень интересно получить оптимальные полиномы для всех N. Это просто делать, когда есть известное оптимальное решение.

 Профиль  
                  
 
 Re: Factorials
Сообщение19.03.2013, 06:14 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #697995 писал(а):
Это полином для 29! по решению, о котором рассказано в предыдущем посте (19 шагов):

Пожалуйста не нарушайте правила конкурса - не надо показывать полное решение (особено если оно достаточно хорошее).

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


22/03/08

7154
Саратов
А где вы видите полное решение? :D
Это всего лишь полином! И даже предложенная Вольфрамом упаковка не помогает найти решение хотя бы в 19 шагов. Я сейчас попыталась по этой упаковке составить решение, ничего не получилось.
А у вас получилось? :wink:

(Оффтоп)

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

 Профиль  
                  
 
 Re: Factorials
Сообщение19.03.2013, 06:51 
Аватара пользователя


21/02/10
1594
Екатеринбург
У всех кризис идей. Мои алгоритмы все реже и реже стали выдавать результаты. И хотя по моим оценкам выйти на рубеж 24,5+ им по силам. Но произойдет это через одну - две недели. Сколько человек к этому времени преодолеет рубеж 24,5 не известно. Одно можно сказать точно в десятку я пока не попадаю.
Отталкиваясь от темы про полиномы, упорно ищу алгебраические преобразования экономящие операции. Увы кроме уже известного A(A+1)B^2=AB(AB+B), ничего интересного не нашел.
Кстати это преобразование можно применить и к:
$x^5 (x+2) (2 x+5)^2 (2 x (x+2)+1) (2 (x-28) (x+2) x+x) ((x+2) (2 x (x+2)+1)-6)^2$
Из него легко виделить конструкцию:
$2x(x+2) (2 x (x+2)+1)$

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


22/03/08

7154
Саратов
Pavlovsky
значит, полученная мной упаковка не совсем бесперспективная? :-)
Как уже написала, в лоб по этой упаковке решение не составляется даже в 19 шагов.
Но вот если над ней поколдовать, то, конечно, в 19 шагов решение просто обязано получиться. Но цель не в 19 шагах, а меньше!

-- Вт мар 19, 2013 08:48:25 --

Уменьшила коэффициенты в полиноме для 29!

$f(x)=x^{20}+12 x^{19}-657 x^{18}-6613 x^{17}-35489 x^{16}-118510 x^{15}-256989 x^{14}-354957 x^{13}-279642x^{12}-71045 x^{11}+57744 x^{10}+36220 x^9-3098 x^8-2498 x^7-24 x^6$
$f(36)=29!$

Зря старалась :D
Вольфрам выдал для этого полинома тривиальную упаковку:

$x^6 (x (x (x (x (x (x (x (x (x (x (x (x (x (x+12)-657)-6613)-35489)-118510)-256989)- 354957)-279642)-71045)+57744)+36220)-3098)-2498)-24)$

 Профиль  
                  
 
 Re: Factorials
Сообщение19.03.2013, 07:50 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #698002 писал(а):
А где вы видите полное решение? :D
Это всего лишь полином! И даже предложенная Вольфрамом упаковка не помогает найти решение хотя бы в 19 шагов. Я сейчас попыталась по этой упаковке составить решение, ничего не получилось.
А у вас получилось? :wink:


А я то думал из этого полинома уже можно получить 19 шагов. Ну в таком случае забираю свои комментарии назад.

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


22/03/08

7154
Саратов
А вот такая оригинальная упаковка с иррациональностями хороша? :-)

$-1/2 (-2 x+\sqrt{2}-2) x^6 (x+2) (2 x+5)^2 (2 x+\sqrt{2}+2) (16 x+33) (2 x^3+8 x^2+9 x-4)^2$

Понятно, что при перемножении двух скобок с иррациональностями, иррациональности исчезают. Но всё-таки весьма интересное представление полинома.

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


22/03/08

7154
Саратов
dimkadimon в сообщении #698011 писал(а):
А я то думал из этого полинома уже можно получить 19 шагов.

Может быть, и можно, если очень постараться :D

Pavlovsky выложил свой полином для 26! и сказал, что он получен из готового решения в 16 шагов.
dmd предложил упаковку этого полинома, которая даёт решение только в 17 шагов (упаковка вычисляется за 13 операций).
Но фактически, как сообщил потом dmd, эту упаковку можно преобразовать так, что она будет вычисляться за 11 операций, а это даёт уже оптимальное решение в 15 шагов.
В-о-о-т --- в чём секрет упаковок :wink:

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

 Профиль  
                  
 
 Re: Factorials
Сообщение19.03.2013, 12:10 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #698071 писал(а):
Pavlovsky выложил свой полином для 26! и сказал, что он получен из готового решения в 16 шагов.
dmd предложил упаковку этого полинома, которая даёт решение только в 17 шагов (упаковка вычисляется за 13 операций).


Ээээ все было не так. Я просто выложил полином. И только когда dmd выложил почти оптимальное решение, я раскололся, откуда ноги растут. Кстати dmd сумел построить решение в 15 операций для 26!. Мне это до сих пор не удалось сделать. :-(

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


22/03/08

7154
Саратов
А, ну да :-) сначала dmd предложил упаковку для вашего полинома, а потом вы раскололись:

Pavlovsky в сообщении #693495 писал(а):
dmd
Классная работа! Не думал, что все будет так просто. Может поделишься как делал преобразования?
Задача появилась так. Если в выражение подставить x=36, то получим 26! Само выражение получилось из решения длиной 16 операций. Сравниваю ваше решение со своим, отличия конечно есть, но есть и много совпадений.

Извините, немного нарушила последовательность событий. Запамятовала малость :?
Но суть-то от этого не изменилась.

-- Вт мар 19, 2013 13:19:23 --

Pavlovsky в сообщении #698078 писал(а):
Кстати dmd сумел построить решение в 15 операций для 26!. Мне это до сих пор не удалось сделать. :-(

Вот о том и речь: искусство упаковки полиномов очень хитрое.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #698080 писал(а):
Вот о том и речь: искусство упаковки полиномов очень хитрое.


После того, как dmd хитро воспользовался моей недальновидностью, я больше полиномами не разбрасываюсь. :-)

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


22/03/08

7154
Саратов
Ну, так это же не впервой :D
В конкурсе с раскрасками вы давали подсказки пачками; при этом не всегда получали из своей идеи оптимальный результат (яркий пример: n-символьная строка для C=10; зыбыла, сколько в ней было символов, то ли 84, то ли 87).

Любите вы выкладывать свои идеи. Я только "за" :wink:
Сама выкладываю всё, что у меня есть; мне не жалко, пусть пользуются все, кто умеет.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1 ... 37, 38, 39, 40, 41, 42, 43 ... 88  След.

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



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

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


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

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