алгоритмизация
.pdfПример №3
Задание. Дано натуральное число n. Среди чисел 1, ... , n найти такие, запись которых совпадает с последними цифрами записи их квадратов (например, 62 = 36, 252 = 625).
Решение.
|
|
|
Тестовая таблица |
№ п/п |
n |
|
Числа из диапазона от 1 до n, запись которых совпа- |
|
|
|
дает с последними цифрами записи их квадратов |
1 |
5 |
|
52 = 25 |
2 |
10 |
|
52 = 25, 62 = 36 |
3 |
50 |
|
52 = 25, 62 = 36, 252 = 625 |
4 |
100 |
|
52 = 25, 62 = 36, 252 = 625, 762 = 5776 |
|
|
52 = 25: 25 / 10 = 2, 25 – 2 * 10 = 5, 5 = 5 |
|
252 = 625: 625 / 100 = 6, 625 – 6 * 100 = 25, 25 = 25 762 = 5776: 5776 / 1000 = 5, 5776 – 5 * 1000 = 776, 776 / 100 = 7, 776 –
7 * 100 = 76, 76 = 76
Текст программы
#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
int n,m,m1,m2,del; printf("n="); scanf_s("%d",&n); for(m=1;m<=n;m++)
{
m1=m;
del=1; while(m1>0)
{
del*=10;
m1/=10;
}
m1=m*m;
if(m==m1%del) printf("%d^2=%d\n",m,m*m);
}
return 0;
}
21
Задача № 5
РЕКУРСИВНЫЕ ФУНКЦИИ
Цель. Знакомство с организацией вычислений посредством рекур-
сии.
Задание. Разработать алгоритм решения задачи, приведенной в табл. 5, используя рекурсию. Алгоритм представить его в виде блоксхемы и программы для ЭВМ на алгоритмическом языке С. Провести полное тестирование программы.
|
Таблица 5 |
|
№ |
Задание |
|
варианта |
||
|
||
|
|
|
1 |
Найти сумму цифр заданного натурального числа. |
|
2 |
Подсчитать количество цифр в заданном натуральном чис- |
|
|
ле. |
|
3 |
Описать функцию С(m, n), где 0 ≤ m ≤ n, для вычисления |
|
|
биномиального коэффициента Cnm по следующей формуле: |
|
|
Cn0 = Cnn = 1; Cnm = Cnm−1 + Cnm−−11 при 0 < m < n. |
|
4 |
Описать рекурсивную функцию Root (а, b, ε), которая мето- |
|
|
дом деления отрезка пополам находит с точностью ε корень |
|
|
уравнения f(x) = 0 на отрезке [а, b] (считать, что ε > 0, а < b, |
|
|
f(a) · f(b) < 0 и f(x) – непрерывная и монотонная на отрезке |
|
|
[а, b] функция). |
|
5 |
Описать функцию min(X) для определения минимального |
|
|
элемента линейного массива X, введя вспомогательную ре- |
|
|
курсивную функцию minl(k), находящую минимум среди |
|
|
последних элементов массива X, начиная с k-го. |
|
6 |
Описать рекурсивную логическую функцию simm(S, i, j), |
|
|
проверяющую, является ли симметричной часть строки S, |
|
|
начинающаяся i-м и заканчивающаяся j-м ее элементами. |
|
7 |
Составить программу для вычисления наибольшего общего |
|
|
делителя двух натуральных чисел. |
|
8 |
Составить программу для нахождения числа, которое обра- |
|
|
зуется из данного натурального числа при записи его цифр |
|
|
в обратном порядке. Например, для числа 1234 получаем |
|
|
результат 4321. |
|
9 |
Составить программу для перевода данного натурального |
|
|
числа в р-ичную систему счисления (2 ≤ р ≤ 9). |
|
10 |
Дана символьная строка, представляющая собой запись |
|
|
натурального числа в p-ичной системе счисления (2 ≤ р ≤ |
|
|
9). Составить программу для перевода этого числа в деся- |
|
|
тичную систему счисления. |
22
11 |
Составить программу для вычисления суммы: 1! + 2! + 3! + |
|
... + n! (n ≤ 15). Примечание. Тип результата значения |
|
функции – long int. |
12 |
Составить программу для вычисления суммы: 2! + 4! + 6! + |
|
... + n! (n ≤ 16, n – четное). Примечание. Тип результата |
|
значения функции – long int. |
13 |
Дано n различных натуральных чисел. Напечатать все пере- |
|
становки этих чисел. |
14 |
Логическая функция возвращает true, если ее аргумент – |
|
простое число. |
15 |
Описать функцию, которая удаляет из строки все лишние |
|
пробелы. Пробелы считаются лишними, если их подряд |
|
идет более двух, если они стоят в конце строки после по- |
|
следней точки, если стоят после открывающегося парного |
|
знака препинания. |
Методические указания
Рекурсивная функция (от лат. recursio – возвращение) – это числовая функция f(n) числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения f(n) на основе значений f(n – 1), f(n – 2), … , подобно рассуждению по индукции. Чтобы вычисление завершалось для любого n, необходимо, чтобы для некоторых n функция была определена нерекурсивно (например, для n = 0, 1). Вот пример рекурсивной функции, дающей n-ое число Фибоначчи:
|
f (0) = 1; |
|
f (1) = 1; |
f = |
|
+ f (n − 2), n >1. |
f (n) = f (n −1) |
Руководствуясь этой записью, мы можем вычислить f(n) для любого натурального n за конечное число шагов. Правда, по пути придется дополнительно вычислить значения f(n – 1), f(n – 2), … , f(2). В связи с этими накладными расходами полезно знать, есть ли у рекурсивной функции нерекурсивная (замкнутая) форма.
Например, рекурсивная функция:
f (0) = 0;
f = f (n) = n + f (n −1), n > 0
23
может быть переведена в замкнутую форму: f (n) = n(n +1) . Замкнутая 2
форма может быть найдена не для всех рекурсивных функций (соотношений). Для некоторых из них найдены лишь приближенные замкнутые формы. Некоторые рекурсивные соотношения, такие как факториал, считаются элементарными математическими операциями.
Рекурсивные функции играют важную роль в теории алгоритмов, так как многие алгоритмы имеют рекурсивную структуру.
Пример №1
Задание. Написать программу, которая используя рекурсию, определяет n-ое число Фибоначчи.
Решение.
Вспомним рекурсивную функцию, задающую n-ое число Фибона-
ччи:
|
f (0) = 1; |
|
f (1) = 1; |
f = |
|
+ f (n − 2), n >1. |
f (n) = f (n −1) |
Текст программы
#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
int fibo(int),n; printf("n="); scanf_s("%d",&n);
printf("fibonacci number=%d\n",fibo(n)); return 0;
}
int fibo(int n)
{
int f; if(n>1)
f=fibo(n-1)+fibo(n-2);
else
f=1; return f;
}
24
|
|
Тестовая таблица |
|
|
|
№ п/п |
n |
Число Фибоначчи f(n) |
1 |
0 |
1 |
2 |
1 |
1 |
3 |
2 |
2 |
4 |
3 |
3 |
5 |
4 |
5 |
6 |
10 |
89 |
Проиллюстрируем процесс вычислений
f(4) = f(3) + f(2) =
=(f(2) + f(1)) + (f(1) + f(0)) =
=((f(1) + f(0)) + f(1)) + (f(1) + f(0)) =
=((1 + 1) + 1) + (1 + 1) =
=5
Пример №2
Задание. Написать программу, которая используя рекурсию, определяет n-факториал.
Решение.
n-факториал может быть задан рекурсивно с помощью функции:
|
f (0) |
=1; |
f = |
|
−1), n > 0. |
f (n) = n f (n |
||
Текст программы
#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
int factorial(int),n; printf("n="); scanf_s("%d",&n);
printf("%d!=%d\n",n,factorial(n)); return 0;
}
25
int factorial(int n)
{
int f; if(n>1)
f=n*factorial(n-1);
else
f=1; return f;
}
|
|
Тестовая таблица |
|
|
|
№ п/п |
n |
n-факториал |
1 |
0 |
1 |
2 |
1 |
1 |
3 |
2 |
2 |
4 |
3 |
6 |
5 |
4 |
24 |
6 |
5 |
120 |
Проиллюстрируем процесс вычислений
f(4) = 4 · f(3) =
=4 · (3 · f(2)) =
=4 · (3 · (2 · f(1))) =
=4 · (3 · (2 · (1))) =
=24
Пример №3
Задание. Написать программу, которая используя рекурсию, определяет n-й элемент последовательности 5, 11, 23, 47, 95, … .
Решение.
Заданная последовательность может быть представлена рекурсивно с помощью функции:
f (1) = 5;
f = |
+1, n > 1. |
f (n) = 2 f (n −1) |
Текст программы
#include "stdafx.h"
26
int _tmain(int argc, _TCHAR* argv[])
{
int f(int),n; printf("n="); scanf_s("%d",&n);
printf("f(%d)=%d\n",n,f(n)); return 0;
}
int f(int n)
{
int a; if(n>1)
a=2*f(n-1)+1;
else
a=5; return a;
}
|
Тестовая таблица |
|
|
n |
n-й элемент последовательности |
1 |
5 |
2 |
11 |
3 |
23 |
4 |
47 |
5 |
95 |
Проиллюстрируем процесс вычислений
f(5) = 2 · f(4) + 1 =
=2 · (2 · f(3) + 1) + 1 =
=2 · (2 · (2 · f(2) + 1) + 1) + 1 =
=2 · (2 · (2 · (2 · f(1) + 1) + 1) + 1) + 1 =
=2 · (2 · (2 · (2 · (5) + 1) + 1) + 1) + 1 =
=95
27