Главная страница


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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 задачка о часах   Vjacheslav Maslov   07 Mar 2003 22:34:41 
 Re: задачка о часах   Pavel Fomin   08 Mar 2003 01:25:53 
 Re: задачка о часах   Oleg I. Khovayko   13 Mar 2003 18:58:49 
 Re: задачка о часах   Igor Krassikov   07 Mar 2003 22:09:00 
 Re: задачка о часах   Andrew Starsh   08 Mar 2003 15:55:59 
 задачка о часах   Alex Kasarab   08 Mar 2003 09:24:10 
 Re: задачка о часах   Sergey Andrianov   09 Mar 2003 23:04:50 
 задачка о часах   Nickita A Startcev   18 Mar 2003 02:50:00 
Архивное /ru.algorithms/160653e693ae9.html, оценка 1 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional