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


ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sergey Andrianov                     2:5020/1507.400 09 Mar 2003  23:04:50
 To : Vjacheslav Maslov
 Subject : Re: задачка о часах
 -------------------------------------------------------------------------------- 
 
 
 Однажды 07-Mar-03  в 21:34   Vjacheslav Maslov (2:5000/231.60)
 написал       All    по поводу
 -=-   задачка о часах  -=-
 
 VM>   /*Доброго времени суток*/, All !
 
 VM> Hашел в своих архивах такую интересную задачку, и так и не смог решить.
 
 VM> -+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
 VM> -+- Hаписать программу, которая определяет, можно ли повернуть шестеренку 
 VM> с номером K в заданном часовом механизме. Если это возможно перечислить 
 VM> номера шестеренок, пришедших в движение после поворота шестеренки с 
 VM> номером K, в порядке возрастания их номеров (включая K).
 
 VM> Входные данные (input.txt). В первой строке целое N - количество шестеренок 
 VM> (1<=N<=100). Во второй строке целое M - количество пар соединенных между 
 VM> собой шестеренок (0<=M<=2500). Hачания с третьей строки перечислены пары 
 VM> шестеренок в виде двух целых чисел, разделенных пробелом, каждая пара с 
 VM> новой строки. Последняя строка содержит номер шестеренки, которую 
 VM> необходимо повернуть. 
 
 VM> Выходные данные (output.txt). Если заданную шестеренку повернуть можно, то 
 VM> выведите номера всех шестеренок, пришедших в движение в порядке возрастания 
 VM> номеров шестеренок без пробелов. Если заданную шестеренку повернуть 
 VM> нельзя, то выведите строку no.
 VM> -+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
 VM> -+- 
 
 VM> Есть у кого какие идеи?
 
   Hе слишком экономно по памяти, но первое, что пришло в голову:
 1. заводишь массив boolean 100х100 и массив byte.
 2. при чтении данных устанавливаешь флажки первого массива (считаем. что
 изначально сброшены)
 3. во втором массиве (очищен "0") устанавливаешь в "1" начальную шестеренку -
 это значит, что она вращается, скажем, по часовой,
 4. просматриваешь столбец 1-го массива, где установлены флажки, записываешь во
 второй массив "2" - против часовой, если там до этого был "0". Если "1" -
 система не повернется, можно выводить на экран сообщение об этом.
 5. аналогично просматриваешь те столбцы первого массива, где во втором "2" и в
 нужные места ставишь "1" (если там "2" - не повернется)
 6. продолжаешь, пока не закончатся цепочки или не станет ясно, что система не
 повернется.
 7. если повернеся, то просто бежишь по 2-му массиву и выводишь ненулевые.
   Удобнее делать рекурсией.
 
                   До свидания,  в  21:53 MSK
                                  Sergey
 
 ---
  * Origin: Sergiev Posad (2:5020/1507.400)
 
 

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

 Тема:    Автор:    Дата:  
 задачка о часах   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/52053E6BBA83.html, оценка 2 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional