Программирование в примерах и задачах

ПРОГРАММИРОВАНИЕ
в примерах и задачах

 

ИНФОРМАТИКА

Т. Ю. Грацианова

6-е издание, электронное 

Москва
Лаборатория знаний
2020

УДК 004.9
ББК 32.97
Г78

Грацианова Т. Ю.
Г78
Программирование в примерах и задачах / Т. Ю. Грацианова. — 6-е изд., электрон. — М. : Лаборатория знаний, 2020. — 373 с. — (ВМК МГУ — школе). — Систем.
требования:
Adobe
Reader
XI
;
экран 10". — Загл.
с титул. экрана. — Текст : электронный.
ISBN 978-5-00101-927-5
Пособие поможет подготовиться к экзамену по информатике, научиться решать задачи по программированию на языке
Паскаль.
Рассмотрено
большое
количество
программ;
листинги приведены в расчете на использование среды Турбо
Паскаль 7.0, однако в большинстве своем будут работать без
всяких изменений и в других версиях Паскаля. Некоторые
задачи имеют несколько вариантов решений, и в пособии
подробно разобрано, какое из них является наилучшим.
Для школьников 8–11 классов, учителей информатики
и методистов, а также студентов первых курсов технических
вузов.
УДК 004.9
ББК 32.97

Деривативное издание на основе печатного аналога: Программирование в примерах и задачах / Т. Ю. Грацианова. —
6-е изд. — М. : Лаборатория знаний, 2020. — 368 с. : ил. —
(ВМК МГУ — школе). — ISBN 978-5-00101-273-3.

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений,
установленных
техническими
средствами
защиты
авторских
прав,
правообладатель вправе требовать от нарушителя возмещения убытков
или выплаты компенсации

ISBN 978-5-00101-927-5
c○ Лаборатория знаний, 2015

Введение

Вы держите перед собой учебное пособие, которое поможет вам подготовиться к экзамену по информатике, научиться программировать, решать задачи на компьютере. В качестве языка программирования мы выбрали язык 
Паскаль. Этот язык создан специально для учебных целей, удобен в качестве первого изучаемого языка программирования, так как, с одной стороны, он не очень сложен, а с другой — на нем можно решать достаточно 
серьезные задачи.
Никаких специальных знаний для того, чтобы начать заниматься программированием, не требуется. Чтобы усвоить материал нашего пособия, 
достаточно уметь читать и немного — считать, поэтому можно начать занятия и в 11-м классе, и в 10-м, и даже раньше.
Главное место в учебном пособии занимают задачи с решениями. Даже 
необходимые теоретические сведения и определения подаются с помощью 
задач. Решая задачи, мы объясняем, зачем нужны новые конструкции языка, как их использовать, показываем способы разработки алгоритмов, приемы программирования. В тексте разобрано порядка полутора сотен задач, 
причем почти все решения снабжены подробными пояснениями и доведены 
до полной программы (ее можно «набить» на компьютере и выполнить — 
будет работать!).
Как «набить» программу? Для этого вам понадобится компьютер, умеющий работать с одной из версий языка Паскаль. В пособии подробно рассматривается, как работать в среде Borland Pascal 7.0 (Борланд Паскаль, 
Турбо Паскаль), — все приведенные программы писались и отлаживались 
именно в ней. Также вы найдете пояснения по работе со средами Free Паскаль и ABC-Паскаль. Приведенные в пособии программы, за некоторым 
исключением, будут без изменений правильно работать в любой среде, так 
как писались на стандартном Паскале. Все случаи, где применены какието особенности Турбо Паскаля, в тексте отмечены, и вы сможете работать 
с такой программой в своей версии языка (например, ABC-Паскаль), может 
быть, слегка изменив ее.
Конечно, подбирая задачи, мы учитывали, что большинству из вас наше 
пособие понадобится для подготовки к ЕГЭ. Однако здесь вы не найдете 
решений вариантов ЕГЭ разных лет (хотя, конечно же, все типовые задачи 
рассматриваются). Наша цель — не показать вам, как решаются задачи, 

Введение

которые когда-то были на экзаменах, а помочь научиться думать, составлять 
новые алгоритмы, писать программы и выполнять их на компьютере.
Немного о содержании учебника. Глава 1 знакомит с основными, базовыми понятиями программирования. Уже в ней мы разбираем достаточно 
сложные задачи, правда, пока на уровне блок-схем. В главах 2–12 мы изучаем основные конструкции языка Паскаль, учимся решать задачи. В принципе, изучив этот материал, можно решить любую задачу по программированию из предлагавшихся на ЕГЭ. В главах 13–14 содержится дополнительный материал, он поможет решать «обычные» задачи лучше и быстрее, 
а также пригодится тем, кто собирается участвовать (и побеждать!) в олимпиадах. А глава 15, можно сказать, развлекательная. Материал, который 
в ней рассматривается, обычно не входит ни в ЕГЭ, ни в школьную программу. Прочитав эту главу, вы сможете научить свой компьютер рисовать, 
сочинять музыку, сможете сами писать простенькие компьютерные игры, 
а заодно повторите все, чему научились ранее. В главе 16 приводятся примеры достаточно сложных задач, для решения которых понадобятся знания 
из разных глав учебника.
В учебнике много задач (около 600). Часть из них вы найдете после объяснения очередной темы. Многие из таких задач очень похожи на примеры, 
разобранные в тексте главы. Так что, если непонятно, как решать задачу, 
попробуйте перечитать материал еще раз, поищите аналогичную задачу. Конечно, есть и более сложные задачи, над которыми придется подумать. Они 
помечены звездочкой. В конце каждой главы вы найдете задачи по всему 
материалу, рассмотренному в главе; в этом случае не всегда удастся найти 
в главе аналог задачи, надо самостоятельно продумать метод решения.
Правильность решения практически всех задач очень легко проверить — 
в этом поможет компьютер. Введите текст программы, входные данные, запустите ее и сравните полученный ответ с правильным. Откуда взять правильный ответ? Подсчитать вручную! Не беспокойтесь, это просто, никаких 
сложных вычислений нигде делать не надо. Только не ленитесь проверять 
программы для разных наборов входных данных. К сожалению, программа 
может быть правильной, но неэффективной (например, слишком громоздкой), — здесь уже компьютер не поможет. Мы постараемся научить вас 
писать хорошие программы: некоторые задачи имеют несколько вариантов 
решений, и мы подробно разбираем, какой из них лучше.

Автору в работе над этой книгой большую помощь оказали преподаватели подготовительных курсов факультета Вычислительной математики и кибернетики (ВМК) МГУ имени М. В. Ломоносова Родин В. И., 
Вовк Е. Т., Линев Н. Б., Дорофеева И. Д., Лапонина О. Р.

Глава 1
Основные понятия и определения

Программирование

Решение многих задач, возникающих в самых различных сферах человеческой деятельности, было бы невозможно без применения компьютеров. 
Причем компьютеры — это не только вычислительные устройства с дисплеем, которые стоят в классе информатики или дома на столе. Они окружают 
нас повсюду: «притаились» в плеере, мобильном телефоне, фотоаппарате, 
в турникетах в метро и в школе, и даже в домашних бытовых приборах.
Для каких бы целей ни было предназначено устройство: полет ракеты 
на Марс, расчет зарплаты, выдача денег в банкомате, пропуск учеников 
в школу — надо «научить» его решать поставленную задачу, т. е. написать 
инструкции, детально разъясняющие, как действовать во всех возможных 
ситуациях. Деятельность по написанию таких инструкций (команд) для вычислительных машин или управляющих чем-либо устройств называется 
программированием, а сами инструкции — программами.

Этапы решения задачи

Предположим, что перед нами стоит задача, для решения которой необходимо написать программу. Решение задачи разбивается на этапы.

1. Постановка задачи. Необходимо определить, каковы будут исходные 
данные (что подается «на вход») и каких результатов надо достичь (что 
получить «на выходе»). При решении учебных задач этот этап иногда 
может отсутствовать, так как исходные данные и конечные результаты 
определены в формулировке задания.

2. Выбор метода решения и разработка алгоритма. Это один из основных, 
главных этапов решения задачи. От правильности выбора метода и эффективности алгоритма зависят размер программы и ее быстродействие.

3. Составление программы и ввод ее в память компьютера. Часто 
именно этот этап неправильно называют программированием. На самом 
деле, составление программы — лишь некоторая часть решения задачи 
с помощью компьютера. Сейчас этот процесс принято называть кодированием.

Глава 1. Основные понятия и определения

4. Отладка программы. Созданная программа может содержать ошибки, 
допущенные как в процессе кодирования, так и на любом из предыдущих этапов (может быть, неправильно разработан алгоритм, неверно выбраны исходные данные и т. д.). Ошибки выявляются в процессе отладки 
и тестирования — выполнения программы с заранее подготовленными 
наборами исходных данных, для которых известен результат.

5. Вычисление и обработка результатов.
Остановимся подробнее на главном этапе — разработке алгоритма.

Что такое алгоритм?

Алгоритм — это система правил, набор инструкций, позволяющий решить 
некоторую задачу, детально разработанное описание методов ее решения.
С алгоритмами мы сталкиваемся в математике (алгоритм сложения мно-
гозначных чисел в столбик), физике, химии, при изучении языков (правила 
правописания); они подстерегают нас и в повседневной жизни: алгоритм 
перехода улицы, правила пользования лифтом и др. Поваренная книга также является сборником алгоритмов для приготовления блюд.
Задание. Приведите еще примеры алгоритмов из математики, физики, 
химии, повседневной жизни.
Любой алгоритм рассчитан на то, что его инструкции будет кто-то выполнять. Назовем этого кого-то «исполнителем» и будем иметь в виду, что 
наши инструкции должны быть понятны ему, он должен уметь выполнять 
действия, записанные в алгоритме.
Существуют разные способы представления алгоритмов: с помощью 
формул, схем, рисунков, также можно записать алгоритм в виде программы 
и, конечно же, просто словами на обычном (естественном) языке.

Словесная формулировка алгоритма

Часто алгоритмы записываются в виде списка инструкций. Сформулируем 
таким образом алгоритм пользования лифтом.

1. Нажмите кнопку вызова.
2. Когда автоматические двери откроются, войдите в лифт.
3. Встаньте так, чтобы не мешать закрытию дверей.
4. Нажмите кнопку нужного этажа.
5. Когда лифт приедет на нужный этаж, дождитесь открывания дверей.
6. Выйдите из лифта.
В получившемся алгоритме все инструкции выполняются ровно один раз, 
последовательно друг за другом. Такие алгоритмы называются линейными.
Все ли учтено в нашем списке инструкций? Вдруг лифт сломался и никогда не придет к тому, кто его вызвал, — не указано, что делать в этом случае. А если лифт остановился между этажами? Все знают, что в этом случае 
нужно вызывать диспетчера. Включим эти инструкции в алгоритм.

Блок-схема. Основные конструкции 
7

Пункт 1 теперь будет выглядеть так.
1. Нажмите кнопку вызова. Если никакой реакции нет, значит, лифт сломан и вам придется идти пешком, если же все в порядке — выполняйте пункт 2.
А пункт 5 так:
5. Дождитесь остановки лифта. Если двери открылись, то выйдите из 
лифта, иначе нажмите кнопку вызова диспетчера и выполняйте его 
указания.
Отметим, что здесь мы использовали прием разработки алгоритмов, называемый «сверху вниз». При этом способе задача сначала разбивается на 
несколько подзадач, а потом некоторые из них, в свою очередь, могут быть 
разбиты на отдельные части.
Получившийся алгоритм уже не является линейным, в нем есть разветвления. В случае поломки лифта пункты 2–6 выполняться не будут, пункт 5 
на самом деле состоит из двух частей, и в каждом случае выполняется одна 
из них.

Блок-схема. Основные конструкции

Для алгоритма с разветвлениями словесная запись в виде перечня инструкций не всегда удобна, в этом случае часто применяется графическая запись 
алгоритма в виде блок-схемы: каждая инструкция помещается в блок (на 
чертеже — геометрическая фигура), блоки соединяются стрелочками, определяющими порядок выполнения инструкций. Этот способ представления 
алгоритмов достаточно популярен и общепринят, существует даже Государственный стандарт на изображение блок-схем. Мы не будем детально его 
изучать и слишком буквально ему следовать, используем некоторые конструкции, с помощью которых удобно графически представлять изучаемые 
нами алгоритмы.
Каждый алгоритм должен иметь начало (точка входа), для его обозначения 
будем использовать значок овал, а для обозначения конца (выхода) — значок 
овал с крестиком внутри. Каждый алгоритм имеет ровно один вход, а вот 
выходов может быть несколько (но никак не менее одного!), так как процесс 
решения задачи должен когда-то заканчиваться с некоторым результатом, 
причем в зависимости от условий результаты могут получаться разные.
Рассмотрим наиболее часто используемые типы блоков (рис. 1.1). Сразу 
заметим, что в любой из этих блоков должен быть хотя бы один вход.
Прямоугольник. В нем приводится описание некоторых действий, которые необходимо выполнить. Из прямоугольника всегда выходит только одна 
стрелочка (т. е. следующая инструкция всегда четко определена).
Параллелограмм. В нем записываются данные, которые необходимо 
ввести или вывести (исходные или выходные данные). Из параллелограмма 
выходит тоже только одна стрелочка.

Глава 1. Основные понятия и определения

Ромб. Используется для обозначения ветвления. В ромбе размещается 
вопрос (условие), на который возможен ответ «да» или «нет» (забегая вперед, скажем, что такая конструкция называется «логическое выражение»). 
Из ромба должны выходить две стрелочки. Одна помечается словом «да» 
(или «верно», «истинно»), другая — словом «нет» (или «неверно», «ложно»). В зависимости от значения истинности помещенного в ромбик условия далее выполняется переход по одной из стрелочек.

Рис. 1.1

Есть и некоторые другие блоки, о которых мы расскажем позже.
Изобразим алгоритм пользования лифтом в виде блок-схемы (рис. 1.2).

Рис. 1.2

Переменная. Присваивание 
9

Обратите внимание, в этой схеме мы не использовали блоки ввода и вывода. Так получилось потому, что это алгоритм не для компьютера, а «бытовой». В программах, которые мы будем писать для компьютера, обычно (но 
не обязательно) будет присутствовать ввод данных и обязательно — вывод 
результатов (если в результате выполнения программы ничего не будет выведено — как же понять, что она сделала).
Задание. Понятно, что наш алгоритм неполон. Например, лифт может 
остановиться, не доехав до нужного этажа, если его кто-то вызвал. Продолжите разработку данного алгоритма. Подумайте, какие инструкции 
нуждаются в уточнении.

Переменная. Присваивание

Составим алгоритм для решения следующей задачи. Человек приобрел огород треугольной формы. Какой длины забор ему понадобится, чтобы огородить свой участок?
Понятно, что надо измерить все стороны треугольника и найти его периметр, сложив полученные величины. Для записи формул в математике, 
физике обычно используют буквенные обозначения. Мы тоже ими воспользуемся, обозначив длины сторон треугольника a, b и c, а периметр — P. 
Блок-схема алгоритма изображена на рис. 1.3.

Рис. 1.3

Обозначенные буквами величины мы будем называть переменными. 
При разных начальных условиях (разных огородах) они будут принимать 
разные числовые значения, меняться.
Обратите внимание на запись формулы P := а + b + c. Здесь вместо 
принятого в математике знака «=» использован знак, состоящий из двух 
символов «:=». Будем называть его присваиванием.
В математике знак равенства используется в двух случаях: когда надо 
проверить, равна ли правая часть левой (например, «если x = 0, то…»), 

Глава 1. Основные понятия и определения

и в формулах, когда надо подсчитать значение правой части и положить
переменную в левой части равной этому значению (т. е. присвоить ей это 
значение). Чтобы избежать двойного толкования этого знака, будем в первом случае использовать знак равенства «=» и называть это действие сравнением, а во втором — знак присваивания «:=», а действие — присваиванием переменной нового значения.
Этот значок произошел от такой стрелочки: . В записи программ для 
первых компьютеров эта стрелочка показывала, что некоторое число пересылается в определенную ячейку, т. е. запись X5 обозначала инструкцию: 
«число 5 переслать (положить) в ячейку, предназначенную для X». Таким 
образом, в левой части операции присваивания всегда пишется переменная, 
которая должна получить новое значение, а в правой — само значение (оно 
может вычисляться, т. е. записываться в виде выражения).
С точки зрения компьютера переменная — это фрагмент оперативной памяти, в котором хранится значение. Компьютер обращается к этому 
участку памяти и записывает туда новое значение или считывает то, что там 
находится. Для наглядности память компьютера можно представить себе 
как большой шкаф с ящиками. Каждый ящик — это место для переменной. 
Для того чтобы можно было найти нужный ящик, наклеиваем на него табличку с именем. Теперь при необходимости туда можно положить значение 
или посмотреть, что лежит в ящике. И еще одна важная особенность: при 
обращении к переменной мы забираем из ящика не само значение, а его 
копию, т. е. само значение остается в ящике без изменения.
При выполнении действия P := а + b + c сначала вычисляется правая 
часть, затем результат вычисления помещается в ящик с именем (табличкой) Р. Это и есть операция присваивания переменной значения. Она всегда 
работает справа налево.
Получившийся алгоритм — линейный. Займемся теперь нелинейными 
алгоритмами.

Условие. Виды разветвлений

Простейшая задача с разветвлением, пожалуй, такая: из двух чисел выбрать 
наибольшее (договоримся, что, если числа равны, «наибольшим» будет любое из них). Блок-схема этого алгоритма представлена на рис. 1.4.

Рис. 1.4