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

[Visitor]

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

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

[Sazabis]

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

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

[esperanto]

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

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

[Visitor]

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

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

[Visitor]

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

[Visitor]

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

[Sazabis]

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

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

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

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

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

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

[Sazabis]

<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.

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

[Visitor]

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

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

[Sazabis]

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

[esperanto]

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


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

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

[Sazabis]

3)

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

4)

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

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

[esperanto]

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

3)

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

4)

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

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

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

[Sazabis]

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

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

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

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

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

[Visitor]

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

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