2014 dxdy logo

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

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




На страницу Пред.  1 ... 7, 8, 9, 10, 11, 12, 13 ... 88  След.
 
 Re: Factorials
Сообщение30.01.2013, 12:33 
Аватара пользователя
Немножко ещё поломала голову :-)
Получила для 18! 15 шагов. Уже близко к лучшему результату, найденному на конкурсе - 13 шагов (если он остаётся ещё лучшим).

 
 
 
 Re: Factorials
Сообщение30.01.2013, 17:12 
Аватара пользователя
Xaositect в сообщении #675739 писал(а):
Если говорить об эвристиках, то можно пытаться разложить факториал или близкое к нему число в произведение как можно более близких друг к другу сомножителей,


Вспомнил из школьного курса математики формулу:

(A+B)*(A-B)=A^2-B^2.

 
 
 
 Re: Factorials
Сообщение31.01.2013, 00:18 
Аватара пользователя
Pavlovsky в сообщении #677901 писал(а):
(A+B)*(A-B)=A^2-B^2.
I do not beleave, that this approach is helpful. Adding/subtracting large numbers is expensive.
With my approach I need 23 steps for 35!, 36! and 37! . Not really good, but not really bad too. In my approach subtraction and addition occurs only with relatively small numbers. Then these are multiplied. I use 10 multiplications as the last operations for 35!, 36! and 37!.
Maybe I should rewrite my programs. If there are many multiplications in the end, it may be unnecessary to use the GMP library. For the multiplication of large numbers you only need to add prime powers.

 
 
 
 Re: Factorials
Сообщение31.01.2013, 08:03 
Аватара пользователя
Я рассматриваю огромное количество идей, в том числе самые сумашедшие. В моем варианте перебора, в качестве входного параметра, вводится запрет операций сложения и вычитания, для чисел превышающих заданный порог.
Herbert Kociemba в сообщении #678133 писал(а):
If there are many multiplications in the end, it may be unnecessary to use the GMP library. For the multiplication of large numbers you only need to add prime powers.


Слава богу у меня такой проблемы нет. В платформу программирования, которую я использую, встроена арифметика длинных чисел. Так что спокойно работаю с 50-ти значными числами.

-- Чт янв 31, 2013 10:53:55 --

Есть первая единичка! N13L11.

 
 
 
 Re: Factorials
Сообщение31.01.2013, 10:46 
Аватара пользователя
Эх, вот так я и знала...уже вчера видела, что Wes Sampson вышел на 11-ое место и рвётся в десятку :-(

Цитата:
10 22.81 Wes Sampson La Jolla, California, United States 31 Jan 2013 04:11
11 22.47 Alex Chernov Penza, Russia 26 Jan 2013 05:41

Ну, ничего, ещё не вечер!

 
 
 
 Re: Factorials
Сообщение31.01.2013, 10:58 
Аватара пользователя
Код:
142 10.22 Valery Pavlovsky Ekaterinburg, Russia 31 Jan 2013 07:45


Я тоже рвусь в десятку. :D Написал переборный алгоритм, достаточно быстрый. Дошел до N=21, везде результаты больше 0,9. То есть когда дойду до N=37 будет больше 22,5.

 
 
 
 Re: Factorials
Сообщение31.01.2013, 12:42 
Аватара пользователя
Pavlovsky в сообщении #678173 писал(а):
В моем варианте перебора, в качестве входного параметра, вводится запрет операций сложения и вычитания, для чисел превышающих заданный порог.
По поводу порога. У меня случилась парадоксальная ситуация. После введения порога я относительно быстро (час? сейчас не помню) нашел N15L12 и N17L12, но вот решение N16L12 и через сутки так и не появилось. И только после увеличения порога удалось получить N16L12.
Цитата:
Слава богу у меня такой проблемы нет. В платформу программирования, которую я использую, встроена арифметика длинных чисел. Так что спокойно работаю с 50-ти значными числами.
Запрограммировать умножение столбиком не сложно, да и полезно вспомнить первый алгоритм, который нам давали в начальной школе :D

 
 
 
 Re: Factorials
Сообщение31.01.2013, 13:05 
Аватара пользователя
svb в сообщении #678242 писал(а):
Запрограммировать умножение столбиком не сложно


Читал описание алгоритмов в конкурсе Orchard Planting. Никто из лидеров не стал связываться с арифметикой длинных чисел. То есть добровольно ограничили в своих решених величину координат.

 
 
 
 Re: Factorials
Сообщение31.01.2013, 13:23 
Аватара пользователя
Pavlovsky
Для вывода результата нет нужды пользоваться скоростной арифметикой, для это достаточен любой простенький алгоритм. А при поиске решений, действительно, весьма сомнительна полезность арифметики длинных чисел.

 
 
 
 Re: Factorials
Сообщение31.01.2013, 13:27 
Аватара пользователя
А что делать с операциями сложения, вычитания, сравнения?!

 
 
 
 Re: Factorials
Сообщение31.01.2013, 13:29 
Аватара пользователя
Herbert Kociemba в сообщении #678133 писал(а):
If there are many multiplications in the end, it may be unnecessary to use the GMP library. For the multiplication of large numbers you only need to add prime powers.

Кстати, переведите кто-нибудь, пожалуйста, последнюю фразу в сообщении Herbert Kociemba. Гугл переводит её невразумительно.

Как я поняла из сообщения Herbert Kociemba, если ограничить числа, для которых использовать сложение/вычитание, то последние операции уже будут только операцией умножения, что даст возможность не использовать библиотеку GMP (то есть арифметику длинных чисел).

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

 
 
 
 Re: Factorials
Сообщение31.01.2013, 13:44 
Аватара пользователя
Pavlovsky
Цитата:
А что делать с операциями сложения, вычитания, сравнения?!
Сложение и вычитание приходится ограничивать :-( , об этом вы уже писали. Сравнение и умножение при представлении чисел в виде наборов степеней 12 простых чисел проблем не вызывает. Получается вариант "задачи о рюкзаке", но количество вариантов на входе в эту задачу ужасает.

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

Nataly-Mak
Мой вольный перевод: для умножения больших чисел потребуется только сложение степеней простых чисел.

 
 
 
 Re: Factorials
Сообщение31.01.2013, 14:05 
Аватара пользователя
svb
спасибо за перевод. Вроде понятно стало.

 
 
 
 Re: Factorials
Сообщение31.01.2013, 15:24 
Аватара пользователя
SLP последовательность:
$1,x_1 ,x_2 ,...,x_k $, $x_i  = op_i \left( {x_m ,x_n } \right)$, $m \le i,n \le i$, $op_i  = \left( { + , - , \times } \right)$
Для шага $x_i  = op_i \left( {x_m ,x_n } \right)$ без ограничения общности можно считать $x_n  \le x_m $, для этого при вычитании достаточно рассматривать абсолютную величину результата. Положим: $f\left( i \right) = m$ и $l(i) = n$.

Теорема. Для любой SLP последовательности $1,x_1 ,x_2 ,...,x_k $ существует эквивалентная ей последовательность $1,y_1 ,y_2 ,...,y_k $ , состоящая из тех же чисел, что $f\left( i \right) = i - 1 $, либо $f\left( i \right) = f\left( {i - 1} \right)$.

Если убрать случай $f\left( i \right) = f\left( {i - 1} \right)$, то резко сокращается пространство перебора.

Приведенную теорему необходимо проверить, т.к. я мог совершить ошибку. Первоначально мне показалось, что при переборе можно убрать вариант $f\left( i \right) = f\left( {i - 1} \right)$, но для конкретной последовательности это невозможно в том варианте, как указано в теореме. При переборе же ситуация сложнее и, возможно, этот случай можно исключить. По крайней мере, конкретные решения мне удалось получить без использования последнего варианта.

Дополнительно полезно рассмотреть функцию $l(i)$.

 
 
 
 Re: Factorials
Сообщение31.01.2013, 15:26 
Аватара пользователя
Pavlovsky в сообщении #678173 писал(а):
В моем варианте перебора, в качестве входного параметра, вводится запрет операций сложения и вычитания, для чисел превышающих заданный порог.


Обрезка сложения – это то, что на второй день контеста дало мне 20-е место. Но не смотря на свою тривиальность, считаю это коллективным решением вслух...

P.S.: вот уже больше недели не решаю. Вынашиваю планы о полуавтоматическом решении.
А с N=13 конкурс начинается не просто так, а потому, что оно как раз превышает int32.

 
 
 [ Сообщений: 1310 ]  На страницу Пред.  1 ... 7, 8, 9, 10, 11, 12, 13 ... 88  След.


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