Re[2]: Есть боллее практичное решение
От: Dragon  
Дата: 30.10.08 15:03
Оценка:
Общая идея предлагаемого алгоритма -- заставить погрешность определения середины саму себя нивелировать.
Алгоритм такой:
Пусть N — общее количество песка в песочных часах. В нашем случае, соответствующее 16 мин.
Будем записывать состояния часов следующим образом. Каждая строка записи соответствует количеству песка в верхней колбе часов.
Значком @ будем обозначать момент переворачивания часов.
Например, запись
@N     ; N/2     ;  0

означает, что в верхней колбе первых часов N песка и мы только что их перевернули. Во вторых часах -- N/2 песка. В третьих — 0.
Временем переворачивания пренебрегаем, считаем что мгновенно.


1. Запускаем первые и вторые часы
@N     ; @N     ;  0


2. Когда пройдет приблизительно N/2 времени, перевернем часы №2 и №3. Если d — погрешность определения середины, получаем

 N/2+d ; @N/2-d ;  @N


, где d может быть положительным или отрицательным.

3. Когда в часах №1 или №2 закончится песок, для удобства записи, переставим их местами, так чтоб под №2 оказались часы, в которых закончился песок

 2d    ;  0     ;  N/2+d


Теперь d строго положительно.Т.к. песок закончился в часах, у которых N/2-|d|
Далее шаги будут такими

 2d    ; @N     ; @N/2-d
 0     ;  N-2d  ;  N/2-3d
@N     ;  N-2d  ;  N/2-3d
 N/2+3d;  N/2+d ;  0
@N/2-3d; @N/2-d ; @N
 0     ; @N/2+2d;  N/2+3d
@N     ; @N/2+2d;  N/2+3d
 N/2-2d;  0     ;  d
@N/2+2d; @N     ;  d
 N/2+d ;  N-d   ;  0
 N/2+d ; @d     ;  0
 N/2   ;  0     ;  0


Собственно, получили в часах №1 8мин. Отмеряем их и ещё 16, получаем 24.

 0     ;  0     ;  0
 0     ;  0     ; @N
 0     ;  0     ;  0


Для алгоритма важно, чтоб выполнялось условие N/2 > 3d. Т.е. d < 8/3 мин. По моему, достаточно для определения "на глаз", но кого не устраивает, предлагаю самостоятельно дополнить алгоритм несколькими условными шагами, для повышения точности.
Последовательность шагов подобрана. Поэтому думаю, что можно их и уменьшить, как с точки зрения количества шагов, так и с точки зрения общего времени подготовки до начала отсчета 24 мин. интервала. Данная последовательность позволяет гарантированно начать отсчет менее чем через 40 мин. Точнее, через 40 мин.- d.

Алгоритм лучше, чем через вычисление НОК, т.к. не требует от "пользователя часов" вычислений, а только повторения шагов. Гарантированно позволяет начать отсчет 24 мин интервала через 40 мин. Хотя временем переворачивания мы и пренебрегали, но на практике, точность данного алгоритма выше за счет меньшего числа переворачиваний часов.

Кто сможет улучшить алгоритм по "времени подготовки" и количеству шагов? Или доказать его оптимальность?

Все шаги полностью:
@N     ; @N     ;  0
 N/2+d ; @N/2-d ; @N
 2d    ;  0     ;  N/2+d
 2d    ; @N     ; @N/2-d
 0     ;  N-2d  ;  N/2-3d
@N     ;  N-2d  ;  N/2-3d
 N/2+3d;  N/2+d ;  0
@N/2-3d; @N/2-d ; @N
 0     ; @N/2+2d;  N/2+3d
@N     ; @N/2+2d;  N/2+3d
 N/2-2d;  0     ;  d
@N/2+2d; @N     ;  d
 N/2+d ;  N-d   ;  0
 N/2+d ; @d     ;  0
 N/2   ;  0     ;  0
 0     ;  0     ;  0
 0     ;  @N    ;  0
 0     ;  0     ;  0
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.