Да, напутали мы с рекуррентной формулой. А ведь какая красивая и попала в известную константу. Но все к лучшему, теперь опять можно надеется, что Константа Гнилых Помидоров окажется новой константой математики. Подтверждаю твои результаты и привожу нашу более полную таблицу (без применения сомнительных рекурсий)
M(5)*5!=411 M(5)/5=0.6849999999999999
M(6)*6!=2921 M(6)/6=0.6761574074074074
M(7)*7!=23633 M(7)/7=0.6698696145124716
M(8)*8!=214551 M(8)/8=0.6651506696428572
M(9)*9!=2160343 M(9)/9=0.6614806853811483
M(10)*10!=23897269 M(10)/10=0.6585446704144621
M(11)*11!=288102189 M(11)/11=0.656142478628274
M(12)*12!=3760013027 M(12)/12=0.6541406519658112
M(13)*13!=52816397219 M(13)/13=0.6524467986483878
M(14)*14!=794536751217 M(14)/14=0.6509949243754914
M(15)*15!=12744659120521 M(15)/15=0.6497366333390322
M(16)*16!=217140271564591 M(16)/16=0.6486356286821274
Мы использовали тип long в Java и точные целочисленные значения для M(n)*n! дальше невозможны, но с типом double можно продолжать вычисление M(n) с точностью до 14-15 знаков пока хватит мощности компьютера.
Гнилые помидоры (сложная)!
Модераторы: Азарапетыч, Администрация
- Antananarivu
- Популярный автор
- Сообщения: 2338
- Зарегистрирован: 24 сен 2007, 16:35
- Пол: Мужской
- Откуда: Мытищи
Блин!
Вот когда самый первый раз читал задачу подумалось про число e, чуял же что сидит где-то оно, только где именно - не понял
А новые соотношения как посчитаны? Как это в смысле алгоритм а не язык Брутфорсный перебор всея вариантов или тоже какие-ть рекурентные формулировки?
P.S> ИМХО, 1-1/e это уже что-то, что даёт надежду, что задачу можно решить красиво... Надежду...
Вот когда самый первый раз читал задачу подумалось про число e, чуял же что сидит где-то оно, только где именно - не понял
А новые соотношения как посчитаны? Как это в смысле алгоритм а не язык Брутфорсный перебор всея вариантов или тоже какие-ть рекурентные формулировки?
P.S> ИМХО, 1-1/e это уже что-то, что даёт надежду, что задачу можно решить красиво... Надежду...
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!
- Инна
- Популярный автор
- Сообщения: 1434
- Зарегистрирован: 18 июл 2006, 18:44
- Пол: Женский
- Откуда: Калифорния
Введем более общую вероятность p(i, queue) того, что будет съеден i-тый помидор в случае queue - массива дней в которые суждено сгнивать помидорам. Для исходной задачи queue(n) = {1,2,3,...,n-1,n}, в общем случае, это любая неубывающая последовательность, кроме того если какие-то значения больше числа L элементов массива (в исходной задаче L=n), то их можно заменить на L. Дальше пишется метод getProbability(i, queue), который проходит цикл по помидору съеденному в первый день, и вызывает этот же метод для i', queue'. Полученное значение помещается в hash, чтобы не вычислять снова.