Конспект лекций по дисциплине «алгоритмизация и программирование»

Литература

1. Седжвик Р. Фундаментальные алгоритмы на С++. Пер. с англ. – К.: Издательство «ДиаСофт», 2001. – 688 с.

2. Либерти Д., Джонс Б. Освой самостоятельно С++ за 21 день. Пер. с англ. – М.: Издательский дом «Вильямс», 2007. – 784.

3. Прата С. Язык программирования С++. Лекции и упраж. Platinum edition: пер. с англ./ Стивен Прата – М.: ООО «ДиаСофтЮП», 2005. – 1104 с.

4. Шеферд Дж. Программирование на Microsoft Visual C++.NET/ Пер с англ. – М.: Издательско-торговый дом «Русская редакция», 2003. – 928 с.

5. Ашарина И. В.Основы программирования на языках С и С++. – М.: Горячая линия – Телеком, 2002. – 207 с.

6. Глушаков С.В., Клевцов А.Л. Программирование в среде Delphi 7. – Харьков: Фолио, 2003. – 528 с.

7. Епанешников А., Епанешников В. Программирование в среде Turbo Pascal 7.0. – М.: «ДИАЛОГ-МИФИ», 1998. – 367 с.

8. В. Н. Пильщиков Сборник упражнений по языку Паскаль: Учеб. Пособие для ВУЗов. – М.: Наука. Гл. Ред. Физ.-мат. Лит., 1989. – 160 с.

9. Кнут Д. Искусство программирования для ЭВМ, т. 1, Основные алгоритмы. – М.: «Мир», 1976. – 730 с.

Лекция № 1. Основные понятия

Слово «алгоритм» произошло от имени арабского математика аль-Хорезми (полное имя – Abu Ja’far Mohammed ibn Musa al-Khowarizmi, означающего буквально «Отец Джафара, Магомет, сын Моисея, уроженец Ховаризма»). Аль-Хорезми родился около 825 года (в настоящее время Ховаризм – это небольшой узбекский город Хива). Этот математик написал знаменитую книгу «Kitab al jabr w’al-muqabala» («Правила восстановления и преобразования»). Заглавие этой книги дало начало другому слову – «алгебра», хотя сама книга в действительности была совсем не алгебраистической.

В средневековой Европе алгоритмом называлась десятичная позиционная система счисления и искусства счета в ней, поскольку именно благодаря латинскому переводу (12 век) трактата аль-Хорезми Европа познакомилась с позиционной системой. Один из ранних немецких математических словарей “Vollstandiges Mathematisches Lexikon” (Leipzig, 1747) дает следующее определение слова Algorithmus: «Под этим именем объединены понятия о четырех типах арифметических действий, а именно о сложении, умножении, вычитании и делении».

В настоящее время термин алгоритм используется в компьютерных науках для описания метода решения задачи, пригодного для реализации в виде компьютерной программы. Коротко это понятие можно определить так:

Алгоритм – это конечная последовательность действий, преобразующая исходные данные в результат.

Алгоритмы составляют основу компьютерных наук, они являются основными объектами изучения во многих, если не в большинстве ее областей. Одну и ту же задачу можно решить разными методами, используя различные алгоритмы. Предпочтение отдается тем из них, которые обеспечивают наименьшее время исполнения компьютерной программы. Существует наука, изучающая алгоритмы. Она называется «Теория алгоритмов» и является частью математики. Достижения этой науки используются для разработки эффективных алгоритмов. Созданием и развитием теории алгоритмов занимались европейские ученые: голландец Лейтзен Эгберт Ян Брауэр (1881-1966), немец Герман Вейль (1885-1955), англичанин Алан Матисон Тьюринг (1912-1954) американские – Алонзо Черч (родился в 1903), Эмиль Леон Пост (1897-1954) и Стивен Коул Клини (р. 1909), русские ученые Андрей Андреевич Марков (р. 1903) и Андрей Николаевич Колмогоров (р. 1903).

Пример 1.1. Рассмотрим следующий пример. Студент приходит домой, и там ему сообщают, что в его отсутствие его навещал один из друзей. У студента четверо друзей: блондинка Маша, брюнетка Юля, блондин Юра и брюнет Сережа. Чтобы узнать, кто из них приходил сегодня, нужно задать несколько вопросов. Например, такие: «Это была девушка?», «Каков цвет ее волос?». Вопросы можно задавать в соответствии с алгоритмом, изображенным на рис. 1.1.

Рис. 1.1. Алгоритм ведения беседы

Данная форма записи алгоритма является стандартной. Схема начинается и заканчивается рамками со скругленными углами, внутри которых написано: «Начало» и «Конец». При реализации алгоритма в виде компьютерной программы это означает начало и конец выполнения программы. Каждая представляющая практический интерес программа должна иметь начало и конец. Обычные операторы изображаются в виде прямоугольников, а операторы перехода по условию – в виде ромбов.

Приведенный алгоритм позволяет прояснить ситуацию после пары вопросов. До начала беседы студент пребывает в состоянии неопределенности. После ее окончания он обладает информацией, позволяющей ему точно установить личность навестившего друга (подруги). В теории алгоритмов используются также такие математические объекты как графы. Пример графа изображен на рис. 1.2.

Рис. 1.2. Граф, описывающий все возможные варианты хода беседы

Данный граф описывает все возможные варианты хода беседы. Он напоминает дерево, перевернутое вверх ногами. Такие графы и в самом деле называют деревьями. Графы и их свойства изучают в разделе математики, именуемой: «Дискретная математика». Как можно видеть, граф представляет собой совокупность линий, соединяющих между собой некоторые точки. Точки называются вершинами, а линии – ребрами. В данном случае вершины соответствуют состоянию информированности студента на разных этапах беседы, а ребра означают действия (вопросы).

Эволюция языков программирования имеет следующую историю. Вначале программисты работали с ограниченным набором примитивных команд, представлявших собой машинный язык. Эти команды состояли из длинных строк нулей и единиц. Вскоре был изобретен ассемблер, способный преобразовывать в машинные команды более понятные для человека инструкции (например, ADD (добавить) и MOV (переместить)).

Со временем были созданы такие языки высокого уровня, как BASIC и COBOL. Благодаря им появилась возможность программировать, используя логические конструкции из слов и предложений, например, Let I = 100. Эти инструкции переводились на машинный язык интерпретаторами и компиляторами.

Интерпретатор превращает инструкции программы в команды машинного кода последовательно, по мере чтения текста программы.

Компилятор преобразует исходный код программы в некоторую промежуточную форму – объектный файл. Этот этап называется компиляцией. Затем компилятор вызывает программу компоновки, которая превращает объектный файл в исполняемый файл программы.

С интерпретатором работать проще, поскольку команды программы выполняются в той последовательности, в какой они написаны. В некоторых языках (например, Visual Basic 6) роль интерпретатора выполняет динамическая библиотека. Интерпретатором языка Java является виртуальная машина (Virtual Machine, или VM).

В процессе компиляции возникают дополнительные этапы преобразования исходного кода (читаемого людьми) в объектный код (который читается машинами). Наличие дополнительного этапа создает определенные неудобства, но скомпилированные программы выполняются гораздо быстрее, поскольку трансляция исходного кода в машинный язык, отнимающая достаточно много времени, выполняется только один раз во время компиляции, и не производится во время выполнения программы.

Еще одно преимущество компилируемых языков программирования, таких, как С++, заключается в том, что программы, написанные на этих языках, могут выполняться на компьютерах, не обладающих соответствующим компилятором. При работе же с интерпретируемыми языками для выполнения готовой программы необходимо обязательно иметь соответствующую программу-интерпретатор.

Язык С++ – это типичный компилятор, хотя и для его кода существует несколько интерпретаторов.

До недавних пор программы рассматривались как последовательность процедур, выполнявших определенные действия над данными. Данные были отделены от процедур, и главным в программировании стало проследить, вызов какой функции осуществляется и какие данные при этом обрабатываются. Чтобы внести ясность в эту потенциально запутанную ситуацию, были разработаны принципы структурного программирования.

Основная идея структурного программирования заключается в следующем. Компьютерную программу можно представить в виде набора задач. Любая задача, которая слишком сложна для простого описания, должна быть разделена на несколько более мелких составных задач, и это деление необходимо продолжать до тех пор, пока задачи не станут достаточно простыми для понимания.

Структурное программирование до сих пор остается довольно успешным способом решения сложных проблем. Однако к концу 1980-х годов слишком очевидными стали некоторые его недостатки. К сожалению, структурное программирование отделяет структуры данных от функций, управляющих ими. Кроме того, в структурном программировании полностью отсутствуют встроенные способы связи данных с функциями. Программисты обнаружили, что возможность многократного использования стандартных блоков, повторяющихся во многих программах, вполне естественна. Однако функции, которые прекрасно работали с одним типом данных, зачастую не могли воспользоваться другими типами, что ограничивало их преимущества.

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

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

Язык С++ полностью поддерживает принципы объектного программирования. Когда назрела необходимость в переменах, Бьерн Страуструп (Bjarne Stroustrup) взял язык С, используемый для разработки коммерческих программных продуктов, и расширил его, обогатив средствами, необходимыми для объектно-ориентированного программирования.

С++ в настоящее время считается господствующим языком, используемым для разработки коммерческих программных продуктов. В последние годы это господство слегка поколебалось вследствие аналогичных претензий со стороны такого языка программирования, как Java, однако многие программисты, которые бросили С++ ради Java, в последнее время решили вернуться назад. В любом случае эти два языка настолько похожи, что, изучив один из них, можно автоматически освоить 90% другого.

Программы на языке С++ обычно создаются в ходе компоновки одного или нескольких объектных файлов (с расширением .obj или .o) с одной или несколькими библиотеками. Библиотекой называется набор компонуемых файлов, которые поставляются вместе с компилятором. Все компиляторы С++ укомплектованы библиотекой функций (или процедур) и классов, которые можно включить в программу. Чтобы создать исполняемый файл, необходимо выполнить следующие действия:

1. Создать файл исходного кода с расширением .cpp;

2. Скомпилировать исходный код в объектный файл с расширением .obj или .o;

3. Скомпоновать объектный файл со всеми необходимыми библиотеками, получив исполняемый файл с расширением .exe.

Традиционно в книгах по программированию первые примеры программ начинаются с вывода на экран слов “Hello World”. Мы не будем отступать от этой традиции. Ниже приведен листинг программы, написанной на языке программирования С++.

Листинг 1.1.

1: #include <iostream>

2:

3: int main()

4: {

5: std::cout << “Hello World!\n”;

6: char response;

7: std::cin >> response;

8: return 0;

9: }

В приведенном листинге слева расположены номера строк. Эти номера установлены только для ссылок на соответствующие строки кода в тексте лекций. В окне редактора их вводить не нужно. Строка 1 подключает к файлу программы внешнюю библиотеку iostream. Это осуществляется следующим образом. Первым стоит символ # (это символ фунта, читается как «паунд»), который является инструкцией для препроцессора. При каждом запуске компилятора запускается и препроцессор. Он читает исходный текст программы, находит строки, которые начинаются с символа фунта #, и обрабатывает их перед началом компиляции программы. Команда #include (подключить) это инструкция препроцессора, которая указывает, что «далее следует имя файла, который необходимо найти и подключить именно здесь». Угловые скобки, в которые заключено имя файла, означают, что этот файл нужно искать во всех папках, отведенных для хранения подобных файлов. Файл iostream (Input-Output-Stream – поток ввода-вывода) используется объектом cout, который обслуживает процесс вывода данных на экран.

Основной код программы начинается в строке 3 с вызова функции main(). Каждая программа на языке С++ содержит эту функцию. Функция – это блок кода программы, который выполняет одно или несколько действий. Обычно функцию вызывает другая функция или оператор, но функция main() – особая: она вызывается автоматически при запуске программы.

Функция main(), подобно всем остальным функциям, должна быть объявлена с указанием типа возвращаемого значения. В данной программе функция main() возвращает целое число (значение типа int от слова integer – целый). По окончании работы эта функция возвратит операционной системе число 0, как показано в строке 8. Возвращение значения в операционную систему не столь важно, и в общем-то это значение самой системой почти не используется, но стандарт языка С++ требует, чтобы функция main() была объявлена по всем правилам (как показано в листинге). Считается, что возврат значения 0 свидетельствует о нормальном завершении программы.

Все функции начинаются открывающей фигурной скобкой ({) и оканчиваются закрывающей фигурной скобкой (}). Фигурные скобки функции main() помещены в строках 4 и 9. Все что находится между этими скобками, считается телом функции.

Объект cout используется для вывода сообщений на экран (Console Output – вывод на консоль (экран)). Для ввода сообщений с клавиатуры используется объект cin (Console Input – ввод с консоли (клавиатуры)).

Объект cout содержится в стандартной библиотеке. Компилятору необходимо указать, что будет использован объект cout именно из стандартной библиотеки. Для этого и предназначена спецификация пространства имен std в сопровождении двух двоеточий.

За словом cout ставим оператор вывода (<<). Все, что следует за этим оператором, будет выводиться на экран. Если необходимо вывести на экран строку текста, то ее необходимо заключить в двойные кавычки (“), как показано в строке 5. Два заключительных символа текстовой строки (\n) означают, что после слов “Hello World!” необходимо перейти на новую строку.

Строки 6 и 7 необходимы для того, чтобы результат оставался на экране после выполнения программы. Это заставит программу приостановиться и ожидать ввода значения. Чтобы завершить выполнение программы, нужно ввести любой символ или число, а затем нажать клавишу <Enter>. Переменная типа char (сокращение слова character – читается как «кар») используется для хранения символов.

Чтобы приступить к созданию и отладке программы, необходимо выполнить следующие действия:

1. Запустить компилятор;

2. Выбрать в меню File (Файл) пункт New (Новый);

3. На вкладке Projects (Проекты) выберите тип Win32 Console Application (Консольное приложение для Win32), введите имя проекта, например, hello, и щелкните по кнопке OK;

4. В появившемся окне мастера нового проекта выберите переключатель An Empty Project (Пустой проект) и щелкните по кнопке Finish (Готово). В результате на экране появится диалоговое окно, отображающее информацию о новом проекте;

5. Чтобы вернуться к основному окну, щелкните по кнопке OK;

6. Выберите в меню File пункт New;

7. Во вкладке Files (Файлы) выберите пункт С++ Source File (Исходный файл С++) и введите его имя hello. Это имя уже было введено в текстовое поле File Name (Имя файла);

8. Чтобы вернуться к основному окну, щелкните по кнопке OK;

9. Введите текст программы;

10. Выберите в меню Build (Создать) пункт Build hello.exe (Создать hello.exe);

11. Убедитесь в отсутствии ошибок компиляции. Эта информация отображается в нижней части окна редактора кода;

12. Для запуска программы выберите в меню Build (Создать) пункт Execute hello.exe (Выполнить hello.exe) или нажмите комбинацию клавиш <Ctrl+F5>.

К сожалению, почти все программы содержат ошибки. Одни ошибки обнаружит компилятор, другие – компоновщик, а третьи проявятся только при запуске программы. Ошибки компиляции могут происходить по разным причинам. Обычно они являются результатом небрежного ввода исходного кода и других случайностей. Приличные компиляторы сообщат не только о том, что именно не в порядке, они укажут также точное место обнаружения ошибки. Наиболее совершенные компиляторы даже предложат вариант исправления.

Лекция № 2. ЭЛЕМЕНТЫ ЯЗЫКА С++