|
|
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) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/52053E6BBA83.html, оценка из 5, голосов 10
|