Цель лабораторной работы: изучить программирование задач, в которых оправдано использование рекурсивных функций в С++. Одни из таких задач – это задачи синтаксического разбора текста. Для лабораторной работы предполагается сделать разбор строки на соответствие некоторым правилам.
Теоретические сведения
Строки как массивы символов
В С++ есть два вида строк: С-строки и класс стандартной библиотеки С++ string. С-строка представляет собой массив символов, завершающийся символом с кодом 0. (Этот вид строк пришел в С++ из языка С). Класс string более безопасен в использовании, чем С-строки, но и более ресурсоемок. Для грамотного использования этого класса необходимо знание объектно-ориентированной технологии, поэтому здесь мы будем рассматривать только С-строки.
Строки как массивы символов могут быть как статические (память выделяется компилятором до работы программы), но и динамические (память выделяется, когда это нужно программе).
Будем сначала рассматривать статические С-строки, для которых изначально надо задать длину. Длину удобно задавать с помощью именованной константы, поскольку такой вариант хорошо читается и при возможном изменении длины строки потребуется изменить программу только в одном месте.
const int LEN_STR = 80;
char str[LEN_STR];
При задании длины необходимо учитывать завершающий нуль-символ. В приведенной выше строке можно хранить не 80 символов, а только 79.
Строки при объявлении можно инициализировать строковыми константами, при этом нуль-символ в позиции, следующей за последним заданным символом, формируется автоматически.
char a [100] = “Never trouble trouble”; // выделено 100 байтов памяти для
// хранения 99 символов
Если строка объявляется и инициализируется сразу же, ее размерность можно опускать (компилятор сам выделит память, достаточную для размещения всех символов строки и завершающего нуля):
char a [ ] = “Never trouble trouble”; // 22 символа
Операция присваивания одной строки другой не определена, поскольку строка является массивом, и может выполняться с помощью цикла (посимвольно) или с помощью функций стандартной библиотеки.
Можно ли вводить и выводить строки с помощью cin/cout?
Пример 1
#include <iostream>
int main ( )
{ const int N = 80;
char s[N];
cin >> s;
cout << s << endl;
return 0;
}
Здесь строка вводится точно так же, как переменные известных нам типов. Можно запустить программу и ввести строку, состоящую из одного слова. Ввод работает, на экране будет введенное слово. Если же ввести строку, состоящую из нескольких слов, то на экране появится только первое слово. Это связано с тем, что ввод выполняется до первого пробельного символа (пробела, знака табуляции, символа перевода строки). Иногда имеет смысл каждое слово строки вводить в отдельную строковую переменную.
Чтобы ввести строку, состоящую из нескольких слов, в одну строковую переменную, используются методы getline или get класса istream ( iostream), объектом которого является cin. Синтаксис вызова метода объекта
cin.getline (…); или cin.get (…);
Пример 2
#include <iostream>
int main ( )
{ const int N = 80;
char s[N];
cin.getline (s, N);
cout << s << endl;
cin.get (s, N);
cout << s << endl;
return 0;
}
Метод getline считывает из входного потока N-1 символов или менее (если символ перевода строки встретится раньше) и записывает их в строковую переменную s. Символ перевода строки также считывается (удаляется) из входного потока, но не записывается в строковую переменную, вместо него размещается завершающий 0. Если в строке данных больше N-1 символа, следующий ввод будет выполняться из той же строки, начиная с первого несчитанного символа.
Метод get работает аналогично, но оставляет в потоке символ перевода строки. В строковую переменную добавляется завершающий 0. Удаление символа перевода строки \n может быть осуществлено вызовом метода get ( ) без параметров.
Удобнее использовать метод getline. Если в программе требуется ввести несколько строк, метод getline удобно использовать в заголовке цикла.
Пример 3
#include <iostream>
int main ( )
{ const int N = 80;
char s[N];
while (cin.getline (s, N))
{ cout << s << endl;
… // обработка строки
}
return 0;
}
Существуют стандартные функции для работы со строками.
Для строк не определена операция присваивания, поскольку строка является не основным типом данных, а массивом. Присваивание строки можно осуществить поэлементным копированием или с помощью стандартной функции копирования строк.
Пример 4 – копирование строки с помощью функции strcpy ( )
#include <iostream>
#include <string.h>
int main ( )
{ const int N = 80; // максимальная длина строки
char s1[ ] = “Нет в мире совершенства”;
char s2[N];
strcpy (s2, s1); // строка s1 копируется в строку s2
cout << s2 << endl;
return 0;
}
Строки можно сцеплять.
Пример 5 – объединение строк с помощью функции strcat ( )
#include <iostream>
#include <string.h>
int main ( )
{ const int N = 80; // максимальная длина строки
char s1[N] = “Следующая лабораторная ”;
char s2[ ] = “будет в пятницу”;
strcat (s1, s2); // к строке s1 приписывается строка s2
cout << s2 << endl;
return 0;
}
Функция strlen ( s) возвращает фактическую длину строки s без 0-символа.
Рекурсия в программировании
Программист разрабатывает программу, сводя некоторую задачу к более простым подзадачам. Среди этих подзадач может оказаться первоначальная задача, но в упрощенной форме. Например, вычисление функции F (n) может потребовать вычисления F (n-1) и еще каких-то действий. Другими словами, частью алгоритма вычисления функции является вычисление той же самой функции. Алгоритм, который являетсясвоей собственной частью, называется рекурсивным алгоритмом.
Эту ситуацию можно сравнить с экраном телевизора, на котором показывают тот же самый телевизор, на экране второго – тот же самый телевизор и так далее.
Возможно, многие попадали в ситуацию, когда, пытаясь строго определить некоторое понятие, приходилось строить определение понятия, опираясь на само это понятие. Определение называется рекурсивным, если оно задает элементы некоторого множества с помощью других элементов этого же множества. Объект, заданный рекурсивным определением, называется рекурсивным, а использование таких объектов – рекурсией.
Рекурсивных определений много в математике.
Например, определение натурального числа:
1 – есть число натуральное.
Число, следующее за натуральным, есть число натуральное.
Рекурсивные определения эффективны, их эффективность состоит в том, что с помощью конечного высказывания мы определяем бесконечное множество объектов.
Другой пример – степенная функция.
1, если n = 0,
xn = xn-1 * x, если n > 0
Рекурсивное определение всегда состоит из двух частей: это базовая (базисная) часть и рекурсивная (индуктивная) часть. Базовая часть задает определение для фиксированной группы объектов. Например, в базовой части утверждается, что “1 – есть число натуральное” или “xn = 1, если n = 0”. Рекурсивная часть определяет бесконечное множество объектов. Она записывается таким образом, чтобы при цепочке повторных применений она редуцировалась бы (приводилась) к базе.
Например, “объект 3” может быть квалифицирован как натуральное число после применения рекурсивной части определения, которая утверждает, что 3 является натуральным числом, если 2 – число натуральное. Теперь применяем рекурсивную часть определения к числу 2 и получаем утверждение, что 2 – есть число натуральное, если 1 – число натуральное. Пришли к базовой части, заключающей, что 1 – есть натуральное число. Отсюда можно сделать вывод, что 2 – натуральное число, тогда и 3 – число натуральное.
Рекурсивных определений много в программировании. Самый простой пример – определение составных операторов (условных, циклов и так далее). Все составные операторы в свою очередь состоят из операторов. Таким образом, представители понятия “оператор” являются рекурсивными. Но вот оператор присваивания определяется без рекурсии, это простой оператор.
Рекурсивные функции
Рекурсия возможна и очень полезна в программировании. До сих пор при записи алгоритмов мы не использовали рекурсию, алгоритмы функций и самих программ записывали как последовательность действий, применяя так называемое операторное программирование.
Существуют языки программирования только операторного типа, например, Фортран. Такие же языки программирования как Паскаль или С++ - это процедурные языки с возможностью рекурсивного программирования. Эта возможность представлена в алгоритмических языках механизмом рекурсивных процедур и функций.
Процедура (функция) называется рекурсивной, если она в процессе выполнения явно или неявно вызывает сама себя. Прямая (явная) рекурсия характеризуется существованием в теле процедуры (функции) оператора обращения к ней же самой. В случае косвенной (неявной) рекурсии процедура (функция) обращается сама к себе через цепочку вызовов других процедур (функций).
Прямая рекурсия Косвенная рекурсия
Прямая рекурсия
Самовызов функции по своей сути ничем не отличается от вызова любой другой обычной функции. Вспомним, что происходит, когда программа или некоторая функция вызывает другую функцию.
1) В специальной области памяти (стеке) размещаются параметры и локальные переменные функции.
2) В другой области памяти (области программы) сохраняются значения внутренних переменных программы или вызывающей функции.
3) Запоминается адрес возврата в программу или вызывающую функцию.
4) Управление передается вызванной функции и выполняются ее операторы.
Если функцию вызвать из нее же самой, то будет происходить то же самое, будут выполняться те же действия, но с другими значениями параметров и другими значениями внутренних переменных. Будет занята другая часть памяти. Это и дает возможность рекурсивно вызывать процедуры и функции.
Рассмотрим классический пример рекурсии – вычисление факториала.
N! = 1 * 2 * 3 * ... * (N-1) * N.
Можно написать функцию вычисления факториала, используя цикл. Это так называемый итерационный вариант.
long fact(long n)
{ if (n < 0) return -1;
long f = 1;
for (long i = 1; i <= n; i++)
f *= i; // f = f * i
return f; }
Но определение факториала – это рекурсивное определение. Его можно записать таким образом:
1, если N=0 или N=1
N! = N * (N-1)! , если N>1
Поскольку определение рекурсивное, то не сложно записать рекурсивную функцию. Это будет целая функция с целым аргументом.
…
long fact(long);
int main()
{ cout << “3!=” << fact(3) << endl;
cout << “5!=” << fact(5) << endl;
return 0;
}
// рекурсивное описание функции
long fact(long n)
{ if (n < 0) return -1;
if (n == 0 || n == 1) return 1; // return (n > 1) ? n * fact(n-1) : 1;
return n * fact(n-1);
}
Рассмотрим, как будет выполняться рекурсия, например, при n = 3. Первый вызов нашей функции будет из основной программы, например, так
fact(3)
При каждой активации функции будет появляться свой набор значений параметров и локальных переменных (сигнатура), в данном случае локальных переменных нет, “размножаться” будет только параметр n.
1-ый вызов (n=3)
n = 3
3*fact(2)
2-ой вызов (n=2)
2*fact(1)
3-й вызов (n=1)
К одной и той же функции fact мы будем обращаться несколько раз с разными значениями n до тех пор, пока при n=1 мы не получим значение fact (это 1). При n=1 вход в следующую рекурсию заканчивается и идет возвращение в точку вызова. В результате возвратов получаем
1*2 (это 2!) *3 (это 3!) = 6. Это значение и будет напечатано на экране.
При написании рекурсивных функций важным моментом является организация выхода изфункции, то есть в функции должен быть обязательно оператор, который останавливает рекурсию (“стоп-условие”). В нашем случае это условие n=1, оно не ведет за собой новой рекурсии. “Стоп-условие” должно быть обязательно, иначе придем к возникновению бесконечной рекурсии.
Максимальное количество одновременно существующих экземпляров локальной памяти, относящихся к рекурсивной функции, называется глубиной рекурсии. Можно также определить глубину рекурсии как максимальное число незавершенных рекурсивных вызовов. Глубина рекурсии для данного примера равна трем.
Схематично это можно изобразить следующим образом.
| |
|
|
à F(2)
|
|
|
à F(1)
|
|
ß F(2)
|
Если глубина рекурсии будет чересчур большой, то автоматической памяти (стека), предоставленной процессу выполнения программы может не хватить
В процессе рекурсии неизбежны так называемые вложенные вызовы. Общим числом вложенных вызовов, порожденных данным вызовом рекурсивной подпрограммы, называется количество вызовов, выполненных между его началом и завершением.
Глубина рекурсии влияет на объем занимаемой памяти в стеке, а общее количество вложенных вызовов -–на длительность выполнения.
Использование рекурсивных подпрограмм требует осторожности и умения оценить возможную глубину рекурсии и общее количество вызовов.
Рекурсивная форма записи алгоритма обычно выглядит изящнее, чем итерационная и дает более компактный вариант программы. Однако, если существует очевидное итерационное решение задачи, то лучше воспользоваться именно им, чтобы не провоцировать дополнительные затраты времени (на вложенные вызовы) и памяти (на хранение данных).
В примере с факториалом задача имеет очевидное итерационное решение и запись задачи в виде рекурсивной функции лишь уменьшает эффективность решения. Кроме того, для вычисления факториала существует еще один алгоритм, который называется построением программ с использованием таблиц.
Если требуется вычислить факториал при не слишком больших значениях n, то можно было бы запомнить все возможные значения факториала в массиве, тем более что растет он очень быстро:
6! = 720
7! = 5040
8! = 40320 и так далее.
Тогда вместо перевычисления факториала всякий раз, когда он понадобится, можно просто найти нужное значение в массиве.
Недостаток подобного метода связан с объемом дополнительной памяти, которая требуется для размещения таблицы.
Подведем итоги. Когда перед вами встает вопрос выбора между рекурсивной и не рекурсивной формой алгоритма, надо помнить следующие правила:
1. Если сложность рекурсивной и не рекурсивной версии алгоритма примерно одинакова, то надо отдать предпочтение не рекурсивной из-за большей эффективности.
2. Если построение не рекурсивной версии значительно усложняет алгоритм или требует введения дополнительных сложных структур данных, то следует выбрать рекурсивную версию.
3. Рассматривайте возможность применения программ, управляемых таблицей.
Если же вы все-таки остановились на рекурсии, то надо иметь в виду, что отлаживать рекурсивныйалгоритм всегда труднее. Надо, во-первых, исключить возможность бесконечной рекурсии, то есть необходимо обеспечить и тщательно проверить завершение рекурсии. Во-вторых, для рекурсивных подпрограмм следует более тщательно проверять корректность, допустимость входных и выходных данных, чтобы исключить ошибки и возможность бесконечной рекурсии. В-третьих, при создании рекурсивных процедур/функций следует более внимательно относиться к использованию параметров. Неправильно выбранный способ передачи параметров может приводить к ошибкам. Надо также иметь в виду, что так как при активации рекурсивных подпрограмм создаются копии параметров и переменных, то для большей эффективности рекурсии надо сводить к минимуму число параметров и локальных переменных рекурсивных процедур и функций. Дополнительно это позволит избежать некоторых ошибок.
Практически все рекурсивные алгоритмы имеют еще и итерационное решение, но для ряда задач рекурсия очень органична. Примерами является дважды рекурсивная функция Аккермана или задача “Ханойские башни”.
Пример – Ханойские башни.
В центре мира в вершинах равностороннего треугольника в землю вбиты три алмазных шпиля. На одном из них надето 64 золотых диска убывающих радиусов (самый большой – нижний). Буддийские монахи день и ночь переносят диски с одного шпиля на другой. При этом диски надо переносить по одному и нельзя класть больший диск на меньший. Когда все диски перенесут на другой шпиль, наступит конец света. (задачу и рассказ придумал французский математик Э. Люка в 1883 году).
Идея рекурсивного алгоритма не вызывает проблем
Пусть алгоритм P ( m, a, b, c) должен перенести со
b шпиля a на шпиль b с помощью шпиля c m дисков
a c
Запишем этот алгоритм на псевдокоде.
P ( m, a, b, c) :
Если m = 1, то перенести верхний диск со шпиля a на шпиль b
Иначе
P ( m-1, a, c, b);
P ( 1, a, b, c);
P ( m-1, c, b, a);
Другими словами, если m=1, то перенеси один диск с a на b. Если же m>1, то перенеси временно m-1 верхних дисков с a на c, потом перенеси один оставшийся диск с a на b и, наконец, перенеси m-1 дисков, хранящихся на c, на шпиль b. Что касается переноса m-1 дисков, то для этого подойдет тот же алгоритм, но с уменьшенным числом переносимых дисков. Таким образом, мы перейдем от m к m-1, от m-1 к m-2, m-3,... и дойдем до единицы.
Если взять число дисков m слишком большим, то компьютеру, даже быстрому, для решения этой задачи понадобится очень много времени.
Для переноса одного диска требуется одно действие, для переноса двух дисков – 3 действия, можно доказать, что для переноса m дисков с одного шпиля на другой по правилам задачи требуется 2m-1 переноса и нельзя сделать это быстрее.
Если предположить, что каждую секунду монахи переносят один диск, то для переноса башни 64 дисков нужно более 1015 лет. У монахов еще много работы.
..
Некоторые графические задачи в программировании решаются методом наложения кривых. Так рисуются, например, кривые Гильберта или кривые Серпинского.
Кривые Гильберта - это самоподобные кривые, которые чаще всего определяются рекурсивно.
Кривая Гильберта Кривая Гильберта
1-го порядка (H1) 2-го порядка (Н2)
Кривая Гильберта Hi+1 получается соединением 4-х экземпляров Hi вдвое меньшего размера, повернутых соответствующим образом и “стянутых” вместе тремя прямыми линиями. Порядок кривой определяется как максимальная глубина рекурсии, которой достигает функция.
Алгоритм запишется компактно, но он будет достаточно сложный. Чтобы проследить сложность этой функции, надо определить число ее вызовов. На каждом шаге рекурсии эта функция вызывает себя четыре раза, размер проблемы увеличивается в четыре раза. Выполнение этого алгоритма в действительности требует много времени, но есть две причины, по которым он не так уж плох.
Во-первых, ни один алгоритм для построения кривых Гильберта не может выполняться быстрее. Кривые Гильберта состоят из множества сегментов линий, и любой рисующий алгоритм будет занимать очень много времени. Существуют другие алгоритмы для рисования Гильбертовых кривых, но все они работают дольше рекурсивного алгоритма.
Второй факт, который доказывает достоинства описанного алгоритма, заключается в следующем: кривая Гильберта порядка 9 содержит так много линий, что большинство компьютерных мониторов становятся полностью закрашенными. Это не удивительно, поскольку такая кривая содержит 262143 сегментов линий. При глубине выше 9 можно исчерпать все ресурсы компьютера.
Кривые Серпинского – это также самоподобные кривые, которые обычно определяются рекурсивно. Кривая Серпинского второго порядка образуется из четырех кривых Серпинского первого порядка. Кривые Серпинского проще строить с помощью четырех отдельных функций, работающих совместно. Эти функции будут косвенно рекурсивные – каждая из них вызывает другие, которые после этого вызывают первоначальную функцию. Они выводят верхнюю, левую, нижнюю и правую части кривой Серпинского соответственно.
Кривые Серпинского так же полностью заполняют экран большинства компьютеров при порядке кривой, большем или равном 9. Рекурсивный алгоритм здесь по сравнению с не рекурсивным сложный, но достаточно эффективный.
// дальше должен быть синтаксический разбор
Дата: 2019-05-28, просмотров: 232.
