
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[216.73.217.2] |
![]() |
|
Сообщ.
#1
,
|
|
|
Есть комната в которой находится круглый стол.
На столе симметрично расположены 4 идентичные кнопки. Нельзя различить включенные кнопки и выключенные. Если все 4 кнопки включить в соседнем здании загорится свет. В начальный момент неизвестно в каком состоянии находятся кнопки (часть вкл часть выкл). Некто хочит зажечь свет в соседнем здании для этого он 1) входит в комнаты нажимает как хочет на кнопки и выходит проверить зажегся ли свет 2) во время его отсутствия стол вращается на 90 или 180 или 270 или 360 градусов 3) если свет не горит человек возвращается и заново вопросы 1) дайте алгоритм зажигающий свет за конечное число шагов 2) дайте оптимальный алгоритм. задача 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 (достаточно в любом случае). ![]() |
Сообщ.
#3
,
|
|
|
Задача 2)
Можно написать нахождение максимума из двух чисел без сравнений (не исп. if и др. условные переходы). Но используется внутреннее представление чисел в компе (т.е. не чисто математически). Следовательно, используя это, можно и для массива. |
Сообщ.
#4
,
|
|
|
Задача 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) ![]() |
Сообщ.
#5
,
|
|
|
-1 сравнения, кажется, не быват.
![]() |
Сообщ.
#6
,
|
|
|
ну так и я о том же
![]() 2n-3 при n = 1 |
Сообщ.
#7
,
|
|
|
Задача 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 кнопки и стол каждй раз очень неудачно крутится) потребуются все эти нажатия. |
Сообщ.
#8
,
|
|
|
комбинируя 2 решения
![]() получаем 4, 1, 4, 2x, 4, 2c, 2x, 4 |
Сообщ.
#9
,
|
|
|
Хм.. а если после
4,1,4,2x,4,2c получилось 0, а мы ето не проверили? |
Сообщ.
#10
,
|
|
|
Согласен, упустил.
4, 2x, 4, 2c, 4, 2x, 4, 1, 4, 2x, 4, 2c, 4, 2x, 4 |
Сообщ.
#11
,
|
|
|
И первую часть можно выкинуть
![]() Остается 4,1,4,2x,4,2c,4,2x,4, как и у меня ![]() |
Сообщ.
#12
,
|
|
|
Угу.
Только то, что осталось, надо будет прокрутить 2 раза. ![]() |
Сообщ.
#13
,
|
|
|
А в каком месте переход теряется? что-то не вижу...
|
Сообщ.
#14
,
|
|
|
После 4,1
|--> двухкнопочная задача +--> соседние кнопки Достаточно решить двухкнопочную (или выяснить про соседние кнопки), привести к двухкнопочной и решить ее еще раз. Итого 9... |
Сообщ.
#15
,
|
|
|
не, zx1024 прав.
до ( 1 ), устраняется возможность двухкнопочного расположения. затем, после ( 1, 4 ), если дошли, у нас опять 2 кнопки. если сразу 4, 1 то это не избавляет от неоднозначности. |
Сообщ.
#16
,
|
|
|
Как не избавляет? В начале-то свет НЕ горел
![]() |
Сообщ.
#17
,
|
|
|
начальное состояние
1000, 1100, 1010, 1110, 0000 [ 1, 2c, 2x, 3, 4 ] 4 0111, 0011, 0101, 0001, 1111 далее например так 1 1111, 1011, 1101, 1001 [3, 2c] |
Сообщ.
#18
,
|
|
|
1) необходими более 10 перекладываний 2) менше чем 1.5*н сравнений |
Сообщ.
#19
,
|
|
|
А, увидел.
![]() ![]() |
Сообщ.
#20
,
|
|
|
2) значит, такой граф все-таки оптимальный:
![]() ![]() <br>min--+--a1--a2--+--max<br> | |<br> +------a3--a4------+<br> | |<br> ...<br> +--a(N-3)--a(N-2)--+ |
Сообщ.
#21
,
|
|
|
(интересно, если строить... ну например, дерево, в среднем сколько будет
![]() |
Сообщ.
#22
,
|
|
|
для 2)
решение такое: сравниваем попарно если надо, то меняем - слева меньше, справа больше. использовали n/2 теперь для всех левых ![]() и для всех правых больший n/2 итого 1.5n для четного n |
Сообщ.
#23
,
|
|
|
![]() ![]() <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. но на мой взгляд первый код оптимальней. Особенно для убывающего массива. |
Сообщ.
#24
,
|
|
|
Тут гарантированные полтора N, там -- средние полтора N
![]() ![]() |
Сообщ.
#25
,
|
|
|
так то оно так, но 2 целых раза по массиву гуляем + эл. меняем
|
Сообщ.
#26
,
|
|
|
для тех кто решил 1
3) показать что если кол-во кнопок не равно степени 2 то задача не решается 4) и показать как решается задача в общем виде для любой степени двойки - кол-во кнопок |
Сообщ.
#27
,
|
|
|
3)
отсутсвие 2 линий симетрии, с помощью которых происходит _точное_ инвертирование, лишает задачу конечного решения. 4) h = n/2 hc - смежная половина hх - симетричное пересечение h ( n, hx, n, hc, n, hx 1 ) |
Сообщ.
#28
,
|
|
|
Цитата Sazabis, 04.11.03, 10:40:34 3) отсутсвие 2 линий симетрии, с помощью которых происходит _точное_ инвертирование, лишает задачу конечного решения. 4) h = n/2 hc - смежная половина hх - симетричное пересечение h ( n, hx, n, hc, n, hx 1 ) не совсем ясен смысл обозначений |
Сообщ.
#29
,
|
|
|
3)
у нас есть круг с кнопками. для наглядности объяснения, рисуем диагональ краской, если диагональ прошла по кнопке, кнопка стала помечена. Необходимо так провести диагонали чтобы получилось закрашено-незакрашено-закрашено-... 4) для кнопок n, где n удовлетваряет условию 3) hc - нажимается половина кнопок, подряд. hх - нажимается половина кнопок, через одну 1 - нажимается 1 кнопка. n - нажимаются все кнопки. ( n, hx, n, hc, n, hx, 1, ) n/2 раз - формула такая. Но суть потерял, надо еще подумать |
Сообщ.
#30
,
|
|
|
Он рекуррентный получится... Только в голове укладывается с трудом... Надо автомат нарисовать
![]() И будет в нем, похоже, 2^2^n-1 шагов... Т.к., если для решения задачи о 2^k кнопках достаточно 2^2^k-1, то если увеличить число кнопок в 2 раза (2^(k+1)), придется 2^k таких же точно задач пытаться решить + по 1 шагу на переход от одной такой задачи к другой... |
Сообщ.
#31
,
|
|||
|
не правильное решение да и с симметрией перегиб |