Один мудрец... (Страница 4 из 4)

надо с боксом завязыать...

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

В худшем результате будет 51 шаг.

brain

Вообще то 19 шагов (кидать ещё раз второй шар с 100-го этажа незачем). Алгоритм неплохой, но он не самый оптимальный, есть ещё кароче

Отредактировано Ktulkhu (2008-04-10 17:04:27)

brain

Именно так, всего два шарика. Иначе самым оптимальным алгоритмом был бы банальный бинарный поиск

Если бы шаг был фиксированным, то действительно оптимальный шаг будет равен 10. Считать довольно просто, особенно составив электронную таблицу.
Однако, не стоит зацикливаться на фиксированном шаге, так как шаг не всегда оптимальный 10. К примеру, если у вас впереди еще 100 этажей, то возможно, оптимальный шаг будет 10. Но если та же задача была бы озвучена для 30-этажного здания, то мы бы выбрали другой шаг. А почему? Потому что условия задачи другие. Но ведь и в нашем случае, если мы находимся уже на 70 этаже и шарики по-прежнему целы, то остается 30 этажей, а их проверять шагом 10 не выгодно. Использовав другой шаг, можно сэкономить еще парочку итераций.

В случае с 100 этажным зданием, проверять лучше так:
0) Надо прибавить 14 этажей.
1) 14 этаж. Если разбился, то сканируем вторым шариком с 1 по 13 этаж и находим нужный в худшем случае на 14 ход; Иначе прибавляем 13 этажей
2) 27 этаж. Если разбился, то сканируем вторым шариком с 15 по 26 этаж и находим нужный в худшем случае за 14 ходов; Иначе прибавляем 12 этажей
.......
39    11
50    10
60    9
69    8
77    7
84    6
90    5

10) 95    этаж. Если разбился, то проверяем 91, 92, 93, 94 этаж и в худшем случае находим нужный этаж на 14 ход.  Иначе прибавляем 5 этажей и попадаем на 99 этаж.
11) 99 этаж. Разбился, тогда 96, 97, 98 и все так же находим на 14 ход в худшем случае.

Вот, вроде не накосячил нигде. К сожалению, результат получил эмпирическим путем. Общую формулу родить увы не смог, подозреваю что тут участие принимают какие-нибудь логарифмы или пределы, или еще что, а у меня по высшей математике с прошлого года долг

В любом случае этот алгоритм позволяет найти этаж за 14 ходов.

Принял идею Данилка за эталон. Согласен. Оптимизировал. результат 14. не улучшен, но есть система
необходимо уменьшать шаг приращения этажа с каждой итеррацией.
оптимальный шаг для заданного количества этажей принимаю за sqrt(количество этажей)

рассчитываю так:
для каждого приращения этажа, рассчитываю остаток. А сколько еще осталось подниматься? (О - остаток)

О = 100 - Пп;
,где Пп - позиция предыдущая

затем корень квадратный из Остатка (Ко - корень остатка)
Ко = sqrt(О);

затем вычисляю текущую позицию (Пт - позиция текущая)
Пт = Пп + ОКРУГЛ_ДО_ЦЕЛОГО ( Ко + ( Ко*0,6 ) / 2)

округление применяется по понятным причинам, дробный этажей не может быть.

0,6 коэффицент подобранный вручную. цель сделать первый шаг меньше 14, чтобы улучшить предыдущий результат
при уменьшении коэффициента, решение задачи ухудшается.

в результате получаем таблицу

№   текущая остаток  корень(ост.)      шаг(округ)
        0    100         10                13
1    13    87         9,327379053    13
2    26    74         8,602325267    12
3    38    62         7,874007874    11
4    49    51         7,141428429    10
5    59    41         6,403124237    9
6    68    32         5,656854249    8
7    76    24         4,898979486    7
8    83    17         4,123105626    6
9    89    11         3,31662479     5
10    94    6         2,449489743    4
11    98    2         1,414213562    2

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

самое интересное дальше. если убрать функцию ОКРУГЛ_ДО_ЦЕЛОГО, чего нельзя делать для расчета шагов, но можно для проверки решения, мы получаем ровно 14 шагов, прежде чем Пт станет равным 100!
похоже оптимально.

кто ничего не понял, но жаждит разобраться могу выслать xls файл с расчетом

Кажется у меня новая идея.
Почему алгоритм, в котором 14 шагов, оказался оптимальным? Не оттого ли, что в худшем случае, количество бросков первого шарика + количество бросков второго шарика всегда оказывается равным 14. Почему именно 14?
Ради интереса: 100/14=7 (с округлением)
Чем замечательно число 7 в данном случае? Не тем ли, что 7+7=14?
Теперь формула такова: необходимо делить 100 на 1,2,3,4 до тех пор, пока делитель при умножении на 2 не совпадет с результатом деления.

К примеру, в здании 50 этажей:
50/1=50; 1*2-50<>0
50/2=25; 2*2-25<>0
50/3=17 (округ); 3*2-17<>0
50/4=13 (округ); 4*2-13<>0
50/5=10; 5*2-10=0
Итак, для 50 этажного здания нашли, что начинать надо с 10 этажа и в худшем случае мы будем находить результат за 10 попыток.

Private Sub UserForm_Click()
Dim EtKol As Integer  'Количество этажей
Dim SharKol As Integer 'Количество шариков
EtKol = CInt(txtEt) 'Из текстового поля получаем количество этажей
SharKol = 2 'Количество шаров пока 2
Dim x As Integer 'Первый шаг будет в этой переменной

For i = 1 To EtKol
If Round(EtKol / i - i * SharKol, 0) = 0 Then x = Round(EtKol / i, 0)
Next
MsgBox (x)

End Sub

Это код программы, которую я написал на VBA. Я предполагаю, что 2 - это как раз количество шариков. Если их количество взять 3, то для 100 этажного здания не получится при переборе получить 0, но зато получится просто ближайшее к 0 значение. Мне просто лень совершенствовать программу, но думаю все и так ясно.
Проверяйте :blush:

Хм... меня тут немного припозорили по поводу цикла в моей программе.
Конечно, цикл там видимо можно заменить формулой  sqrt(этаж / 2)
Например, sqrt(100/2)=7 (округлено)
Конечно же, x=2*sqrt(100/2)=14 (округленно).
Спасибо Zerkms за тычок носом. Хотя, мой алгоритм выше - это просто поиск нужного русла.
Судя по всему, x=2*sqrt(100/2) как раз и есть искомая формула, где x - этаж, с которого надо начинать

Вот вам новая задачка

Есть N коробок. Все они открыты.
Человек проходит и закрывает каждую вторую коробку.
Затем проходит по каждой третей коробки, если она открыта закрывает, если закрыта открывает.
Потом по каждой четвёртой и так до N.
Сколько коробок останутся открытыми после всех этих действий?

если она открыта закрывает, если закрыта открывает.

zerkms

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