Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Конспект лекций по дисциплине
«ОСНОВЫ ПРОГРАММИРОВАНИЯ И АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ»
(Первый семестр)
Литература
Седжвик Р. Фундаментальные алгоритмы на С++. Пер. с англ. – К.: Издательство «ДиаСофт», 2001. – 688 с.
Либерти Д., Джонс Б. Освой самостоятельно С++ за 21 день. Пер. с англ. – М.: Издательский дом «Вильямс», 2007. – 784.
Прата С. Язык программирования С++. Лекции и упраж. Platinum edition: пер. с англ./ Стивен Прата – М.: ООО «ДиаСофтЮП», 2005. – 1104 с.
Шеферд Дж. Программирование на Microsoft Visual C++.NET/ Пер с англ. – М.: Издательско-торговый дом «Русская редакция», 2003. – 928 с.
Ашарина И. В.Основы программирования на языках С и С++. – М.: Горячая линия – Телеком, 2002. – 207 с.
Любош Бруга. Java по быстрому. Практический экспресс-курс. – СПб.: Наука и Техника, 2006. – 384 с.
Глушаков С.В., Клевцов А.Л. Программирование в среде Delphi 7. – Харьков: Фолио, 2003. – 528 с.
Епанешников А., Епанешников В. Программирование в среде Turbo Pascal 7.0. – М.: «ДИАЛОГ-МИФИ», 1998. – 367 с.
В. Н. Пильщиков Сборник упражнений по языку Паскаль: Учеб. Пособие для ВУЗов. – М.: Наука. Гл. Ред. Физ.-мат. Лит., 1989. – 160 с.
Кнут Д. Искусство программирования для ЭВМ, т. 1, Основные алгоритмы. – М.: «Мир», 1976. – 730 с.
Лекция № 1. ОСНОВНЫЕ ПОНЯТИЯ
Компьютер работает по программам, которые составляет для него человек. Человек пишет программы, пользуясь языками программирования. За последние несколько десятилетий языки программирования претерпели значительную эволюцию. Вначале программисты работали с ограниченным набором примитивных команд, представлявших собой машинный язык. Эти команды состояли из длинных строк нулей и единиц. Вскоре был изобретен ассемблер, способный преобразовывать в машинные команды более понятные для человека инструкции (например, ADD (добавить) и MOV (переместить)).
Со временем были созданы языки высокого уровня, такие как BASIC, FORTRAN, PASCAL или COBOL. Благодаря им появилась возможность программировать, используя логические конструкции из слов и предложений, например, “Let i = 100”. В языках высокого уровня одна команда соответствует целой подпрограмме, написанной на ассемблере.
Инструкции языка высокого уровня переводятся на машинный язык с помощью специальных программ: интерпретаторов и компиляторов.
Интерпретатор превращает инструкции программы в команды машинного кода последовательно, по мере чтения текста программы.
Компилятор преобразует исходный код программы в некоторую промежуточную форму – объектный файл. Этот этап называется компиляцией. Затем компилятор вызывает программу компоновки, которая превращает объектный файл в исполняемый файл программы.
С интерпретатором работать проще, поскольку команды программы выполняются в той последовательности, в какой они написаны. В некоторых языках (например, Visual Basic 6) роль интерпретатора выполняет динамическая библиотека. Интерпретатором языка Java является виртуальная машина (Virtual Machine, или VM).
В процессе компиляции возникают дополнительные этапы преобразования исходного кода (читаемого людьми) в объектный код (который читается машинами). Наличие дополнительного этапа создает определенные неудобства, но скомпилированные программы выполняются гораздо быстрее, поскольку трансляция исходного кода в машинный язык, отнимающая достаточно много времени, выполняется только один раз во время компиляции, и не производится во время выполнения программы.
Еще одно преимущество компилируемых языков программирования заключается в том, что программы, написанные на этих языках, могут выполняться на компьютерах, не обладающих соответствующим компилятором. При работе же с интерпретируемыми языками для выполнения готовой программы необходимо обязательно иметь соответствующую программу-интерпретатор.
Основная идея структурного программирования заключается в следующем. Компьютерную программу можно представить в виде набора задач. Любая задача, которая слишком сложна для простого описания, должна быть разделена на несколько более мелких составных задач, и это деление необходимо продолжать до тех пор, пока задачи не станут достаточно простыми для понимания. Таким образом, в соответствии с принципом структурного программирования сложная компьютерная программа делится на множество простых подпрограмм.
Преимуществом такого подхода является возможность многократного использования подпрограмм. Это приводит к удешевлению программирования, поскольку одну и ту же подпрограмму использует множество людей, и к повышению его качества, поскольку программы многократного использования, как правило, разрабатывают программисты высокого класса.
Структурное программирование до сих пор остается довольно успешным способом решения сложных проблем. Однако к концу 1980-х годов слишком очевидными стали некоторые его недостатки. К сожалению, структурное программирование отделяет структуры данных от функций, управляющих ими. Кроме того, в структурном программировании полностью отсутствуют встроенные способы связи данных с функциями. Программисты обнаружили, что возможность многократного использования стандартных блоков, повторяющихся во многих программах, вполне естественна. Однако функции, которые прекрасно работали с одним типом данных, зачастую не могли воспользоваться другими типами, что ограничивало их преимущества.
Вследствие этого была разработана новая концепция объектно-ориентированного программирования. Суть объектно-ориентированного программирования заключается в использовании «объектов», т.е. скорее образов, чем «данных». Объекты объединяются в классы, причем любой программист может создавать собственные классы. Например, можно создать класс «Животные», или «Механизмы», или «Средства передвижения». Каждый конкретнй класс имеет собственные функции (методы) и собственные переменные. Некоторые переменные (члены класса) могут быть защищены от прямого доступа из внешней программы.
Любая компьютерная программа выполняет какую-то конкретную задачу, в решении которой заинтересован человек. Для решения этой задачи задаются определенные исходные данные. Правильно написанная программа позволяет получить требуемый результат.
Алгоритмом называется конечная последовательность действий, преобразующая исходные данные в результат.
Другими словами, алгоритм – это метод получения результата.
Само слово «алгоритм» произошло от имени арабского математика аль-Хорезми (полное имя – 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. Граф, описывающий все возможные варианты хода беседы
Данный граф описывает изменения состояния информированности студента. Он напоминает дерево, перевернутое вверх ногами. Такие графы и в самом деле называют деревьями. Графы и их свойства изучают в разделе математики, именуемой: «Дискретная математика». Как можно видеть, граф представляет собой совокупность линий, соединяющих между собой некоторые точки. Точки называются вершинами, а линии – ребрами. В данном случае вершины соответствуют состоянию информированности студента на разных этапах беседы, а ребра означают действия (вопросы).
С++ в настоящее время считается господствующим языком, используемым для разработки коммерческих программных продуктов. В последние годы это господство слегка поколебалось вследствие аналогичных претензий со стороны такого языка программирования, как Java, однако многие программисты, которые бросили С++ ради Java, в последнее время решили вернуться назад. В любом случае эти два языка настолько похожи, что, изучив один из них, можно автоматически освоить 90% другого.
Как правило, язык С++ поставляется пользователям в виде компиляторов, хотя и для его кода существует несколько интерпретаторов. Он полностью поддерживает принципы объектного программирования. Когда назрела необходимость в переменах, Бьерн Страуструп (Bjarne Stroustrup) взял язык С, используемый для разработки коммерческих программных продуктов, и расширил его, обогатив средствами, необходимыми для объектно-ориентированного программирования.
Программы на языке С++ обычно создаются в ходе компоновки одного или нескольких объектных файлов (с расширением .obj или .o) с одной или несколькими библиотеками. Библиотекой называется набор компонуемых файлов, которые поставляются вместе с компилятором. Все компиляторы С++ укомплектованы библиотекой функций (или процедур) и классов, которые можно включить в программу. Чтобы создать исполняемый файл, необходимо выполнить следующие действия:
Традиционно в книгах по программированию первые примеры программ начинаются с вывода на экран слов “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 – читается как «кар») используется для хранения символов.
Чтобы приступить к созданию и отладке программы, необходимо выполнить следующие действия:
К сожалению, почти все программы содержат ошибки. Одни ошибки обнаружит компилятор, другие – компоновщик, а третьи проявятся только при запуске программы. Ошибки компиляции могут происходить по разным причинам. Обычно они являются результатом небрежного ввода исходного кода и других случайностей. Приличные компиляторы сообщат не только о том, что именно не в порядке, они укажут также точное место обнаружения ошибки. Наиболее совершенные компиляторы даже предложат вариант исправления.
Лекция № 2. ВВЕДЕНИЕ В СИНТАКСИС ЯЗЫКА С++
Если операторы cout и cin применяются очень часто, то использование идентификатора std:: перед ними становится обременительным. Эту проблему можно решить двумя способами. Первый заключается в том, что в начале текста кода можно сообщить компилятору об использовании объектов cout и cin (или любых других) только из стандартной библиотеки, как показано в листинге 2.1.
Листинг 2.1. Использование ключевого слова using
1: #include <iostream>
2: int main()
3: {
4: using std::cout; // Вместо этих двух строк можно записать
5: using std::endl; /* одну: using namespace std;*/
6:
7: cout << “Hello there.\n”;
8: cout << “Here is 5: ” << 5 << “\n”;
9: cout << “The manipulator endl “;
10: cout << “writes a new line to the screen.”;
11: cout << endl;
12: cout << “Here is a very big number: \t” << 70000;
13: cout << endl;
14: cout << “Here is the sum of 8 and 5: \t”;
15: cout << 8+5 <<endl;
16: cout << “Here is a fraction: \t”;
17: cout << (float) 5/8 << endl;
18: cout << “And a very very big number: \t”;
19: cout << (double) 7000*7000 << endl;
20: return 0;
21: }
РЕЗУЛЬТАТ
Hello there.
Here is 5: 5
The manipulator endl writes a new line to the screen.
Here is a very big number: 70000;
Here is the sum of 8 and 5: 13
Here is a fraction: 0.625
And a very very big number: 4.9е+07
Помимо стандартного объекта cout в данной программе используется стандартный оператор endl, который выводит на экран символ новой строки. В строке 12 (и в некоторых других) используется еще один символ форматирования – \t, который вставляет символ табуляции, используемый для выравнивания выводимой информации. Идентификатор float указывает объекту cout, что результат должен выводиться как вещественное (с плавающей точкой) число. Идентификатор double устанавливает вывод результата в экспоненциальном представлении.
Второй способ избежать необходимости писать каждый раз std:: перед стандартными операторами заключается в том, что вместо строки using std:: cout; используется определение пространства имен using namespace std.
Преимуществом формы записи using namespace std; является отсутствие необходимости указывать каждый используемый объект явно. Недостатком является риск непреднамеренного использования объектов из несоответствующей библиотеки. Ортодоксы предпочитают писать std:: перед каждым экземпляром cout и endl. Лентяи предпочитают использовать пространство имен (using namespace std;) и рисковать.
В строках 4 и 5 программы используются комментарии. Комментарии представляют собой текст, который игнорируется компилятором, но позволяет описать прямо в исходном коде назначение отдельной строки или целого блока.
В языке С++ используются два типа комментариев: с двойной наклонной чертой (//) и с сочетанием наклонной черты и звездочки (/*). Комментарий с двойной наклонной чертой (его называют комментарием в стиле С++) велит компилятору игнорировать все, что следует за этими символами, вплоть до конца текущей строки. Комментарий с двойной наклонной чертой и звездочкой (его называют комментарием в стиле С) велит компилятору игнорировать все, что следует за символами (/*), до того момента, пока не встретится символ завершения комментария: звездочки и наклонной черты (*/). Каждой открывающей паре символов /* должна соответствовать закрывающая пара символов */.
Большинство программистов используют в основном комментарий в стиле С++ (//), а комментарий в стиле С (/* */) применяют для временного отключения больших участков программы.
В комментариях, разъясняющих очевидные места, мало проку. Наоборот, они могут ввести в заблуждение, поскольку, изменив код, программист может забыть внести изменения в комментарий. Комментарий должен разъяснять не что это за операторы, а для чего они здесь используются.
В языке С++ все подпрограммы и сама главная программа называются функциями. Хотя main() и является функцией, но она нетипична. Функцию необходимо вызывать (или обращаться к ней) программно, в ходе выполнения кода. Функцию main() вызывает операционная система, и обратиться к ней из кода программы невозможно.
Программа выполняется по строкам в порядке их расположения в исходном коде до тех пор, пока не встретит вызов какой-нибудь функции. После выполнения функции управление возвращается той строке программы, которая следует за вызовом функции.
Функции возвращают либо некоторое реальное значение, либо значение типа void, т.е. не возвращают ничего. Функцию, которая складывает два целых числа и возвращает значение суммы, следует определить как возвращающую целочисленное значение. Функции, которая только выводит сообщение, возвращать нечего, возвращать нечего, поэтому для нее задается возвращаемый тип void.
Функции состоят из заголовка и тела. Заголовок содержит объявление типа возвращаемого значения, имени и параметров функции. Параметры позволяют передавать в функцию данные. Следовательно, если функция предназначена для сложения двух чисел, то их необходимо передать в функцию как параметры. Вот как будет выглядеть заголовок возвращающей целочисленное значение функции Sum(), которой передаются два целых числа (first и second):
Int Sum(int first, int second)
Параметр – это объявление типа данных, передаваемых функции. Реальное значение, передаваемое при вызове функции, называется аргументом. Некоторые программисты рассматривают эти понятия как синонимы. Другие считают смешение терминов признаком непрофессионализма.
Тело функции состоит из открывающейся фигурной скобки, любого количества операторов и закрывающейся фигурной скобки. Функция может возвращать значение в программу при помощи оператора return. Этот оператор также означает выход из функции. Если не поместить в функцию оператор return, то по завершении функция автоматически возвратит значение типа void. Значение, возвращаемое функцией, должно иметь тип, объявленный в заголовке функции. Если функция, как и положено, возвращает значение, но оператора return не содержит, то некоторые компиляторы передают предупреждение или сообщение об ошибке.
В листинге 2.2 приведена функция, которая получает два целочисленных параметра и возвращает целочисленное значение.
Листинг 2.2. Пример простой функции
#include <iostream>
int Add (int first, int second)
{
return (first+second);
}
void main() {
using std::cout;
using std::cin;
int a, b, c;
cout << “Enter two numbers: “;
cin >> a;
cin >> b;
c=Add(a, b);
cout << “c=“ << c;
char response;
cin >> response;
}
РЕЗУЛЬТАТ
Enter two numbers: 3 5
C=8
В последней программе мы использовали переменные a, b, c. В языке С++, как и в других языках, переменные используются для хранения информации. Переменная – это место в оперативной памяти компьютера, где можно размещать хранимое значение, а затем извлекать его (табл. 2.1).
Таблица 2.1.
|
Тип переменной |
Размер |
Значение |
|
bool |
1 байт |
True или false |
|
unsigned short int |
2 байта |
от 0 до 65 535 |
|
short int |
2 байта |
от -32 768 до 32 767 |
|
unsigned long int |
4 байта |
от 0 до 4 294 967 295 |
|
long int |
4 байта |
от -2 147 483 648 до 2 147 483 648 |
|
int (16 разрядов) |
2 байта |
от -32 768 до 32 767 |
|
int (32 разряда) |
4 байта |
от -2 147 483 648 до 2 147 483 648 |
|
unsigned int (16 разрядов) |
2 байта |
от 0 до 65 535 |
|
unsigned int (32 разряда) |
4 байта |
от 0 до 4 294 967 295 |
|
char |
1 байт |
256 значений символов |
|
float |
4 байта |
от 1.2е-38 до 3.4е38 |
|
double |
8 байтов |
от 2.2е-308 до 1.8е308 |
Чтобы определить переменную, необходимо указать тип, за которым (после одного или нескольких пробелов) должно следовать ее имя, завершающееся точкой с запятой. Для имени переменной можно использовать практически любую комбинацию букв, но оно не должно содержать пробелов, например: x, J23qrsnf и myAge. Следует подбирать осмысленные имена, позволяющие судить о назначении переменных, поскольку это облегчает понимание работы программы в целом.
Соблюдая культуру программирования, избегайте таких ужасных имен, как J23qrsnf, и ограничьте применение односимвольных имен (таких как x или i) лишь общепринятыми переменными, которые используются особенно часто. Старайтесь использовать осмысленные имена, например myAge (мой возраст). Впоследствии такие имена избавят от мучительных попыток вспомнить, что именно имелось в виду во время написания этой строки кода.
Язык С++ чувствителен к регистру букв, прописные и строчные буквы считаются разными. Переменные с именами age, Age и AGE рассматриваются как три различные переменные. Некоторые компиляторы позволяют отключать чувствительность к регистру букв. Лучше этого не делать, поскольку такая программа не сможет работать с другими компиляторами, а остальные программисты не смогут разобраться в ней.
Некоторые слова изначально зарезервированы в языке С++, и поэтому их нельзя использовать в качестве имен переменных. Такие слова называются ключевыми и используются компилятором для управления программой. В их число входят if, while, for, main и т.д.
Вполне допустимо создавать несколько переменных с помощью одного оператора, указав их тип и перечень имен, разделенных запятыми. Например:
unsigned int myAge, myWeight; //две переменные типа unsigned int.
Начинающим программистам иногда трудно решить, когда объявлять переменную типа long, а когда – типа short. Правило довольно простое: если существует хоть малейший шанс, что значение будет слишком большим для предполагаемого типа, то используйте тип с большим размером.
Переменные типа bool – это логические переменные (переменные булевой алгебры), которые могут иметь только два значения True (истина) или false (ложь). Переменные типа char – это символьные переменные (буквы). Char – это сокращение слова character (буква, символ), читается как «кар».
Подобно переменным, константы (постоянные) предназначены для хранения данных. Но, в отличие от переменных, константы нельзя изменить. Создаваемую константу необходимо сразу же инициализировать, поскольку присвоить ей значение позже не удастся. В языке С++ предусмотрены два типа констант: литеральные и символьные.
Литеральная константа – это значение, непосредственно вводимое в самой программе. Например, в выражении int myAge = 39; слово myAge является переменной типа int, а число 39 – литеральной константой. Константе 39 никакое иное значение присвоить нельзя.
Символьная константа – это константа, представленная именем (точно так же, как представлена любая переменная). Но, в отличие от переменной, значение инициализированной константы изменить нельзя.
В языке С++ существуют два способа объявления символьной константы: с использованием ключевого слова const и ныне уже устаревший, заключающийся в использовании директивы препроцесора #define. Например:
#define myAge 39;
const int myAge = 39;
Как можно видеть, в первом случае тип константы не определен. Поскольку препроцессор запускается перед компилятором, последний никогда не увидит константу, а будет видеть только число 39.
Перечисляемые константы позволяют создавать новые типы данных, а затем определять переменные этих типов, значения которых ограничены набором значений константы. Например, можно объявить константу COLOR как перечисляемую и определить для нее пять значений: RED, BLUE, GREEN, WHITE, BLACK.
Для создания перечисляемой константы используется ключевое слово enum, за которым следуют: название типа, открывающаяся фигурная скобка, список значений константы, разделенных запятыми, закрывающаяся фигурная скобка и точка с запятой. Например:
enum COLOR { RED, BLUE, GREEN, WHITE, BLACK };
Это выражение выполняет две задачи:
создается перечисляемая константа нового типа с именем COLOR;
определяются символьные константы: RED со значением 0, BLUE со значением 1, GREEN со значением 2 и т.д.
Каждому элементу перечисляемой константы соответствует определенное целочисленное значение. По умолчанию первый элемент имеет значение 0, а каждый последующий – на единицу больше. Любому элементу константы можно присвоить произвольное значение; в этом случае остальные элементы (значения которых не задавались явно) инициализируются значением, на единицу больше предыдущего. Предположим, что константа объявлена так:
enum COLOR { RED=100, BLUE, GREEN=500, WHITE, BLACK=700 };
Здесь значение RED будет равно 100, значение BLUE=101, значение GREEN=500, значение WHITE=501, значение BLACK=700.
Теперь можно определять переменные типа COLOR, каждой из них следует присвоить только одно из перечисленных значений (в данном случае – RED, BLUE, GREEN, WHITE, BLACK или 100, 101, 500, 501, 700).
Важно понимать, что перечисляемые переменные на самом деле имеют тип unsigned int и соответствуют целочисленным беззнаковым переменным. Но иногда при работе с цветами, днями недели или другими подобными наборами значений неплохо иметь возможность называть значения по имени.
Листинг 2.3. Использование перечисляемых констант
#include <iostream.h>
void main() {
enum Days { Sunday, Monday, Tuesday, Wednsday,
Thursday, Friday, Saturday };
Days today;
today = Monday;
if (today == Sunday || today == Saturday)
cout << “\nWeekends!\n”;
else
cout << “\nBack to work.\n”;
}
РЕЗУЛЬТАТ
Back to work.
Лекция № 3. ОПЕРАТОРЫ
В языке С++ операторы управляют последовательностью выполнения выражений, возвращают результаты вычислений или ничего не делают (пустые операторы). Операторы последовательного действия выполняют определенные действия над операндами – одно за другим, как показано на схеме рис. 3.1.
Рис. 3.1. Обозначение операторов последовательного действия на блок-схеме алгоритма программы
Все выражения языка С++ оканчиваются точкой с запятой. Пустые операторы представляют собой просто точку с запятой. Самый простой пример выражения – это операция присвоения значения:
x=a+b;
Здесь a и b – операнды, а x – результат операции. В отличие от алгебры, это выражение не означает, что x равняется a+b. Данное выражение следует понимать так: присвоим результат суммирования значений переменных a и b переменной x. Несмотря на то, что в этом выражении одновременно выполняются два действия (вычисление суммы и присвоение значения), после него устанавливается только один символ точки с запятой.
Оператор присвоения (=) присваивает результаты операций, выполняемых над операндами, расположенными справа от знака равенства, операнду, находящемуся слева от него.
Арифметические операторы. Существуют пять арифметических операторов: сложения (+), вычитания (-), умножения (*), целочисленного деления (/) и деления по модулю (%).
Вычитание беззнаковых чисел может преподнести сюрприз, если полученная разность окажется отрицательным числом.
Целочисленное деление несколько отличается от обычного. В случае целочисленного деления числа 21 на число 4 (21/4) в ответе получается 5. Чтобы получить остаток, число 21 необходимо разделить по модулю на 4 (21%4), в результате получим остаток 1.
Для получения дробного результата нужно использовать вещественные числа. Например, выражение 21.0/4.0 даст дробный ответ 5.25. Если делимое и делитель имеют вещественный тип, то результат также будет иметь вещественный тип. Но если результат присваивается целочисленной переменной, то значение будет усечено.
Очень часто в программах к переменным добавляется (или вычитается) единица. В языке С++ увеличение значения на единицу называется инкрементом, а уменьшение – декрементом. Для этих действий предусмотрены специальные операторы.
Оператор инкремента (++) увеличивает значение переменной на единицу, а оператор декремента (--) уменьшает его на единицу. Так, если переменную Counter необходимо увеличить на единицу, то можно использовать следующее выражение:
Counter++; // Увеличить значение Counter на единицу
Этот оператор эквивалентен подробному:
Counter= Counter+1;
Можно было бы подумать, что язык С++ получил свое имя после применения оператора приращения к имени языка его предшественника С. Так и есть: С++ является инкрементным приращением языка С.
Как оператор инкремента (++), так и оператор декремента (--) существуют в двух вариантах: префиксном и постфиксном. Префиксный вариант записывается перед именем переменной (++myAge), а постфиксный – после него (myAge++). В простом выражении вариант использования не имеет большого значения, но в сложном, при выполнении приращения одной переменной с последующим присвоением результата другой переменной, это весьма существенно.
Префиксный оператор вычисляется до присвоения, а постфиксный – после. Рассмотрим следующий пример. Предположим, что целочисленная переменная x имеет значение 5. Выражение int a = ++x; сообщает компилятору, что переменную x необходимо увеличить на единицу (сделав равной 6), а затем присвоить это значение переменной а. Следовательно, значение переменной а теперь равно 6 и значение переменной x тоже равно 6.
Если затем написать int b = x++, то компилятор получит команду сначала присвоить переменной b текущее значение переменной x (равное 6), а затем увеличить переменную x на единицу. В этом случае значение переменной b будет равно 6, а переменной x – 7.
В языке C++, как и в любом другом языке высокого уровня, используются математические функции. Декларации математических функций содержатся в файле <math.h>. При использовании таких функций мы должны добавить в начале программы строку: #include <math.h>. В табл. 3.1 приведены обозначения математических функций, принятые в языках C и C++. Аргументы математических функций имеют тип float или double. Аргументы тригонометрических функций задаются в радианах. Все математические функции возвращают результат типа double.
Таблица 3.1
|
№ |
Математическая функция |
Имя функции в языке C++ |
|
1 |
sqrt(x) |
|
|
2 |
fabs(x) |
|
|
3 |
exp(x) |
|
|
4 |
pow(x, y) |
|
|
5 |
log(x) |
|
|
6 |
log10(x) |
|
|
7 |
sin(x) |
|
|
8 |
cos(x) |
|
|
9 |
tan(x) |
|
|
10 |
asin(x) |
|
|
11 |
acos(x) |
|
|
12 |
atan(x) |
|
|
13 |
atan2(x,y) |
|
|
14 |
sinh(x) |
|
|
15 |
cosh(x) |
|
|
16 |
tanh(x) |
|
|
17 |
Остаток от деления на |
fmod(x,y) |
|
18 |
Наименьшее целое, которое |
ceil(x) |
|
19 |
Наибольшее целое, которое |
floor(x) |
В листинге 3.1 приведен пример использования функции fmod(x,y) для генерации псевдослучайных чисел.
Листинг 3.1. Генератор псевдослучайных чисел
#include <iostream.h>
#include <math.h>
void main(){
unsigned int a=81;
unsigned int b=9;
unsigned int c=65536;
unsigned int x;
unsigned int T[11];
cout<<"Input key: ";
cin>>T[0];
for (int i=0; i<10; i++)
{
x=a*T[i]+b;
T[i+1]=fmod(x, c);
cout<<T[i+1]<<"\n";
}
char ans;
cin>>ans;
}
Случайные числа генерируются с помощью следующего алгоритма:
,
где – предыдущее псевдослучайное число, – последующее псевдослучайное число, а коэффициенты a, b, c постоянны. Обычно c=, где – разрядность процессора, , а b – нечетное. В этом случае последовательность псевдослучайных чисел имеет период c.
Таблица 3.2
|
1 |
90 |
7299 |
1404 |
48197 |
37342 |
10055 |
28032 |
42377 |
24674 |
32523 |
|
10 |
819 |
812 |
245 |
19854 |
35319 |
42800 |
58937 |
55314 |
23995 |
43060 |
|
100 |
8109 |
1478 |
54191 |
64104 |
15089 |
42570 |
40307 |
53612 |
17205 |
17358 |
|
1000 |
15473 |
8138 |
3827 |
47852 |
9397 |
40270 |
50615 |
36592 |
14841 |
22482 |
|
10000 |
23577 |
9202 |
24475 |
16404 |
18013 |
17270 |
22623 |
63000 |
56737 |
8186 |
В данном случае принято: a=81, b=9, c=65536. Генерируемая последовательность чисел T[i] зависит от ключа T[0], который вводится пользователем. Результаты работы программы сведены в табл. 3.2.
Необходимо заметить, что в программе из листинга 3.1 можно было бы обойтись и без файла <math.h>, если вместо функции fmod(x,y) использовать арифметический оператор деления по модулю (%). Тогда вместо строки
T[i+1]=fmod(x, c);
мы должны были бы записать
T[i+1]=x%c;
Впрочем, если вам потребуются использовать в программе случайные числа, то для этого не обязательно писать собственные функции. Можно воспользоваться библиотечной функцией rand() из библиотеки <iostream>. Пример использования такой функции приведен в листинге 3.2. Данная программа выводит на экран действительные положительные числа, заключенные между нулем и единицей.
Листинг 3.2. Использование библиотечной функции rand() для генерации псевдослучайных чисел
#include <iostream>
void main() {
using namespace std;
for (int i=0; i<10; i++)
cout<<(rand()/32768.0)<<endl;
}
РЕЗУЛЬТАТ
Если запустить эту программу несколько раз, то получится один и тот же результат. Значит, мы снова имеем дело с псевдослучайными, а не с истинно случайными, числами.
Логический оператор AND (И) оценивает два операнда, и если оба они истинны (true), то результатом оператора AND также будет true. Оператор AND в тексте программы обозначается как: «&&». Пример:
if ((x==5)&&(y==5))
Это логическое выражение возвратит значение true, если обе переменные (x и y) равны 5, и значение false, если хотя бы одна из них не равна 5.
Логический оператор OR (ИЛИ) также оценивает два операнда. Если хотя бы один из них имеет значение true, то результатом этого оператора также будет true. Оператор OR в тексте программы обозначается как: «||».
Пример:
if ((x==5) || (y==5))
Это логическое выражение возвратит значение true, если значение либо переменной x, либо переменной y, либо оба они равны 5.
Логический оператор NOT (НЕ) оценивает только один операнд. Результат оператора NOT противоположен значение операнда. Оператор NOT в тексте программы обозначается как восклицательный знак: «!», например:
if (!(x==5))
Это логическое выражение возвратит значение true только в том случае, если x не равно 5. Это же выражение можно записать и по-другому
if (x!=5)
Существует шесть операторов отношения, они представлены в табл. 3.3.
Таблица 3.3
|
Имя |
Оператор |
Пример |
Значение |
|
Равно |
== |
100 == 50; 50 == 50; |
False True |
|
Не равно |
!= |
100 != 50; 50 != 50; |
True False |
|
Больше |
> |
100 > 50; 50 > 50; |
True False |
|
Больше или равно |
>= |
100 >= 50; 50 >= 50; |
True True |
|
Меньше |
< |
100 < 50; 50 < 50; |
False False |
|
Меньше или равно |
<= |
100 <= 50; 50 <= 50; |
False True |
Условный оператор if. Этот оператор позволяет проверить условие (например, равны ли две переменные) и в зависимости от результата выполнить тот или иной участок кода. На блок-схеме алгоритма программы этот оператор обозначается следующим образом
Рис. 3.2. Обозначение условного оператора if на блок-схеме алгоритма программы
Простейшая форма оператора if имеет вид:
if (выражение)
оператор;
Выражение в круглых скобках может быть любым, но обычно оно содержит операторы отношения. Если это выражение возвращает значение false, то последующий оператор опускается. Если же оно возвращает значение true, то оператор выполняется.
Блок операторов, заключенных в фигурные скобки, эквивалентен единому оператору. Поэтому условный оператор можно использовать также следующим образом:
if (выражение)
{
оператор 1;
оператор 2;
оператор 3;
}
Довольно часто в программах требуется, чтобы при выполнении условия (т.е. когда оно возвратит значение true) программа выполняла один блок кода, а при его невыполнении (т.е. когда условие возвратит значение false) – другой. В этом случае используется ключевое слово else, как показано в примере.
if (выражение)
оператор;
else
оператор;
Вместо оператора if можно использовать так называемый троичный условный оператор ? : Это единственный оператор в языке С++, который работает сразу с тремя операндами. Он записывается в следующей форме
(выражение 1) ? (выражение 2) : (выражение 3)
Эту строку можно прочитать так: «Если выражение 1 истинно, возвратить значение выражения 2, в противном случае возвратить значение выражения 3». Как правило, это значение присваивается переменной. Например, строка программного кода
z=(x>y) ? x : y;
эквивалентна следующему выражению
if (x>y)
z=x;
else
z=y;
однако она гораздо короче.
Оператор switch. В некоторых ситуациях применение оператора if может привести к возникновению очень сложных конструкций с большим количеством вложенных операторов. Язык С++ располагает альтернативным решением этой проблемы – оператором switch. Этот оператор имеет следующий синтаксис:
switch (выражение)
{
case значение Один: оператор;
break;
case значение Два: оператор;
break;
……………………
case значение N: оператор;
break;
default: оператор;
}
Выражение в скобках оператора switch представляет собой любое допустимое выражение языка С++, а оператор – это любой допустимый оператор или блок операторов. Выражение возвращает (или может быть однозначно преобразовано в) целочисленное значение. Поэтому использование логических операций или выражений сравнения здесь недопустимо.
Переход осуществляется к той строке оператора switch, где после ключевого слова case находится значение, соответствующее результату выражения. С этой строки выполнение операторов продолжается до тех пор, пока оператор switch не завершится, либо пока не встретится оператор break. Если ни одно значение case не соответствует результату выражения, выполняются операторы, следующие за ключевым словом default, а в случае его отсутствия оператор switch завершается.
Использование в операторах switch строки default считается хорошим стилем программирования. Даже если видимой необходимости в строке default нет, то в ней можно разместить обработчик непредвиденной ситуации, а также сообщение о ее возникновении. Это окажет неоценимую помощь при отладке. Следует заметить, что если оператор break в конце оператора case отсутствует, то выполнение переходит к следующему оператору case. Иногда это необходимо, но, как правило, приводит к ошибкам. Если такой прием решено применить, то стоит описать его в комментарии, чтобы впоследствии это не воспринималось как случайная ошибка. Пример использования оператора switch приведен в листинге 3.3.
Листинг 3.3. Пример использования оператора switch
1: #include <iostream>
2: int main()
3: {
4: using namespace std;
5: unsigned short int number;
6: cout << “Enter a number between 1 and 5: “;
7: cin >> number;
8: switch (number)
9: {
10: case 0: cout << “Too small, sorry!”;
11: break;
12: case 5: cout << “Good job! “ << endl; // далее
13: case 4: cout << “Nice Pick! “ << endl; // далее
14: case 3: cout << “Excellent! “ << endl; // далее
15: case 2: cout << “Masterful! “ << endl; // далее
16: case 1: cout << “Incredible! “ << endl;
17: break;
18: default: cout << “Too large! ” << endl;
19: break;
20: }
21: cout << endl << endl;
22: return 0;
23: }
РЕЗУЛЬТАТ
Enter a number between 1 and 5: 3
Excellent!
Masterful!
Incredible!
Enter a number between 1 and 5: 8
Too large!
Лекция № 4. ЦИКЛЫ
Для решения ряда задач требуется многократное повторение одних и тех же действий. На практике это реализуется либо с помощью рекурсии, либо с помощью итерации. Итерация – это повторение одних и тех же действий определенное количество раз. Основным методом итерации является цикл. На заре компьютерной эры программы были простыми и короткими. Циклы состояли из метки, нескольких команд и оператора безусловного перехода.
В С++ метка представляет собой имя, за которым следует двоеточие (:). Метка размещается слева от того оператора С++, к которому будет выполнен переход по оператору goto с соответствующим именем метки.
Листинг 4.1. Цикл на основе оператора goto
1: #include <iostream>
2: int main()
3: {
4: using namespace std;
5: int counter=0; // инициализировать счетчик
6: loop: //метка – начало цикла
7: counter ++; //инкрементируем счетчик
8: cout << “counter: “ << counter << “\n”;
9: if (counter < 5) //проверка значения
10: goto loop; //перейти к началу
11:
12: cout << “Complete. Counter: ” << counter << “.\n”;
13: return 0;
14: }
РЕЗУЛЬТАТ
counter: 1
counter: 2
counter: 3
counter: 4
counter: 5
Complete. Counter: 5.
Как правило, программисты избегают оператора goto, и на то есть причины. Оператор goto позволяет перейти в любую точку программы – как вперед, так и назад. Беспорядочное использование операторов goto приводит к сознанию запутанного, трудно читаемого кода, прозванного «спагетти». Чтобы избежать оператора goto, используют более сложные, управляемые операторы цикла: for, while, do..while.
Оператор while создает в программе цикл, который будет повторять последовательность операторов до тех пор, пока условие в начале цикла остается истинным.
Рис. 4.1. Обозначение цикла while на блок-схеме алгоритма программы
Листинг 4.2. Цикл на основе оператора while
1: #include <iostream>
2: int main()
3: {
4: using namespace std;
5: int counter=0; // присвоить начальное значение
6: while (counter < 5) //проверка истинности условия
7: {
8: counter ++; //инкрементируем счетчик
9: cout << “counter: “ << counter << “\n”;
10: }
11: cout << “Complete. Counter: ” << counter << “.\n”;
12: return 0;
13: }
РЕЗУЛЬТАТ
counter: 1
counter: 2
counter: 3
counter: 4
counter: 5
Complete. Counter: 5.
Следует заметить, что заключать в фигурные скобки выполняемый в цикле блок кода имеет смысл всегда, даже когда это только одна строка кода. Такая привычка позволит избежать весьма распространенной ошибки, когда в конце оператора цикла оказывается символ точки с запятой, приводящий к возникновению бесконечного цикла.
Иногда необходимо перейти к началу цикла еще до завершения выполнения всех операторов тела цикла. Для этого используется оператор continue. Однако в ряде случаев требуется выйти из цикла еще до проверки условия продолжения цикла. Для этого используется оператор break.
Операторы continue и break следует использовать осторожно. Это наиболее опасные команды после оператора goto. Программы, которые внезапно меняют свое поведение, тяжело понять, а свободное применение операторов continue и break способно запутать даже маленький цикл while и сделать его непонятным. Необходимость в операторе безусловного выхода из цикла зачастую свидетельствует о плохо продуманной логике условия выхода из цикла. Как правило, внутри тела цикла можно использовать оператор if, чтобы пропустить несколько строк кода, а не прибегать к оператору break.
Рис. 4.2. Обозначение цикла do..while на блок-схеме алгоритма программы
Вполне возможен вариант, когда тело цикла while вовсе не будет выполнено. Оператор цикла while проверяет выражение условия цикла до того, как приступит к выполнению операторов тела цикла, и если условие ложно с самого начала, то тело цикла будет пропущено.
Цикл do..while сначала выполняет тело цикла, а условие продолжения проверяет потом. Это гарантирует выполнение операторов цикла, по крайней мере, один раз. Оператор do..while имеет следующий синтаксис:
do
оператор;
while (условие);
Пример:
// считать до 10
int x=0;
do
cout << “x: “ <<x++;
while (x<10);
Рис. 4.3. Обозначение цикла c заданным числом повторений
Синтаксис этого оператора следующий:
for (инициализация; условие; приращение)
оператор;
Оператор инициализация устанавливает начальное значение счетчика. Следующий оператор: условие – это любое выражение языка С++, результат которого проверяется на каждом цикле. Если результат этого выражения является истинным, то выполняется тело цикла, а затем, после изменения счетчика на величину приращения (по умолчанию – увеличение на единицу), действия повторяются.
Пример:
// вывести Hello десять раз
for (int i=0; i<10; i++)
cout << “Hello! “;
Цикл, организованный в теле другого цикла, называется вложенным. В этом случае внутренний цикл полностью выполняется на каждой итерации внешнего. Листинг 4.3 демонстрирует заполнение элементов матрицы случайными числами с помощью вложенного цикла for.
Листинг 4.3. Вложенный цикл for
#include <iostream>
#define rnd (rand()/32768.0) /* директива #define задает переменную rnd, которая изменяется случайным образом в диапазоне от 0 до 1 */
int main (){
using namespace std;
int i, j, n, m;
float a[50][50];
cout<<"Input n: ";
cin>>n;
cout<<"Input m: ";
cin>>m;
cout<<endl;
cout<<"Random Array \n";
for (i=0; i<n; i++){
cout<<endl;
for (j=0; j<m; j++){
a[i][j]=rnd*10-5;
cout<<a[i][j]<<" \t";
}
}
char response;
cin>>response;
return 0;
}
Лекция № 5. МАССИВЫ
Массив (array) – это набор элементов, способных хранить данные одного типа. Каждый элемент хранения называется элементом массива. Объявляя массив, необходимо сначала указать тип хранимых данных, а затем имя массива и его размер. Размером массива называется количество его элементов, указываемое в квадратных скобках.
Пример 5.1. long LongArray[25];
В примере 5.1. объявлен массив с именем LongArray из 25-ти элементов типа long. Поскольку каждой переменной типа long необходимы четыре байта, весь объявленный набор займет непрерывную область памяти размером 100 байт.
К каждому из элементов можно обратиться по его номеру, расположенному в квадратных скобках после имени массива. Номера элементов массива начинаются с нуля. Следовательно, первым элементом массива LongArray будет LongArray[0], вторым – LongArray[1], последним – LongArray[24].
При записи значения в элемент массива компилятор вычисляет необходимую область памяти на основании размера типа элемента и размера массива. Если необходимо записать значение в переменную LongArray[5], являющуюся шестым элементом массива, компилятор умножает индекс 5 на размер переменной (в данном случае 4 байта). Затем текущий указатель смещается на 20 байтов от начального адреса массива, и записывается новое значение.
Если попробовать записать значение в элемент LongArray[50], то компилятор, проигнорировав тот факт, что такого элемента не существует, вычислит смещение от начала массива (200 байт), а затем запишет значение по этому адресу. Здесь могут оказаться другие данные, и запись нового значения может иметь непредсказуемые последствия.
Небольшой массив переменных встроенных типов можно инициализировать при объявлении. Для этого после имени массива помещают знак равенства и заключенный в фигурные скобки список значений, отделяемых запятой. Например:
int IntegerArray[5] = {10, 20, 30, 40, 50};
Если размер массива не указан, но список значений присутствует, то будет создан и инициализирован массив достаточного размера, чтобы содержать все перечисленные значения. Таким образом, эта строка аналогична предыдущей:
int IntegerArray[ ] = {10, 20, 30, 40, 50};
Нельзя инициализировать количество элементов, превосходящее объявленный размер массива:
int IntegerArray[5] = {10, 20, 30, 40, 50, 60};
Такая строка приведет к ошибке во время компиляции, поскольку объявлен массив для пяти элементов, а инициализировать пытались шесть. Но следующая запись вполне допустима:
int IntegerArray[5] = {10, 20};
В данном случае объявлен массив из пяти элементов, а инициализированы только два: IntegerArray[0] и IntegerArray[1].
Массивы могут иметь любые имена, допустимые для переменных. Имена массивов и переменных не могут совпадать в пределах одной области видимости. При объявлении количества элементов можно использовать не только константу, но и перечисление. Такой подход облегчает контроль над количеством элементов всех массивов, позволяя указать их размеры в едином месте.
Листинг 5.1. Задание размера массива с помощью перечислений
#include <iostream>
int main(){
enum WeekDays {Sun, Mon, Tue, Wed, Thu, Fri, Sat, DaysInWeek};
int ArrayWeek[DaysInWeek]={10, 20, 30, 40, 50, 60, 70};
std::cout<<"The value at Tuesday is: "<<ArrayWeek[Tue]<<" \n";
std::cout<<"The value at Friday is: "<<ArrayWeek[Fri]<<" \n";
char resp;
std::cin>>resp;
return 0;
}
РЕЗУЛЬТАТ
The value at Tuesday is: 30
The value at Friday is: 60
Можно создать массив более одной размерности. Каждая размерность представляет собой дополнительный индекс массива. Следовательно, двумерный массив имеет два индекса, трехмерный – три и т.д. Массив может иметь любое количество размерностей, но в большинстве случаев достаточно одной или двух.
Многомерный массив можно инициализировать тем же способом, что и одномерный, например
int theArray[5][3] =
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
Чтобы было понятнее, значения при инициализации можно разделить фигурными скобками:
int theArray[5] [3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
{10, 11, 12},
{13, 14, 15} };
Компилятор проигнорирует внутренние фигурные скобки, но они сделают набор чисел нагляднее.
Строка в стиле С++ представляет собой массив символов, завершающийся пустым значением null. Строку можно объявлять инициализировать, как и любой другой массив, например:
Char Greeting[ ] = {‘H’,’e’,’l’,’l’,’o’, ‘ ‘, ‘W’, ‘o’,’r’,’l’,’d’, ‘\0’};
В данном случае объявлен массив символов Greeting, который инициализирован набором символов. Последний символ ‘\0’ является пустым символом (символом null). Именно он служит для функций языка С++ признаком конца строки. Хотя такой «посимвольный» подход и работоспособен, но труден для вывода и порождает слишком много ошибок. Язык С++ допускает использование более кратких форм. Например, объявление предыдущей строки может выглядеть так
Char Greeting[ ] = “Hello World”;
В последнем случае добавлять символ null в конце строки не нужно, компилятор сделает это сам (однако нужно помнить, что он там присутствует).
При объявлении строковой переменной необходимо удостовериться, что ее размер достаточен для выполнения поставленной задачи. Длину строки составляет количество символов строки, включая символы пробела и завершающий нулевой символ. Например, строка “Hello World” занимает 12 байт: Hello – 5 байт, пробел – 1, World – 5 и символ null – еще один.
Можно также создавать и неинициализированные символьные массивы. Однако при этом следует удостовериться, что в буфер будет записано данных не больше его вместимости. Для этого используется метод cin.get().
Листинг 5.2. Заполнение массива максимальным количеством символов с помощью метода cin.get()
// Применение метода cin.get()
#include <iostream>
using namespace std;
int main(){
char buffer[80];
cout<<"Enter the string: ";
cin.get(buffer, 79);
cout<<"Here's the buffer: "<<buffer<<endl;
char resp;
cin>>resp;
return 0;
}
Первый аргумент метода cin.get() – это буфер, объявленный ранее как массив символов (букв). Второй аргумент – максимально количество вводимых символов. В данном случае – 79, чтобы учесть завершающий символ null. Третий параметр (символ завершения ввода) необязателен, поскольку по умолчанию признаком завершения является новая строка. При вводе пробелов, символов табуляции или других непечатаемых символов они также войдут в состав строки. Символом новой строки заканчивается ввод. Ввод 79-ти символов также приведет к завершению ввода.
Лекция № 6. УКАЗАТЕЛИ И ССЫЛКИ
Обычно программисту не нужно знать реальный адрес каждой переменной, поскольку компилятор способен сам позаботиться о таких подробностях. Но если необходимость в этой информации все же возникает, то получить ее можно с помощью оператора обращения к адресу: &. Например, если в программе используется переменная Var типа unsigned short, то набрав команду:
cout<<&Var;
мы получим результат: 0012FF7C – адрес этой переменной в шестнадцатеричном коде. На другом компьютере результат может получиться другим.
Каждая переменная имеет адрес. Даже не зная сам адрес (номер ячейки памяти), значение его можно сохранить в другой переменной. Такая переменная, хранящая адрес другого объекта, и называется указателем (pointer).
Поскольку указатели – это не более чем обычные переменные, им можно присваивать любые имена, допустимые для других переменных, но большинство программистов, следуя соглашению об именовании, пишут имена всех указателей с маленькой буквы p (от pointer – указатель).
Предположим, что существует целочисленная переменная howOld. Чтобы объявить указатель на нее по имени pAge, применяется следующая форма записи:
int *pAge=0;
В результате будет получена переменная pAge, предназначенная для хранения адреса значения типа int. В этом примере переменная pAge инициализируется нулевым значением. Указатели, значения которых равны нулю, называются пустыми (null pointer). После объявления указателю обязательно нужно присвоить какое-либо значение. Если предназначенный для хранения в указателе адрес заранее не известен, ему следует присвоить нулевое значение. Неинициализированные указатели называются дикими (wild pointer). Они очень опасны. Не шутите с этим, всегда инициализируйте указатели!
Присвоить адрес переменной howOld указателю pAge можно следующим образом:
int howOld=50;
int *pAge=0;
pAge=&howOld;
Две последние строки можно объединить в одну:
int howOld=50;
int *pAge=&howOld;
В указателях звездочка (*) используется двумя различными способами: при объявлении указателя и в операторе косвенного доступа. При объявлении указателя звездочка (*) является частью синтаксиса и располагается после указания типа объекта. Например:
// объявить указатель на тип int
int *pAge = 0;
При косвенном доступе звездочка означает, что речь идет о значении в памяти, находящемся по адресу в данной переменной, а не о самом адресе.
// разместить значение 5 по адресу, находящемуся в pAge
*pAge = 5;
Заметьте, что тот же символ (*) используется как оператор умножения. Что именно имел в виду программист, поставив звездочку, компилятор определяет, исходя из контекста.
Наиболее часто указатели применяются для манипулирования данными в динамически распределяемой памяти. Оперативная память компьютера состоит из следующих областей:
Стек представляет собой память, организованную по принципу LIFO (“Last In, First Out” – «Последним вошел, первым вышел»). Локальные переменные размещаются в стеке. Код программы размещается в сегментах. Регистры используются для внутренних целей процессора, например, для контроля вершины стека и указателя команд. Остальная часть памяти составляет так называемую динамически распределяемую память, или heap (кучу).
Особенностью локальных переменных является то, что после выхода из функции, в которой они были объявлены, память, выделенная для их хранения, освобождается, а значения переменных уничтожаются. Глобальные переменные позволяют частично решить эту проблему ценой неограниченного доступа к ним из любой точки программы, что значительно усложняет восприятие текста программы. Использование динамической памяти полностью решает обе проблемы.
Динамически распределяемую память можно представить как огромный массив последовательно пронумерованных ячеек, предназначенных для хранения данных. В отличие от стека, ячейкам свободной памяти нельзя присвоить имя, но можно, зарезервировав определенное количество ячеек, запомнить адрес первой из них в указателе.
Когда функция возвращает значение, стек очищается автоматически. Когда область видимости локальных переменных заканчивается, они также удаляются из стека. Но динамическая память не очищается до завершения самой программы. Поэтому ответственность за освобождение всей памяти, зарезервированной для всех использованных данных, ложится на программиста.
Преимуществом динамического выделения памяти по сравнению с глобальными переменными является то, что доступ к данным можно получить только из тех функций, которые обладают доступом к указателю, хранящему нужный адрес.
Для выделения участка в динамически распределяемой области памяти используется ключевой слово new. Например, чтобы создать в динамически распределяемой памяти переменную типа int, необходимо ввести команду:
int *pPointer = new int;
Теперь мы можем записать
*pPointer=72;
что можно прочитать так: «Разместить число 72 в той области динамически распределяемой памяти, на которую указывает pPointer».
По завершении работы с выделенной областью памяти ее нужно освободить. Для этого применяется оператор delete, после которого следует имя указателя. Например:
delete pPointer;
Помните, что сам указатель, в отличие от области памяти, на которую он указывает, является локальной переменной. Поэтому, когда объявившая указатель функция завершает работу, указатель выходит из области видимости, а содержащийся в нем адрес теряется. Поскольку динамическая память автоматически не освобождается, в случае потери адреса ее не удается ни удалить, ни использовать. Такой участок памяти становится абсолютно недоступным, а подобная ситуация называется утечкой памяти.
Поэтому каждый раз, когда в программе используется оператор new, за ним должен следовать оператор delete. Наилучшим способом нажить себе неприятностей является переприсвоение указателя без предварительного освобождения участка памяти, на который он указывает. Это приводит к утечке памяти. Рассмотрим следующий фрагмент кода:
int *pPointer = new int;
*pPointer = 72;
pPointer = new int;
*pPointer = 84;
В первой строке объявляется указатель pPointer и выделяется память для хранения переменной типа int. В следующей строке в выделенную область записывается значение 72. Затем в третьей строке указателю присваивается адрес другой области памяти, в которую записывается число 84 (строка 4). Теперь исходный участок памяти, содержащий значение 72, оказывается недоступен, поскольку указателю на эту область было присвоено новое значение. В результате невозможно ни использовать, ни освободить зарезервированную память до завершения программы. Правильно этот фрагмент выглядел бы так:
int *pPointer = new int;
*pPointer = 72;
delete pPointer;
pPointer = new int;
*pPointer = 84;
Ссылка (reference) – это псевдоним; при создании она инициализируется именем другого объекта, адресата. С этого момента ссылка выступает в роли альтернативного имени адресата, и все, что делается со ссылкой, происходит и с объектом. Ссылки обладают почти теми же возможностями, что и указатели, но синтаксис их несколько проще.
При объявлении ссылки вначале указывается тип объекта адресата, за которым следуют оператор ссылки (&) и имя ссылки.
int &rSomeRef=someInt;
Это можно прочитать как «rSomeRef является ссылкой на целочисленное значение, инициализированное адресом переменной someInt».
Оператор ссылки (&) выглядит так же, как и оператор возвращения адреса, который используется при работе с указателями. Но это не один и тот же оператор, хотя они очень похожи. Пробел перед оператором ссылки обязателен, а пробел между оператором ссылки и именем ссылки необязателен.
Функции имеют два ограничения: аргументы передаются как значения и теряют связь с исходными данными, а возвращать функция может только одно значение. Передавая функции аргументы по ссылке, можно преодолеть оба ограничения. В языке С++ передача данных по ссылке осуществляется двумя способами: либо с помощью указателей, либо с помощью ссылок. Ниже приведены примеры реализации функции swap(), обменивающей значения двух переменных, с помощью указателей и с помощью ссылок.
Листинг 6.1. Реализация функции swap() для работы с указателями
void swap (int *px, int *py)
{
int temp;
temp = *px;
*px = *py;
*py = temp;
}
Для вызова функции swap() из основной программы используется команда swap(&x, &y).
Листинг 6.2. Реализация функции swap() для работы со ссылками
void swap (int &rx, int &ry)
{
int temp;
temp = rx;
rx = ry;
ry = temp;
}
Для вызова функции swap() из основной программы используется команда swap(x, y).
Как можно видеть, при работе со ссылками функции swap() передаются именно значения x и y, а не их адреса. Таким образом, благодаря использованию ссылок функция приобретает новую возможность изменять исходные данные в вызывающей функции, хотя при этом сам вызов функции ничем не отличается от обычного.
Опытные программисты безоговорочно отдают предпочтения ссылкам, а не указателям. Ссылки легче использовать, и они проще для понимания. Однако их нельзя переназначать. Поэтому, если необходимо сначала указывать на один объект, а затем на другой, придется использовать указатель. Ссылки не могут быть нулевыми, поэтому, если существует вероятность того, что рассматриваемый объект может стать нулевым, использовать ссылку нельзя. В этом случае необходим указатель.
Как уже говорилось, функции могут возвращать только одно значение. Если необходимо вернуть несколько, то решением этой проблемы является передача функции нескольких объектов по ссылкам. В этом случае можно обойтись без главного возвращаемого значения, которое (зачем же добру пропадать?) можно использовать для сообщений об ошибках.
Листинг 6.3. Возвращение из функций нескольких значений при помощи ссылок
#include <iostream.h>
enum ERR_CODE {SUCCESS, ERROR};
ERR_CODE Factor(int, int&, int&); //Объявление функции
int main() {
int number, squared, cubed;
ERR_CODE result;
cout << ”Enter a number (0 – 20); “;
cin >> number;
result = Factor (number, squared, cubed);
if (result == SUCCESS)
{
cout << “number: “ << number << endl;
cout << “squared: “ << squared << endl;
cout << “cubed: “ << cubed << endl;
}
else
cout << “Error encountered!!” << endl;
char res;
cin>>res;
}
// Реализация функции
ERR_CODE Factor(int n, int &rSquared, int &rCubed) {
if (n > 20)
return ERROR;
else
{
rSquared = n*n;
rCubed = n*n*n;
return SUCCESS;
}
}
В этой программе функция Factor() вначале объявляется, а затем реализуется. Такая структура типична для профессиональных программ. Объявление записано выше функции main(), а реализация – ниже ее. В объявлении не обязательно писать имена аргументов, нужно только указать их типы. Объявление функции заканчивается точкой с запятой (в отличие от заголовка реализации функции).
Лекция № 7. НЕКОТОРЫЕ ПРОСТЫЕ АЛГОРИТМЫ
Предположим, что мы имеем массив из n элементов. Необходимо найти элемент с максимальным (или минимальным) числовым значением. Задача поиска максимального элемента может быть решена с помощью следующего алгоритма.
Рис. 7.1. Алгоритм поиска максимального элемента массива
Алгоритм поиска минимального элемента имеет ту же структуру. Только вместо условия: a[i]>Max – нужно записать условие: a[i]<Min. Программа поиска максимального и минимального элементов массива приведена в листинге 7.1.
Листинг 7.1. Поиск максимального и минимального элементов массива
# include <iostream>
int main(){
using namespace std;
int i, n;
float Min, Max;
float a[100];
cout<<"Input n: ";
cin>>n;
cout<<endl;
cout<<"Input array";
cout<<endl;
for (i=0; i<n; i++){
cin>>a[i];
}
Min=a[0];
Max=a[0];
for (i=0; i<n; i++){
if (a[i]<Min)
Min=a[i];
if (a[i]>Max)
Max=a[i];
}
cout<<endl;
cout<<"Max: " << Max << endl;
cout<<"Min: " << Min << endl;
char Res;
cin>>Res;
return 0;
}
С помощью операции сортировки можно расставить элементы числового массива в порядке их возрастания (или убывания). Существуют различные методы сортировки. Самым простым (но не самым быстрым) является пузырьковый метод. Он заключается в том, что два соседних элемента меняются местами, если они нарушают заданный порядок. При многократном повторении этой операции наименьший элемент «всплывает на поверхность как пузырек» – то есть попадает в начало выборки. Один из простых вариантов программы, реализующих данный метод, приведен в листинге 7.2.
Листинг 7.2. Пузырьковая сортировка элементов массива
# include <iostream>
void exch(double &a, double &b)
{ double t=a; a=b; b=t; }
void compexch(double &a, double &b)
{ if (a>b) exch(a, b); }
void bubble(double x[], int r)
{ for (int i=0; i<r-1; i++)
for (int j=0; j<r-1; j++)
compexch(x[j], x[j+1]);
}
void main()
{
using namespace std;
int i, n;
double a[100];
cout<<"Input n: ";
cin>>n;
cout<<endl<<"Input array"<<endl;
for (i=0; i<n; i++){
cin>>a[i];
}
cout<<endl;
bubble(a, n);
for (i=0; i<n; i++){
cout<<a[i]<<endl;
}
char Res;
cin>>Res;
}
В данной программе используется функция exch, которая меняет местами значения двух переменных («exchange» – на английском означает «обмен»). Функция может иметь несколько аргументов, но возвратить она способна максимум только одно значение. В данном случае функция exch вообще не возвращает ничего. Локальные переменные, которыми манипулирует функция, стираются из памяти сразу после ее выполнения. Чтобы изменения сохранились, необходимо использовать ссылки.
Если задана переменная x, то оператор &x вернет нам адрес этой переменной в оперативной памяти компьютера. Ссылка (reference) – это псевдоним адресата. Все, что делается со ссылкой, происходит и с объектом, который находится по указанному адресу.
Ссылки используются также и в функции compexch, которая сравнивает значения двух переменных и, если они стоят не в том порядке, вызывает функцию exch.
В функции exch используется локальная переменная t для временного хранения первоначального значения переменной a. Можно обойтись и без нее, если использовать следующий вариант функции exch.
void exch(double &a, double &b)
{ a=a+b; b=a-b; a=a-b; }
Эта программа использует меньше памяти, однако требуется комментарий, чтобы объяснить, для чего она предназначена.
Функция может вызывать сама себя – это свойство называется рекурсией. Рекурсию можно использовать для вычисления чисел Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, … Эти числа определяются с помощью рекуррентной формулы
. (7.1)
В листинге 7.3 приведена программа непосредственной рекурсивной реализации рекуррентного соотношения (7.1). Однако эта программа весьма неэффективна. В ней количество рекурсивных вызовов для вычисления равно . Но теория чисел Фибоначчи утверждает, что приближенно равно при больших , где – золотое сечение (для обозначения золотого сечения принято использовать букву в честь известного афинского скульптора Фидия). Таким образом, для программы из листинга 7.3 время этого элементарного вычисления определяется экспоненциальной зависимостью.
Листинг 7.3. Числа Фибоначчи (рекурсивная реализация)
# include <iostream.h>
int F(int i) {
if (i<1) return 0;
if (i==1) return 1;
return F(i-1)+F(i-2);
}
void main() {
int k, fib;
cout<<"Input number:";
cin>>k;
fib=F(k);
cout<<"F="<<fib;
char res;
cin>>res;
}
Можно легко вычислить первые чисел Фибоначчи за время, пропорциональное значению , используя массив, как показано в листинге 7.4.
Листинг 7.4. Числа Фибоначчи (динамическое программирование)
# include <iostream.h>
int F(int i) {
static int knownF[46];
if (knownF[i]!=0) return knownF[i];
int t=1;
if (i<0) return 0;
if (i>1) t=F(i-1)+F(i-2);
return knownF[i]=t;
}
void main() {
int k, fib;
cout<<"Input number:";
cin>>k;
fib=F(k);
cout<<"F="<<fib;
char res;
cin>>res;
}
Числа возрастают экспоненциально, поэтому размер массива невелик. Например, =1836311903 – наибольшее число Фибоначчи, которое может быть представлено 32-разрядным целым, поэтому достаточно использовать массив из 46 элементов.
Этот подход предоставляет непосредственный способ получения численных решений для любых рекуррентных соотношений. В случае с числами Фибоначчи можно даже обойтись без массива и ограничиться только первыми двумя значениями, однако для многих других часто встречающихся рекуррентных соотношений необходимо поддерживать массив, хранящий все известные значения.
Рекуррентное соотношение – это рекурсивная функция с целочисленными значениями. Любую такую функцию можно вычислить, вычисляя все значения функции, начиная с наименьшего, используя на каждом шаге ранее вычисленные значения для подсчета текущего значения. Эта технология называется восходящим динамическим программированием (bottom-up dynamic programming). Она применима к любому рекурсивному вычислению при условии, что мы можем себе позволить хранить все ранее вычисленные значения.
Нисходящее динамическое программирование (top-down dynamic programming) – еще более простая технология, которая позволяет автоматически выполнять рекурсивные функции при том же (или меньшем) количестве итераций, что и восходящее динамическое программирование. При этом рекурсивная программа используется для сохранения каждого вычисленного ею значения и для проверки сохраненных значений во избежания повторного вычисления любого из них. Программа из листинга 7.4 – механически измененная программа из листинга 7.3, в которой за счет применения нисходящего динамического программирования достигается резкое снижение времени выполнения.
Лекция № 8. ЧИСЛЕННОЕ РЕШЕНИЕ УРАВНЕНИЙ
Предположим, нам нужно решить кубическое уравнение
. (8.1)
Это означает, что нужно найти корни уравнения – такие числа, которые обращают уравнение в ноль, если приравнять неизвестную переменную x какому-либо из этих чисел. Основная теорема алгебры утверждает, что корней может быть несколько, причем, некоторые из них могут являться комплексными числами. Обычно практический интерес представляют только действительные корни. Убедиться в наличии действительных корней в уравнении (8.1) можно путем построения графика функции
. (8.2)
Такой график приведен на рис. 8.1.
Рис. 8.1. График функции
Как можно видеть, действительный корень уравнения (8.1) располагается где-то в диапазоне между 0,6 и 0,8. Если известно, что в заданном диапазоне находится только один корень уравнения, то функции от крайних точек диапазона, как правило, имеют разные знаки. Например, в случае функции, изображенной на графике рис. 8.1, имеет положительное значение, а – отрицательное значение. Можно утверждать и обратное: если значения функции на краях интервала имеют разные знаки, то внутри интервала содержится корень уравнения. Однако если функция имеет разрывы в некоторых точках, это правило не справедливо. Например, функция изменяет знак в точках , , как показано на рис. 8.2. Однако в этих точках нет корней уравнения, поскольку функция не пересекает ось . Такие точки называются сингулярными.
Рис. 8.2. График функции
Самым простым методом решения алгебраических уравнений является метод перебора в заданном интервале. Программа, которая реализует данный метод, представлена в листинге 8.1. Помимо основной функции main() она содержит также функции RootSearch()и Func(). В функции main() пользователь вводит исходные данные, после чего вызывается функция RootSearch(), которая непосредственно и вычисляет корень уравнения.
Листинг 8.1. Решение уравнения методом перебора
#include <iostream.h>
/* Ниже следуют прототипы функций */
void RootSearch ();
double Func (double);
int n;
double p[10];
double a, b, dx; // Глобальные переменные
void main ()
{
cout<<"Input degree of polynomial: ";
cin>>n;
cout<<endl;
cout<<"Input coefficients of function:\n";
cout<<endl;
for (int i=n; i>=0; i--) cin>>p[i];
cout<<endl;
cout<<"Input left limit: ";
cin>>a;
cout<<endl;
cout<<"Input right limit: ";
cin>>b;
cout<<endl;
cout<<"Input step: ";
cin>>dx;
cout<<endl;
RootSearch();
char Res;
cin>>Res;
}
void RootSearch ()
{
double x1, x2, f1, f2; //Локальные переменные
x1=a;
x2=a+dx;
f1=Func(x1);
f2=Func(x2);
while (f1*f2>0.0)
{
if (x1>=b)
{
cout<<"Root is not bracketed in
("<<a<<","<<b<<")"<<"\n";
return;
}
x1=x2;
f1=f2;
x2=x1+dx;
f2=Func(x2);
}
cout<<"x1: "<<x1<<"\n";
cout<<"x2: "<<x2<<"\n";
}
double Func (double x)
{
double Sum=0;
double y=1;
for (int i=0; i<(n+1); i++)
{
Sum=Sum+p[i]*y;
y=y*x;
}
return Sum;
}
РЕЗУЛЬТАТ
Функция Func() используется функцией RootSearch() как подпрограмма. Во второй и третьей строчках программы заявлены прототипы функций. Далее объявляются глобальные переменные, которые доступны для всех функций программы. В языке С++ глобальные переменные почти никогда не используются, поскольку существует возможность, что какая-либо из функций может изменить их значение. Альтернативой глобальным переменным являются статические переменные-члены, которые доступны всем экземплярам своего класса (термин из области объектно-ориентированного программирования). Они представляют собой компромисс между глобальными данными, доступными всем элементам программы, и данными-членами, доступными только объектам этого класса. В данной программе глобальные переменные используются в качестве примера. Угроза их несанкционированного изменения отсутствует. В отличие от глобальных переменных локальные переменные объявляются внутри функций. После выполнения функцией своей задачи ее локальные переменные стираются из памяти.
Метод половинного деления называется также методом дихотомии (от греческого – разделяю на две части). Англоязычные народы называют его method of bisection. Этот метод не самый скорый, однако наиболее надежный. Он использует следующий принцип: если корень находится в интервале , то произведение .
При использовании метода дихотомии вначале определяют точку в середине отрезка: . Затем находят значение функции в этой точке . Если , то корень заключен в интервале , а если , то – в интервале . Далее операцию деления повторяют с тем отрезком, в котором может находиться корень. Итерации продолжают до тех пор, пока интервал поиска не станет меньше заданной малой величины :
.
Исходный интервал уменьшается до после одного деления. А после делений уменьшается до величины . Приравнивая , и решая это уравнение относительно , получим
. (8.3)
В листинге 8.2 представлена программа, решающая заданное уравнение методом половинного деления. Для определения количества делений используется формула (8.3). В данной программе помимо основной функции main() содержатся также функции Bisect()и Func(). В отличие от предыдущего примера (листинг 8.1) данные для вычислений вводятся в самой функции Bisect(), а функция main() используется только для вызова функции Bisect(). Такой подход считается более приемлемым.
Входной аргумент filter предназначен для фильтрации возможной сингулярности. Устанавливая filter=1, мы заставляем программу проверять, уменьшается ли величина функции с каждым делением интервала пополам. Если нет, искомый «корень», является не корнем, а сингулярностью. Если есть уверенность, что сингулярность в данной задаче отсутствует, следует установить: filter=0.
Листинг 8.2. Решение уравнения методом дихотомии
#include <iostream.h>
#include <math.h>
int Bisect(); // Прототипы функций
double Func(double, int, double);
void main()
{
Bisect();
}
int Bisect()
{
int i, n, k, filter;
double p[10];
double a, b, x1, x2, x3, f1, f2, f3, tol, root;
cout<<"Input degree of polynomial: ";
cin>>n;
cout<<endl;
cout<<"Input coefficients of function:\n";
cout<<endl;
for (int i=n; i>=0; i--) cin>>p[i];
cout<<endl;
cout<<"Input left limit: ";
cin>>a;
cout<<endl;
cout<<"Input right limit: ";
cin>>b;
cout<<endl;
cout<<"Input tol: ";
cin>>tol;
cout<<endl;
//filter=singularity filter: 0=off (default), 1=on.
cout<<"Input filter (0 or 1): ";
cin>>filter;
cout<<endl;
f1=Func(p, n, a);
if (f1==0.0)
{
root=a;
cout<<"Root: "<<root<<"\n";
char Res;
cin>>Res;
return 0;
}
f2=Func(p, n, b);
if (f2==0.0)
{
root=b;
cout<<"Root: "<<root<<"\n";
char Res;
cin>>Res;
return 0;
}
if (f1*f2>0)
{
cout<<"Root is not bracketed in ("<<a<<", "<<b<<")"<<"\n";
char Res;
cin>>Res;
return 0;
}
k=ceil(log(fabs(b-a)/tol)/log(2.0));
x1=a;
x2=b;
for (
i=1; i<(k+1); i++)
{
x3=0.5*(x1+x2);
f3=Func(p, n, x3);
if ((filter==1)&&(fabs(f3)>fabs(f1))&&(fabs(f3)>fabs(f2)))
{
cout<<"Root is not bracketed in ("<<a<<",
"<<b<<")"<<"\n";
char Res;
cin>>Res;
return 0;
}
if (f3==0.0)
{
root=x3;
cout<<"Root: "<<root<<"\n";
char Res;
cin>>Res;
return 0;
}
if (f2*f3<0.0)
{
x1=x3;
f1=f3;
}
else
{
x2=x3;
f2=f3;
}
}
root=0.5*(x1+x2);
cout<<"Root: "<<root<<"\n";
char Res;
cin>>Res;
return 0;
}
double Func (double p[], int n, double x)
{
double Sum=0;
double y=1;
for (int i=0; i<(n+1); i++)
{
Sum=Sum+p[i]*y;
y=y*x;
}
return Sum;
}
Алгоритм Ньютона-Рафсона является наиболее известным методом отыскания корней уравнения по причине своей простоты и высокого быстродействия. Гладкую и непрерывную функцию можно разложить в ряд Тейлора
.
Если является корнем уравнения , то можем записать
.
Приравнивая остаток нулю, получим формулу Ньютона-Рафсона:
. (8.4)
Эта формула позволяет находить корень уравнения (если он существует на заданном отрезке) с заданной ошибкой за конечное число шагов. Программа, решающая заданное уравнение методом Ньютона-Рафсона, представлена в листинге 8.3.
Листинг 8.3. Решение уравнения методом Ньютона-Рафсона
#include <iostream.h>
#include <math.h>
void NewtonRaphson(int, double);
double Func(int, double);
double dFunc(int, double);
double p[10];
void main (){
int n;
double x;
cout<<"Input degree of polynomial: ";
cin>>n;
cout<<endl;
cout<<"Input coefficients of function:\n";
cout<<endl;
for (int i=n; i>=0; i--) cin>>p[i];
cout<<endl;
cout<<"Input x: ";
cin>>x;
cout<<endl;
NewtonRaphson(n, x);
char Res;
cin>>Res;
}
void NewtonRaphson(int n, double x)
{
const double tol=0.000001;
double dx, root;
for (int i=1; i<31; i++)
{
dx=-Func(n, x)/dFunc(n, x);
x=x+dx;
if (fabs(dx)<tol)
{
root=x;
cout<<"Root: "<<root<<endl;
return;
}
}
cout<<"The root isn't found";
}
double Func (int n, double x)
{
double Sum=0;
double y=1;
for (int i=0; i<(n+1); i++)
{
Sum=Sum+p[i]*y;
y=y*x;
}
return Sum;
}
double dFunc (int n, double x)
{
double Sum=0;
double y=1;
for (int i=1; i<(n+1); i++)
{
Sum=Sum+i*p[i]*y;
y=y*x;
}
return Sum;
}
РЕЗУЛЬТАТ
На рис. 8.3 показан график функции
. (8.5)
Как можно видеть, эта функция на интервале (0, 5) имеет два корня. Причем, первый корень совпадает с локальным экстремумом функции, при этом значения функции слева и справа от этого корня имеют один и тот же знак. Поэтому метод дихотомии не позволит определить этот корень. Однако метод Ньютона-Рафсона вполне способен справиться с данной проблемой.
Рис. 8.3. График функции
Численные методы позволяют найти лишь один корень – даже в том случае, если уравнение имеет несколько действительных корней. Например, если в качестве исходных данных мы возьмем полином (8.5), и в качестве начального значения примем х=3, то получим корень х=2,1. Если же мы возьмем начальное значение х=3,9; то получим второй корень х=4.
Метод Гаусса относится к наиболее известным методам решения систем линейных уравнений. Он делится на две части: фазу исключения и фазу обратной подстановки. Рассмотрим этот метод на примере, решив следующую систему из трех уравнений.
, (a)
, (b)
. (c)
Фаза исключения. Эта фаза заключается в умножении одного уравнения на одно и то же число , и затем вычитания полученного произведения из другого уравнения. В результате количество членов преобразованного уравнения уменьшается. Символически это можно записать так
.
Вычитаемое уравнение, обозначенное как , называется стержневым уравнением. Возьмем вначале в качестве стержневого уравнения и преобразуем остальные уравнения по следующей схеме
,
.
После этой трансформации получим следующую систему уравнений
, (a)
, (b)
. (c)
Далее в качестве стержневого уравнения выбираем уравнение (b) и преобразуем уравнение (c) по следующей схеме:
.
В результате получим
, (a)
, (b)
. (c)
Фаза обратной подстановки. Поскольку мы получили систему с верхней треугольной матрицей, то вначале находим неизвестную с наибольшим индексом, а затем – остальные неизвестные:
,
,
.
Алгоритм метода Гаусса. Рассмотрим систему в следующем виде.
Пусть i-тая строка является текущей строкой, лежащей ниже стержневой, ее мы будем трансформировать. Для исключения из этой строки элемента, нужно, чтобы сомножитель был равен отношению . Получаем следующий алгоритм:
,
.
После приведения матрицы к треугольному виду k-я строка имеет вид:
.
Поэтому неизвестные переменные можно найти по формуле:
.
Листинг 8.4. Решение систем линейных уравнений методом Гаусса
#include <iostream.h>
void input();
void output();
void gauss();
double A[100][100], b[100];
int n;
void main() {
input();
gauss();
cout<<endl;
cout<<"Result:"<<endl;
output();
char res;
cin>>res;
}
void input() {
cout<<"Input matrix size: ";
cin>>n;
cout<<"Input matrix:"<<endl;
cout<<endl;
cout<<"A = ";
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
cin>>A[i][j];
}
}
cout<<endl;
cout<<"Input vector:"<<endl;
cout<<endl;
cout<<"b = ";
for (i=1; i<=n; i++)
cin>>b[i];
}
void output() {
cout<<endl;
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
cout<<A[i][j]<<"\t";
}
cout<<endl;
}
cout<<endl;
for (i=1; i<=n; i++)
cout<<b[i]<<"\n";
}
void gauss() {
double lambda;
int i, j, k;
// Elimination phase
for (k=1; k<n; k++) {
for (i=k+1; i<=n; i++) {
if (A[i][k]!=0) {
lambda=A[i][k]/A[k][k];
b[i]=b[i]-lambda*b[k];
for (j=k; j<=n; j++) {
A[i][j]=A[i][j]-lambda*A[k][j];
}
}
}
}
// Back substitution phase (x=b, Sum=lambda)
for (k=n; k>0; k--) {
lambda=0;
for (j=k+1; j<=n; j++) {
lambda=lambda+A[k][j]*b[j];
}
b[k]=(b[k]-lambda)/A[k][k];
}
}
РЕЗУЛЬТАТ
Лекция № 9. ПОИСК НА ГРАФЕ
Граф (graph) – это графическая схема, представляющая собой совокупность вершин (vertexes), соединенных между собой ребрами (edges). Иногда вершины также называют узлами (nodes). На рис. 9.1. показан пример неориентированного (undirected) графа.
Рис. 9.1. Граф
Один из простых методов представления графа в компьютерной программе заключается в использовании двумерного массива, называемого матрицей смежности (adjacency matrix). Она позволяет быстро определять, существует ли ребро между вершинами i и j путем простой проверки наличия ненулевого значения в елементе матрицы, находящегося на пересечении i-ой строки и j-ого столбца. Для неориентированного графа матрица смежности симметрична. В листинге 9.1 показана программа создания матрицы смежности для вводимой последовательности ребер.
Листинг 9.1. Представление графа в виде матрицы смежности
#include <iostream.h>
void main()
{ int i, j, V, adj[100] [100];
cout<<"Input number of nodes: ";
cin>>V;
for (i=0; i<V; i++)
for (j=0; j<V; j++)
adj[i][j]=0;
for (i=0; i<V; i++) adj[i][i]=1;
cout<<"Input numbers of linked nodes: i-j.\n";
cout<<"If (i<0) or (j<0) - end.\n\n";
int k=0;
for (;;) //"Бесконечный цикл"
{
cout<<k<<": ";
cin>>i>>j;
if ((i<0)||(j<0)) break; // Условие выхода
k++; // из цикла
adj[i][j]=1; adj[j][i]=1;
}
cout<<endl;
cout<<"Adjacency matrix:\n";
cout<<endl;
for (i=0; i<V; i++)
{
for (j=0; j<V; j++)
cout<<adj[i][j]<<" ";
cout<<endl;
}
char res;
cin>>res;
}
РЕЗУЛЬТАТ
На распечатке показана матрица смежности графа, представленного на рис. 9.1. Иногда в матрице смежности элементы главной диагонали приравнивают нулю. В данном примере они равны единице. Вообще-то, это философский вопрос: нужно ли учитывать соединение вершины с самой собой.
Другой простой метод представления графа предусматривает использование массива связанных списков, называемых списками смежности (adjacency lists). Каждой вершине соответствует связной список с узлами для всех вершин, связанных с данной. На рис. 9.2 показан пример представления неориентированного графа (рис. 9.1) с помощью списков смежности.
Рис. 9.2. Представление графа в виде списков смежности
Обозначим количество вершин графа буквой , а количество ребер – буквой . Для матрицы смежности необходимо пространство в памяти, пропорциональное , а для списков смежности расход памяти пропорционален величине +. При небольшом количестве ребер (такой граф называется разреженным (sparse)), представление с использованием списков смежности потребует намного меньшего пространства. Если большинство пар соединено ребрами (такой граф называется насыщенным), использование матрицы смежности предпочтительнее, поскольку оно не связано со ссылками.
Оба рассмотренных типа представлений можно просто распространить и на другие типы графов. Они служат основой большинства алгоритмов обработки графов.
Рассмотрим одну из наиболее важных рекурсивных программ: рекурсивный обход графа, или поиск в глубину (depth-first search). В листинге
9.2 приведена программа поиска в глубину. При этом используется представление графа в виде списка соседних узлов. Начиная с любого узла (в данной программе это узел с индексом 0, однако программу легко переделать, чтобы индекс начального узла был любым), мы посещаем , а затем рекурсивно посещаем каждый непосещенный узел, связанный с . Если граф является связным (connections), то со временем будут посещены все узлы.
Листинг 9.2. Поиск в глубину
#include <iostream.h>
struct node
{
int v; node* next;
node(int x, node* t)
{ v=x; next=t;}
};
void traverse(int k, void visit(int));
void visit(int n);
typedef node *link;
link adj[100];
int visited[100];
void main() {
int i, j, V;
cout<<"Input number of nodes:";
cin>>V;
cout<<endl;
for (i=0; i<V; i++) adj[i]=0;
cout<<"Input numbers of linked nodes as: i_j
<Enter>"<<endl;
cout<<endl;
cout<<"(if i < 0 or j < 0 - this is indication of
end)"<<endl;
cout<<endl;
int k=0;
for (;;)
{
cout<<k<<": ";
cin>>i>>j;
if ((i<0)||(j<0)) break;
k++;
adj[j]=new node(i, adj[j]);
adj[i]=new node(j, adj[i]);
}
cout<<endl;
traverse(0, visit);
char res;
cin>>res;
}
void traverse(int k, void visit(int)) {
visit(k);
visited[k]=1;
for (link t=adj[k]; t!=0; t=t->next)
if (!visited[t->v]) traverse(t->v, visit);
}
void visit(int n) {
cout<<"visit "<<n<<endl;
}
РЕЗУЛЬТАТ
Для посещения в графе всех узлов, связанных с узлом k, мы помечаем его как посещенный, а затем рекурсивно посещаем все непосещенные узлы в списке смежности для узла k. Функция traverse() вызывает функцию visit()для каждого из узлов графа. Время, требующееся для выполнения поиска в глубину в графе с вершинами и ребрами, пропорционально +, если использовать представление графа в виде списков смежности.
В программе используется структура node. В языке C++ структура представляет собой класс, все члены которого по умолчанию открыты (public). Структуру можно объявить точно так же, как и класс, наделив ее такими же переменными-членами и функциями. А если следовать всем правилам программирования и всегда объявлять в явном виде открытые и закрытые разделы структуры, то никаких отличий не будет вовсе.
Возникает закономерный вопрос: почему два ключевых слова выполняют одинаковые действия? Так сложилось исторически. Когда разрабатывался язык C++, за основу был принят язык C, который содержал структуры. Но эти структуры не имели методов, как классы. Создатель языка C++ Бьерн Страуструп опирался на структуры, но заменил имя типа данных struct типом class, чтобы заявить о новых расширенных функциональных возможностях этого нового образования. Это позволило также продолжать использование множество библиотек функций языка C в программах C++.
В функции traverse() используется оператор косвенного доступа (indirection operator): «указатель на» (->), который состоит из символов «минус» и «больше». Компилятор С++ воспринимает его, как единый оператор. Выражение (t->v) означает: «получить доступ к переменной v (которая является членом структуры node) по заданному указателю t.
Лекция № 10. АНАЛИЗ АЛГОРИТМОВ
Обычно одну и ту же задачу можно решить различными способами. Среди различных алгоритмов, с помощью которых можно решить задачу, естественно выбрать один – наилучший. Обычно лучшим считается тот алгоритм, который позволяет решить задачу за самый короткий промежуток времени.
Рассмотрим следующий пример. Предположим, что имеется последовательность пар целых чисел, в которой каждое целое число представляет объект некоторого типа, а пара p-q интерпретируется в значении «p связано с q». Мы предполагаем, что отношение «связано с» является транзитивным: если p связано с q, а q связано с r, то p связано с r. Задача состоит в написании программы для исключения лишних пар из набора: когда программа вводит пару p-q, она должна выводить эту пару только в том случае, если просмотренные до данного момента пары не предполагают, что p связано с q. Если в соответствии с ранее рассмотренными парами следует, что p связано с q, программа должна игнорировать пару p-q и переходить ко вводу следующей пары. Пример такого процесса показан с помощью табл. 10.1. Назовем описанную выше задачу задачей связности.
При задании последовательности пар целых чисел, представляющих связь между объектами (вторая колонка таблицы), задача алгоритма связности заключается в выводе тех пар, которые обеспечивают новые связи (третья колонка). Например, пара 2-9 не должна выводиться, поскольку связь 2-3-4-9 определяется ранее указанными связями (подтверждение этого показано в последней колонке).
Задача состоит в разработке программы, которая может заполнить достаточный объем информации о просмотренных парах, чтобы решить, связана ли новая пара объектов.
Таблица 10.1.
|
№ |
Связь между объектами |
Новые связи |
Подтверждение ранее указанных связей |
|
1 |
3-4 |
3-4 |
|
|
2 |
4-9 |
4-9 |
|
|
3 |
8-0 |
8-0 |
|
|
4 |
2-3 |
2-3 |
|
|
5 |
5-6 |
5-6 |
|
|
6 |
2-9 |
2-3-4-9 |
|
|
7 |
5-9 |
5-9 |
|
|
8 |
7-3 |
7-3 |
|
|
9 |
4-8 |
4-8 |
|
|
10 |
5-6 |
5-6 |
|
|
11 |
0-2 |
0-8-4-3-2 |
|
|
12 |
6-1 |
6-1 |
Эта задача возникает в ряде важных приложений. Например, целые числа могли бы представлять компьютеры в большой сети, а пары могли бы представлять соединения в сети. Тогда такая программа могла бы использоваться для определения того, нужно ли устанавливать новое прямое соединение между p и q, чтобы иметь возможность обмениваться информацией, или же можно было бы использовать существующие соединения для установки коммуникационного пути.
Все алгоритмы решения задачи связности используют массив целых чисел, каждое из которых соответствует отдельному объекту, для хранения информации, необходимой для реализации операций объединения и поиска (union and find).
Первый алгоритм назовем алгоритмом быстрого поиска. Ниже приведена программа на языке С++, реализующая данный алгоритм.
Листинг 10.1. Решение задачи связности методом быстрого поиска
#include <iostream.h>
static const int N=10000;
int main()
{ int i, p, q, id[N];
for (i=0; i<N; i++) id[i]=i;
while (cin>>p>>q)
{ int t=id[p];
if (t==id[q]) continue;
for (i=0; i<N; i++)
if (id[i]==t) id[i]=id[q];
cout << " " << p << " " << q << endl;
}
char response;
cin >> response;
return 0;
}
Эта программа считывает последовательность пар неотрицательных целых чисел, меньших чем N, из стандартного ввода (интерпретируя пару p-q, как «связать объект p с объектом q») и выводит пары, представляющие объекты, которые еще не связаны. Она поддерживает массив id, содержащий запись для каждого объекта и характеризующийся тем, что элементы id[p] и id[q] равны тогда и только тогда, когда объекты p и q связаны. Для простоты N определена как константа времени компиляции. Иначе можно было бы считывать ее из ввода и распределять массив id динамически.
Изменения массива при выполнении операции union показаны в табл. 10.2.
Таблица 10.2.
|
№ |
p-q |
0 1 2 3 4 5 6 7 8 9 |
|
1 |
3-4 |
0 1 2 4 4 5 6 7 8 9 |
|
2 |
4-9 |
0 1 2 9 9 5 6 7 8 9 |
|
3 |
8-0 |
0 1 2 9 9 5 6 7 0 9 |
|
4 |
2-3 |
0 1 9 9 9 5 6 7 0 9 |
|
5 |
5-6 |
0 1 9 9 9 6 6 7 0 9 |
|
6 |
2-9 |
0 1 9 9 9 6 6 7 0 9 |
|
7 |
5-9 |
0 1 9 9 9 9 9 7 0 9 |
|
8 |
7-3 |
0 1 9 9 9 9 9 9 0 9 |
|
9 |
4-8 |
0 1 0 0 0 0 0 0 0 0 |
|
10 |
5-6 |
0 1 0 0 0 0 0 0 0 0 |
|
11 |
0-2 |
0 1 0 0 0 0 0 0 0 0 |
|
12 |
6-1 |
1 1 1 1 1 1 1 1 1 1 |
Алгоритм быстрого поиска выполняет не менее MN инструкций для решения задачи связности при наличии N объектов, для которых требуется выполнение M операций объединения. На современных компьютерах можно выполнять десятки и сотни миллионов инструкций в секунду, поэтому затраты времени не заметны, если значения N и M малы, но в современных приложениях может потребоваться обработка миллиардов объектов и миллионов вводимых пар.
Задачу связности можно решить с использованием альтернативного алгоритма быстрого объединения (но не очень быстрого поиска). Этот алгоритм реализует следующая программа.
Листинг 10.2. Решение задачи связности методом быстрого объединения (но не очень быстрого поиска)
#include <iostream.h>
static const int N=10000;
int main()
{ int i, j, p, q, id[N];
for (i=0; i<N; i++) id[i]=i;
while (cin>>p>>q)
{
for (i=p; i!=id[i]; i=id[i]);
for (j=q; j!=id[j]; j=id[j]);
if (i==j) continue;
id[i]=j;
cout << " " << p << " " << q << endl;
}
char response;
cin >> response;
return 0;
}
Данная программа выполняет меньше вычислений для операции union за счет выполнения большего количества вычислений для операции find. Циклы for и последующий оператор if в этом коде определяют необходимые и достаточные условия для того, чтобы массив id для p и q был связанным. Оператор присваивания id[i]=j реализует операцию union.
В табл. 10.3 показано содержимое массива id после обработки каждой из показанной слева пар алгоритмом быстрого поиска. При обработке пары p и q мы следуем указателям, указывающим из p, чтобы добраться до записи i, у которой id[i]= = i; затем мы следуем указателям, исходящим из q, чтобы добраться до записи j, у которой id[j]= = j; затем, если i и j различны, мы устанавливаем id[i]= id[j]. Для выполнения операции find для пары 5-8 (последняя строка) i принимает значение 56901, а j – значения 801.
Таблица 10.3.
|
№ |
p-q |
0 1 2 3 4 5 6 7 8 9 |
|
1 |
3-4 |
0 1 2 4 4 5 6 7 8 9 |
|
2 |
4-9 |
0 1 2 4 9 5 6 7 8 9 |
|
3 |
8-0 |
0 1 2 4 9 5 6 7 0 9 |
|
4 |
2-3 |
0 1 9 4 9 5 6 7 0 9 |
|
5 |
5-6 |
0 1 9 4 9 6 6 7 0 9 |
|
6 |
2-9 |
0 1 9 4 9 6 6 7 0 9 |
|
7 |
5-9 |
0 1 9 4 9 6 9 7 0 9 |
|
8 |
7-3 |
0 1 9 4 9 6 9 9 0 9 |
|
9 |
4-8 |
0 1 9 4 9 6 9 9 0 0 |
|
10 |
5-6 |
0 1 9 4 9 6 9 9 0 0 |
|
11 |
0-2 |
0 1 9 4 9 6 9 9 0 0 |
|
12 |
6-1 |
1 1 9 4 9 6 9 9 0 0 |
|
13 |
5-8 |
1 1 9 4 9 6 9 9 0 0 |
На рис. 10.1. показано представление быстрого объединения в виде дерева.
Рис. 10.1. Представление быстрого объединения в виде дерева
При наличии M пар N объектов, в худшем случае, когда M>N, для решения задачи связности алгоритму быстрого объединения может потребоваться выполнения более чем MN/2 инструкций.
Можно модифицировать этот алгоритм, чтобы худшие случаи гарантированно не имели места. Вместо того чтобы произвольным образом соединять второе дерево с первым для выполнения операции union, можно отслеживать количество узлов в каждом дереве и всегда соединять меньшее дерево с большим. Это изменение требует несколько более объемного кода и наличия еще одного массива для хранения счетчиков узлов, как показано в следующей программе, но оно ведет к существенному повышению эффективности. Мы будем называть этот алгоритм алгоритмом взвешенного быстрого объединения (weighted quick-union algorithm).
Листинг 10.3. Взвешенная версия быстрого объединения
#include <iostream.h>
static const int N=10000;
int main()
{ int i, j, p, q, id[N], sz[N];
for (i=0; i<N; i++)
{ id[i]=i; sz[i]=1;}
while (cin>>p>>q)
{
for (i=p; i!=id[i]; i=id[i]);
for (j=q; j!=id[j]; j=id[j]);
if (i==j) continue;
if (sz[i]<sz[j])
{id[i]=j; sz[j]+=sz[i];}
else {id[j]=i; sz[i]+=sz[j];}
cout << " " << p << " " << q << endl;
}
char response;
cin >> response;
return 0;
}
Эта программа – модификация алгоритма быстрого объединения, которая в служебных целях для каждого объекта, у которого id[i]= = i, поддерживает дополнительный массив sz, представляющий собой массив количества узлов в соответствующем дереве, чтобы операция union могла связывать меньшее из двух указанных деревьев с большим, тем самым предотвращая разрастание длинных путей в деревьях. Представление взвешенного быстрого объединения в виде дерева показано на рис. 10.2.
Рис. 10.2. Представление взвешенного быстрого объединения
в виде дерева
На приведенной последовательности рисунков демонстрируется результат изменения алгоритма быстрого объединения для связывания корня меньшего из двух деревьев с корнем большего из деревьев. Расстояние от каждого узла до корня его дерева не велико, поэтому операция поиска выполняется эффективно. Для определения того, связаны ли два из N объектов, алгоритму взвешенного быстрого объединения требуется отследить максимум logN указателей. Поэтому количество инструкций, которые алгоритм взвешенного быстрого объединения использует для обработки М ребер между N объектами, не превышает МlogN, умноженного на некоторую константу.
Результаты экспериментального исследования различных алгоритмов объединения-поиска представлены в табл. 10.4. Приведенные в таблице сравнительные значения времени, затрачиваемые на решение случайных задач связности с использованием алгоритмов объединения-поиска, демонстрируют эффективность взвешенной версии алгоритма быстрого объединения.
Таблица 10.4
|
N |
M |
Quick find |
Quick union |
Weighted QU |
|
1000 |
6206 |
14 |
25 |
6 |
|
2500 |
20236 |
82 |
210 |
13 |
|
5000 |
41913 |
304 |
1172 |
46 |
|
10000 |
83857 |
1216 |
4577 |
91 |
|
25000 |
309802 |
219 |
||
|
50000 |
708701 |
469 |
||
|
100000 |
1545119 |
1071 |
Здесь M – количество случайных соединений, генерируемых до тех пор, пока все N объектов не оказываются связанными. Этот процесс требует значительно больше операций find, чем операций union, поэтому быстрое объединение выполняется существенно медленнее быстрого поиска. Ни быстрый поиск, ни быстрое объединение не годятся для случая, когда значение N очень велико. Время выполнения при использовании взвешенных методов явно пропорционально значению N, поскольку оно уменьшается вдвое при уменьшении N вдвое.
Большинство алгоритмов имеет главный параметр N, который значительно влияет на время их выполнения. Параметр N может быть степенью полинома, размером файла при сортировке или поиске, количеством символов в строке или некоторой другой абстрактной мерой размера рассматриваемой задачи. Чаще всего он прямо пропорционален величине обрабатываемого набора данных. Когда таких параметров существует более одного (например, М и N в алгоритмах union- find), задачу часто сводят к одному параметру, задавая его как функцию других.
Обычно алгоритмы имеют время выполнения, пропорциональное одной из следующих функций: N, logN, NlogN, .
4
8
7
6
5
1
0
2
9
3
4
8
7
6
5
1
0
9
3
4
8
7
6
5
2
1
0
ережа
Юра
Юля
Маша
Неопределенность
Брюнет
Блондинка
Юноша
Девушка
Да
Да
Да
Нет
Нет
Нет
Конец
Сережа
Юра
Юля
Маша
Блондин?
Блондинка?
Девушка?
Начало
9
3
4
8
7
6
5
2
1
0
9
8
7
6
5
4
3
2
1
0
0
1
8
7
9
6
4
2
5
3
8
0
7
9
6
4
2
5
3
1
0
7
9
6
4
2
8
5
3
1
6
4
9
2
8
7
5
3
1
0
4
9
2
8
7
6
5
3
1
0
4
9
2
8
7
6
5
3
1
0
9
8
7
6
5
4
3
2
1
0
9
8
7
6
4
0
2
1
0
4
3
4
0
3
7
5
6
4
5
0
7
6
1
0
7
7
2
5
5
4
3
2
1
0
9
8
7
6
5
4
3
2
1
0
7
6
5
4
3
4
3
7
1
2
6
2
0
5
1
0
Блондин
Брюнетка
Условие
Действие 1
Математический
оператор 2
Математический
оператор 1
Действие 2
Да
Нет
Условие
Действие
Условие
Да
Нет
Действие
Да
Нет
Вводим
массив a[n] из n элементов
i=0, n, 1
Действие
i=n1, n2, h
a[i]>Max
Max=a[i]
Да
Нет
Начало
Задаем
Max=a[0]
Выводим на
экран значение
Max
Конец
9
2
0
1
6
7
8
2
9
4
3
5
0
1
6
8
2
9
4
5
3
7
0
1
6
2
9
4
5
7
3
8
0
6
2
9
4
5
7
8
3
1