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

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

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

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

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

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


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




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

Алгоритм для двух кнопок:
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

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

Задача 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)

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

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

2n-3 при n = 1

Задача 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 кнопки и стол каждй раз очень неудачно крутится) потребуются все эти нажатия.

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

получаем

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

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

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

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

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

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

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

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

не, zx1024 прав.

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

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

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

Как не избавляет? В начале-то свет НЕ горел . Значит, [4,1] останавливается по-марковски, либо переводит в класс {0,2x,2c}. А [4,2x,4] останавливается, либо сохраняет {2c}

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

начальное состояние

1000, 1100, 1010, 1110, 0000 [ 1, 2c, 2x, 3, 4 ]
4
0111, 0011, 0101, 0001, 1111
далее например так
1
1111, 1011, 1101, 1001 [3, 2c]

1) необходими более 10 перекладываний

2) менше чем 1.5*н сравнений

А, увидел. В самом начале Тогда да.

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

2) значит, такой граф все-таки оптимальный:

<br>min--+--a1--a2--+--max<br> |                  |<br> +------a3--a4------+<br> |                  |<br>       ...<br> +--a(N-3)--a(N-2)--+

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

(интересно, если строить... ну например, дерево, в среднем сколько будет )

для 2)
решение такое:

сравниваем попарно если надо, то меняем - слева меньше, справа больше.

использовали n/2

теперь для всех левых ищем меньший n/2
и для всех правых больший n/2

итого 1.5n для четного n

Сообщение отредактировано: Sazabis - 03.11.03, 13:48

<br>const n = ?<br><br>randominit( n, m[n] );<br>min = m[n-1];<br>max = m[n-1];<br><br>for( int i=0;i<n-1;i+=2 ){<br>  if( m[i] > m[i+1] )swap( m[i], m[i+1] );<br>}<br><br>for( int i=0;i<n;i+=2 ){<br>  if( m[i] < min )min = m[i];<br>}<br><br>for( int i=1;i<n;i+=2 ){<br>  if( m[i] > max )max = m[i];<br>}<br>

для чет и нечет N.

но на мой взгляд первый код оптимальней. Особенно для убывающего массива.

Тут гарантированные полтора N, там -- средние полтора N Как коворил преподаватель ТиП ЭВМ, при отсутствии доп. условий -- сильной половой разницы нет.

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

так то оно так, но 2 целых раза по массиву гуляем + эл. меняем

для тех кто решил 1


3) показать что если кол-во кнопок не равно степени 2 то задача не решается

4) и показать как решается задача в общем виде для любой степени двойки - кол-во кнопок

3)

отсутсвие 2 линий симетрии, с помощью которых происходит _точное_ инвертирование, лишает задачу конечного решения.

4)

h = n/2
hc - смежная половина
hх - симетричное пересечение

h ( n, hx, n, hc, n, hx 1 )

Цитата Sazabis, 04.11.03, 10:40:34

3)

отсутсвие 2 линий симетрии, с помощью которых происходит _точное_ инвертирование, лишает задачу конечного решения.

4)

h = n/2
hc - смежная половина
hх - симетричное пересечение

h ( n, hx, n, hc, n, hx 1 )

не совсем ясен смысл обозначений

3)
у нас есть круг с кнопками.
для наглядности объяснения, рисуем диагональ краской, если диагональ прошла по кнопке, кнопка стала помечена.

Необходимо так провести диагонали чтобы получилось закрашено-незакрашено-закрашено-...

4)
для кнопок n, где n удовлетваряет условию 3)

hc - нажимается половина кнопок, подряд.
hх - нажимается половина кнопок, через одну
1 - нажимается 1 кнопка.
n - нажимаются все кнопки.

( n, hx, n, hc, n, hx, 1,  ) n/2 раз - формула такая. Но суть потерял, надо еще подумать

Он рекуррентный получится... Только в голове укладывается с трудом... Надо автомат нарисовать
И будет в нем, похоже, 2^2^n-1 шагов... Т.к., если для решения задачи о 2^k кнопках достаточно 2^2^k-1, то если увеличить число кнопок в 2 раза (2^(k+1)), придется 2^k таких же точно задач пытаться решить + по 1 шагу на переход от одной такой задачи к другой...

Сообщение отредактировано: Visitor - 05.11.03, 09:01

не правильное решение
да и с симметрией перегиб