|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Pavel Fomin 2:5026/49.21 08 Mar 2003 01:25:53 To : Vjacheslav Maslov Subject : Re: задачка о часах --------------------------------------------------------------------------------
07 Mar 03 21:34, you wrote to All:
VM> - -+-- Hаписать программу, которая определяет, можно ли повернуть
VM> шестеренку с номером K в заданном часовом механизме. Если это возможно
VM> перечислить номера шестеренок, пришедших в движение после поворота
VM> шестеренки с номером K, в порядке возрастания их номеров (включая K).
VM> ----- -+--
VM> Есть у кого какие идеи?
Предположим что можем повернуть. Тогда поворачиваем ее по часовой стрелке.
Очевидно, за ней повернуться все смеженые против часовой стрелки. Итого
алгоритм: (полагаем что все шестеренки одного диаметра, иначе запоминать будем
не только направление, но и угол поворота).
Есть массив чисел, по одному на шестеренку. Числа могут быть 0, 1 и -1. 0 - еще
не поворачивали, 1 и -1 - поворачиваем по/против часовой стрелки.
1) Обнулить вышеупомянутый массив.
2) Поместить в очередь стартовую шестеренку, поставить ей в массиве пометку 1.
3) Пока очередь не пуста:
3_1) Извечь номер из очереди
3_2) Для каждой смежной с ней:
3_2_1) Если ей сопоставлено число 0 - заменить на минус число сопоставленное
извлеченной шестеренке и поместить ее номер в очередь
3_2_2) Если же сопоставлено число, равное минус числу извлеченной шестеренки -
ничего не делаем
3_2_3) Иначе повернуть не сможем, прервать цикл, матюгнуться и выйти
4) Если мы до сюда добрались (не споткнулись на шаге 3_2_2), то повернуть
можем, и будут задействованы все шестеренки, для которых в массиве указано
ненулевое значение.
Pasha 1st, RU.(PASCAL[.SOURCES|.CHAINIK|.ASM]|ACM)
... Говорила мне мама: "Hе лезь в системщики"
--- GoldED/W32 3.0.1-asa9 SR3
* Origin: Windows имеет всех, кто ее имеет (2:5026/49.21)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/160653e693ae9.html, оценка из 5, голосов 10
|