Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=109874 Fri, 07 Nov 2003 09:04:25 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=109874
QUOTE (Sazabis @ 4.11.03, 18:46)
3)
у нас есть круг с кнопками.
для наглядности объяснения, рисуем диагональ краской, если диагональ прошла по кнопке, кнопка стала помечена.

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

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

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

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

не правильное решение
да и с симметрией перегиб ]]> Влад Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88983 Tue, 04 Nov 2003 15:52:33 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88983 И будет в нем, похоже, 2^2^n-1 шагов... Т.к., если для решения задачи о 2^k кнопках достаточно 2^2^k-1, то если увеличить число кнопок в 2 раза (2^(k+1)), придется 2^k таких же точно задач пытаться решить + по 1 шагу на переход от одной такой задачи к другой...]]> Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88982 Tue, 04 Nov 2003 15:46:04 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88982 у нас есть круг с кнопками.
для наглядности объяснения, рисуем диагональ краской, если диагональ прошла по кнопке, кнопка стала помечена.

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

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

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

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




]]> Sazabis Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88981 Tue, 04 Nov 2003 13:23:29 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88981 Цитата Sazabis, 04.11.03, 10:40:34
3)

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

4)

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

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


не совсем ясен смысл обозначений]]> esperanto Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88980 Tue, 04 Nov 2003 07:40:34 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88980
отсутсвие 2 линий симетрии, с помощью которых происходит _точное_ инвертирование, лишает задачу конечного решения.

4)

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

h ( n, hx, n, hc, n, hx 1 )
]]> Sazabis Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88979 Mon, 03 Nov 2003 17:48:14 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88979

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

4) и показать как решается задача в общем виде для любой степени двойки - кол-во кнопок]]> esperanto Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88978 Mon, 03 Nov 2003 15:16:37 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88978 Sazabis Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88977 Mon, 03 Nov 2003 14:27:51 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88977 Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88976 Mon, 03 Nov 2003 13:58:06 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88976
    <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.

но на мой взгляд первый код оптимальней. Особенно для убывающего массива.]]> Sazabis Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88975 Mon, 03 Nov 2003 13:47:39 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88975 решение такое:

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

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

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

итого 1.5n для четного n
]]> Sazabis Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88974 Mon, 03 Nov 2003 12:57:49 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88974 Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88973 Mon, 03 Nov 2003 12:55:30 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88973
    <br>min--+--a1--a2--+--max<br> |                  |<br> +------a3--a4------+<br> |                  |<br>       ...<br> +--a(N-3)--a(N-2)--+
]]> Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88972 Mon, 03 Nov 2003 12:45:47 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88972 Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88971 Mon, 03 Nov 2003 12:34:53 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88971

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

2) менше чем 1.5*н сравнений]]> esperanto Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88970 Mon, 03 Nov 2003 12:34:28 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88970
1000, 1100, 1010, 1110, 0000 [ 1, 2c, 2x, 3, 4 ]
4
0111, 0011, 0101, 0001, 1111
далее например так
1
1111, 1011, 1101, 1001 [3, 2c]
]]> Sazabis Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88969 Mon, 03 Nov 2003 12:19:03 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88969 Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88968 Mon, 03 Nov 2003 12:16:32 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88968
до ( 1 ), устраняется возможность двухкнопочного расположения.

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

если сразу 4, 1 то это не избавляет от неоднозначности.]]> Sazabis Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88967 Mon, 03 Nov 2003 12:04:52 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88967 |--> двухкнопочная задача
+--> соседние кнопки
Достаточно решить двухкнопочную (или выяснить про соседние кнопки),
привести к двухкнопочной и решить ее еще раз.  Итого 9...]]> Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88966 Mon, 03 Nov 2003 11:57:48 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88966 Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88965 Mon, 03 Nov 2003 11:43:07 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88965 Только то, что осталось, надо будет прокрутить 2 раза. :)]]> zx1024 Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88963 Mon, 03 Nov 2003 11:18:19 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88963 Остается 4,1,4,2x,4,2c,4,2x,4, как и у меня :)]]> Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88962 Mon, 03 Nov 2003 11:12:13 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88962 4, 2x, 4, 2c, 4, 2x, 4, 1, 4, 2x, 4, 2c, 4, 2x, 4]]> zx1024 Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88961 Mon, 03 Nov 2003 10:37:30 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88961 4,1,4,2x,4,2c получилось 0, а мы ето не проверили?]]> Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88960 Mon, 03 Nov 2003 10:30:27 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88960
получаем

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


]]> Sazabis Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88959 Mon, 03 Nov 2003 10:09:46 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88959 Я строил автомат с 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 кнопки и стол каждй раз очень неудачно крутится) потребуются все эти нажатия.]]> zx1024 Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88958 Mon, 03 Nov 2003 08:51:18 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88958
2n-3 при n = 1
]]> Sazabis Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88957 Mon, 03 Nov 2003 08:40:52 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88957 Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88956 Mon, 03 Nov 2003 08:34:45 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88956
    <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)
;)]]> Sazabis Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88955 Sun, 02 Nov 2003 22:47:03 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88955 Можно написать нахождение максимума из двух чисел без сравнений (не исп. if и др. условные переходы). Но используется внутреннее представление чисел в компе (т.е. не чисто математически).
Следовательно, используя это, можно и для массива.]]> zx1024 Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88954 Sun, 02 Nov 2003 19:02:34 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88954 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 Алгоритмы https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88953 Sun, 02 Nov 2003 16:03:43 +0000 интересная задача https://forum.sources.ru/index.php?showtopic=9046&view=findpost&p=88953 На столе симметрично расположены 4 идентичные кнопки.
Нельзя различить включенные кнопки и выключенные.
Если все 4 кнопки включить в соседнем здании загорится свет.
В начальный момент неизвестно в каком состоянии находятся кнопки (часть вкл часть выкл).

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

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

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

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


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




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