Текст книги "Песни о Паскале (СИ)"

Автор книги: Олег Деревенец

сообщить о нарушении

Текущая страница: 29 (всего у книги 29 страниц)

P_18_2

Распечатка строки по вертикали, версия 2

19

P_19_1

Процедура без параметров

P_19_2

Процедура с параметром

20

P_20_1

Замена символов в строке (заготовка)

P_20_2

Процедура замены символов в строке

22

P_22_1

Процедура обмена

23

P_23_1

Подсчет символов в строке

23

P_23_2

Замена символов в строке

24

P_24_1

Криптография (шифрование строки)

25

P_25_1

Распечатка текстового файла, версия 1

P_25_2

Распечатка текстового файла, версия 2

26

P_26_1

Запись в текстовый файл

P_26_2

Шифрование файла

27

P_27_1

Проверка наличия заданного файла

29

P_29_1

Полицейская база данных, версия 1

P_29_2

Полицейская база данных, версия 2

30

P_30_1

Обработка классного журнала (первый этап)

31

P_31_1

Обработка классного журнала (второй этап)

37

P_37_1

Вывод множества в текстовый файл

P_37_2

Ввод и вывод множеств

P_37_3

Задача о кружках, версия 1

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.

7. Брудно А. Л., Каплан Л. И. Олимпиады по программированию для школьников / Под ред. Б. И. Наумова /. – М.: Наука, 1985. 96 с.

8. Брудно А. П., Каплан Л. И. Московские олимпиады по программированию. – М.: Наука, 1990.

9. Вирт Н. Алгоритмы+структуры данных=Программы. – М.: Наука, 1989.

10. Дагене В. А., Григас Г. К., Аугутис К. Ф. 100 задач по программированию. – М.: Просвещение, 1993.

11. Долинский М. С. Решение сложных и олимпиадных задач по программированию: Учебное пособие. – СПб.: Питер, 2006. – 366 с

12. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. – М.: Наука, 1990.

13. Епанешников А., Епанешников В.. Программирование в среде Turbo Pasca 7.0. – М.: «Диалог-МИФИ», 1995.

14. Йодан Э. Структурное проектирование и конструирование программ. – М.: Мир, 1979.

15. Кирюхин В. М., Лапунов А. В., Окулов С.М. Задачи по информатике. Международные олимпиады 1989-1996. – М.: «ABF», 1996.

16. Кнут Д. Искусство программирования. Т. 1-3, Получисленные алгоритмы. Сортировка и поиск. – М.: Издательский дом «Вильямс», 2000.

17. Кормен Т., Лейзерстон Ч., Ривест Р. Алгоритмы: Построение и анализ. – М.: МЦНМО, 2001.

18. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978.

19. Лапунов А. В., Окулов С. М. Задачи международных олимпиад по информатике. – Киров, Изд-во ВятГПУ, 1993.

20. Меньшиков Ф. В. Олимпиадные задачи по программированию (+CD). – СПб.: Питер, 2006.

21. Овсянников А., Овсянникова Т., Марченко А., Прохоров Р. Избранные задачи олимпиад по информатике. – М.: Тровант, 1997.

22. Окулов С. М. Задачи кировских олимпиад по информатике. – Киров, Изд-во ВятГПУ, 1993.

23. Окулов С. М. Конспекты занятий по информатике (алгоритмы на графах): Учебное пособие. – Киров, Изд-во ВятГПУ, 1996.

24. Окулов С. М. Основы программирования. – М.: Лаборатория Базовых Знаний, 2001.

25. Окулов С. М., Пестов А. А. 100 задач по информатике. – Киров, Изд-во ВятГПУ, 2000.

26. Окулов С. М., Пестов А. А., Пестов О. А. Информатика в задачах. – Киров, Изд-во ВятГПУ, 1998.

27. Поляков Д.Б., Круглов И.Ю. Программирование в среде Тубо Паскаль (версия 5.5) – М.: Издательство МАИ 1992.

28. Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. – М.: Мир, 1989.

29. Седжвик Роберт. Фундаментальные алгоритмы на C++. Анализ. Структуры данных. Сортировка. Поиск. – Москва, С-Петербург, Киев: Диасофт, 2003.

30. Скиена С. С, Ревилла М. А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям Пер. с англ. – М: КУДИЦ-ОБРАЗ, 2005. – 416 с.

31. Ставровский А. Б. Турбо Паскаль 7.0: Учебник. – К.: Изд. группа BHV, 2000. 400 с.

32. Уэзерелл Ч. Этюды для программистов. – М.: Мир, 1982. 288 с.

33. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс: Учебное пособие – М.: КНОРУС, 2007, 576 с.

34. Фаронов В.В. Турбо Паскаль 7.0. Практика программирования. Учебное пособие – М.: КНОРУС, 2007, 416 с.

35. Федоров А. Borland Pascal: практическое использование Turbo Vision 2.0 – Киев: Диалектика 1993.

36. Федоров А. Особенности программирования на Borland Pascal – Киев: Диалектика 1994.

37. Шень А. Программирование: теоремы и задачи. – М.: МЦНМО, 1995.

38. Шпак Ю.А. Turbo Pascal 7.0 на примерах. – К.: «Юниор», 2003.