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

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

 

ИНФОРМАТИКА

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

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