Тема 1.7. Функции и рекурсия
Цель.
Получить навыки оформления одинаковых или почти одинаковых (похожих) фрагментов программы в виде процедур и функций. Научиться передавать нужные параметры разных типов и получать результаты, даже если их много.
Основные понятия.
Описание и определение функции
Передача параметров-значений, адресов и ссылок
Передача массивов, матриц и указателей
Передача параметров в главную функцию
Описание функций с прямой и косвенной рекурсией
Ключевые слова.
Функция, параметр, изменяющийся параметр, вызов функции, возврат одного результата и нескольких результатов, рекурсия
Замечания.
Для демонстрации правильности работы той или иной функции (в этом и последующих разделах) необходимо в программу включать основную функцию и несколько вспомогательных функций.
ПРИМЕР.
Написать функцию с одним параметром (целое n) для вычисления факториалаn! В главной функции продемонстрировать вызовы функций и получение результатов.
Алгоритм.
Будем писать функцию согласно определению факториала.
Решение.
// С++
# include <iostream>
# include <cstdlib>
using namespace std;
int F (int n) // Вариант 1 с рекурсией
{
if ( n < 2 )
return 1;
else
return n*F (n-1);
}
int F2 (int n) // Вариант 2 без рекурсии и с циклом
{
int f=1;
for ( int i=2; i <= n; i++ )
f *= i;
return f;
}
int main ()
{
setlocale (LC_ALL, "RUS");
cout << "Вычисление факториала. ВВедите n = ";
int n;
cin >> n;
cout << F (n) << endl;
cout << F2 (n) << endl;
system ("PAUSE");
return 0;
}
// C#
using System;
class Program
{
public static int F (int n) // Вариант 1 с рекурсией
{
if ( n < 2 )
return 1;
else
return n*F (n-1);
}
public static int F2 (int n) // Вариант 2 без рекурсии и с циклом
{
int f=1;
for ( int i=2; i <= n; i++ )
f *= i;
return f;
}
static void Main (string [] args)
{
Console.WriteLine ("Вычисление факториала. ВВедите n = ");
int n = int.Parse (Console.ReadLine ());
Console.WriteLine (F (n));
Console.WriteLine (F2 (n));
Console.ReadKey ();
}
}
Замечание.
Программы печатают результат 2 раза, т.к. работают 2 варианта функции вычисления факториала.
Задачи для обязательного решения.
В задачах на написание функций исходные данные показывают содержимое передаваемых параметров. Вызов для проверки работы функций и печать результатов выполнять в главной функции.
1.7.1.1. Число сочетаний. Написать рекурсивную функцию longlongintCombiR(int,int) и не рекурсивнуюlonglongintCombi(int,int) с двумя параметрами для вычисления числа сочетаний изnпоk. Результат типаlonglongint(__int64).
1.7.1.2. Написать рекурсивную функцию int MaxR (int * a, int n) для поиска максимума в одномерном целочисленном массиве, который передаётся в качестве первого параметра. Второй параметр – размер массива.
1.7.1.3. Алгоритм Эвклида. Написать рекурсивную функцию intGCD_R(int,int) и не рекурсивнуюintGCD(int,int) с двумя параметрами для вычисления наибольшего общего делителя двух натуральных чисел - своих параметров.
1.7.1.4. Число Фибоначчи. Написать рекурсивную функцию intFibonacci_R(int) и не рекурсивнуюintFibonacci(int) для вычисления числа Фибоначчи по его номеру (передаётся в качестве параметра).
1.7.1.5. Цепная дробь. Даны два массива вещественных чисел размера n. Написать программу для вычисления значения дроби:
A0 + Bn-1 / (A1 + Bn-2 / (A2 + Bn-3 / (... + B1 / (An-1 + B0) ... )))
В первой строке задаётся размер массивов n, во второй строке – массив целых чисел А, в третьей строке – массив целых чисел В. Напечатать результат с точностью 5 знаков после запятой.
Исходные данные:
3
1 1 1
1 1 1
Результат:
1.66667
Задачи для самостоятельного решения.
1.7.2.1. Функция. Функция f(n) определена следующим образом:
f(0)=0,f(1)=1,f(2n)=f(n),f(2n+1)=f(n)+f(n+1). Написать программу, которая по заданному натуральному числу N определяет значение функции f(N). Вводится число N (1 <= N <= 2147483647). Вывести значение f(N).
Исходные данные:
5
Результат:
3
1.7.2.2. Лесенка. Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем предыдущий. Написать функцию, вычисляющую число лесенок, которое можно построить из N кубиков. Параметр функции натуральное число N (1 ≤ N ≤ 100) – количество кубиков в лесенке. Вывести число лесенок, которые можно построить из N кубиков.
Исходные данные:
6
Результат:
4
1.7.2.3. Задача Иосифа Флавия. Выстроим в круг N человек, пронумерованных числами от 1 до N, и будем исключать каждого k-ого до тех пор, пока не уцелеет только один человек.
Например, если N=10, K=3, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним - 5-й, и потом 10-й. Таким образом, уцелеет 4-й.
Написать функцию, которая по заданным N и K (параметры) будет определять номер уцелевшего человека.
Исходные данные:
10 3
Результат:
4
1.7.2.4. Написать рекурсивную функцию для быстрой сортировки целочисленного массива. Параметры: массив целых чисел и два индекса – начало сортируемого куска и его конец.
1.7.2.5. Для заданного «счастливого» числа найти следующее за ним по возрастанию. Счастливое число состоит только из цифр 4 и 7. Функция получает в качестве первого параметра длинное число (в массиве находятся цифры этого числа) и его длину во втором параметре. Результат поместить в тот же массив и вернуть ИСТИНУ. Если результат не умещается в этом массиве, вернуть ЛОЖЬ.
Исходные данные:
47477 5
Результат:
47744
1.7.2.6. Написать функцию для слияния двух упорядоченных массивов. Параметры – сами массивы и их размеры.
1.7.2.7. Написать функцию для вычисления количества слов в тексте. Параметр – строка, содержащая текст из последовательности слов.
1.7.2.8. Написать функцию для перемножения двух прямоугольных матриц. Параметры – сами матрицы и их размеры. Результат возвращается через созданную динамическую матрицу. Проверку правильности задания размеров не выполнять.
1.7.2.9. Найти корень функции методом деления отрезка пополам. Имеется описание непрерывной на отрезке [a,b] функции со значениями разных знаков на концах это отрезка. Написать функцию для вычисления корня этой функции методом деления пополам. Параметры – два вещественных числа – концы отрезка. Результат – вещественное число.
1.7.2.10. Вычисление площади по формуле Симпсона (трапеций). Имеется описание непрерывной на отрезке [a,b] функции. Написать функцию для вычисления площади фигуры, ограниченной этой функцией и осью Х. Параметры – два вещественных числа – концы отрезка. Результат – вещественное число.
1.7.2.11. Вычисление корня квадратного по итерационной формуле Ньютона. Написать функцию с одним параметром – положительным вещественным числом. Результат – корень из этого числа.
1.7.2.12. Интерполяция с помощью полинома Лагранжа. Дан массив значений аргумента x1,x2, ...,xnи массив значений некоторой функции в этих точкахf1,f2, ...,fn. Написать функцию для вычисления значения этой функции в некоторой точке Х. Параметрами функции являются вещественные массивыx,f, число точекnи значение аргумента Х.
Продвинутые задачки.
1.7.3.1. Перестановки. Написать функцию для генерации очередной перестановки в лексикографическом порядке. Функция получает в качестве первого параметра перестановку (в массиве находятся её элементы) и длину перестановки n во втором параметре. Результат поместить в тот же массив и вернуть ИСТИНУ. Если следующей перестановки нет, вернуть ЛОЖЬ.
Исходные данные:
45132 5
Результат:
45312
1.7.3.2. Написать функцию (с рекурсией и без нее) для вычисления функции Аккермана:
Параметры функции неотрицательные целые числа.
Исходные данные:
2 3
Результат:
9
1.7.3.3. Ханойские башни. Имеется 3 вертикальных штырька. На первый из них нанизаны Nколец одно поверх другого, причём ни одно кольцо большего радиуса не находится поверх кольца меньшего радиуса. Два других штырька пустые. За один ход разрешается переставить верхнее кольцо с любого штырька на другой штырёк, но запрещается поверх малого кольца помещать кольцо большего радиуса. Написать программу, которая выведет кратчайшую последовательность перемещений колец с первого штырька на второй. Вывод оформить так, как это показано в примере. В первой строке вывести количество операций, а в остальных – сами операции.
Исходные данные:
3
Результат:
7
1 -> 2
1 -> 3
2 -> 3
1 -> 2
3 -> 1
3 -> 2
1 -> 2
1.7.3.4. Дано натуральное число N. Найти наименьшее натуральное число M, сумма цифр которого равна N.
Исходные данные:
47
Результат:
299999