Лабораторная работа 11. Программирование рекурсивных алгоритмов

Рекурсивные функции

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

Говоря кратко, рекурсивной называется функция, в которой имеется обращение к ней самой. Алгоритм быстрой сортировки, заключается в использовании «процедурыа разделения», присмснясмая к фрагменту массива (изначально - ко всему массиву). На каждом шаге образовывались две половинки текущего фрагмента, и к ним снова нужно было применять процедуру разделения. То есть но своей сути алгоритм является рекурсивным, и если не здесь приме­нять рекурсивные функции, то где?..

К счастью, любая функция в программе на C++ может вызываться рекурсивно. При этом в стеке выделяется новый участок памяти для размещения копий пара­метров, а также автоматических и регистровых переменных, поэтому предыдущее состояние выполняемой функции сохраняется, и к нему впоследствии можно вер­нуться (так и произойдет, если только вата программа где-нибудь не зависнет). Одна из возможных версий программы сортировки приведена ниже. «include < lostream.h>

#include < iostream.h>

void qsort(f1oat* array, int left, int right);

int main(){

const int n = 10;

float arr[n];

int i, l, r;

cout < < " Введите элементы массива: ";

for (i= 0; i < n; i++) cin > > arr[i1];

l=0; r= n - 1; // левая и правая границы начального фрагмента

qsort(arr, l, r); // 1

for (i= 0; i< n; i++) cout< < аrr[i] < < ' ';

return 0;

}

void qsort(float* array, int left, int right){

int 1= left, j = right;

float middle = array[(left * right) / 2];

float temp;

while (i < j) {

while (array[i] < middle) i++;

while (middle < array[j]) j--;

if (i < =j) {

temp = array[i];

array[i]= array[j]:

array[j] = temp;

i++;

j--; }

}

if (left < j) qsort(array, left, j);

if (i < right) qsort(array, i, right); }

}}

Мы не будем подробно анализировать эту программу, поскольку алгоритм уже использовался. Единственное изменение это то, что процедура разделения реализована здесь в виде рекурсивно вызываемой функции qsortt). в теле которой есть два обраще­ния к самой себе: в операторе 2 — для сортировки левой (юловннки текущего фраг­мента, и в операторе 3 — для сортировки его правой половинки. Однако, у рекурсии есть и недостатки: во-первых, такую программу труднее отлаживать, поскольку требуется контролировать глубину рекурсивного обращения, во-вторых, при большой глубине стек может переполниться, а в-третьих, использование рекурсии повышает накладные расходы (например, в данном случае в стеке сохраняются отнюдь не два числа, представляющие собой границы фрагмента, а гораздо больше, не говоря уже о затратах, связанных с вызовом функции). Поэтому рекурсию при всей ее красоте следует применять с осторожностью.

Многофайловые проекты

До сих пор мы писали программы, исходный текст которых размешался в одном файле. Однако, реальные задачи требуют создания многофайловых проектов с рас­пределением решаемых подзадач по разным модулям (4> айлам).

Напомним, что пользуясь технологией нисходящего проектирования программ. мы разбиваем исходную задачу на подзадачи, затем при необходимости каждая из них также разбивается на подзадачи, и так далее, пока решение очередной подза­дачи не окажется достаточно простым, то есть реализуемым в виде функции обо­зримого размера (как уже указывалось, наиболее предпочтительным считается размер не более одного-двух экранов текстового редактора). Исходные тексты совокупности функций для решения какой-либо подзадачи, как правило, размешаются в отдельном модуле (файле). Такой файл называют исход-i: f.4 (source 1Не). Обычно он имеет расширение.с или.срр. Прототипы всех функ­ций исходного файла выносят в отдельный так называемый заголовочный файл (headerfile), для него принято использовать расширение.h или.hop.

Таким образом, заголовочный файл ххх.h содержит интерфейс для некоторого на­бора функций, а исходный файл ххх.ерр содержит реализацию этой ■ набора. Если некоторая функция из указанного набора вызывается из какого-то другого исход­ного модуля ууу. срр. то вы обязаны включить в этот модуль заголовочный файл ххх. h с помощью директивы #t ncl ибе'. Негласное правило стиля программирования на C++ требует включения этого же заголовочного файла (с помощью#include> и в исходный файл ххх.ерр.

Теперь о глобальных переменных. В многофайловом проекте возможны два «вида глобальности». Если некоторая глобальная переменная glvarl объявлена в файле ххх.ерр с модификатором static, то она видима от точки определения до конца этого файла, то есть область ее видимости ограничена файлом. Если же другая гло­бальная переменная gl var2 объявлена в файле ххх.ерр без модификатора static, то она может быть видимой в пределах всего проекта. Правда, для того, чтобы она оказалась видимой в другом файле, необходимо иметь в этом файле ее объявление с модификатором extern (рекомендуется это объявление помес­тить в файл ххх. п).

Что и как следует размещать в заголовочном файле

В заголовочном файле принято размещать:

□ определения типов, задаваемых пользователем, констант, шаблонов;

□ объявления (прототипы) функций;

Q объявления внешних глобальных переменных (с модификатором extern); -J пространства имен¹.

Теперь обратим ваше внимание на проблему повторного включения заголовочных файлов. Проблема может возникнуть при иерархическом проектировании струк­тур данных, когда в некоторый заголовочный файл ууу. h включается при помощи директивы #inclixte другой заголовочный файл ххх. h (например, для использова­ния типов, определенных в этом файле). Впрочем, лучше рассмотреть эту пробле­му на конкретном примере.

Ниже приведены тексты очень простой многофайловой программы, в которой опре­делены типы данных «Точка» (структура Point в файле Point.h) и «Прямоуголь­ник» (структура Reel в файле Rect.п). Поскольку второй тип данных определяется через первый, в файле Rect.г имеется директива (Hnclude " Point.h".

В основном модуле maln.cpp просто создаемся объект типа «Прямоугольник»¹ и выводятся координаты его левого верхнего и правого нижнего углов. В основном модуле используются как функции из модуля Point.срр. так и функции из модуля Rect.срр. поэтому в него включены оба заголовочных файла Point.h и Rect.h. Но после обработки этих директив препроцессором окажется, что структура Point оп­ределена дважды. В результате компилятор выдаст сообщение об ошибке наподо­бие следующего: «error...: 'Point': 'struct' type redefinition».

iiilUilll Файл Polnt.h HIIIIUII

а Объявления тигов

struct Point 1 int x: tnt y:

):

// Прототипы функций

void SetXYlPointi point, int x. 1nt y):

mt GetX(Polnt4 point):

int GetY(Pomt4 point):

aaaaa Файл Rect.h Ulllll/ll . #tnclude " Point.h" // Объявление типов struct Rect {

Point leftTop:

Point rlghtBottom;

):

// Прототипы функций

void SetlTR8(Rect& rect. Point It. Point rb):

void GetlTlRectS rect. Pointi It):

void GetRBfRecti rect. Point* rb);

aaaaa Файл Point.cpp шиши linclude -Point.h"

void SetXKPoint* point. 1nt x. int y) {

point.x - x:

polnt.y - y: I

Int Getx(Po1nt& point) { return point.x:

int GetVtPoinU point) { return point.y:

)

Ullllllll Файл Rect.cpp Ullllllll #include -Rect.h"

void SetLTR6(Rect4 rect. Point It. Point rb) {

rect.leftTop - It:

rect.rlojitBottom - rt>; J

void GeUT(Rect& rect. Points It) {

It - rect.leftTop; I

void GetRB(fiect& rect. Point* rb) { rb - rect.rightBotto»:

I

♦ include < stdio.h>

♦ include -point.h" «Include 'Rect.h"

llllllllll Файл Main.cpp Ullllllll int ma1n(){

Point ptl, pt2. It. rb:

Rect recti:

SetXY(ptl. 2. 5); SetXY(pt2. 10. 14);

SetLTRBtrecti, ptl. pt2);

GetLKrectl. It):

GetRB(rectl. rb):

printfCrect.lt.x - Xd. rect.lt.y - Xd\n". It.x. lt.y):

printfCrect.rb.x - Xd. rect.rb.y - Xd\n\ rb.x. rt.y);

return 0; } Каков выход из этой ситуации? Бьерн СтрауструЛ рекомендует использовать так называемые стражи включения, и этот способ нашел широкое применение. Он со­стоит в следующем; чтобы предотвратить повторное включение заголовочных фай­лов, содержимое каждого. h-файла-должно находиться между директивами услов­ной компиляции #1fndef и #endif. как описано ни#е: #ifndef FILEW*_H

Heffne FILENMC.H

/* содержимое эасогювочного файла */

lendlf /* FILENAMEH */ Применительно к нашему примеру файл Point.h должен содержать следующий текст;

IIIIIIIIII «айп Point.h UIIUUU #ifndef P01NT_H Wefine POINT.H // Объявления типов struct Point {

int x;

int y: )i

// Прототипы функций void SetXY(Polnt& point, int x. int y): int GetX(Polnt4 point): int GetYfPoint* point):

#endif /* P0INT_H •/ Реюлиндуем вам проверить рассмотренный пример на вашем компиляторе.

Задача 7.7. Многофайловый проект — форматирование текста

Написать программу форматирования текста, читаемою из файла unformt.txt и состоящего из строк ограниченной длины. Слова в строке разделены произвольным количеством пробелов. Программа должна читать входной файл по строкам, qbop-матировать каждую строку и выводить результат в выходной файл formtd. txt. Форматирование.заключаете* в выравнивании границ текста слева и справа пу­тем равномерного распределения пробелов между соседними словами, а также в отступе с левой стороны страницы на margin позии/лй, то есть результирующий текстдолжен находиться в позицияхmargin ♦ 1..margin • maxljine. Кроме этого, программа должна подсчитать общее количество слов в тексте.

На примере этой задачи мы показываем технологию разработки многофайловых

проектов.

Алгоритм решении задачи не представляет особой сложности:

1. Открыть входной фай л.

2. Читать файл построчно в текстовый буфер line, попутно удаляя возможные пробелы в начале строки (да первого слова).

3. Для каждойстроки line выполнить следующие действия:

■ Вычислить величину интервала (количество пробелов), которую необходи­мо обеспечить между соседними словами для равномерного распределения слов в пределах строки.

■ Вывести каждое слово из строки 1i пе в выходной файл, вставляя между сло­вами необходимое количество пробелов и одновременно увеличивая счет­чик слов па единицу.

4. После обработки последней строки входного файла вывести на экран значение

счетчика слов и закрыть выходной файл. Разбиение на подзадачи.

В результате детализации описанного алгоритма определяем спецификации нуж­ных нам функций:

Q void Definter (const char* pline. int 8 base_int. int A adoMnt. lot S inter) определяет для строки, на которую указывает pi ine. количество межсловных промежутков inter, требуемую величину основного интервала base^int для каж­дого промежутка (количество пробелов) и величину дополнительного интер­вала add_int. определяемую как остаток от деления общего количества пробе­лов в строке на количество межсловных промежутков; последняя величина должна быть равномерно распределена путем добавления одного пробела в каж­дый из первых add_mt промежутков;

□ void Getltne (FILE* finp. char* pi ine) читает очередную строку из входного файла в массив символов с адресом р1 ire. ликвидируя при этом пробелы в на­чале строки;

Q void Ptrtlfiterval (FILE* 'out. const int k) выводит очередной интервал, состо­ящий из К пробелов;

□ Int PutWord (FILE* fout. const char* pline. const int startpos) выводит очеред­ное слово в выходной файл, начиная с позиции startpos текущей строки pi ine; возвращает номер позиции в строке pltne, следующей за последним передан­ным символом, или 0 — если достигнут конец строки;

Q int SearchNextWord (const char* pline. const int curpos) возвращает номер пози­ции, с которой начинается следующее слово в строке pi ine. или 0. если достиг­нут конец строки (поиск начинается с позиции curpos).

Разбиение на модули.

Наша программа будет располагаться Р двух исходных файлах: task7_7.cpp — с функцией main, edi t.срр - с реализацией перечисленных выше функций, а также заголовочный (райл edit.h с ннтер< ]> ейсом этих функций. Ниже приводится содержимое этих файлов.

Illllllllllllltlllllttllllllllllllltlllllinitllllltlltlltl

II Файл Task7_7.cpp

♦ include < stdio.h>

♦ include < strlng.h>

«include < stdlib.h>

♦ include " edit.h"

// Глобальные перевен^ые const irt maxlHne - 63: const int margin - 5;

 

12345

Поделиться:

Популярное:

1. I.8. Работа является поклонением
2. III. Сообщение темы и целей урока. Работа над новым материалом.
3. IV. РАБОТА МЕЖДУНАРОДНОЙ КОНФЕРЕНЦИИ
4. IV. РАБОТА, МОЩНОСТЬ, ЭНЕРГИЯ.
5. АДАПТАЦИЯ И ОПИСАНИЕ ИСПОЛЬЗУЕМЫХ АЛГОРИТМОВ
6. Б. Работа над «телом» в классе
7. Б. Работа над тестом курсовой
8. Бедные предпочитают получать деньги за отработанные часы.
9. БОГАТЫЕ НЕ РАБОТАЮТ НА ДЕНЬГИ
10. Богатые не работают ради денег
11. В Украине компания официально работает с 1998 года.
12. Важнейший фактор перераспределения богатства – это ростовщические проценты на деньги, которые ежедневно переводят деньги от тех, кто работает, к тем, кто владеет капиталом.