интересная задача

[esperanto]

Есть комната в которой находится круглый стол.
На столе симметрично расположены 4 идентичные кнопки.
Нельзя различить включенные кнопки и выключенные.
Если все 4 кнопки включить в соседнем здании загорится свет.
В начальный момент неизвестно в каком состоянии находятся кнопки (часть вкл часть выкл).

Некто хочит зажечь свет в соседнем здании для этого он

1) входит в комнаты нажимает как хочет на кнопки
и выходит проверить зажегся ли свет

2) во время его отсутствия стол вращается на 90 или 180 или 270 или 360 градусов

3) если свет не горит человек возвращается и заново


вопросы
1) дайте алгоритм зажигающий свет за конечное число шагов
2) дайте оптимальный алгоритм.




задача 2)
за минимальное число сравнений найти в массиве состоящем из разных чисел минимальный и максимальный элементы и доказать оптимальность решения

[Visitor]

Алгоритм для двух кнопок:
1. нажимаем обе кнопки. есть свет -- решили. нет света -- выяснили, что вкл только одна из кнопок.
2. нажимаем одну кнопку. есть свет -- решили, нет света -- выяснили, что обе кнопки выкл
3. нажимаем обе кнопки.
(в худшем -- 3 нажатия)

Алгоритм для 4х:

1. нажимаем все кнопки. есть свет -- решили. нет света -- выяснили, что вкл 1, 2 или 3 кнопки
2. нажимам одну кнопку. есть свет -- решили. нет света -- выяснили, что вкл 2  или 0 кнопок.
3. нажимаем все кнопки. есть свет -- решили. нет света -- выяснили, что вкл 2 кнопки.
4. две вкл кнопки могут быть рядом или по диагонали друг от друга. предполагаем, что они стоят по диагонали -- тогда задача еквивалентна задаче о двух кнопках.
5. пытаемся решить задачу 2х кнопок. либо решаем, либо выясняем, что вкл кнопки стоят рядом.
6. нажимаем две рядом стоящие кнопки. теперь кнопки стоят по диагонали (или все выкл/все вкл)
7. решаем задачу 2х кнопок.
(в худшем -- 9 нажатий)

Оптимальность -- хз

--
Сравнений надо не менее N-1 (связности нет) и не более 2N-3 (достаточно в любом случае).

Сообщение отредактировано: Visitor - 02.11.03, 19:32

[zx1024]

Задача 2)
Можно написать нахождение максимума из двух чисел без сравнений (не исп. if и др. условные переходы). Но используется внутреннее представление чисел в компе (т.е. не чисто математически).
Следовательно, используя это, можно и для массива.

[Sazabis]

Задача 2)

<br>const n = ?<br><br>m[n] = random( ? );<br><br>min = m[0];<br>max = m[1];<br><br>for( int i=2;i<n;i++ ){<br>  if( cur < min )min = cur;<br>    else if( cur > max )max = cur;<br>}<br><br>// для худшего варианта 2n - 4;<br><br>if( min > max )swap( min, max ); // еще -1 :)<br><br>// итого (2n-3) как и писал Visitor :)<br>

Но!, не учтен вариант: n = 1
еще -1

итого мах: 2(n-1)

<br>const n = ?<br><br>m[n] = random( ? );<br><br>min = max = *m;<br><br>for( int i=1;i<n;i++ ){<br>  if( cur < min )min = cur;<br>    else if( cur > max )max = cur;<br>}<br>

итого от n-1, до 2(n-1)

[Visitor]

-1 сравнения, кажется, не быват.

[Sazabis]

ну так и я о том же

2n-3 при n = 1

[zx1024]

Задача 1)
Я строил автомат с 6 состояниями (0, 1, 2с, 2х, 3, 4) по количеству нажатых кнопок и по положению (2c, 2x - смежные и крестом). 5 входных сигналов (1, 2c, 2x, 3, 4) по действиям человека (нажатие кнопок).
Построил таблицу переходов. По ней начал строить дерево.
Рисовать его здесь не буду.
Вот решение.
4, 2x, 4, 2c, 4, 2x, 4, 1, 4, 2x, 4, 2c, 2x, 4
После некоторых нажатий можно (с вероятностью) перейти в состояние - 4.
В худшем случае (изначально нажаты 1 или 3 кнопки и стол каждй раз очень неудачно крутится) потребуются все эти нажатия.

[Sazabis]

комбинируя 2 решения

получаем

4, 1, 4, 2x, 4, 2c, 2x, 4

[Visitor]

Хм.. а если после
4,1,4,2x,4,2c получилось 0, а мы ето не проверили?

[zx1024]

Согласен, упустил.
4, 2x, 4, 2c, 4, 2x, 4, 1, 4, 2x, 4, 2c, 4, 2x, 4

[Visitor]

И первую часть можно выкинуть
Остается 4,1,4,2x,4,2c,4,2x,4, как и у меня

[zx1024]

Угу.
Только то, что осталось, надо будет прокрутить 2 раза.

[Visitor]

А в каком месте переход теряется? что-то не вижу...

[Visitor]

После 4,1
|--> двухкнопочная задача
+--> соседние кнопки
Достаточно решить двухкнопочную (или выяснить про соседние кнопки),
привести к двухкнопочной и решить ее еще раз.  Итого 9...

Сообщение отредактировано: Visitor - 03.11.03, 12:05

[Sazabis]

не, zx1024 прав.

до ( 1 ), устраняется возможность двухкнопочного расположения.

затем, после ( 1, 4 ), если дошли, у нас опять 2 кнопки.

если сразу 4, 1 то это не избавляет от неоднозначности.