А.А. Белеванцев, С.С. Гайсарян, Л.С. Корухова, Е.А. Кузьменкова, В.С. Махнычев. Семинары по курсу Алгоритмы и алгоритмические языки (1108027), страница 5

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

Текст из файла (страница 5)

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

Для обеспечениявозможности изменять значения передаваемых в качестве параметров объектовнеобходимо использовать указатели, при этом моделируется передача параметров поссылке: формальные параметры связываются (ссылаются) с той же областью памяти, что ифактические.5.1.2. Понятие указателяУказатель – это переменная, значением которой является адрес некоторого объекта.Пример определения указателя:19int x, *p;Здесь x - переменная целочисленного типа, p - указатель на объект целочисленноготипа. Указатель p может содержать адрес любого объекта целочисленного типа.Для указателей определены операции & (взятие адреса объекта) и * (операцияразыменования, взятие значения по адресу).

Например, при выполнении оператора:p = &x;в переменной p будет зафиксирован адрес переменной x, а при выполнении оператора:*p = 10;объекту, на который ссылается указатель p, будет присвоено значение 10.Использование указателей в качестве параметров функции проиллюстрируем напримере следующей задачи.Задача 1.

Описать функцию, меняющую местами две целочисленные переменные.Попробуем решить задачу без использования указателей, описав функцию swap:voidswap (int a, int b){int tmp = a;a = b;b = tmp;}Проверим полученный результат:int x = 1, y = 2;swap (x, y);printf ("%d %d\n", x, y);На стандартный поток вывода будет выведено:1 2Следовательно, значения переменных не изменились! Это и понятно, потому чтопараметры функции swap передаются по значению и, следовательно, поменялисьместами только копии параметров x и y внутри функции, при этом никакого влияния насами фактические параметры x и y не произошло.Для достижения нужного эффекта необходимо в качестве параметров функциииспользовать указатели на соответствующие переменные, т.е.

передавать в функциюадреса переменных, значения которых требуется поменять:voidswap (int *pa, int *pb) // обмен местами *pa и *pb{int tmp = *pa;*pa = *pb;*pb = tmp;}20Убедимся в работоспособности данного варианта функции swap:int x = 1, y = 2;swap (&x, &y); // передаем в функцию адреса переменных x и yprintf ("%d %d\n", x, y);На стандартный поток вывода будет выведено:2 1Следовательно, обмен значений переменных действительно произошел. Работуданного варианта функции swap иллюстрирует следующий рисунок:вызывающая функцияswappa:x:pb:y:Рис.

3. Работа функции swapТаким образом, для обеспечения непосредственного доступа к объектам ввызывающей функции (в частности, для модификации их значений) соответствующиепараметры должны передаваться в виде указателей на эти объекты.5.2. Рекурсивные функцииПонятие рекурсии. Примеры рекурсивных определений. Рекурсия и итерация.Методика разработки рекурсивных функций. Задачи.5.2.1.

РекурсияРекурсия подразумевает использование в определении некоторого понятия самогоопределяемого понятия. В качестве примера рекурсивного определения рассмотримопределение понятия <выражение> :<выражение> ::= <терм> | <выражение> <операция> <выражение><терм> ::= <число> | <переменная> | <обращение к функции> | (<выражение>)Здесь в определении понятия <выражение> используется само определяемое понятие.Рекурсивным может быть и определение функции. Например, функциювычисления n! рекурсивно можно определить так:n! =1,n = 0,n * (n - 1)!, n>0В этом определении n! определяется через (n - 1)!,т.е.

также имеется рекурсивное определение.21Заметим, что ту же функцию n! можно определить и без использования рекурсиикак произведение последовательных целых чисел от 1 до n. Такому определению будетсоответствовать итеративная реализация функции, использующая цикл для вычисленияпроизведения указанных чисел.Задача 1.

Привести рекурсивную и итеративную реализацию функции n!.Воспользуемся приведенными выше определениями функции n!.Рекурсивная реализация:unsigned intfact (unsigned int n){return (n < 2) ? 1 : n * fact (n-1);}Промоделируйте вычисление fact(3).Итеративная реализация:unsigned intfact (unsigned int n){int i, f = 1;for (i = 2; i <= n; i++) {//цикл для вычисления факториалаf *= i;}return f;}Сравните предложенные реализации с точки зрения их эффективности.Задача 2.

На стандартном потоке ввода задан текст (последовательность символов,заканчивающаяся точкой, точка в текст не входит). На стандартный поток вывода вывестиэтот текст в обратном порядке.Приведем рекурсивную реализацию решения задачи.voidprint_rev (void){char ch;scanf ("%c", &ch); //ввод очередного символаif (ch != '.') {print_rev (); //рекурсивный вызов для обработки//оставшихся символовprintf ("%c", ch); //вывод символа}}В предложенной реализации для хранения очередного вводимого символаиспользуется локальная переменная ch.

Реализация механизма обработки вызововфункций предусматривает для каждого вызова функции print_rev создание своегоэкземпляра этой локальной переменной и размещение ее в стеке (в стековом фреймефункции – области памяти в стеке, используемой для работы функции). Аналогичнымобразом обрабатываются и параметры функции. При выходе из функции выделенная ей встеке память освобождается.Промоделируйте работу функции print_rev на примере текста "abcd.".22При разработке рекурсивных функций целесообразно следовать следующейметодике. Как правило, тело рекурсивной функции содержит условный оператор if, однаиз ветвей которого (нерекурсивная) обеспечивает выход из рекурсии (эта ветвь реализуетобработку простейших случаев исходных данных), а вторая (рекурсивная) реализуетобработку всех остальных случаев исходных данных, используя при этом рекурсивныйвызов самой определяемой функции.

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

Особенно хорошо это видно при обработке структур данных,предполагающих внутри себя рекурсию, таких как списки, деревья и т.д. Однако за счетнакладных расходов на обеспечение рекурсивных вызовов функции рекурсивнаяреализация проигрывает итеративной в эффективности как по памяти, так и побыстродействию.5.3. Задачи для самостоятельного решенияФункции5.3.1. Описать функцию, которая проверяет, обладает ли целое неотрицательноечисло n указанным свойством. В случае положительного ответа функция возвращаетзначение 1 и 0 в противном случае.

Свойства:a) n является полным квадратом,b) n является простым числом,c) n является степенью числа 3.5.3.2. Программа. На стандартном потоке ввода задано число n (n > 0) ипоследовательность из n целых чисел. Описав соответствующую функцию, найтиколичество элементов последовательности, являющихся:a) числами Фибоначчи (задаются соотношениемf0 = 1, f1 = 1, fk + 1 = fk - 1+ fk, k >1),b) палиндромами.5.3.3. Пусть n – целое неотрицательное число. Описать функцию от параметра n,которая находит:a) сумму цифр этого числа,b) максимальную цифру в десятичной записи этого числа,c) количество нечетных цифр в десятичной записи этого числа.Рекурсивные функции5.3.4. Рекурсивно описать функцию вычисления xn для вещественного x (x ≠ 0) ицелого n:23nx =1при n = 0,1 / x|n| при n < 0,x * x n-1 при n > 0.Протестировать эту функцию на подходящих наборах входных данных.5.3.5.

Рекурсивно описать функцию с(m, n), где 0 ≤ m ≤ n, для вычислениябиномиального коэффициента Cnm по формуле:Cn0 = Cnn = 1, Cnm = Cn-1m + Cn-1m-1 при 0 < m < n.5.3.6. Программа. Рекурсивно описать функцию вычисления НОД(n, m) наибольшего общего делителя неотрицательных целых чисел n и m, основанную насоотношении НОД(n, m) = НОД(m, r), где r – остаток от деления n на m.

С ее помощьюнайти наибольший общий делитель натуральных чисел a и b. Сравнить эффективностьрекурсивной и нерекурсивной реализации функций вычисления НОД.5.3.7. Программа. Рекурсивно описать функцию вычисления НОД(n1, n2, n3, ..., nm),где m > 2, воспользовавшись для этого соотношением:НОД(n1, n2, n3, ..., nk) = НОД(НОД(n1, n2, n3, ..., nk-1), nk), k = 3, 4, ... , m.С помощью этой функции найти НОД (a1, a2, a3, ..., a10).5.3.8. Программа. Числа Фибоначчи задаются соотношением:f0 = 1, f1 = 1, fn + 1 = fn - 1+ fn, n >1.Рекурсивно описать функцию вычисления n-ого числа Фибоначчи и с ее помощьювычислить 10-е число Фибоначчи.5.3.9.

Пусть n – целое неотрицательное число. Рекурсивно описать функцию отпараметра n, которая находит:a) сумму цифр этого числа,b) максимальную цифру в десятичной записи этого числа,c) старшую (самую левую) цифру в десятичной записи этого числа.5.3.10. На стандартном потоке ввода задан текст (последовательность символов,заканчивающаяся точкой, точка в текст не входит). Рекурсивно описать функцию, котораяподсчитывает количество цифр в данном тексте.5.3.11. Программа.

Характеристики

Список файлов семинаров