Программирование на языке высокого уровня (стр. 11 )

Для перегрузки операции применительно к классу в число членов класса должна быть включена специальная функция операции, которая определяет действия, выполняемые по этой операции. формат определения функции-операции:

тип возвращаемого_значения operator знак_операции (спецификации_параметров операции) {тело_функции-операции}

Рассмотрим пример программы, в которой используются перегруженные операции.

Пример 5. Класс vector определяет трехмерный вектор в евклидовом пространстве. В этом классе будут использоваться перегруженные операции сложения (+) и присваивания (=) как операции с трехмерными векторами. Сумма двух векторов вычисляется как вектор, компоненты которого равны суммам соответствующих компонент слагаемых. Операция = выполняет покомпонентное присваивание векторов.

В результате выполнения программы на экране получим:

Здесь естествен вопрос: почему бинарные операции-функции + и = имеют в описании только по одному аргументу? Дело в том, что другой аргумент всегда передается неявно с использованием this-указателя. Оператор temp. x=x+t. x; аналогичен строке temp. x=this->x+t. х, т. е. х ссылается на this->x. Здесь this ассоциируется с объектом, предшествующим знаку операции. Объект справа от знака операции передается как параметр функции.

Если аналогичным образом определять унарные операции как функции-члены класса, то для них не требуется указания параметра. Объект, к которому относится операция, передается в функцию неявно через указатель this. Например, для класса vector можно добавить объявление унарной постфиксной операции ++:

vector operator++(void);

Описание этой функции будет следующим:

vector vector::operator++(void)

( х++;

у++;

х++;

return *this; )

4.15. Форматированный ввод-вывод в Си++

Для организации ввода-вывода в Си++ можно использовать средства языка Си (conio. h). Однако в Си++ существует стандартная библиотека классов, ориентированная на организацию потокового ввода-вывода. Классы ввода-вывода образуют иерархию по принципу наследования. Базовым в этой иерархии является класс ios (исключение составляют лишь классы буферизированных потоков). В классе ios объединены базовые данные и методы для ввода-вывода. Прямыми потомками класса ios являются классы istream и ostream. Класс istream — это класс входных потоков; ostream — класс выходных потоков. Потомком этих двух классов является iostream — класс двунаправленных потоков ввода-вывода. С этим классом мы уже много раз имели дело, подключая его к программам с помощью головного файла iostream. h.

Объект cout принадлежит к классу ostream и представляет собой поток вывода, связанный с дисплеем. Объект cin принадлежит классу istream и является потоком ввода, связанным с клавиатурой. Оба эти объекта наследуются классом iostream.

Знак << обозначает перегруженную операцию вставки символов в поток вывода cout, а >> — знак операции извлечения из потока ввода cin.

Для организации форматированного потокового ввода-вывода в Си++ существуют два средства:

• применение функций-членов класса ios для управления флагами форматирования;

• применение функций-манипуляторов.

Управление флагами форматирования. Флаги форматирования — двоичные коды, управляющие форматом выводимых значений. В заголовочном файле iostream. h определено следующее перечисление, задающее флаги форматирования:

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

Изменить состояние флагов формата можно с помощью функции-члена класса ios, имеющей прототип

long setf(long flags)

Например, чтобы установить флаг showbase в активный режим (включить) применительно к стандартному потоку вывода cout, используется оператор

cout. setf(ios::showbase) ;

Для установки флагов можно использовать побитовые операции. Например:

cout. setf(ios::left|ios::hex);

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

Для выключения используется функция

unsetf(long flags);

Например, для отмены вывода основания системы счисления используется оператор:

cout. unsetf(ios::showbase);

Вот еще некоторые функции-члены класса ios:

long flags (void) - возвращает текущее состояние флагов;

int width (int len) — возвращает текущую ширину поля вывода и устанавливает значение ширины, равное len;

char fill (char ch) — возвращает текущий символ заполнения и устанавливает новый символ заполнения ch;

int precision (int num) — возвращает текущее число десятичных знаков после точки и устанавливает значение этого параметра равным num.

Пример 1. Следующая программа иллюстрирует применение рассмотренного способа управления форматным выводом.

Использование манипуляторов. Для управления форматами потокового вывода можно использовать специальные функции, называемые манипуляторами. Доступ в программе к стандартным манипуляторам можно получить, подключив файл iomanip. h. Список стандартных манипуляторов:

Пример 2. В следующей программе вычисляется и выводится на экран таблица значений функций sin x и cos x на п шагах в интервале от 0 до р. Для форматирования таблицы результатов используются манипуляторы.

Начальная часть таблицы, выводимой по этой программе, имеет вид:

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

Приложение 4. Библиотека функций языка Си/Си++

Таблица П4.1. Математические функции — файл math. h

Таблица П4.2. Функция проверки и преобразования символов — файл ctype. h

Таблица П4.3. Функции ввода-вывода для стандартных файлов — файл stdio. h

Таблица П4.4. Функции для работы со строками — файлы string. h, stdlid. h

Таблица П4.5. Функции для работы с терминалом в текстовом режиме — файл conio. h

Таблица П4.6. Специальные функции

Графическая библиотека в C++

Таблица П4.7. Функции для управления графической системой

Таблица П4.8. Функции для получения изображения на экране

Таблица П4.9. Функции для получения параметров изображения

ГЛАВА 5. МЕТОДЫ ПОСТРОЕНИЯ АЛГОРИТМОВ

5.1. Основные понятия структурного программирования

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

На первых ЭВМ с «тесной» памятью и небольшим быстродействием основным показателем качества программы была ее экономичность по занимаемой памяти и времени счета. Чем программа получалась короче, тем класс программиста считался выше. Такое сокращение программы часто давалось большими усилиями. Иногда программа получалась настолько «хитрой», что могла «перехитрить» самого автора. Возвращаясь через некоторое время к собственной программе, желая что-то изменить, программист мог запутаться в ней, забыв свою «гениальную идею».

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

В процессе изготовления программного продукта программист должен пройти определенные этапы.

На стадии проектирования строится алгоритм будущей программы, например, в виде блок-схемы. Кодирование — это составление текста программы на языке программирования. Отладка осуществляется с помощью тестов, т. е. программа выполняется с некоторым заранее продуманным набором исходных данных, для которого известен результат. Чем сложнее программа, тем большее число тестов требуется для ее проверки. Очень «хитрую» программу трудно протестировать исчерпывающим образом. Всегда есть шанс, что какой-то «подводный камень» остался незамеченным.

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

В конце 60-х — начале 70-х гг. XX столетия вырабатывается дисциплина, которая получила название структурного программирования. Ее появление и развитие связаны с именами , , и других ученых. Структурное программирование до настоящего времени остается основой технологии программирования. Соблюдение его принципов позволяет программисту быстро научиться писать ясные, безошибочные, надежные программы.

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

Следование — это линейная последовательность действий:

Каждый блок может содержать в себе как простую команду, так и сложную структуру, но обязательно должен иметь один вход и один выход.

Ветвление — алгоритмическая альтернатива. Управление передается одному из двух блоков в зависимости от истинности или ложности условия. Затем происходит выход на общее продолжение:

Неполная форма ветвления имеет место, когда на ветви «нет» пусто:

Цикл — повторение некоторой группы действий по условию. Различаются два типа цикла. Первый — цикл с предусловием (цикл-пока): 

Пока условие истинно, выполняется серия, образующая тело цикла.

Второй тип циклической структуры — цикл с постусловием (цикл-до):

Здесь тело цикла предшествует условию цикла. Тело цикла повторяет свое выполнение, если условие ложно. Повторение кончается, когда условие станет истинным.

Теоретически необходимым и достаточным является лишь первый тип цикла — цикл с предусловием. Любой циклический алгоритм можно построить с его помощью. Это более общий вариант цикла, чем цикл-до. В самом деле, тело цикла-до хотя бы один раз обязательно выполнится, так как проверка условия происходит после завершения его выполнения. А для цикла-пока возможен такой вариант, когда тело цикла не выполнится ни разу. Поэтому в любом языке программирования можно было бы ограничиться только циклом-пока

Однако в ряде случаев применение цикла-до оказывается более удобным, и поэтому он используется.

Иногда в литературе структурное программирование называют программированием без goto. Действительно, при таком подходе нет места безусловному переходу. Неоправданное использование в программах оператора goto лишает ее структурности, а значит, всех связанных с этим положительных свойств: прозрачности и надежности алгоритма. Хотя во всех процедурных языках программирования этот оператор присутствует, однако, придерживаясь структурного подхода, его употребления следует избегать.

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

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

Структурный подход требует соблюдения стандарта в изображении блок-схем алгоритмов. Чертить их нужно так, как это делалось во всех приведенных примерах. Каждая базовая структура должна иметь один вход и один выход. Нестандартно изображенная блок-схема плохо читается, теряется наглядность алгоритма. Вот несколько примеров структурных блок-схем алгоритмов (рис. 47).

Такие блок-схемы легко читаются. Их структура хорошо воспринимается зрительно. Структуре каждого алгоритма можно дать название. У приведенных на рис. 47 блок-схем следующие названия:

1. Вложенные ветвления. Глубина вложенности равна единице.

2. Цикл с вложенным ветвлением.

3. Вложенные циклы-пока. Глубина вложенности — единица.

4. Ветвление с вложенной последовательностью ветвлений на положительной ветви и с вложенным циклом-пока на отрицательной ветви.

5. Следование ветвления и цикла-до.

6. Вложенные циклы. Внешний — цикл-пока, внутренний — цикл-до.

Наряду с блок-схемами для описания алгоритмов часто используются псевдокоды. Учебный алгоритмический язык школьной информатики является примером такого псевдокода. Учебный АЯ — структурный псевдокод. В нем вообще отсутствует безусловный переход. Обучение составлению алгоритмов на этом языке способствует «структурному воспитанию» программиста.

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

• конструкции одного уровня вложенности записываются на одном вертикальном уровне (начинаются с одной позиции в строке);

• вложенная конструкция записывается смещенной по строке на несколько позиций вправо относительно внешней для нее конструкции.

Для приведенных выше блок-схем структура текста программы на Паскале должна быть следующей:

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

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

• «сверху вниз»: сначала строится основной алгоритм, затем вспомогательные алгоритмы;

• «снизу вверх»: сначала составляются вспомогательные алгоритмы, затем основной.

Первый подход еще называют методом последовательной детализации, второй — сборочным методом.

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

Метод последовательной детализации применяется в любом конструировании сложных объектов. Это естественная логическая последовательность мышления конструктора: постепенное углубление в детали. В нашем случае речь идет тоже о конструировании, но только не технических устройств, а алгоритмов. Достаточно сложный алгоритм другим способом построить практически невозможно.

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

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

5.2. Метод последовательной детализации

Суть метода была описана выше. Сначала анализируется исходная задача. В ней выделяются подзадачи. Строится иерархия таких подзадач (рис. 48).

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

Вернемся к задаче «Интерпретатор», которая рассматривалась в разд. 3.16. Напомним условие: дана исходная символьная строка, имеющая следующий вид:

а

b=

На месте а и b стоят десятичные цифры; значком

 обозначен один из знаков операций: +, -, *. Нужно, чтобы машина вычислила это выражение и после знака = вывела результат. Операция деления не рассматривается для того, чтобы иметь дело только с целыми числами.

Сформулируем требования к программе Interpretator, которые сделают ее более универсальной, чем вариант, рассмотренный в разд. 3.16:

1. Операнды а и b могут быть многозначными целыми положительными числами в пределах MaxInt.

2. Между элементами строки, а также в начале и в конце могут стоять пробелы.

3. Программа осуществляет синтаксический контроль текста. Ограничимся простейшим вариантом контроля: строка должна состоять только из цифр, знаков операций, знака = и пробелов.

4. Проводится семантический контроль: строка должна быть построена по схеме а

 b =. Ошибка, если какой-то элемент отсутствует или нарушен их порядок.

5. Осуществляется контроль диапазона значений операндов и результата (не должны выходить за пределы MaxInt).

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

1. Ввод строки.

2. Синтаксический контроль (нет ли недопустимых символов?).

3. Семантический контроль (правильно ли построено выражение?).

4. Выделение операндов. Проверка операндов на допустимый диапазон значений. Перевод в целые числа.

5. Выполнение операции. Проверка результата на допустимый диапазон.

6. Вывод результата.

Этапы 2, 3, 4, 5 будем рассматривать как подзадачи первого уровня, назвав их (и будущие подпрограммы) соответственно Sintax, Semantika, Operand, Calc

В свою очередь, для их реализации потребуется решение следующих подзадач: пропуск лишних пробелов (Propusk), преобразование символьной цифры в целое число (Cifra). Кроме того, при выделении операндов понадобится распознавать операнд, превышающий максимально допустимое значение (Error). Обобщая все сказанное в схематической форме, получаем некоторую структуру подзадач. Этой структуре будет соответствовать аналогичная структура программных модулей (рис. 49).

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

Обратите внимание на то, что функция Error определена как внутренняя в процедуре Operand. Это объясняется тем, что указанная функция используется только в данной процедуре. Другим программным модулям она «не нужна».

Окончательно объединив тексты подпрограмм с основной программой, получаем рабочий вариант программы Interpretator. Теперь ее можно вводить в компьютер.

Отладка и тестирование программы. Никогда нельзя быть уверенным, что одним махом написанная программа будет верной (хотя такое и возможно, но с усложнением программы становится все менее вероятным). До окончательного рабочего состояния программа доводится в процессе отладки.

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

Алгоритмические ошибки приводят к различным последствиям. Во-первых, могут возникнуть невыполнимые действия. Например, деление на нуль, корень квадратный из отрицательного числа, выход индекса за границы строки и т

п. Это ошибки времени исполнения. Они приводят к прерыванию выполнения программы. Как правило, имеются системные программные средства, помогающие в поиске таких ошибок.

Другая ситуация, когда алгоритмические ошибки не приводят к прерыванию выполнения программы. Программа выполняется до конца, получаются какие-то результаты, но они не являются верными. Для окончательной отладки алгоритма и анализа его правильности производится тестирование. Тест — это такой вариант решения задачи, для которого заранее известны результаты. Как правило, один тестовый вариант не доказывает правильность программы. Программист должен придумать систему тестов, построить план тестирования для исчерпывающего испытания всей программы.

Мы уже говорили о том, что качественная программа ни в каком варианте не должна завершаться аварийно. Тесты программы Interpretator должны продемонстрировать, что при правильном вводе исходной строки будут всегда получаться верные результаты, а при наличии ошибок (синтаксических, семантических, выхода за диапазон) будут получены соответствующие сообщения. План тестирования нашей программы может быть, например, таким:

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

5.3. Рекурсивные методы

Суть рекурсивных методов — сведение задачи к самой себе. Вы уже знаете, что как в Паскале, так и в Си существует возможность рекурсивного определения функций и процедур. Эта возможность представляет собой способ программной реализации рекурсивных алгоритмов. Однако увидеть рекурсивный путь решения задачи (рекурсивный алгоритм) часто очень непросто.

Рассмотрим классическую задачу, известную в литературе под названием «Ханойская башня» (рис. 50).

На площадке (назовем ее А) находится пирамида, составленная из дисков уменьшающегося от основания к вершине размера.

Эту пирамиду в том же виде требуется переместить на площадку В. При выполнении этой работы необходимо соблюдать следующие ограничения:

• перекладывать можно только по одному диску, взятому сверху пирамиды;

• класть диск можно либо только на основание площадки, либо на диск большего размера;

• в качестве вспомогательной можно использовать площадку С.

Название «Ханойская башня» связано с легендой, согласно которой в давние времена монахи одного ханойского храма взялись переместить по этим правилам башню, состоящую из 64 дисков. С завершением их работы наступит конец света. Монахи все еще работают и, надеемся, еще долго будут работать!

Нетрудно решить эту задачу для двух дисков. Обозначая перемещения диска, например, с площадки А на В так: А → В, напишем алгоритм для этого случая

А→С; А→В; С→В.

Всего 3 хода! Для трех дисков алгоритм длиннее:

А→В; А→С; В→С; А→В; С→А; С→В; А→В.

В этом случае уже требуются 7 ходов.

Подсчитать количество ходов (N) для k дисков можно по следующей рекуррентной формуле:

N(1) = 1; N(k) = 2х N(k - 1) + 1.

Например, N(10) = 1023, N(20) = 104857. А вот сколько перемещений нужно сделать ханойским монахам:

N(64) = .

Попробуйте прочитать это число.

Теперь составим программу, по которой машина рассчитает алгоритм работы монахов и выведет его для любого значения п (количества дисков). Пусть на площадке А находятся п дисков. Алгоритм решения задачи будет следующим:

1. Если п = 0, то ничего не делать.

2. Если п > 0, то   переместить п — 1 диск на С через В;

переместить диск с А на В (А → В)

переместить п — 1 диск с С на В через А.

При выполнении пункта 2 последовательно будем иметь три состояния (рис. 51).

Описание алгоритма имеет явно рекурсивный характер

Перемещение n дисков описывается через перемещение п — 1 диска. А где же выход из этой последовательности рекурсивных ссылок алгоритма самого на себя? Он в пункте 1, каким бы ни показалось странным его тривиальное содержание.

А теперь построим программу на Паскале. В ней имеется рекурсивная процедура Напоу, выполнение которой заканчивается только при п = 0. При обращении к процедуре используются фактические имена площадок, заданные их номерами: 1, 2, 3. Поэтому на выходе цепочка перемещений будет описываться в таком виде:

1→2 1→3 2→3 и т. д.

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

5.4. Методы перебора в задачах поиска

В данном разделе мы рассмотрим некоторые задачи, связанные с проблемой поиска информации. Это огромный класс задач, достаточно подробно описанный в классической литературе по программированию (см., например, книги Н. Вирта, Д. Кнута и другие).

Общий смысл задач поиска сводится к следующему: из данной информации, хранящейся в памяти ЭВМ, выбрать нужные сведения, удовлетворяющие определенным условиям (критериям).

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

Полный перебор является «лобовым» способом поиска и, очевидно, не всегда самым лучшим.

Рассмотрим пример. В одномерном массиве X заданы координаты п точек, лежащих на вещественной числовой оси. Точки пронумерованы. Их номера соответствуют последовательности в массиве X. Определить номер первой точки, наиболее удаленной от начала координат.

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

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

А теперь такая задача: исходные данные — те же, что и в предыдущей; требуется определить пару точек, расстояние между которыми наибольшее.

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

Очевидно, что такое решение задачи нерационально. Здесь каждая пара точек будет просматриваться дважды, например при i = 1, j = 2 и i = 2, j= 1. Для случая п = 100 циклы повторят выполнение 100 х 100 = 10000 раз.

Выполнение программы ускорится, если исключить повторения. Исключить также следует и случай совпадения значений i и j. Тогда число повторений цикла будет равно

. При n = 100 получается 4950.

Для исключения повторений нужно в предыдущей программе изменить начало внутреннего цикла с 1 на i +1. Программа примет вид:

Рассмотренный вариант алгоритма назовем перебором без повторений.

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

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

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

For I:=l To N Do

For J:=I+1 To N Do

For K:=J+1 To N Do

If X[I]+X[J]+X[K]=10

Then WriteLn(X[I],X[J],X[K]);

А теперь представьте, что из массива Х требуется выбрать все группы чисел, сумма которых равна десяти. В группах может быть от 1 до п чисел. В этом случае количество вариантов перебора резко возрастает, а сам алгоритм становится нетривиальным.

Казалось бы, ну и что? Машина работает быстро! И все же посчитаем. Число различных групп из п объектов (включая пустую) составляет 2n. При п = 100 это будет 2100 ≈ 1030. Компьютер, работающий со скоростью миллиард операций в секунду, будет осуществлять такой перебор приблизительно 10 лет. Даже исключение перестановочных повторений не сделает такой переборный алгоритм практически осуществимым.

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

Перебор с возвратом. Рассмотрим алгоритм перебора с возвратом на примере задачи о прохождении лабиринта (рис. 52).

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

Для получения программы решения этой задачи нужно решить две проблемы:

• как организовать данные;

• как построить алгоритм.

Информацию о форме лабиринта будем хранить в квадратной матрице LAB символьного типа размером N x N, где N — нечетное число (чтобы была центральная точка). На профиль лабиринта накладывается сетка так, что в каждой ее ячейке находится либо стена, либо проход.

Матрица отражает заполнение сетки: элементы, соответствующие проходу, равны пробелу, а стене — какому-нибудь символу (например, букве М)

Путь движения по лабиринту будет отмечаться символами +.

Например, приведенный выше рисунок (в середине) соответствует следующему заполнению матрицы LAB:

Исходные данные — профиль лабиринта (исходная матрица LAB без крестиков); результат — все возможные траектории выхода из центральной точки лабиринта (для каждого пути выводится матрица LAB с траекторией, отмеченной крестиками).

Алгоритм перебора с возвратом еще называют методом проб.

Суть его в следующем:

1. Из каждой очередной точки траектории просматриваются возможные направления движения в одной и той же последовательности; договоримся, что просмотр будет происходить каждый раз против часовой стрелки — справа-сверху-слева-снизу; шаг производится в первую же обнаруженную свободную соседнюю клетку; клетка, в которую сделан шаг, отмечается крестиком.

2. Если из очередной клетки дальше пути нет (тупик), то следует возврат на один шаг назад и просматриваются еще не испробованные пути движения из этой точки; при возвращении назад покинутая клетка отмечается пробелом.

3. Если очередная клетка, в которую сделан шаг, оказалась на краю лабиринта (на выходе), то на печать выводится найденный путь.

Программу будем строить методом последовательной детализации. Первый этап детализации:

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

Запишем сначала общую схему процедуры без детализации:

Для вывода найденных траекторий составляется процедура PRINTLAB.

В окончательном виде программа будет выглядеть так:

Еще один пример красивой программы с использованием рекурсивного определения процедуры (вспомните ханойскую башню!).

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

Замечание. Из-за использования массива LAB в качестве параметра-значения в процедуре GO могут возникнуть проблемы с памятью при реализации программы на ЭВМ. В таком случае можно перейти к глобальной передаче массива.

Упражнения

1. Даны декартовы координаты N точек на плоскости. Составить программы решения следующих задач:

а) найти две самые близкие друг к другу точки;

б) найти две самые удаленные друг от друга точки;

в) найти три точки, лежащие в вершинах треугольника с наибольшим периметром;

г) найти две ближайшие точки, отрезок между которыми может служить радиусом окружности, заключающей внутри себя все остальные точки; указать, какая из них является центральной.

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

3. Составить программу, в соответствии с которой шахматный конь обойдет всю доску, побывав на каждом поле всего один раз.

4. Составить программу расстановки на шахматной доске восьми ферзей так, чтобы они не угрожали друг другу.

5.5. Эвристические методы

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

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

5.6. Сложность алгоритмов

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

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

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

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

Как правило, временная сложность алгоритма зависит от исходных данных. Это может быть зависимость как от величины исходных данных, так и от их объема. Если обозначить значение параметра временной сложности алгоритма α

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

Пример 1. Оценим временную сложность алгоритма вычисления факториала целого положительного числа.

Function Factorial(x:Integer): Integer;

Var m, i: Integer;

Begin m:=l;

For i:=2 To x Do m:=ro*i;

Factorial:=m

End;

Подсчитаем общее число операций, выполняемых программой при данном значении x. Один раз выполняется оператор m:=1; тело цикла (в котором две операции: умножение и присваивание) выполняется х — 1 раз; один раз выполняется присваивание Factorial:=m. Если каждую из операций принять за единицу сложности, то временная сложность всего алгоритма будет 1 + 2 (x — 1) + 1 = 2х Отсюда понятно, что в качестве параметра следует принять значение х. Функция временной сложности получилась следующей:

Tα(V)=2V.

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

Пример 2. Вычисление скалярного произведения двух векторов А = (a1, a2, …, ak), В = (b1, b2, …, bk).

АВ:=0;

For i:=l To k Do AB:=AB+A[i]*B[i];

В этой задаче объем входных данных п = 2k. Количество выполняемых операций 1 + 3k = 1 + 3(n/2). Здесь можно взять V= k= п/2. Зависимости сложности алгоритма от значений элементов векторов А и В нет. Как и в предыдущем примере, здесь можно говорить о линейной зависимости временной сложности от параметра данных.

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

Вторая проблема связана с классификацией алгоритмов по временной сложности. Функция Tα(V) обычно растет с ростом V. Как быстро она растет? Существуют алгоритмы с линейной зависимостью Тα от V (как это было в рассмотренных нами примерах), с квадратичной зависимостью и с зависимостью более высоких степеней. Такие алгоритмы называются полиномиальными. А существуют алгоритмы, сложность которых растет быстрее любого полинома. Проблема, которую часто решают теоретики — исследователи алгоритмов, заключается в следующем вопросе: возможен ли для данной задачи полиномиальный алгоритм?

5.7. Методы сортировки данных

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

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

Различают алгоритмы внутренней сортировки — во внутренней памяти и алгоритмы внешней сортировки — сортировки файлов. Далее мы будем рассматривать только внутреннюю сортировку.

Как правило, сортируемые данные располагаются в массивах. В простейшем случае это числовые массивы. Однако для нечисленных алгоритмов более характерна ситуация, когда сортируется массив записей (в терминологии Паскаля) или массив структур (в терминологии Си). Поле, по значению которого производится сортировка, называется ключом сортировки. Обычно оно имеет числовой тип. Например, массив сортируемых записей содержит два поля: наименование товара и количество товара на складе. В программе на Паскале он описан так:

Сортировка производится либо по возрастанию, либо по убыванию значения ключа A[i].key.

Во всех дальнейших примерах программ предполагается, что приведенные выше описания в программе присутствуют глобально и область их действия распространяется на процедуры сортировки. Хотя все примеры приводятся на Паскале, но по тому же принципу можно разработать функции сортировки на Си/Си++.

Алгоритм сортировки «методом пузырька» рассматривался в разделе 3.17. Здесь мы обсудим два алгоритма: сортировку простым включением и быструю сортировку.

Сортировка простым включением. Предположим, что на некотором этапе работы алгоритма левая часть массива с 1-го по (i — 1)-й элемент включительно

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

Процесс начинается с левой части, состоящей из одного элемента А[1], а заканчивается, когда правая часть становится пустой.

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

Оценим величину минимальной временной сложности алгоритма. Если массив уже отсортирован, то тело цикла while не будет выполняться ни разу. Выполнение процедуры сведется к работе следующего цикла:

Поскольку тело цикла for исполняется n — 1 раз, то число пересылок элементов массива

Мmin = 2(п - 1),

а число сравнений ключей равно

Сmin = n - 1.

Сложность алгоритма будет максимальной, если исходный массив упорядочен по убыванию. Тогда каждый элемент А[i] будет «прогоняться» к началу массива, т. е. устанавливаться в первую позицию. Цикл while выполнится 1 раз при i = 2, 2 раза при i = 3 и т. д., п — 1 раз при i = п. Таким образом, общее число пересылок записей равно:

Более подходящей для реальной ситуации является средняя оценка сложности. Для ее вычисления надо предположить, что все элементы исходного массива — случайные числа и их значения никак не связаны с их номерами. В таком случае результат очередной проверки условия x. key<A[j].key в цикле While также является случайным.

Разумно допустить, что среднее число выполнений цикла While для каждого конкретного значения i равно i/2, т. е. в среднем каждый раз приходится просматривать половину последовательности до тех пор, пока не найдется подходящее место для очередного элемента

Тогда формула для среднего числа пересылок (средняя оценка сложности) будет следующей:

Как максимальная, так и средняя оценка сложности алгоритма квадратична (является полиномом второй степени) по параметру п — размеру сортируемого массива.

Алгоритм быстрой сортировки. Этот алгоритм был разработан Э. Хоаром. В алгоритме быстрой сортировки используются три идеи:

• разделение сортируемого массива на 2 части, левую и правую;

• взаимное упорядочение двух частей (подмассивов) так, чтобы все элементы левой части не превосходили элементов правой части;

• рекурсия, при которой подмассив упорядочивается точно таким же способом, как и весь массив.

Для разделения массива на две части нужно выбрать некоторое «барьерное» значение ключа. Это значение должно удовлетворять единственному условию: лежать в диапазоне значений для данного массива (т. е. между минимальной и максимальной величиной). За «барьер» можно выбрать значение ключа любого элемента массива, например первого, или последнего, или находящегося в середине.

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

Сложность алгоритма быстрой сортировки. Исследование временной сложности алгоритма быстрой сортировки является очень трудоемкой задачей, и поэтому мы здесь приводить его не будем. Рассмотрим лишь окончательный результат этого анализа. Временная сложность T как функция от п — размера массива — по порядку величины выражается следующей формулой:

Т(п) = 0 (n 1n (n)).

Здесь использовано принятое в математике обозначение: O(х) обозначает величину порядка х. Следовательно, временная сложность алгоритма быстрой сортировки есть величина порядка п 1n(n). Эта величина для целых положительных п меньше, чем п2 (вспомним, что алгоритм сортировки простым включением имеет сложность порядка n2). И чем больше значение п, тем эта разница существеннее. Например:

Лекции на основе электронного учебника «Основы программирования на C++, PASCAL» с сайта © ***** | All Rights Reserved
Designed by SysADMIN XHTML | CSS