nod(x,y,z)=nod(nod(x,y),z).

nod(x,y,z)=nod(nod(x,y),z).

4.2. Рекурсивность арифметических операций.

Возникнув в глубокой древности из практических потребностей счета и простейших измерений, арифметика прошла долгий путь развития. Более или менее современное изложение она приобрела благодаря Л. Эйлеру и его последователям. Новый этап развития арифметики начался в XIX веке и связан с общим процессом критического пересмотра логических основ математики в целом. В середине XIX века Г. Грассман заложил основы, а Дж. Пеано завершил аксиоматическое построение арифметики. Пеано выделил основные понятия арифметики – натуральное число и следование и связал их пятью аксиомами. Фактически, операции сложения и умножения, лежащие в основании арифметики, были определены им рекурсивным способом, опираясь на аксиому «о существовании последующего числа» и аксиому «математической индукции». Первая из названных аксиом звучит так: «Для каждого натурального x имеется и притом только одно натуральное число, называемое его последующим и обозначаемое число x’».

Опишем рекурсивную модель арифметических операций сложения и умножения. Пусть для целых неотрицательных чисел n и m разрешены операции нахождения:

ü последующего числа (n+1) – n++ или inc(n);

ü предыдущего числа (n–1) (n>0) – n– – или dec(n);

Тогда сумму двух чисел a и b можно выразить следующим соотношением:

Такое соотношение задает одновременно и базу рекурсии и правило декомпозиции. По нему может быть построена следующая рекурсивная функция:

функция plus(целое a, целое b)

{

если b=0 то plus=a

иначе plus=plus(inc(a), dec(b));

}

Параметры: функция plus(целое a, целое b)

База: если b=0 то plus=a

Декомпозиция: plus=plus(inc(a), dec(b));

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

Соответствующая функция тогда запишется так:

функция multi(целое a, целое b)

{

если b=0 то multi=0

иначе

      если b=1 то multi =1

      иначе multi=plus(multi(a, dec(b)), a);

}

Параметры: функция multi(целое a, целое b)

База: если b=0 то multi=0

Декомпозиция: иначе multi=plus(multi(a, dec(b)), a);

Моделирование различных операций возможно не только для целых неотрицательных чисел. Их можно было бы определить и для множества всех целых чисел, и даже для множества вещественных чисел. Например, опишем рекурсивную программу-функцию нахождения дробной части вещественного числа, если разрешены лишь операции x+1 и x-1:

функция drob(вещ x)

{

если x>=0 и x<1 то drob=x

иначе

      если x>=1 то drob=drob(x-1)

      иначе drob=drob(x+1);

}

Параметры: функция drob(вещ x)

База: если x>=0 и x<1 то drob=x

Декомпозиция: если x>=1 то drob=drob(x-1)

                          иначе drob=drob(x+1);

Задания для выполнения

1. Составить рекурсивную функцию вычисления факториала целого неотрицательного числа n.

2. Составьте программу, которая позволяет организовать ввод последовательности натуральных чисел. Индикатором окончания ввода является число 0. Для элементов данной последовательности вычисляется наибольший общий делитель.

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

4. Составьте рекурсивную функцию, которая подсчитывает количество простых чисел, не превосходящих заданное натуральное число x.

5. Составьте рекурсивную функцию, вычисляющую количество делителей натурального числа. Продемонстрируйте работу данной функции на интервале [a,b].

6. Составить рекурсивную программу вычисления приближения к основанию натуральных логарифмов, то есть к числу e, используя следующий алгоритм Ламберта:

⇐ Предыдущая 123 Следующая ⇒