Рекурсия. Пример работы с натуральным числом

Опубликовано 03.05.2012 | Автор: admin

Задача:

Дано натуральное число. С помощью рекурсии определить разницу между минимальной и максимальной цифрой этого числа и найти сумму максимальной и минимальной цифры этого числа.

Отрицательные и нецелые числа натуральными не являются.

Сама задача не напрашивает себе применения рекурсии, но мне кажется сам пример именно на рекурсии очень познавателен и полезен:

Для понимания примера необходимо знать:

//Рекурсия		Пример работы с натуральным числом
#include <iostream>

using namespace std;

int getnumber(const int N,int &min,int &max) //Рекурсивная функция решения поставленной задачи
{
	if (N == 0) return N;                   //Если параметр N равен нулю, то выходим без рекурсии

	int temp = N%10;                        //Получаем остаток от деления на 10
	cout << temp << " ";                    //Выводим полученный остаток на экран

	if (min > temp) min = temp;               //проверяем минимум и при необходимости перезаписываем его
	if (max < temp) max = temp;               //проверяем максимум и при необходимости перезаписываем его

	return getnumber(N/10, min, max);       //Рекурсивный вызов функции
}

int main()
{
   int N = 2391472;                         //Любое натуральное число типа int

   int min = N%10;                          //за минимум принимаем самую правую цифру числа N
   int max = N%10;                          //за максимум принимаем самую правую цифру числа N
   getnumber(N, min, max);                  //Получаем минимальную цифру и максимальную цифру из числа N

   cout << "\n\n";
   cout << "Max digit is  " << max << "\n";       //Выводим на экран максимальную цифру
   cout << "Min digit is  " << min << "\n";       //Выводим на экран минимальную цифру
   cout << "\n";
   cout << "Max-Min   is  " << max-min << "\n";   //Выводим на сколько максимальная цифра больше чем минимальная
   cout << "Max+Min   is  " << max+min << "\n";   //Выводим сумму максимальной и минимальной цифры числа

   cin.get();
}

//Рекурсия Пример работы с натуральным числом

#include <iostream>

using namespace std;

int getnumber(const int N,int &min,int &max) //Рекурсивная функция решения поставленной задачи

{

if (N == 0) return N; //Если параметр N равен нулю, то выходим без рекурсии

int temp = N%10; //Получаем остаток от деления на 10

cout << temp << " "; //Выводим полученный остаток на экран

if (min > temp) min = temp; //проверяем минимум и при необходимости перезаписываем его

if (max < temp) max = temp; //проверяем максимум и при необходимости перезаписываем его

return getnumber(N/10, min, max); //Рекурсивный вызов функции

}

int main()

{

int N = 2391472; //Любое натуральное число типа int

int min = N%10; //за минимум принимаем самую правую цифру числа N

int max = N%10; //за максимум принимаем самую правую цифру числа N

getnumber(N, min, max); //Получаем минимальную цифру и максимальную цифру из числа N

cout << "\n\n";

cout << "Max digit is " << max << "\n"; //Выводим на экран максимальную цифру

cout << "Min digit is " << min << "\n"; //Выводим на экран минимальную цифру

cout << "\n";

cout << "Max-Min is " << max-min << "\n"; //Выводим на сколько максимальная цифра больше чем минимальная

cout << "Max+Min is " << max+min << "\n"; //Выводим сумму максимальной и минимальной цифры числа

cin.get();

}

В этом примере параметр, принимающий значение входящего в функцию аргумента, внутри функции не изменяется. Само число на каждом рекурсивном шаге делится на 10, а из полученного делением числа выдирается последняя цифра, которая записывается в переменную temp. Контрольной точкой для прекращения рекурсивных вызовов является момент времени, когда результатом очередного деления оказывается ноль. Ссылочные параметры используются для того, чтобы каждый новый экземпляр функции не создавал копий ради них, а просто чтобы подставлял одну и ту же сущность: непосредственный аргумент. Так у нас получается два непосредственных аргумента, которые изменяются множеством экземпляров функций, если условие для изменения справедливо.

Процесс работы программы при заданном N = 12345 можно описать так:
будут созданы функции, в параметры которых придут следующие значения:
12’345
(12’345/10) ==> 1’234
(1’234/10) ==> 123
(123/10) ==> 12
(12/10) ==> 1
(1/10=0 — возврат не рекурсивный) ==> 0

Итого: 6 экземпляров функций, где значение каждого параметра отлично от значения параметра любого другого экземпляра функции.

Поскольку параметры min и max имеют тип ссылочного характера — любой экземпляр функции может повлиять на ушедший в функцию аргумент напрямую. Чем мы и пользуемся, когда проверяем значение на минимум и максимум. Проверяем параметр и если результат проверки положительный — изменяем значение параметра, чем влечём прямое изменение ушедшего в функцию аргумента.

Ход изменений значений в temp для каждого нового экземпляра функции при N = 12345 выглядит приблизительно так:
12 345 % 10 == 5 //Получили самую правую цифру числа
12 34 % 10 == 4 //Получили вторую справа цифру числа
123 % 10 == 3 //Получили третью справа цифру числа
12 % 10 == 2 //Получили четвёртую справа цифру числа
1 % 10 == 1 //Получили пятую справа цифру числа

В начале работы с рекурсивной функцией нужно определить первые значения минимуму и максимуму. Разумеется, и минимум, и максимум — должны входить в заданное число. Очень удобно взять самую правую цифру, а потом уже сверять с получаемыми остатками и, при необходимости, их изменять.

Рубрика: Решения задач, Функции

Рекурсия. Пример работы с натуральным числом

Один комментарий на «“Рекурсия. Пример работы с натуральным числом”»

Добавить комментарий Отменить ответ

Поиск

Последние темы

Случайная книга в электронном формате

Последние комментарии

Мета