Основы программирования

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

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

С. М. Окулов

ОСНОВЫ
ПРОГРАММИРОВАНИЯ

Р А З В И Т И Е  И Н Т Е Л Л Е К Т А  Ш К О Л Ь Н И К О В

УДК 519.85(023)
ББК 22.18

О-52

С е р и я о с н о в а н а в 2008 г.
Окулов С. М.

О-52
Основы программирования / С. М. Окулов. — 10-е изд.,
электрон. — М.
:
Лаборатория
знаний,
2020. — 339 с. —
(Развитие интеллекта школьников). — Систем. требования:
Adobe Reader XI ; экран 10".— Загл. с титул. экрана. —
Текст : электронный.
ISBN 978-5-00101-759-2
В
книге
рассмотрены
фундаментальные
положения
программирования:
конечная
величина
и
конструируемые
на
ее
основе различные типы данных; управляющие конструкции —
элементарные составляющие любого алгоритма и основа управления
вычислительным
процессом;
структуризация
задач
как
основополагающий
механизм
их
реализации
на
компьютере;
упорядочение
(сортировка)
как
основа
эффективной
работы
с
любыми
данными
и,
наконец,
перебор
вариантов,
как
универсальная схема компьютерного решения задач.
Для
учащихся
старших
классов,
студентов
и
учителей
информатики.
УДК 519.85(023)
ББК 22.18

Деривативное издание на основе печатного аналога: Основы
программирования / С. М. Окулов. — 9-е изд. — М. : Лаборатория знаний, 2018. — 336 с. : ил. — (Развитие интеллекта школьников). — ISBN 978-5-00101-136-1.

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

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

2

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Часть I. Программирование в среде Паскаль . . . . . . . . . . . . 10

1.1. Основные управляющие конструкции. . . . . . . . . . . . . . . . . . 10

Занятие ¹ 1. Первая программа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Занятие ¹ 2. Целый тип данных. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Занятие ¹ 3. Команды редактора для работы с блоками,
работа с окнами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Занятие ¹ 4. Логический тип данных, операции сдвига . . . . . . . . . 29
Занятие ¹ 5. Составной оператор и оператор If – Then – Else . . . . . 34
Занятие ¹ 6. Оператор цикла For . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Занятие ¹ 7. Оператор цикла While. . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Занятие ¹ 8. Оператор цикла Repeat – Until . . . . . . . . . . . . . . . . . . . 52
Занятие ¹ 9. Вложенные циклы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

1.2. Процедуры и функции — элементы структуризации
программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

Занятие ¹ 10. Одномерные массивы. Работа с элементами . . . . . . . 69
Занятие ¹ 11. Процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Занятие ¹ 12. Функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
Занятие ¹ 13. Рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
Занятие ¹ 14. Символьный и строковый типы данных . . . . . . . . . 123
Занятие ¹ 15. Текстовые файлы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

1.3. Массив – фундаментальная структура данных . . . . . . . . . 158

Занятие ¹ 16. Методы работы с элементами одномерного
массива . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

Занятие ¹ 17. Двумерные массивы. Работа с элементами . . . . . . . 170
Занятие ¹ 18. Двумерные массивы. Вставка и удаление . . . . . . . . 185

1.4. Дополнительные занятия. . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

Занятие ¹ 19. Вещественный тип данных . . . . . . . . . . . . . . . . . . . . 196
Занятие ¹ 20. Множественный тип данных. . . . . . . . . . . . . . . . . . . 208
Занятие ¹ 21. Комбинированный тип данных (записи). . . . . . . . . 216

Содержание

Часть II. Фундаментальные алгоритмы . . . . . . . . . . . . . . . . 231

Занятие ¹ 22. Поиск данных. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
Занятие ¹ 23. Алгоритмы сортировки
с временной сложностью O(n2). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

Занятие ¹ 24. Алгоритмы быстрой сортировки данных . . . . . . . . 258
Занятие ¹ 25. Перебор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

Приложение. Этюд о программировании. . . . . . . . . . . . . . . 296

1. О понятии «программа», принципах работы программиста
и программировании . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296

2. Развитие технологий программирования. . . . . . . . . . . . . . . . 301

2.1. Операциональное программирование . . . . . . . . . . . . . . . . . . . . . 301
2.2. Нисходящее проектирование, структурное и модульное
программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303

3. Платформа Microsoft .Net Framework,
или от Pascal к C# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
3.1. Общие положения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
3.2. История развития . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
3.3. Сферы применения .Net Framework . . . . . . . . . . . . . . . . . . . . . . 331

Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334

4
Основы программирования

Данный учебник является переработанным вариантом книги
автора «Основы программирования», которая выходит в издательстве «БИНОМ. Лаборатория знаний» начиная с 2002 года
(пять изданий). Но даже не этот момент времени следует считать точкой отсчета. Приведем фрагмент предисловия к книге
«Основы программирования».
«Из истории возникновения учебника. В 1988 году перед автором возникла проблема: «чему учить в информатике и как
учить». Исходным «багажом» при принятии решения было образование в классическом университете по специальности «прикладная математика» и более чем 15-летний опыт разработки
программного обеспечения специализированных вычислительных комплексов в промышленности. Попытки обучения по существующим в то время учебникам, а их было не так много, как
в настоящее время, не принесли ни удовлетворения, ни результатов. Информатика воспринималась как обычный предмет.
Дидактические возможности компьютера не использовались в
полной мере. Может быть, причиной явилось отсутствие у автора соответствующего опыта и педагогического образования.
Ограничимся констатацией факта, оставим критику этого результата, так же как и обсуждение достоинств и недостатков существующих учебников, доброжелателям.
Тезисно обозначим исходные положения при принятии решения.
Первой посылкой было убеждение в том, что программирование является «стержнем информатики». В нем синтезировано
все, что десятилетиями нарабатывалось в Computer Science. Это
и результаты работы специалистов, работающих на «стыке» математики и информатики, это и достижения в вычислительной
технике, это и, наконец, огромный опыт формализации и решения сложнейших проблем в самом программировании, связанный с созданием больших программных комплексов.

Предисловие

Второй исходной посылкой является убеждение в том, что
занятия по информатике в корне должны отличаться от традиционных занятий по любому другому предмету. Во-первых, на
занятиях по информатике должна поощряться ошибка, ибо
только через ошибку можно прийти к результату, при изучении же любого другого предмета ошибка карается двойкой.
Во-вторых, постоянная обратная связь с обучаемым через компьютер, объективная и лишенная эмоций, — это инструментарий индивидуального и развивающего обучения. В-третьих,
стиль мышления у программистов свой, отличающийся от стиля мышления как математика, так и любого другого специалиста. Он настроен, если так можно выразиться, на борьбу с хаосом. Любая сложная программа — это миллионы и более
составляющих, движущихся и взаимодействующих. И в результате этого взаимодействия должен получаться определенный результат. Представим себе техническую систему такого
уровня сложности...
Итак, за основу обучения следует взять программирование,
с максимальным использованием компьютера на занятиях, и
при этом должен формироваться определенный стиль мышления. В таком ключе и шла вся последующая работа. Большое
влияние на нее оказала подготовка школьников к олимпиадам
по информатике. Синтезировались и обобщались все педагогические находки, которые затем находили применение в преподавании информатики и подтверждали обозначенные выше положения.
Основной методический принцип учебника — все познается через труд, через преодоление ошибок (собственных), через
процесс решения задач. Этот принцип определяет структуру
занятий. Вводная часть – обсуждение нового материала, эксперименты с заготовками решений задач, самостоятельное решение задач.
В идейном плане наиболее близкими к данному учебнику,
несмотря на кажущиеся принципиальные отличия, являются
учебники А. Г. Кушниренко и Г. В. Лебедева1. Эти учебники — наиболее цельные из существующих по идеям, заложенным в них, и, следовательно, по содержанию. Они имеют свое
«лицо» и идут к методике преподавания информатики от методики обучения математике. Единственное отличие, на наш

6
Предисловие

1
Ныне незаслуженно забытые.

взгляд, заключается в том, что при совпадении идейных установок мы в методике преподавания идем от компьютера, решая проблемы обучения через практическое программирование.
При
этом
компьютер,
система
программирования
являются не самоцелью обучения, а инструментом для реализации целей, хотя при этом познается и сам инструментарий».
И в 2010 году автор ничего не хочет изменять из написанного. Более того, в развитие данного подхода за прошедшие
годы, автор пытался ответить на вопрос, что является фундаментальным в информатике, какие понятия являются основополагающими. Если, например, в математике они известны —
число и форма, в физике, химии и других областях знания они
также определены, то что с информатикой? Этот вопрос — далеко не праздный. Ответ на него определяет многое, в частности судьбу школьного предмета информатики2. Точка зрения
автора в развернутом виде изложена в его монографии3, здесь
же тезисно обозначим основные положения, кратко изложив
один из ее параграфов.
Мы говорим о содержании курса информатики. Фундаментальных понятий должно быть немного, они должны пронизывать все содержание и на каждом витке содержания, образно
выражаясь, иметь свою «окраску», свой уровень сложности.
Перечислим эти понятия.
1. Величины, структуры данных (в первую очередь массив). Структуры данных и величины — это тот инструмент, с
помощью которого данные о проблеме оформляются таким образом, чтобы она могла быть воспринята и обработана компьютером.
2. Управление вычислительным процессом (управляющие
конструкции, рекурсия).
3.
Структуризация
проблем
(процедуры,
функции
—
инструмент реализации принципа «разделяй и властвуй», механизмов абстрагирования, декомпозиции и формализации).

Предисловие
7

2
Понятие «информатика» — достаточно объемное, включающее и кибернетику, и моделирование, и т. д. В данной книге мы, скорее всего, говорим о
Computer Science, об отрасли человеческого знания, охватывающей решения проблем с использованием компьютера, но называем ее, в силу сложившейся традиции отождествления понятий при переводе, информатикой.
3
Окулов С. М. Информатика: развитие интеллекта школьника. 2-е изд. – М.:
БИНОМ. Лаборатория знаний, 2008.

4. Отношение порядка (упорядоченности) на множестве
объектов определенной структуры.
5. Перебор вариантов в пространстве состояний задачи.
Итак, только пять, и выбор их не случаен. Коротко обоснуем его.
1. Структуризация данных. Фундаментальная основа любого управления есть данные (информация) и действия, совершаемые над данными (с информацией). При их структуризации очевидна аналогия со структурой ЭВМ (с ее процессором и
памятью, организованной по принципу массива).
2. Управляющие конструкции. Перечень управляющих
конструкций полный: любое алгоритмическое действие, вероятно, в любой области деятельности, может быть представлено
с использованием только следования, ветвления и повторения.
В классической работе4 показано, что этих конструкций достаточно для реализации любого алгоритма.
Структуры данных и управляющие конструкции позволяют в компактной форме записать большое количество действий
и обозначить большие объемы информации.
3. Структуризация задач. Нельзя объять необъятное. Человек при решении сложной проблемы всегда пытается выделить главное, расчленить ее на более простые. Такова природа
человеческого интеллекта. По данным когнитивных психологов, человек может следить не более чем за семью непрерывно
меняющимися во времени величинами, эффективно работать
не более чем с пятью–семью людьми. Инструментами этого
разъятия (разделения и властвования) являются процедуры и
функции. Причем этот процесс — нелинейный. Если на
каком-то этапе дальнейшее продвижение невозможно (из
разъятого не удается методами синтеза создать гармонию), то
человек возвращается в своих действиях назад и повторяет на
новом витке, в новом варианте последовательный анализ проблемы.
4. Отношение порядка (упорядоченности) на множестве
объектов определенной структуры. Множество ячеек оперативного запоминающего устройства упорядочено, множество
регистров процессора имеют свои имена, множество дорожек
магнитного диска упорядочено, множество электронных адре
8
Предисловие

4
Bohm C., Jacopini G. Flow Diagrams Turing Machines, and Languages with
Only Two Formulation Rules//Communicatins of the ASM. 1966. May.

сов в сети Интернет связано отношениями порядка и т. д. Это
один аспект — связь с нижним уровнем компьютера. С другой
стороны, упорядоченность воспринимается как что-то естественное и для человека, на что даже не стоит специально обращать внимание. Действительно, данное понятие формируется
на стадии конкретных операций (Ж. Пиаже), а это возраст от 7
до 11 лет.
Проблема упорядоченности неразрывно связана с другой
проблемой — поиска данных (информации). Упорядоченность
упрощенно можно трактовать как необходимое условие быстрого поиска. Проблема эта как была, так и остается одной из ключевых в информатике. Например, поиск общей подпоследовательности максимальной длины в двух текстах. Несмотря на
возросшую многократно производительность компьютера, исследованием методов нахождения данных за возможно меньшее
время по-прежнему занимаются ведущие ученые отрасли. Достижение, исследование упорядоченности на множестве объектов — очень непростая задача, даже на простых структурах данных. Фундаментальность понятия «упорядоченность» следует
из того, что всякое развитие есть, в определенной степени, увеличение упорядоченности в системе.
5. Перебор вариантов в пространстве состояний задачи.
В принципе универсальная, хотя далеко не всегда реально достижимая схема компьютерного решения задач. Особенность
компьютера заключается в том, что он действует только с упорядоченными структурами данных. Только там, где есть отношение порядка, функционируют циклические конструкции, и
т. д. — решаются переборные задачи. Только перечисляемое
подвластно компьютеру, а в этом и есть сущность перебора вариантов.
Именно эти фундаментальные для информатики понятия
и рассматриваются в данной книге. Двадцатипятилетний опыт
работы в образовательной
информатике
позволяет
утверждать, что школьник, своевременно их освоивший, может
стать (при его желании) успешным специалистом в Computer
Science.

Предисловие
9

1.1. Основные управляющие конструкции

Занятие ¹ 1. Первая программа

План занятия
1. Краткое знакомство со средой программирования.
2. Экспериментальный раздел занятия.
3. Выполнение самостоятельной работы.

Краткое знакомство со средой программирования
После загрузки системы программирования на экране появляются три окна (рис. 1.1):

File Edit ...
– окно 1 – главное меню

Line 1 Col 1 ...
– окно 2 – основное или рабочее окно

F1– Help ...
– окно 3 – окно помощи, в нем указано
назначение основных
функциональных клавиш

Рис. 1.1. Схематическое изображение структуры экрана

Переход из первого окна во второе и наоборот осуществляется нажатием клавиши F10.
В рабочем окне редактора среды программирования наберем текст первой программы — вычисления произведения
двух целых чисел:

Program My1_1;
Var a,b,rez: Integer;
Begin
WriteLn('Введите два числа через пробел');
ReadLn(a,b);

Часть I

Программирование
в среде Паскаль

rez:=a*b;
WriteLn('Их произведение равно ',rez);
WriteLn('Нажмите Enter');
ReadLn;
End.

Программа начинается с заголовка, имеющего следующий
вид:

Program
<имя программы>;

Имя нашей программы — My1_1. Заметим, что в имени
программы не должно быть пробелов, оно должно начинаться с
буквы, состоять только из латинских букв, цифр и некоторых
символов, не допускается использование символов точки и
запятой.
За заголовком идет раздел описаний, в котором должны
быть описаны все идентификаторы (константы, переменные,
типы, процедуры, функции, метки), которые будут использованы в программе. В данном случае из разделов описаний имеется лишь один — раздел переменных. Он начинается со служебного слова Var, после которого идет последовательность
объявления
переменных,
разделенных
точкой
с
запятой.
В каждом объявлении перечисляются через запятую имена переменных (идентификаторы) одного типа, после чего ставится
двоеточие и указывается тип переменных. В нашем примере
описаны три переменные: a, b и rez; все они имеют целый тип
(Integer), т. е. значениями переменных этого типа являются
целые числа.
Понятие переменной — центральное в любом языке программирования. Для описания переменной (величины, которая изменяется в процессе работы программы) следует указать
имя переменной, ее тип и значение. Соблюдается следующий
принцип: использовать переменную можно лишь тогда, когда
ей присвоено некоторое значение. Использование в выражениях неинициализированных переменных, то есть переменных,
значения которым не были присвоены явно, часто является
причиной ошибок.
После раздела описаний идет раздел операторов, который
начинается со служебного слова Begin и заканчивается служебным словом End. В этом разделе задаются действия над объектами программы, введенными в разделе описаний. Операторы в
этом разделе отделяются друг от друга точкой с запятой. После

1.1. Основные управляющие конструкции
11

последнего слова End ставится точка. После слова Begin ни точка, ни точка с запятой не ставятся.
Первый
встречающийся
оператор
—
это
WriteLn('текст'); — записать (вывести) на экран текст, заключенный между апострофами и взятый в скобки. Ln добавляется в
конце имени оператора для того, чтобы после вывода на экран текстов или результатов выполнения программы курсор автоматически переходил на следующую строку.
Следующий оператор — это ReadLn(a,b); — читать данные с клавиатуры. В данном случае необходимо ввести два целых числа через пробел, тогда переменной a присваивается
значение, равное первому введенному числу, а переменной b
присваивается значение, равное второму введенному числу.
Например, вы ввели числа 12 и 45, тогда a=12, а b=45. В конце
этого оператора также можно ставить Ln.
После этих двух операторов стоит оператор присвоения:
rez:=a*b; (:= — это знак оператора присвоения в языке Паскаль; * — это знак умножения). Значение выражения из правой части оператора присвоения заменяет текущее значение
переменной из левой части. Тип значения выражения должен
совпадать с типом переменной. При выполнении оператора пе
12
Часть I. Программирование в среде Паскаль

Рис. 1.2. Схема выполнения операторов ReadLn(a,b) и rez:=a*b