Песни о Паскале
Шрифт:
P_37_4
Задача о кружках, версия 2
38
P_38_1
Задача о кружках, версия 3
P_38_2
Подвиг контрразведчика
P_38_3
Поиск стран-соседей
P_38_4
Решето Эратосфена
40
P_40_1
Программа «вопрос-ответ», версия 2 (с массивом)
P_40_2
Полицейская база данных, версия 3 (с массивом)
P_40_3
Подсчет букв в файле
41
P_41_1
«Пузырьковая» сортировка массива чисел
P_41_2
Пиратская делёжка по справедливости
P_41_3
Футбольный чемпионат, версия 1
42
P_42_1
Сравнение методов
43
P_43_1
"Фермерская" сортировка
P_43_2
«Быстрая» сортировка
P_43_3
Сравнение методов сортировки
44
P_44_1
Структура строки
P_44_2
Поиск в строке слова «PASCAL»
P_44_3
Замена в строке слова «Pascal»
45
P_45_1
Запись в танцевальный кружок, версия 1
P_45_2
Моделирование сортировочной станции
46
P_46_1
Печать сверхбольшого числа
P_46_2
Сложение сверхбольших чисел
47
P_47_1
Преобразование из десятичной системы
P_47_2
Преобразование в десятичную систему
48
P_48_3
Логические операции с числами
49
P_49_1
Подсчет пересечений границ между странами
P_49_2
Реклама «крестики-нолики»
50
P_50_1
Футбольный чемпионат, версия 2
P_50_2
Футбольный чемпионат, версия 3
51
P_51_1
Принцип действия указателей
P_51_2
Действия с указателями, размеры указателей
53
P_53_1
Ввод и вывод массив указателей
P_53_2
Сортировка массива указателей
54
P_54_1
Ввод и вывод списка
P_54_2
Поиск в списке
P_54_3
Сортированный список
P_54_4
Поиск в сортированном списке
55
P_55_1
Частотный анализатор текста
56
P_56_1
Перестановка строк файла
P_56_2
Запись в танцевальный кружок, версия 2
57
P_57_1
Ввод и вывод графа
58
P_58_1
Обход графа в ширину
P_58_2
Поиск кратчайшего пути в графе
5959
P_59_1
Перестановка строк файла (используется модуль MyLibr)
MyLibr
Библиотечный модуль к программе P_59_1
61
P_61_1
Демонстрация работы Turbo Vision
P_61_2
Программа с объектом типа «человек»
P_61_3
Демонстрация наследования и полиморфизма
Приложение М
Пример олимпиадной задачи
Представлена одна из задач XVII районной (городской) олимпиады по информатике Московской области 2004 г.
Дано
Трамвайная сеть города состоит из N трамвайных остановок, пронумерованных числами от 1 до N. Остановки соединяются друг с другом M перегонами, пронумерованными числами от 1 до M. На трамвайных остановках есть стрелки для перехода трамвая с любого ведущего к остановке перегона на любой другой перегон, ведущий от нее. Все перегоны имеют одинаковую длину, но принадлежат к двум типам: односторонние и двухсторонние. По односторонним перегонам трамваи могут двигаться только в одном направлении; по
Требуется
По заданной схеме трамвайной сети города найти кратчайший по времени путь между двумя заданными остановками, при условии, что трамваи никогда не мешают друг другу (в городе один трамвай). Входные данные гарантируют, что путь между остановками всегда существует.
Входные данные
В первой строке входного файла приведено количество остановочных пунктов N (2<= N<= 100) и число перегонов M (1 <= M <= 30000). Далее идут M строк с описаниями перегонов по одному описанию в строке. Каждое описание состоит из четырех чисел, разделенных пробелом: номера перегона; двух номеров остановок, которые соединяет данный перегон; тип перегона (1 – если перегон односторонний и 2 – если двусторонний). Если перегон односторонний, то движение трамваев по нему разрешается от первого остановочного пункта в описании ко второму. Далее следует строка с двумя номерами остановок, между которыми следует найти кратчайший по времени путь (от исходной остановки к конечной)
Выходные данные
В выходной файл «output.txt» следует вывести список номеров остановочных пунктов и перегонов между ними в порядке их прохождения трамваем. В случае нескольких возможных правильных ответов вывести любой из них.
Контрольный пример
Входные данные
4 61 2 1 12 2 1 23 1 3 15 2 4 24 2 3 26 4 3 11 4
Вывод
1 2 2 5 4
Библиография
1. Алексеев А. В. Олимпиады школьников по информатике. Задачи и решения. – Красноярск: Красноярское книжное издательство, 1995.
2. Андреева Е. В., Фалина И. Н. Информатика: Системы счисления и компьютерная арифметика. – М.: Лаборатория Базовых Знаний, 1999.
3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
4. Бабушкина И. А., Бушмелева Н. А., Окулов С. М., Черных С.Ю. Конспекты занятий по информатике (практикум по Паскалю). – Киров: Изд-во ВятГПУ, 1997.
5. Бадин Н. М., Волченков С. Г., Дашниц Н. Л., Корнилов П. А. Ярославские олимпиады по информатике. – Ярославль: Изд-во ЯрГУ, 1995.
6. Беров В. И., Лапунов А. В., Матюхин В. А., Пономарев А. А. Особенности национальных задач по информатике. – Киров: Триада-С, 2000.