III. Задания для самостоятельной работы

A.

1. Вычислить числа Фибоначчи второго порядка:

u₀ =1; u₁ =2; u₂ =3

u_n = u_n-1 + u_n-2 + u_n-3 , при n=3, 4,…

2. Написать рекурсивную функцию для вычис­ления значения так называемой функции Аккермана для неотрицательных чисел n и m. Функция Аккермана определяется следующим образом:

3. Вычислить рекурсивно функцию:

n –10, если n>100

F(n)= F(F(n+4)), если n<100

4. Вычислить рекурсивно функцию :

1, если n=1

S(n) S(n/2), если n=2k

S((3n+1)/2), если n=2k+1

5. Написать рекурсивную и нерекурсивную функции вычисления биномиальных коэффициентов:

C(n,0) = C(n,n) = 1

C(m,n) = C(m,n-1) + C(m-1,n-1) при 0 < m < n

6. Написать рекурсивную и нерекурсивную функции для разностного уравнения

А(0) = 1

A(n) = A(ndiv2)+A(ndiv3)

7. Написать рекурсивную функцию:

а) вычисления суммы цифр натурального числа;

б) вычисления количества цифр натурального числа.

8. Даны первый член и разность арифметичес­кой прогрессии. Написать рекурсивную функцию для нахождения:

а) n-го члена прогрессии;

б) суммы n первых членов прогрессии.

9. Даны первый член и знаменатель геометри­ческой прогрессии. Написать рекурсивную функцию:

а) нахождения ее n-го члена;

б) нахождения суммы n первых членов прогрессии.

B.

1. Вычислить рекурсивно полином Лежандра порядке n:

P₀(x) = 1; P₁(x) = x;

P_n(x)=((2n-1)P_n-1(x) - (n-1)P_n-2(x)/n

2. Написать рекурсивную и не рекурсивную функции вычисления полинома Чебышева первого ряда:

T₀(x)=1; T₁(x)=x

T_n(x)=2xT_n-1(x) – T_n-2(x)

Сравнить число операций.

3. Написать рекурсивную и не рекурсивную функции вычисления полинома:

H₀(x)=1; H₁(x)=x

H_n(x)=xH_n-1(x) –(n-2)H_n-2(x)

Сравнить число операций.

4. Написать рекурсивную и не рекурсивную функции вычисления полинома:

G₀(x)=1; G₁(x)=x-1

G_n(x)=(x-2n+1)G_n-1(x) –(n-1)²G_n-2(x)

Сравнить число операций.

5. Написать рекурсивную и не рекурсивную функции вычисления полинома:

L₀(x)=1; L₁(x)=x

Сравнить число операций.

6. Написать рекурсивную и не рекурсивную функции вычисления полинома Эрмита

H₀(x)=1; H₁(x)=2x

H_n(x)=2xH_n(x) – 2nH_n-1(x)

7. Написать рекурсивную и не рекурсивную функции вычисления полинома Лагерра:

, n=1,2,

L₀(x)=1; L₁(x)=1-x.

8. Вычислить рекурсивно и нерекурсивно:

,

где

k!! = 1*3*5*…k, если k – нечетно

k!! = 2*4*6*…k, если k - четно

9. Вычислить, используя рекурсию и без нее:

а) ;

б) ;

в) ;

г) ;

д) ;

е)

C.

1. Используя команды write(x) лишь при х=0,1,…9 написать рекурсивную процедуру вывода на экран десятичной записи натурального числа n.

2. Используя команды write(x) лишь при х=0,1 написать рекурсивную процедуру вывода на экран двоичной записи натурального числа n.

3. Используя команды write(x) лишь при х=0,1,…9 написать рекурсивную процедуру вывода на экран восьмеричной записи натурального числа n.

4.Написать рекурсивную и нерекурсивную функции возведения вещественного числа х в натуральную степень n.

5. Цифровой корень натурального числа находится через сумму цифр этого числа до тех пор, пока эта сумма не станет цифрой. Написать рекурсивную функцию нахождения цифрового корня натурального числа.

6. Написать рекурсивную процедуру перевода числа из десятичной системы в N –ю

(2<= N <= 16).

7. Составить рекурсивную функцию нахождения суммы первых n членов арифметической и геометрической прогрессий.

8. Составить рекурсивную процедуру нахождения максимального элемента в массиве.

9. Написать рекурсивный алгоритм головоломки «ханойская башня».

10. Написать рекурсивный алгоритм перевода из двоичной системы счисления в десятичную ( из восьмеричной и шестнадцатеричной в десятичную).

11. Написать рекурсивный алгоритм представления натурального числа в римском исчислении.

12. Написать рекурсивную процедуру для вывода на экран цифр натурального числа в обратном порядке.

13. Написать рекурсивную процедуру перевода натурального числа из десятичной системы счисления в N-ичную. Значение N в основной программе вводится с клавиатуры (2 N 1б).

14. Написать рекурсивную функцию, определяющую, является ли заданное натуральное число простым (про­стым называется натуральное число, большее 1, не имею­щее других делителей, кроме единицы и самого себя).