2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 56, 57, 58, 59, 60, 61, 62 ... 88  След.
 
 Re: Factorials
Сообщение22.04.2013, 11:15 
Заблокирован


21/04/13

78
Nataly-Mak в сообщении #713958 писал(а):
Это разложение

$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$

можно записать и так:

$23! = 323\cdot (323-1) \cdot 12636 \cdot 4435200^2$

Никакой разницы нет абсолютно.

Формальная разница есть: это два различных решения. И далеко не всегда существуют решения: одно - с плюсом, а другое - с минусом.
Еще раз повторяю: ваша запись содержит операции (x-1, x*(x-1), a^2), которых нет в оптимальном решении.

-- 22.04.2013, 12:22 --

dimkadimon в сообщении #713915 писал(а):
wanderers в сообщении #713906 писал(а):
Такая задача перед конкурсантами не ставилась: я действовал в рамках поставленной задачи. Мне вот более интересно, с чего это победители конкурса людям мозги "компостируют"?

P.S.
Я уже ранее писал, что достаточно взглянуть на решения для 13!, 14!, 15!, 16! и 17!, чтобы понять, что все оптимальные решения достаточно разнообразны и не вписываются в мой метод.


Перефразирую свой вопрос. Может ли ваш метод набрать 25 в конкурсе? Мой опыт показал что найти оптимальные решения для N<=27 не достаточно, так как найти оптимальные решения для N>27 гораздо сложнее.

Например для больших N вашей таблицы может не хватить. Конечно таблицу можно увеличить, но она будет расти очень быстро и время просмотра этой таблицы тоже будет расти.

Давайте считать: 31! у меня посчитал на 14 ядрах за полчаса. Этот расчет можно было значительно ускорить, если работать не со всей базой данных, а только с ее участками, которые дают наибольшее количество решений - это примерно 1/5 базы. Вроде получается, что мой алгоритм гарантированно за приемлемое время может набрать 25 баллов. И я ведь еще не исчерпал методы ускорения решения, не связанные с таблицами. Что касается просмотра таблиц, то я использую хеширование и практически сразу определяю, что, где и почему: я об этом ранее писал. Для случая (y, x, a) методика хеширования довольно нетривиальна: из-за ее реализации да плюс еще командировка у меня не хватило времени.

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


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #713968 писал(а):
Прочитал описание алгоритмов лидеров. Понравилось:


Мне тоже это больше всего понравилось. Я никак не мог придумать как ускорить сложение и вычитание. Умножение можно представить как сумму: (a^k * b^m) * (a^p * b^q) представляем как (k,m)+(p,q)=(k+p,m+q).

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


22/03/08

7154
Саратов
wanderers
ещё раз повторяю: моё решение содержит 15 шагов.

Вы не ответили на мой предыдущий вопрос, где у меня какие-то 5 операций?
Пкажите мне в моём решении, в котором 15 шагов, лишнюю операцию.

По-моему, давно пора признать, что вы были не правы.
Но вы упорствуете в своей неправоте.
Хорошо, я не поленюсь и всё снова повторю :D
Повторить? Или вы всё-таки признаете свою неправоту?

Кстати, сначала вы писали, что x=322. Привести цитату?
Потом вы уже стали исходить из x=323.
Так в этом примере решение есть в обоих случаях: и для x=322 и x=323.

Будете продолжать упорствовать в своей неправоте?
Тогда давайте показывайте конкретно: где в моём решении лишняя операция?

-- Пн апр 22, 2013 12:30:13 --

wanderers в сообщении #713971 писал(а):
Еще раз повторяю: ваша запись содержит операции (x-1, x*(x-1), a^2), которых нет в оптимальном решении.

Понимаю... у вас по алгебре в школе была двойка? :-)

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 11:35 
Заблокирован


21/04/13

78
Nataly-Mak в сообщении #713980 писал(а):
Понимаю... у вас по алгебре в школе была двойка? :-)

Угу, за всю жизнь в университете была только одна четверка по физике (из точных наук) и то только за то, что профессору Толстому (сыну писателя) не понравилось, что я отвечал не по его лекциям.

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


21/02/10
1594
Екатеринбург
Мне в моих алгоритмах все таки понадобилось разложение чисел на простые множители. Чтобы быстро вычислить разложение на простые множители выражения a+b (a-b), использовал процедуры:
1) Заранее посчитал разложения на простые множители для всех чисел меньших 300000.
2) Использовал преобразование a+b=d(a'+b'), где d= НОД(a,b). До идеи tomrokicki осталось совсем немного. :D Правда я так и не решился целиком положиться на эвристику, составлять последовательности только из делителей N! А идея tomrokicki основана на этой эвристике.

-- Пн апр 22, 2013 13:45:41 --

Опс следующие конкурсы:
Код:
Hell's Kitchen 13 Jul 2013 16:00
Alphabet City 21 Sep 2013 16:00

А вроде говорили, что следующий конкурс будет не раньше октября?!

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


22/03/08

7154
Саратов
wanderers в сообщении #713984 писал(а):
Nataly-Mak в сообщении #713980 писал(а):
Понимаю... у вас по алгебре в школе была двойка? :-)

Угу, за всю жизнь в университете была только одна четверка по физике (из точных наук) и то только за то, что профессору Толстому (сыну писателя) не понравилось, что я отвечал не по его лекциям.

А по делу будете отвечать?
Где в моём решении в 15 шагов лишняя операция?

*в сторону* д-а-а-а, тяжёлый случай. Ну, если ... упорствует, не старайся его переупорствовать - сам козлёночком станешь :D

-- Пн апр 22, 2013 12:57:06 --

wanderers в сообщении #713899 писал(а):
Существуют решения с x=322 и с x=223: просто хочу донести до сознания окружающих, что никаких велосипедов изобретать не нужно - достаточно двух сгенерированных таблиц.

Может быть, здесь у вас банальная опечатка и вы хотели написать, что существует решение для x=322 и для x=323?
А в следующих постах вы на мой вопрос о решении для x=223 просто сказали, что не поняли вопроса.

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

-- Пн апр 22, 2013 13:10:09 --

$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$

wanderers
вы утверждаете, что в этой записи 5 операций?
А в этой записи

$23! = 322 \cdot 4435200 \cdot (322 \cdot 4435200 + 4435200) \cdot 12636$

сколько операций?
Неужели вы не видите, что в моём решении всё завершается как раз 4 операциями?

Здесь как раз и применено преобразование Pavlovsky:

A(A+1)CB^2=AB(AB+B)C

Простейшее алгебраическое преобразование, которое знает любой школьник.

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 12:23 
Заблокирован


21/04/13

78
Nataly-Mak в сообщении #713990 писал(а):
$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$

wanderers
вы утверждаете, что в этой записи 5 операций?
.

Утверждаю.
1. 322+1
2.322*(322+1)
3.(322*(322+1))*12636
4.4435200^2
5.((322*(322+1))*12636)*(4435200^2)

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


22/03/08

7154
Саратов
Цитата:
А в этой записи

$23! = 322 \cdot 4435200 \cdot (322 \cdot 4435200 + 4435200) \cdot 12636$

сколько операций?
Неужели вы не видите, что в моём решении всё завершается как раз 4 операциями?

Здесь как раз и применено преобразование Pavlovsky:

A(A+1)CB^2=AB(AB+B)C

Простейшее алгебраическое преобразование, которое знает любой школьник.

:D

А по поводу x=223 что вы утверждаете?
Это действительно надо понимать как x=223? Или это надо понимать как x=323?

-- Пн апр 22, 2013 13:42:12 --

Pavlovsky в сообщении #713985 писал(а):
Опс следующие конкурсы:
Код:
Hell's Kitchen 13 Jul 2013 16:00
Alphabet City 21 Sep 2013 16:00

А вроде говорили, что следующий конкурс будет не раньше октября?!

Это где-то не у Al Zimmermann?

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 12:42 
Заблокирован


21/04/13

78
Слева 5 операций, а справа - 4 операции: этот неприложный факт не смжет опровергнуть даже самый заядлый двоечник.
И не надо про школу: именно я первый опубликовал прорывной подход к решению задачи, где как раз и используется тройка чисел (y, x, a):
post713672.html#p713672

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


19/12/10
1546
wanderers в сообщении #714015 писал(а):
Слева 5 операций, а справа - 4 операции: этот неприложный факт не смжет опровергнуть даже самый заядлый двоечник.

Извините, что вмешиваюсь, но у заядлого двоечника $2\cdot2=5$, так что он легко найдёт опровержение :lol:

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


22/03/08

7154
Саратов
wanderers в сообщении #714015 писал(а):
... именно я первый опубликовал прорывной подход к решению задачи, где как раз и используется тройка чисел (y, x, a):

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

Всё-таки позволю себе заметить (ох, не стать бы козлёночком :-) ), что именно решение с тройкой чисел для 23! и продемонстрировал Pavlovsky.

Цитата:
Применяем преобразование A(A+1)B^2=(AB)(AB+B)
322*(322+1)*12636* 4435200^2
(322*4435200)*(322*4435200+4435200)*12636
1,2,3,9,27,36,324,351,322,12636,4435236,4435200, 1428134400, 1432569600, 2045901926154240000, 25852016738884976640000
Итого 15 операций

Таким образом, он открыл вашу парадигму (y,x,a) независимо от вас. Точь-в-точь такую же парадигму с тройкой чисел, которая даёт решение для 23! в 15 шагов.

А я просто повторила решение по разложению, предложенному Pavlovsky. И нет в моём решении никакой лишней операции. Вот! :D

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 13:10 
Заблокирован


21/04/13

78
Причем здесь Павловский? Вот что он писал только что: "wanderers Разобраться с вашим подходом мне нужно время. Поэтому не думайте, что ваши посты игнорируются".
Я пришел к своему алгоритму, изучая кропотливо решения для 13!, 14!, 15!, 16! и 17!

P.S.

(Оффтоп)

Зависть - отнють не лучшее из человеческих чувств. К счастью, природа меня обошла стороной с этим "подарком"

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


22/03/08

7154
Саратов
wanderers в сообщении #714026 писал(а):
Причем здесь Павловский?

Ну, это уже даже не смешно.
Да притом, что он открыл эту вашу парадигму независимо от вас.
Я же привела цитату!

Цитата:

(Оффтоп)

Зависть - отнють не лучшее из человеческих чувств. К счастью, природа меня обошла стороной с этим "подарком"

Это кто тут кому завидует? :D
Есть тут один товарищ из Венгрии... Но больше тут завистливых отнюдь не бывало (кстати, отнюдь пишется через "д").

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 13:27 
Заблокирован


21/04/13

78
Nataly-Mak в сообщении #714030 писал(а):
Это кто тут кому завидует? :D

(Оффтоп)

Кроме вас на эту кандидатуру никого не заметил

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


22/03/08

7154
Саратов
wanderers в сообщении #714032 писал(а):
Nataly-Mak в сообщении #714030 писал(а):
Это кто тут кому завидует? :D

(Оффтоп)

Кроме вас на эту кандидатуру никого не заметил

(Оффтоп)

И кому же я завидую? Уж не вам ли? :D


-- Пн апр 22, 2013 14:48:37 --

Ну, а теперь я буду искать решение по второму разложению:

$23! = 323 \cdot (323-1) \cdot 12636\cdot  4435200^2 $

Уж сразу запишу так, чтобы было 4 операции :D

$23! = 323 \cdot  4435200 \cdot  (323 \cdot  4435200- 4435200) \cdot 12636$

Так будет понятно?

Теперь (как и в прошлом примере) ищу на первом этапе по программе mertz все решения для числа 12636 в 8 шагов. Их нашлось 279.
На втором этапе ищу от найденных решений все решения, в которых 9-ым шагом появляется число 323. Таких решений найдено 9 штук.

Код:
found 14 solutions for 323 in 9 steps
1,2,3,4,9,36,39,324,12636,323
1,2,3,6,18,21,324,39,12636,323
1,2,3,6,18,36,324,39,12636,323
1,2,3,6,36,39,108,324,12636,323
1,2,3,6,9,36,39,324,12636,323
1,2,3,9,12,108,324,117,12636,323
1,2,3,9,12,27,39,324,12636,323
1,2,3,9,12,36,39,324,12636,323
1,2,3,9,18,21,324,39,12636,323
1,2,3,9,18,36,324,39,12636,323
1,2,3,9,27,36,324,351,12636,323
1,2,3,9,27,36,39,324,12636,323
1,2,3,9,81,162,78,161,12636,323
1,2,3,9,81,162,78,324,12636,323

Наконец, от найденных последовательностей ищу решение, в котором 11-ым шагом появляется число 4435200.
Такое решение найдено только одно:

Код:
found 1 solutions for 4435200 in 11 steps
1,2,3,9,27,36,324,351,12636,323,4435236,4435200

И теперь завершаю решение за 4 шага:

Код:
1,2,3,9,27,36,324,351,12636,323,4435236,4435200,1432569600,1428134400,2045901926154240000,25852016738884976640000

Это вторая парадигма для x=323.
Надеюсь, теперь нет лишних операций :D

wanderers
а опечатку x=223 вы хоть признаете? Или и тут будете что-то утверждать? :D

(Оффтоп)

Кстати, тот, кто пишет "я первый опубликовал прорывной подход к решению задачи", и есть первый завистник.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1 ... 56, 57, 58, 59, 60, 61, 62 ... 88  След.

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



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

Сейчас этот форум просматривают: Dmitriy40


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

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