Стеклянные шарики Опции

[scoute]

Между прочим недопонимание этого алгоритма чем-то вяжется с архиваторами ... учёные придумывают алгоритмы для частных случаев методом тыка, но до понимания "идеального" им далеко. Хотя кое-какие изыскания в области хаотичностей имеются ...
Не понятно только, как за минимум усилий определить степень "минимальной хаотичности" ряда нулей и единиц.

И разгадка, (как мне кажется), таится в 3х- или 4х-мерном представлении этого ряда.

А может даже N-мерном представлении.

[scoute]

Есть несколько идей по этому поводу, но формулу пока привести не могу.
Тут фишка в подобии. У нас 2 шарика, значит подобие будет 2-го уровня. Если 3 шарика - то 3-го уровня.

Но это для линейного поиска(19 бросков), где не нужно всё подгонять под минимум. А вот как применить смещение, я пока не знаю.
Получается, что количество бросков от первого до 14 этажа(наш частный случай) должно ровняться количеству бросков, учитывая подобие.

Прикрепленные файлы

 2_3.png ( 931 байт ) Кол-во скачиваний: 12

 

[scoute]

Ухх ... чисто практически подобрал кое-что, возможно ошибаюсь , поправьте.

Значит 100 этажей лежат между рядами {1+2+3+..+13}(=91) <100<{1+2+3+..+14}(=105). ==> 91<100<105
То есть за 14 бросков можно осилить вплоть до 105 этажа.
Как же дело обстоит с 3 шариками, тут покруче ))

3 шарика за 9(!) бросков осиливают 100 этажный дом ... Итак, найдено подбором:
37,66,88,100. ... потом любое окно по 1-му методу. В этом случае 100 этажей не дают полной картины, т.к ряд немного длиннее:
37,66,88,104,115,122,126,128,129.
Однако вывести зависимость и построить ряд мне так и не удалось.
Если первый ряд геометрически похож на
 5_12.png ( 3,21 килобайт ) Кол-во скачиваний: 2

то есть для 12 этажей понадобится минимум 5 бросков. Что касается 3х шаров, представление типа
 5_13.png ( 1,07 килобайт ) Кол-во скачиваний: 1

катит, но с некоторыми нюансами. Допустим у нас 3 шара и 100 этажей.
Тогда в объёмную пирамиду
*10 ступени - влезет 220 шаров,
*9 ступени - влезет 165 шаров,
*8 ступени - влезет 120 шаров.
*7 ступени - влезет 84 шара.
Казалось бы, раз число 100 находится между 84 и 120, ответ - минимум надо 8 бросков. ОДНАКО
Но тут затаился один нюанс. Из числа шаров, которые влезают в объёмную пирамиду, надо вычесть
число шаров, которые влезают в ПЛОСКУЮ пирамиду, построенной на ступени "минус 1 шар",
поэтому ответ будет не 8, а 9.

Привожу ряды

1) 1,   2,   3,   4,   5,   6,   7,   8,   9,  10 - просто по порядку.
2) 1,   3,   6,  10,  15,  21,  28,  36,  45,  55 - числа для плоской пирамиды.
3) 1,   4,  10,  20,  35,  56,  84, 120, 165, 220 - числа для объёмной пирамиды.

4) 1,   3,   7,  14,  25,  41,  63,  92, 129, 175 - результат для 3х шаров.

Обратили внимание?
Каждый новый ряд получается путём прибавления к текущему числу следующего элемента предыдущего ряда, то есть:
 posled.png ( 1,81 килобайт ) Кол-во скачиваний: 4

А наш искомый ряд получается дополнительным вычитанием из текущего числа предыдущего элемента предыдущего ряда, то есть:
 posled2.png ( 2,03 килобайт ) Кол-во скачиваний: 4

Однако ПОЧЕМУ надо из объёмного ряда вычитать плоский, да ещё и со смещением, этого я, увы, объяснить не могу.
Есть предположения, что когда шара 3 а броска 2, то получается переизбыток шаров, который влияет на дальнейший ряд.
Видимо надо рассматривать больше примеров с большим количеством шаров, бросков и этажей.



Ещё есть идея про треугольники. Представим 2 треуголника в виде холма (пока без фиолетового маленького)
 geo1.png ( 1,15 килобайт ) Кол-во скачиваний: 7

Высота в этом холме - это искомое число этажей, а левый и правый склоны - это балланс
между бросками без рекурсии (то есть после первого броска мы уже не подымаемся выше)
и полной рекурсией, когда приходится подыматься аж до 100го этажа. Углы "альфа" одни и те же.

Третий (фиолетовый) треугольник я пририсовал(но туда ли?) в надежде выявить зависимость для N количества шариков.
Единственное, что мне не нравится в треугольниках, это дробные числа в решении, которые потом надо округлять до целых, +1.
Вариант с шариками гораздо нагляднее и проще.

Возможно это ещё дифференциалами решается ... типо f(x)=f'(x)=f''(x)

Сообщение отредактировал scoute - 28.12.2009, 13:44