Книга программиста/Задачи на рекурсию
Внешний вид
К оглавлению | Назад | Вперёд
Все программы, код которых выложен здесь, являются работоспособными. На момент написания программ использовалась среда PascalABC.Net 3.0 (и 3.3).
PascalABC.Net
[править]Произведение
[править]Найти произведение первых n членов такой последовательности, что каждый следующий ее член больше предыдущего на 2.
function F(n: integer): integer;
function F2(x, k, n: integer): integer;
begin
if k = n then Result := x else Result := x * F2(x + 2, k + 1, n);
end;
begin
Result := F2(1, 1, n);
end;
begin
for var i := 1 to 10 do
Writeln(F(i));
end.
Дроби
[править]Вычислить выражение вида: x^n / n!.
function F(x: real; n: integer): real;
begin
if n = 0 then Result := 1 else Result := x / n * F(x, n - 1);
end;
begin
Writeln(F(ReadlnReal('X:'), ReadlnInteger('N:')));
end.
Остаток от деления a на b
[править]function F(a, b: integer): integer;
begin
if a < b then Result := a else Result := F(a - b, b);
end;
begin
Writeln(F(ReadlnInteger('A:'), ReadlnInteger('B:')));
end.
Определение степени пятерки
[править]Описать рекурсивную функцию, которая вычисляет, какой степенью числа 5 является натуральное число a. Если a не степень пяти, функция должна вернуть число -1.
function F(a: integer): integer;
begin
if a = 1 then
Result := 0
else if a mod 5 <> 0 then
Result := -1
else
begin
Result := F(a div 5);
Inc(Result, Ord(Result <> -1));
end;
end;
begin
Writeln(F(ReadlnInteger('A:')));
end.
Возведение числа в степень
[править]function F(a, n: integer): real;
begin
if n = 0 then Result := 1
else if n > 0 then Result := a * F(a, n - 1) else Result := 1 / F(a, Abs(n));
end;
begin
Writeln(F(ReadlnInteger('A:'), ReadlnInteger('B:')));
end.
Используется формула: x^(-n) = 1 / x^n.
Максимальная цифра числа
[править]function MaxDigit(a: integer): integer;
begin
if a < 10 then MaxDigit := a
else
begin
var l := a mod 10;
var m := MaxDigit(a div 10);
if m > l then Result := m else Result := l;
end;
end;
begin
Writeln(MaxDigit(413));
end.
Добавление цифр
[править]Добавление в конец
[править]function AddAfter(x: integer; a: byte) := x * 10 + a;
begin
Writeln(AddAfter(123, 4));
end.
Добавление в начало
[править]function AddBefor(x: integer; a: byte): integer;
begin
if x < 10 then
Result := a * 10 + x
else
Result := x mod 10 + AddBefor(x div 10, a) * 10;
end;
begin
Writeln(AddBefor(123456, 9));
end.
Вывод числа наоборот
[править]procedure Print(x: integer);
begin
Write(x mod 10);
var d := x div 10;
if d <> 0 then Print(d);
end;
begin
Print(123);
Writeln();
end.
Равенство сумм цифр числа и суммы, передаваемой в s
[править]function IsEqual(x: integer; s: integer): boolean;
begin
if s < 0 then
Result := false
else
if x < 10 then
Result := x = s
else
Result := IsEqual(x div 10, s - x mod 10);
end;
begin
Writeln(IsEqual(123, 5));
end.
Количество делителей числа
[править]function Dividers(N: integer): integer;{N>1}
function DivF(k: integer): integer;
begin
if k > N div 2 then
Result := 0
else
Result := Ord(N mod k = 0) + DivF(k + 1)
end;
begin
Result := DivF(2)
end;
begin
Writeln(Dividers(12));
end.
Числа Фибоначчи
[править]function F(n: integer): integer;
begin
if n <= 2 then Result := 1 else Result := F(n - 1) + F(n - 2);
end;
begin
for var i := 1 to 10 do
Writeln(F(i));
end.
Возведение экспоненты в степень с заданной точностью
[править]var
Eps, X: real;
function F(): real;
function F2(d: real; n: integer): real;
begin
Result := d;
if Result > Eps then
begin
Inc(n);
d := d * X / n;
Result := Result + F2(d, n);
end
end;
begin
Result := F2(1, 0);
end;
begin
Readln(Eps, X);
Writeln(F());
end.
Вычисление суммы с заданной точностью
[править]Найти сумму всех членов последовательности таких, что каждый из них по модулю больше Eps. Остановиться на том члене, который по модулю меньше Eps. Каждый член последовательности равен: (-1)^i / i!.
var
Eps: real;
function F(): real;
function F2(factr, i: integer): real;
begin
var j := i + 1;
var n := (1 - 2 * (i mod 2)) / factr;
if Abs(n) < Eps then Result := n else Result := n + F2(factr * j, j);
end;
begin
Result := F2(1, 1);
end;
begin
Readln(Eps);
Writeln(F());
end.
Максимальный элемент массива
[править]const
N = 10;
type
TArray = array [0..N - 1] of integer;
var
A: TArray;
function MaxF(a: TArray; i: integer): integer;
begin
Result := i > 0 ? Max(a[i], MaxF(a, i - 1)) : a[0];
end;
begin
for var i := 0 to N - 1 do
A[i] := Random(10);
Writeln(A);
Writeln(MaxF(A, N - 1));
end.
Python 3
[править]Произведение
[править]def F(n):
def F2(x, k, n):
if k == n:
return x
else:
return x*F2(x + 2, k + 1, n)
return F2(1, 1, n)
for i in range(9):
print('{0}\n'.format(F(i + 1)))
Дроби
[править]def F(x, n):
if n == 0:
return 1
else:
return x/n*F(x, n - 1)
print(F(int(input('X:')), int(input('N:'))))
Остаток от деления а на b
[править]def F(a, b):
if a < b:
return a
else:
return F(a - b, b)
print(F(int(input('A:')), int(input('B:'))))
Определение степени пятерки
[править]def F(a):
if a == 1:
return 0
elif a%5 != 0:
return -1
else:
result = F(a//5)
result += result != -1
return result
print(F(int(input('A:'))))
Возведение числа в степень
[править]import math
def F(a, n):
if n == 0:
return 1
elif n > 0:
return a*F(a, n - 1)
else:
return 1/F(a, math.fabs(n))
print(F(int(input('A:')), int(input('B:'))))