Котов В.М., Волков И.А., Лапо А.И. Информатика. Методы алгоритмизации. 8-9 классы. - Минск, 2000. — 300 с.
Зачастую решение задачи по информатике протекает следующим образом: вы смотрите на постановку задачи и, используя приобретенные навыки и известные вам методы, выдаете решение. При этом обычно неявно считается, что «первый взгляд — наиболее верный», и если решение получено, то на этом «акт творения» программы завершен. Но насколько это «творение» является законченным и эффективным? Обычно при анализе такого решения оказывается, что первый взгляд может всего не увидеть, и что если после него еще чуть-чуть подумать, то результат получается намного лучше (что верно не только в информатике).
Учебное пособие предназначено для того, чтобы помочь вам выбрать эффективное решение для поставленной задачи и рассказать о стандартных подходах к решению задач по информатике.
Некоторые из рассматриваемых в пособии задач вам уже встречались в курсе математики. Иногда для этих задач предлагаются отличные от уже известных методы решения. Эти методы ориентированы в первую очередь на применение компьютера, позволяющего за небольшое время выполнить большие объемы вычислений.
Книга состоит из 5 глав, в которых приводятся сведения из таких областей математики, как геометрия, арифметика, комбинаторика и теория алгоритмов. Главы содержат теоретический материал, задачи для повторения, задачи повышенной сложности и задачи для самостоятельного решения.
Теоретический материал направлен на то, чтобы дать представление об общих подходах и наиболее распространенных и эффективных методах решения задач. Фрагменты алгоритмов приводятся на алгоритмическом языке, принятом в базовом курсе. Для задач повышенной сложности приводятся указания по их решению. В конце книги даны Приложения, содержащие алгоритмы на языке Паскаль. Теоретический материал, предназначенный для факультативных занятий, обозначен значком *.
СОДЕРЖАНИЕ
От авторов 3
Глава 1. Уравнение прямой
§ 1. Прямые и отрезки на плоскости 4
1.1. Формы записи уравнения прямой —
1.2. Положение точек относительно прямой 7
1.3. Взаимное расположение двух отрезков 9
1.4. Точка пересечения отрезков 12
§ 2. Расстояние на плоскости 13
2.1. Расстояние между точками. Расстояние от точки до прямой —
2.2. Расстояние между точкой и отрезком 15
§ 3. Многоугольники 16
3.1. Виды многоугольников —
3.2. Выпуклость многоугольников 17
§ 4. Площади фигур 19
4.1. Площадь треугольника —
4.2. Площадь прямоугольника 20
4.3. Площадь трапеции —
4.4. Площадь плоского многоугольника 21
§ 5. Взаимное расположение фигур на плоскости 23
5.1. Взаимное расположение многоугольника и точки . . —
5.2. Взаимное расположение многоугольников 26
Задачи для повторения 27
Задачи повышенной сложности ' ... 29
Задачи для самостоятельного решения 38
Указания к решению задач повышенной сложности ... 40
Глава 2. Поиск и сортировки ~
§ 1. Последовательный поиск необходимого элемента в массиве 66
§ 2. Поиск максимального и минимального элементов в массиве 70
§ 3. Упорядочение элементов массива 71
3.1. Сортировка выбором .72
3.2. Сортировка обменом 74
§ 4. Сокращение области поиска. Двоичный поиск 78
§ 5*. Другие виды сортировок . 81
5.1. Сортировка вставками —
5.2. Сортировка слияниями 83
Задачи для повторения 85
Задачи повышенной сложности 90
Задачи для самостоятельного решения 94
Указания к решению задач повышенной сложности ... 98
Глава 3. Алгоритмы целочисленной арифметики
§ 1. Поиск делителей числа. Простые числа 116
§ 2. Разложение числа на простые множители 122
§ 3. Поиск наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК) 125
3.1. Поиск НОД —
3.2. Поиск НОК 128
§ 4. Представление чисел. Выделение цифр числа 129
4.1. Преобразование числа из обычного представления в табличное 130
4.2. Преобразование табличного представления числа в обычное 132
§ 5. Перевод чисел из одной системы счисления в другую . . 134
§ 6. Делимость чисел 136
§ 7. Действия с многозначными (большими) числами .... 139
7.1. Сложение многозначных чисел —
7.2. Вычитание многозначных чисел 141
7.3*. Произведение многозначных чисел 142
Задачи для повторения 143
Задачи повышенной сложности 149
Задачи для самостоятельного решения 154
Указания к решению задач повышенной сложности . . . 159
Глава 4. Рекуррентные соотношения и динамическое программирование
§ 1. Понятие задачи и подзадачи 176
§ 2. Сведение задачи к подзадачам 178
§ 3. Понятие рекуррентного соотношения 179
§ 4. Правильные рекуррентные соотношения 182
§ 5. Способ организации таблиц 184
5.1. Организация одномерных таблиц 185
5.2. Организация двумерных таблиц 186
§ 6. Способ вычисления элементов таблицы 188
6.1. Вычисление элементов одномерной таблицы . . . . —
6.2. Вычисление элементов двумерной таблицы 190
6.3. Вычисление элементов двумерной таблицы с дополнительными ограничениями 192
