Тема 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. Число сочетаний. Написать рекурсивную функцию long long int CombiR (int, int) и не рекурсивную long long int Combi (int, int) с двумя параметрами для вычисления числа сочетаний из n по k. Результат типа long long int (__int64).

1.7.1.2. Написать рекурсивную функцию int MaxR (int * a, int n) для поиска максимума в одномерном целочисленном массиве, который передаётся в качестве первого параметра. Второй параметр – размер массива.

1.7.1.3. Алгоритм Эвклида. Написать рекурсивную функцию int GCD_R (int, int) и не рекурсивную int GCD (int, int) с двумя параметрами для вычисления наибольшего общего делителя двух натуральных чисел - своих параметров.

1.7.1.4. Число Фибоначчи. Написать рекурсивную функцию int Fibonacci_R (int) и не рекурсивную int Fibonacci (int) для вычисления числа Фибоначчи по его номеру (передаётся в качестве параметра).

1.7.1.5. Цепная дробь. Даны два массива вещественных чисел размера n. Написать программу для вычисления значения дроби:

A₀ + B_n-1 / (A₁ + B_n-2 / (A₂ + B_n-3 / (... + B₁ / (A_n-1 + B₀)... )))

В первой строке задаётся размер массивов n, во второй строке – массив целых чисел А, в третьей строке – массив целых чисел В. Напечатать результат с точностью 5 знаков после запятой.

Исходные данные:

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).

Исходные данные:

Результат:

1.7.2.2. Лесенка. Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем предыдущий. Написать функцию, вычисляющую число лесенок, которое можно построить из N кубиков. Параметр функции натуральное число N (1 ≤ N ≤ 100) – количество кубиков в лесенке. Вывести число лесенок, которые можно построить из N кубиков.

Исходные данные:

Результат:

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

Результат:

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

1.7.2.5. Для заданного «счастливого» числа найти следующее за ним по возрастанию. Счастливое число состоит только из цифр 4 и 7. Функция получает в качестве первого параметра длинное число (в массиве находятся цифры этого числа) и его длину во втором параметре. Результат поместить в тот же массив и вернуть ИСТИНУ. Если результат не умещается в этом массиве, вернуть ЛОЖЬ.

Исходные данные:

47477 5

Результат:

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. Интерполяция с помощью полинома Лагранжа. Дан массив значений аргумента x₁, x₂, ..., x_n и массив значений некоторой функции в этих точках f₁, f₂, ..., f_n. Написать функцию для вычисления значения этой функции в некоторой точке Х. Параметрами функции являются вещественные массивы x, f, число точек n и значение аргумента Х.

Продвинутые задачки.

1.7.3.1. Перестановки. Написать функцию для генерации очередной перестановки в лексикографическом порядке. Функция получает в качестве первого параметра перестановку (в массиве находятся её элементы) и длину перестановки n во втором параметре. Результат поместить в тот же массив и вернуть ИСТИНУ. Если следующей перестановки нет, вернуть ЛОЖЬ.

Исходные данные:

45132 5

Результат:

1.7.3.2. Написать функцию (с рекурсией и без нее) для вычисления функции Аккермана:

Параметры функции неотрицательные целые числа.

Исходные данные:

2 3

Результат:

1.7.3.3. Ханойские башни. Имеется 3 вертикальных штырька. На первый из них нанизаны N колец одно поверх другого, причём ни одно кольцо большего радиуса не находится поверх кольца меньшего радиуса. Два других штырька пустые. За один ход разрешается переставить верхнее кольцо с любого штырька на другой штырёк, но запрещается поверх малого кольца помещать кольцо большего радиуса. Написать программу, которая выведет кратчайшую последовательность перемещений колец с первого штырька на второй. Вывод оформить так, как это показано в примере. В первой строке вывести количество операций, а в остальных – сами операции.

Исходные данные:

Результат:

1 -> 2

1 -> 3

2 -> 3

1 -> 2

3 -> 1

3 -> 2

1 -> 2

1.7.3.4. Дано натуральное число N. Найти наименьшее натуральное число M, сумма цифр которого равна N.

Исходные данные:

Результат:

Тема 1.8. Автоматы

Цель.

Основные понятия.

Ключевые слова.

Автомат, диаграмма состояний

ПРИМЕР.

Алгоритм.

Решение.

⇐ Предыдущая 1 23