 |
Лабораторная работа 5. Программирование алгоритмов при помощи рекурсивных процедур и функций
|
|
|
|
ЛАБОРАТОРНАЯ РАБОТА 5. ПРОГРАММИРОВАНИЕ АЛГОРИТМОВ ПРИ ПОМОЩИ РЕКУРСИВНЫХ ПРОЦЕДУР И ФУНКЦИЙ
5. 1 ЦЕЛЬ РАБОТЫ
Познакомиться с понятиями " рекурсия", закрепить практические навыки работы с VBScript на примере реализации алгоритмов при помощи рекурсивных процедур и функций.
5. 2 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Рекурсия (самоповторение) – это действие, возвращающееся к “самому себе”. Существует два вида рекурсии:
1. прямая рекурсия (процедура или функция вызывает саму себя);
2. косвенная рекурсия означает, что одна процедура или функция вызывает другую процедуру или функцию, а это в свою очередь прямо или косвенно приводит к вызову первоначальной процедуры или функции.
Рекурсию следует использовать только тогда, когда задача легко поддается рекурсивному решению. Важно отметить, что любая задача, которая решена рекурсивно, может быть решена и без рекурсии.
С понятием " рекурсия" тесно связано понятие " рекуррентная последовательность”, вычисление n-го члена которой производится с помощью рекурсии. Определим это понятие.
Числовая последовательность {хk} называется рекуррентной последовательностью, если
где k=p, p=1, …
5. 3 ДЕМОНСТРАЦИОННЫЕ ПРИМЕРЫ
Пример 1
'Имя файла Factorial. vbs
'Задача: вычислить значение факториала введённого натурального числа n
'--------------------------------------
FUNCTION RecFact(n)
'Рекурсивное вычисление факториала
If n=0 Then
RecFact=1
Else
RecFact=n*RecFact(n-1)
End If
End FUNCTION
'---------------------------------------
FUNCTION NonRecFact(n)
'Вычисление факториала при помощи цикла
dim P
P=1
While (n> 1)
P=n*P
n=n-1
WEnd
NonRecFact=P
End FUNCTION
'---------------------------------------
Dim n
n=CInt(InputBox(" Введите натуральное число", _
|
|
|
" Вычисление факториала натурального n: ", " 0" ))
number=n
MsgBox " Рекурсивно вычисленный факториал: " & RecFact(n)& _
VbCrLf& _
" Нерекурсивно вычисленный факториал: " & NonRecFact(n)_
, vbInformation, " Результат вычисления факториала числа " & number& ": "
Пример 2
'Имя файла Nod. vbs
'Задача: найти наибольший общий делитель (НОД) двух целых чисел
'--------------------------------------
FUNCTION RecNod(n, m)
'Рекурсивное вычисление НОД
If n=m Then
RecNod=n
ElseIf n> m Then
RecNod=RecNod(n-m, m)
Else
RecNod=RecNod(n, m-n)
End If
End FUNCTION
'---------------------------------------
FUNCTION NonRecNod(n, m)
'Вычисление НОД с помощью цикла
While (n< > m)
If n> m Then
n=n-m
Else
m=m-n
End If
WEnd
NonRecNod=n
End FUNCTION
'---------------------------------------
Dim n, m
n=CLng(InputBox(" Введите натуральное число n", " Вычисление НОД: ", " 25" ))
m=CLng(InputBox(" Введите натуральное число m", " Вычисление НОД: ", " 50" ))
MsgBox " Рекурсивно вычисленный НОД: " & CStr(RecNod(abs(n), abs(m)))& _
VbCrLf& _
" Нерекурсивно вычисленный НОД: " & CStr(NonRecNod(abs(n), abs(m)))_
, vbInformation, " Результат вычисления НОД: "
Пример 3
'Имя файла: Fib. vbs
'Задача: При помощи рекурсивной функции найти и вывести на экран
' к-й элемент последовательности Фибоначчи. Последовательность Фибоначчи:
' 1, 1, 2, 3, 5, 8, 13, ... Нумерация данных чисел начинается с 0.
'-----------------------------------------
FUNCTION Fib(k)
If k=0 or k=1 Then
Fib=1
Else
Fib=fib(k-1)+Fib(k-2)
End If End FUNCTION
'-----------------------------------------
dim k
k=Cint(InputBox(" Введите k: ", " Вычисление к-го элемента посл-ти Фибоначчи: " ))
MsgBox k& " -й" & " элемент последовательности фибоначчи: " & _
vbCrlf& Fib(k), vbInformation, " Результат: "
Пример 4
'Имя файла Koren. vbs
'Задача: 'Вычислить, используя рекурсию: 'sqr(1+(n+1)*sgr(1+(n+2)*sqr(1+(n+3)*sqr(1+...
|
|
|
' где n - натуральное число,
' k - количество корней
'--------------------------------------
FUNCTION Kor(i, n)
If i=k Then
Kor=sqr(1+(n+k))
Else
Kor=sqr(1+(n+i)*Kor(i+1, n))
End If
End FUNCTION
'---------------------------------------
Dim n, k, i
n=CInt(InputBox(" Введите натуральное число n: ", " Ввод параметров: ", " 1" ))
k=CInt(InputBox(" Введите количество корней k: ", " Ввод параметров: ", " 1" ))
i=1
MsgBox " Значение вычисленного корня: " & CStr(Kor(i, n)), vbInformation, " Результат: "
5. 4 ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
1. Дано натуральное число n. Вычислите (2n)! и 2n!; при этом используйте рекурсивную функцию вычисления факториала.
2. Переделайте программу Fib. vbs, так чтобы она находила к-й член последовательности Фибоначчи, но последовательность начиналась бы не с 1, а с 0:
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
3. Проверьте, будет ли к-й член последовательности Фибоначчи делиться на 5.
4. Опишите рекурсивную функцию Stepen(x, n), формальными параметрами которой являются вещественная переменная x и натуральная переменная n, вычисляющую величину xn следующим образом:
5. Напишите рекурсивную процедуру, при выполнении которой на экран будет выводиться отрезок натурального ряда чисел.
6. Напишите программу вычисления первого числа Фибоначчи, большего m (m> 1), включающую рекурсивную функцию, которая основана на непосредственном использовании соотношения un=un-1+un-2.
7. Числа Фибоначчи второго порядка u0, u1, u2,... определяются следующим образом:
Напишите программу вычисления un для данного неотрицательного целого n. Используйте рекурсивную функцию.
8. Вычислите, используя рекурсию:
9. Опишите семантику приведённой ниже программы:
Function koren(i)
If i=0 Then
koren=sqr(11)
Else
koren=sqr(11-2*sqr(11+2*sqr(11-2*koren(i-1))))
End If
End Function
Dim n, k, i
i=CInt(InputBox(" Введите количество рекурсий", " Ввод параметров", " 1" ))
msgbox " Результат: " & koren(i)
|
|
|
