Задача

← →
SPeller (2003-04-28 12:08) [0]

Всем доброго времени суток!
Задали мне задачу про бокалы. Дано N бокалов, причём некоторые из них стоят неправильно (перевёрнуты). Задано также число А, которое определяет количество бокалов, которое можно перевернуть за 1 раз. Переворачивать можно любые А бокалов, расположенных непосредственно по соседству, то есть подряд. Бокалы расположены "кольцом", т.е. первый бокал следует за последним. Требуется найти наименьшее число переворотов, требующееся для того, чтобы все бокалы стояли правильно и вывести пошаговую информацию о переворачиваемых бокалах. Если этого сделать нельзя, то вывести соответствующее сообщение.

Кто-нибудь знает, как решить задачу или алгоритм её решения? Может, есть ресурсы, где она описана?

← →
Думкин (2003-04-28 12:32) [1]

A<N?
%-)

← →
SPeller (2003-04-28 12:33) [2]

Естественно :-)) Тогда смысл задачи потерялся бы.

← →
Vlad Oshin (2003-04-28 12:35) [3]

задача на четность, смотря сколько всего и сколько неправильных
Поиши М.Гарднер "Математические досуги"

← →
Думкин (2003-04-28 12:42) [4]

> SPeller © (28.04.03 12:33)

Зря ты так. Переворачивать то можно только соседей.

← →
SPeller (2003-04-28 12:46) [5]

> Думкин © (28.04.03 12:42)

Что зря?

> Vlad Oshin © (28.04.03 12:35)

В электронном виде я её не нашёл, а в библиотеке ещё давно спрашивал - сказали что нет такой у них.... :(

← →
Vlad Oshin (2003-04-28 12:48) [6]

> SPeller © (28.04.03 12:46)

сейчас мбо придет и решит, а если нет - поищу дома, тогда завтра только напишу :)

← →
REA (2003-04-28 12:49) [7]

А чего общественность то напрягать? Кубик рубика вот тоже собрать можно и т.п.

← →
SPeller (2003-04-28 12:51) [8]

> Vlad Oshin © (28.04.03 12:48)
> сейчас мбо придет и решит, а если нет - поищу дома, тогда
> завтра только напишу :)

Хорошо, буду ждать пришествия Бориса или завтра :)

← →
Думкин (2003-04-28 13:11) [9]

> SPeller © (28.04.03 12:51)

Зря - потому что смысл все равно есть.

← →
MBo (2003-04-28 13:19) [10]

На MBo надейся, а сам не плошай ;)))

Я сразу так не вижу, как искать минимальное количество.

Сама возможность добиться правильной расстановки - по четности, видимо, как Vlad Oshin сказал.

← →
SPeller (2003-04-28 13:43) [11]

> MBo © (28.04.03 13:19)
> На MBo надейся, а сам не плошай ;)))

Это само собой разумеется, просто я пока не могу тронуться с места в раздумьях своих. Мне нужно направление куда копать. Мне бы почву, а там сам до всего дойду, не глупый вроде :-))

2 Vlad Oshin
Посмотрите чего-нибудь у себя, я до завтра подожду да буду вплотную уже этим вопросом заниматься.

← →
DAC (2003-04-28 15:59) [12]

Могу предложить достаточно простое, но тупое (долгое) решение.
Смысл следующий: берешь конечное состояние (все правильно перевернутые) и посредством операции перевертывания (ее можно рассматривать также, как отношения двух состояний) производишь построение замыкания множества. Если во множестве есть твое первоначальное состояние, то задача имеет решение. При некоторой упорядоченности построения множества, можно получить оптимальное решение (например, если использовать что-то типа очереди – поиск вширь).

← →
Sha (2003-04-28 16:06) [13]

2SPeller © (28.04.03 13:43)

В отношении сушествования решения.
Если (A,N)=1, то можно перевернуть 2 любых стакана, не трогая остальные. Т.е. в этом случае решение всегда существует, если перевернуто четное количество стаканов. Если при этом A нечетное, то решение всегда существует.

В отношении оптимальности ясности нет.

← →
SPeller (2003-04-29 00:25) [14]

Частный случай из задачи: имеем последовательность 00100 (0-перевёрнутые). Если А=3 (оба числа нечётные), то эту последовательность поставим правильно за 2 раза. Вот такие случаи надо предусматривать.

← →
Sha (2003-04-29 07:18) [15]

>SPeller © (29.04.03 00:25)
>Вот такие случаи надо предусматривать.

5 и 3 взаимнопросты, 3 - нечетное => решение есть всегда.
А как найти оптимальное - думай сам. В приведенном случае подойдет простой перебор.

← →
Vlad Oshin (2003-04-29 09:06) [16]

Вчера к родителям не попал(там книга)
Но тут и так много сказали, есть зацепки.
Извините, Александр.

Задача Найти похожие ветки