.

Н.М.Бадин, С.Г.Волченков, Н.Л.Дашниц, П.А.Корнилов
ЯРОСЛАВСКИЕ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ

АННОТАЦИЯ

Сборник содержит задачи, предлагавшиеся на Ярославских городских и областных школьных олимпиадах по информатике в 1990-1995 годах. Авторы - постоянные организаторы этих олимпиад.

Издание включает в себя около 90 задач теоретических и практических туров. Здесь есть как простые задачи, близкие к школьному курсу, так и довольно сложные, например, на тему параллельных вычислений или теоремы Холла. Широко представлены такие темы, как рекурсия, поиск, динамическое программирование, структуры данных, численные методы, геометрия, игры и другие. Задачи охватывают большой спектр различных стандартных и оригинальных алгоритмов. Большинство задач - результат творческой работы авторского коллектива. При составлении каждой задачи авторы хотели совместить элементы занимательности и серьезные идеи, стремясь привнести в информатику стиль блестящего популяризатора математики Мартина Гарднера.

Даются подробные решения и комментарии для задач теоретических туров. Многие из приводимых алгоритмов могут быть запрограммированы и использованы как в школе, так и на младших курсах университетов. Авторы надеются, что читатели данного сборника не только углубят свои познания в информатике, но и получат от решения задач большое удовольствие.

Авторы:

Волченков Сергей Геннадьевич - к.т.н., доцент кафедры прикладной информатики и архитектур ЭВМ Ярославского государственного университета (ЯрГУ);
Дашниц Наталья Леонидовна - преподаватель информатики школы N 76 г.Ярославля;
Корнилов Петр Анатольевич - к.ф.-м.н., заведующий кафедры информатики Ярославского государственного педагогического университета;
Бадин Николай Михайлович - доцент кафедры теоретической информатики ЯрГУ.

Сборник издан Ярославским областным институтом повышения квалификации педагогических и руководящих работников образования.

Объем: 79 стр. Цена экземпляра без почтовых расходов: 8 тыс.руб.

По вопросам покупки просьба обращаться:

тел: (0852) 219-424 (редакционно-издательский отдел ИПК)
(0852) 218-564 (региональный центр НИТ ИПК)
E-mail: badin@univ.uniyar.ac.ru
rcnit@bit-ipku.yaroslavl.su

ПРИМЕРЫ ОЛИМПИАДНЫХ ЗАДАНИЙ

28. Бензовоз (5 баллов)
Бензовоз должен доставить горючее из пункта А в пункт В, расстояние между которыми равно d миль. Запас горючего в пункте А равен V литров. Бензовоз расходует 1 литр на одну милю, а его бак вместе с цистерной вмещает 1000 литров.
Разработать алгоритм, который отвечает на вопрос, какое максимальное количество бензина можно перевезти из А в В, если:
а) промежуточных пунктов для хранения бензина между А и В нет (2 балла);
б) в пункте С на расстоянии х по пути от А до В стоит пустая цистерна, куда предварительно можно завезти некоторый запас бензи- на, а затем его использовать (3 балла).

56. Химия (8 баллов)
Задано N веществ и таблица их взаимодействий, т.е., а[i,j]=0, если i-ое вещество не взаимодействует с j-ым веществом и а[i,j]=k (1<=i,j,k<=N), если при их взаимодействии получается k-ое вещество.
В пробирку одно за другим засыпаются вещества. Оказавшись рядом, они могут вступить в реакцию. Вновь образованное вещество, возможно,реагирует с нижележащим и т.д. Известно, что реакция взаимодействия происходит мгновенно и только между двумя соседними слоями.
Описать алгоритм, определяющий по заданной последовательности, какие вещества останутся в пробирке.

87. Сапер (7 баллов)
На прямоугольном поле размером 2 на N в нижней строке случайным образом расставлено некоторое количество мин, не видимых игроку (саперу), а в верхней строке в каждой клетке написаны числа от 0 до 3, которые совпадают с количеством мин в полях нижней строки, соседних с этой клеткой. Игрок должен определить расположение мин.
а) Предложите алгоритм, который определяет все возможные положения мин (3 балла).
б) Какое максимальное количество решений возможно (1 балл)?
в) Каким условиям должны удовлетворять начальные данные, чтобы решение было неоднозначным (3 балла)?

СОДЕРЖАНИЕ СБОРНИКА 

          
         ОЛИМПИАДЫ 1990/91 уч.г.
  1. Записка Бормана
  2. Сортировка вагонов
  3. Вложенный цикл
  4. Корень
  5. Четырехугольник и точка
  6. Фрагмент программы
  7. Часы
  8. Игра
  9. Циклы
  10. Письмо
  11. Пересечение отрезков
  12. Скобки
  13. Игра "Даты"
  14. Алгорит  15. Последовательность
  16. Многочлен
  17. Игра "7"
  18. Имена
         ОЛИМПИАДЫ 1991/92 уч.г.
  19. Биллиард
  20. Роман
  21. Польский калькулятор
  22. Список
  23. Билеты
  24. Алгорит  25. Умножение "столбиком"
  26. Кроссворд
  27. Порядок
  28. Бензовоз
  29. Слово
  30. Цепь
  31. Польская запись
  32. Алгорит  33. Спички
  34. Числительные
  35. Степень двойки
  36. Цепочка
         ОЛИМПИАДЫ 1992/93 уч.г.
  37. Лидеры
  38. Циклы
  39. Фестиваль
  40. Программа
  41. Сумма квадратов
  42. Треугольник и точки
  43. Робот
  44. Миниму  45. Путь коня
  46. Алгорит  47. Таблица
  48. Маршрут
  49. Триангуляция
  50. Клавиатура
  51. Родственники
  52. Схема
  53. Родословная
  54. Параллельные вычисления
         ОЛИМПИАДЫ 1993/94 уч.г.
  55. Перестановки
  56. Химия
  57. Фибоначчи
  58. Вычисление
  59. Дни в месяце
  60. Признак делимости
  61. Кольцевая дорога
  62. Точки в круге
  63. Ребусы
  64. Лототрон
  65. Латинский квадрат
  66. Дешифровка
  67. Кулинария
  68. Алгорит  69. Джонсон & Джонсон
  70. Подстрока
  71. Игра
  72. Сумма простых
         ОЛИМПИАДЫ 1994/95 уч.г.
  73. Капитал
  74. Вирус
  75. Библиотека алгоритмов
  76. Альфа
  77. Сейф
  78. Алгоритм Маркова
  79. Арифметика по-русски
  80. Колесо
  81. ЧЕГОНАДО
  82. Список
  83. УХТЫ-01
  84. Лабиринт
  85. Дисперсия
  86. Алгорит  87. Сапер
  88. Уравнение по-польски
  89. Шахматы