2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 80, 81, 82, 83, 84, 85, 86 ... 88  След.
 
 Re: Factorials
Сообщение07.05.2013, 09:05 
Заслуженный участник
Аватара пользователя


19/12/10
1539
Nataly-Mak в сообщении #720589 писал(а):
Вот опять:

Цитата:
5 267 Michael Hürter Saarbrücken, Germany 6 May 2013 17:52
6 268 Alex Chernov Penza, Russia 5 May 2013 19:12

Alex Chernov (вчера) взял решение Michael Hürter (появившееся сегодня) и удлинил его на 1 шаг. :D
Ещё пример:
Код:
3    247    Helge Keller    Karlsruhe, Germany    2 May 2013 18:47
4    248    Robert Gerbicz    Halasztelek, Hungary    27 Apr 2013 23:05

27 апреля Gerbicz взял решение, найденное Helge Keller 2 мая, и удлинил его на один шаг :D

-- 07 май 2013, 10:19 --

(Gerbicz)

dimkadimon в сообщении #720673 писал(а):
Gerbicz

This is your final warning. If you don't stop your accusations then you will be banned from the contest (and perhaps from future AZ contests).

Лично я не заинтересован, чтобы Вас исключили из конкурса (ибо поставил на Вашу победу).
Но Вы, видимо, решили, что бан будет для Вас хорошим выходом.
После конкурса сможете утверждать, что обязательно победили бы, если бы Вас не забанили (разумеется "несправедливо").

Если это не так, повторю совет который давал ранее -- о всех своих подозрениях сообщайте только администратору конкурса, и только в личных сообщениях.
Помните о презумпции невиновности.
Любое публичное обвинение без доказательств это клевета.
Клевета наказуема.

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


22/03/08

7154
Саратов
Ура! Не могу удержаться, чтобы не показать:

Цитата:
5 259 Alex Chernov Penza, Russia 7 May 2013 12:28

Алексей идёт вперёд! Молодец!
Постоянно заглядываю на конкурс, болею за Алексея :wink:

До "золотой рыбки" Алексею осталось сбросить 29 шагов.

 Профиль  
                  
 
 Re: Factorials
Сообщение07.05.2013, 21:23 


16/08/05
827
dimkadimon в на яхе писал(а):
V[k]=10000 for all k<=N!
V[ai]=0 for all i

k=1
while k<=N!
..next=k+1
..for ai in S
....V[k+ai]=min(V[k+ai],V[k]+1) //for addition
....V[k*ai]=min(V[k*ai],V[k]+1) //for multiplication

....if V[k]+1<V[abs(k-ai)] //for subtraction
......V[abs(k-ai)]=V[k]+1
......next=min(next,abs(k-ai)) //opportunity to go back
....end
..end
..k=next
end


Не могли бы Вы дополнительно прокомментировать Ваш алгоритм. Попробовал его перекодировать в pari/gp

Код:
dimkadimon()=
{
  f= 13!; d= divisors(f);
  a= setunion(Set(), [1,2,4,6,36,32,1152,2304,2310]); \\аналог S
  k= setunion(Set(), d);  \\ список всех дивизоров f
  v= vector(#k, X, 10000); \\аналог "V[k]=10000 for all k<=N!", но только для дивизоров
  for(i=1, #a, j= setsearch(k, a[i]); v[j]= 0); \\аналог "V[ai]=0 for all i"
  for(j=1, #k,
   for(i=1, #a,
    \\ сложения
    z= k[j]+a[i]; ij= setsearch(k, z);
    if(ij, v[ij]= min(v[ij], v[j]+1));
    \\ умножения
    z= k[j]*a[i]; ij= setsearch(k, z);
    if(ij, v[ij]= min(v[ij], v[j]+1));
    \\ вычитания
    z= abs(k[j]-a[i]); ij= setsearch(k, z);
    if(ij,
     if((v[j]+1)<v[ij],
      v[ij]= v[j]+1;
      j= min(j, ij)
     )
    )
   )
  );
  \\ итоговый вывод результатов
  for(j=1, #k, if(v[j]<10000, print("j= ",j,"    k= ",k[j],"   v= ",v[j])));
  print();
  print("jmax= ",#k,"    k= ",k[#k],"   v= ",v[#k])
};


в принципе работает, но только для уже наполовину готовой последовательности S.


Допустим пытаюсь достроить 1,2,4,6,36 до оптимального решения 13!, ориентируясь на одно из известных оптимальных решений 1,2,4,6,36,32,1152,2304,2310,2340,2661120,6227020800.

Но S=[1,2,4,6,36] слишком короткая, алгоритм не сумел достроить:

Код:
. . .
j= 1511    k= 43545600   v= 8
j= 1515    k= 47900160   v= 8
j= 1528    k= 68428800   v= 10
j= 1535    k= 80870400   v= 7
j= 1540    k= 95800320   v= 9

jmax= 1584    k= 6227020800   v= 10000


Последовательность S=[1,2,4,6,36,32] тоже не достраивается, S=[1,2,4,6,36,32,1152,2304] аналогично, а вот S=[1,2,4,6,36,32,1152,2304,2310] успешно достроилась:

Код:
. . .
j= 1577    k= 778377600   v= 4
j= 1579    k= 1037836800   v= 4
j= 1580    k= 1245404160   v= 4
j= 1581    k= 1556755200   v= 5
j= 1582    k= 2075673600   v= 5
j= 1583    k= 3113510400   v= 5
j= 1584    k= 6227020800   v= 3

jmax= 1584    k= 6227020800   v= 3


Вопрос собственно такой: какие входные последовательности использовались для этого алгоритма?

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


22/03/08

7154
Саратов
dmd в сообщении #720927 писал(а):
Последовательность S=[1,2,4,6,36,32] тоже не достраивается, S=[1,2,4,6,36,32,1152,2304] аналогично, а вот S=[1,2,4,6,36,32,1152,2304,2310] успешно достроилась:

Извините, что вмешиваюсь.
Последовательность S=[1,2,4,6,36,32,1152,2304] не достраивается :?:
Но тут остаётся добавить всего 4 шага!
Программа mertz выполняет достраивание этой последовательности до 13! мгновенно:

Код:
found 3 solutions for 6227020800 in 11 steps
1,2,4,6,36,32,1152,2304,2310,2340,2661120,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,2695680,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,5405400,6227020800

Сейчас попробую достроить последовательность S=[1,2,4,6,36,32].

Эта последовательность достроилась за 1 мин. 19 сек.
Те же три решения.

-- Вт май 07, 2013 23:29:36 --

Цитата:
Но S=[1,2,4,6,36] слишком короткая, алгоритм не сумел достроить.

Программа mertz достраивает эту последовательность до 13! за 14 мин. 33 сек.
Вот найденные решения:

Код:
found 14 solutions for 6227020800 in 11 steps
1,2,4,6,36,144,30,576,546,78624,79200,6227020800
1,2,4,6,36,144,576,540,546,78624,79200,6227020800
1,2,4,6,36,144,576,582,546,78624,79200,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,2661120,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,2695680,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,5405400,6227020800
1,2,4,6,36,38,1444,1440,54720,56160,110880,6227020800
1,2,4,6,36,38,40,1440,54720,56160,110880,6227020800
1,2,4,6,36,40,1440,1404,56160,112320,110880,6227020800
1,2,4,6,36,40,1440,1404,56160,54720,110880,6227020800
1,2,4,6,36,40,1440,57600,56160,112320,110880,6227020800
1,2,4,6,36,40,1440,57600,56160,54720,110880,6227020800
1,2,4,6,36,40,39,1440,56160,112320,110880,6227020800
1,2,4,6,36,40,39,1440,56160,54720,110880,6227020800

Это притом, что у меня очень слабая машина.

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


22/03/08

7154
Саратов
До кучи --- эксперимент.
Ищу все решения для 13! по программе mertz с применением обеих эвристик:
(обрезка по делителям 13! и "только чётные числа").
Программа работала 2 мин. 22 сек. Найдено 31 решение.

(Оффтоп)

Код:
found 31 solutions for 6227020800 in 11 steps
1,2,4,16,12,10,160,156,24960,24948,249480,6227020800
1,2,4,16,12,10,160,156,24960,24948,249600,6227020800
1,2,4,16,12,10,160,156,24960,24948,622702080,6227020800
1,2,4,16,20,36,720,2880,756,2860,2162160,6227020800
1,2,4,16,20,36,720,2880,756,2860,2177280,6227020800
1,2,4,16,20,36,720,2880,756,2860,8236800,6227020800
1,2,4,6,24,22,132,576,600,79200,78624,6227020800
1,2,4,6,24,22,576,600,13200,79200,78624,6227020800
1,2,4,6,24,22,576,600,3600,79200,78624,6227020800
1,2,4,6,24,26,144,576,550,79200,78624,6227020800
1,2,4,6,24,26,576,550,13200,79200,78624,6227020800
1,2,4,6,24,26,576,550,3300,3276,10810800,6227020800
1,2,4,6,24,26,576,550,3300,3276,1886976,6227020800
1,2,4,6,24,26,576,550,3300,3276,1900800,6227020800
1,2,4,6,24,26,576,550,3300,79200,78624,6227020800
1,2,4,6,24,30,144,576,546,78624,79200,6227020800
1,2,4,6,24,30,576,546,13104,78624,79200,6227020800
1,2,4,6,24,30,576,546,3276,3300,10810800,6227020800
1,2,4,6,24,30,576,546,3276,3300,1886976,6227020800
1,2,4,6,24,30,576,546,3276,3300,1900800,6227020800
1,2,4,6,24,30,576,546,3276,78624,79200,6227020800
1,2,4,6,24,576,572,600,3600,3024,10886400,6227020800
1,2,4,6,24,576,572,600,3600,3024,1729728,6227020800
1,2,4,6,24,576,572,600,3600,3024,2059200,6227020800
1,2,4,6,36,144,576,540,546,78624,79200,6227020800
1,2,4,6,36,30,144,576,546,78624,79200,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,2661120,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,2695680,6227020800
1,2,4,6,36,32,1152,2304,2310,2340,5405400,6227020800
1,2,4,6,36,40,1440,1404,56160,112320,110880,6227020800
1,2,4,6,36,40,1440,57600,56160,112320,110880,6227020800

В программе mertz реализован поиск от 4-х различных баз данных:
последовательности из 4 членов (Base 4), из 5 членов (Base 5), из 6 членов (Base 6) и из 7 членов (Base 7).
Понятно, что решения для 13! надо искать от Base 7. Можно, конечно, и от других базовых последовательностей, но это будет дольше.

Ради интересна проверила тот же поиск 13! (с двумя эвристиками) от Base 5 и от Base 6.
Те же 31 решения и то же время: 2 мин. 22 сек.
А мне почему-то думалось, что от более коротких последовательностей поиск будет выполняться дольше.

 Профиль  
                  
 
 Re: Factorials
Сообщение08.05.2013, 03:39 


02/11/12
141
The different bases are just used to break the work down into smaller pieces.

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


22/03/08

7154
Саратов
mertz в сообщении #721007 писал(а):
The different bases are just used to break the work down into smaller pieces.

Google перевёл так:

Цитата:
Различные базы используются только нарушить работу на более мелкие куски.

Ничего не поняла :-)

Когда работала с программой, всегда для решений в 10-11 шагов использовала Base 7, для решений в 9 шагов - Base 6, для решений в 8 шагов - Base 5, для решений в 7 шагов - Base 4. Вроде всё получалось нормально.
Просто интуитивно так решила :-) рассуждала: чем длиннее решение, тем длиннее берём базовые последовательности для его построения.
Первоначально в программе была только одна база - Base 5. Потом появились другие, но я не стала спрашивать о назначении других, использовала их по своему разумению :?

Вот он --- языковой барьер :-)

-- Ср май 08, 2013 06:05:30 --

dimkadimon в сообщении #716120 писал(а):
На Yahoo я описал свой Dynamic Programming метод: http://tech.groups.yahoo.com/group/AlZi ... ssage/5629

Суть в том что мы можем решить упрощенную задачу: найти оптимальное SLP в котором все операции используют одно из чисел в последовательности S=a1, a2, ..., ai. Tо есть мы берем S и оптимально достраиваем еe до N! используя числа из S. Чтобы реализовать этот метод надо использовать условие что все числа делители N!.

Нашла описание метода dimkadimon.
Мне тоже стал интересен вопрос, заданный dmd: какие последовательности S мы берём в качестве начальных последовательностей, чтобы их потом достраивать.
И почему некоторые последовательности, выбранные dmd, не достраиваются до решения 13! :?:
Тогда как программой mertz эти начальные последовательности очень быстро достраиваются (даже безо всяких эвристик).

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


01/06/12
862
Adelaide, Australia
dmd в сообщении #720927 писал(а):
Последовательность S=[1,2,4,6,36,32] тоже не достраивается, S=[1,2,4,6,36,32,1152,2304] аналогично, а вот S=[1,2,4,6,36,32,1152,2304,2310] успешно достроилась:


Метод использует только операции в которых хотя бы одно число из S. Допустим S=[1,2,4,6,36,32,1152,2304,2310] тогда

2340=2304+36
2695680=2340*1152
6227020800=2695680*2310

Если S=[1,2,4,6,36,32,1152,2304] то можно получить 2310=2304+6, а вот умножать на 2310 уже нельзя. Без этого наверно нельзя получить 13! из его делителей. Вам надо проверить сам путь достройки.

Я этот метод использовал как быстрый способ для определения оценки для незаконченой последовательности S. Конечно для этого можно использовать другие способы, как например поиск на следующие k шагов. Когда у нас есть оценка для каждого S тогда можно использовать например beam search и сортировать последовательности по их оценке. Свой метод с beam search я описал на yahoo.

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


22/03/08

7154
Саратов
Ах, вот как близко "золотая рыбка" :D
Умеют же люди! :wink:

Цитата:
1 233 Wes Sampson La Jolla, California, United States 8 May 2013 00:53

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


21/02/10
1594
Екатеринбург
Блин, никак не могу поймать крупную золотую рыбку. Наловил рыбок средней величины. Что позволяет получить решение в районе 240 операций. Не хочется даже тратить время на сборку этого решения.

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


01/06/12
862
Adelaide, Australia
Pavlovsky в сообщении #721021 писал(а):
Блин, никак не могу поймать крупную золотую рыбку. Наловил рыбок средней величины. Что позволяет получить решение в районе 240 операций. Не хочется даже тратить время на сборку этого решения.

240 это 3-е место...

 Профиль  
                  
 
 Re: Factorials
Сообщение08.05.2013, 07:29 


16/08/05
827
dimkadimon в сообщении #721013 писал(а):
Метод использует только операции в которых хотя бы одно число из S.

Ну это видно невооружённым глазом в Вашем коде. Именно так буквально и транслировал его в код для pari/gp.

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


22/03/08

7154
Саратов
Фантастика!
Wes Sampson до решения 230 шагов остался всего 1 шаг --- в буквальном смысле :D

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #721025 писал(а):
240 это 3-е место...

Очевидно у победителя будет результат заметно меньше 230. С результатом 240 даже в пятерку попасть проблематично.

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


22/03/08

7154
Саратов
Цитата:
1 231 Wes Sampson La Jolla, California, United States 8 May 2013 11:35
2 234 Jarek Wroblewski Wroclaw, Poland 9 May 2013 04:44

Кто же будет первым :?:
Сильные противники, интересная борьба!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1 ... 80, 81, 82, 83, 84, 85, 86 ... 88  След.

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



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

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


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

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