Среда, 26.04.2017, 08:57
Приветствую Вас Гость | RSS


Государственное бюджетное общеобразовательное учреждение

средняя общеобразовательная школа № 141  
Красногвардейского района Санкт-Петербурга
Адрес ОУ: 195030, ул. Коммуны, дом 32, корпус 4, литер "А"

 

[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
Страница 1 из 11
Модератор форума: pep-spb 
Школьный форум » Персональные страницы учителей » Попова Елена Петровна » Рекурсивные алгоритмы 9 класс
Рекурсивные алгоритмы 9 класс
pep-spbДата: Суббота, 10.12.2016, 14:06 | Сообщение # 1
Учитель
Группа: Модераторы
Сообщений: 141
Награды: 0
Репутация: 2
Статус: Offline
Задачи для тренировки :

1) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * (n + 1), при n > 1
Чему равно значение функции F(5)? В ответе запишите только целое число.

Решение:
Сначала в рекуррентную формулу вместо n подставим 5, т.к. в вопросе F(5).
Затем распишем формулы для неизвестных n.
Дойдя до строки, которую можем вычислить, поднимаемся по формулам вверх, подставляя найденные значения функций.

F(n) = F(n–1) * (n + 1)
F(5) = F(4) * 6 = 60 * 6 =360
F(4) = F(3) * 5 = 12 * 5 = 60
F(3) = F(2) * 4 = 3 * 4 = 12
F(2) = F(1) * 3 = 1 * 3 = 3

Ответ: 360
______________________________________________________

2) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * (n + 2), при n > 1
Чему равно значение функции F(5)? В ответе запишите только целое число.

3) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * (2*n + 1), при n > 1
Чему равно значение функции F(4)? В ответе запишите только целое число.

4) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * (2*n - 1), при n > 1
Чему равно значение функции F(5)? В ответе запишите только целое число.

5) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * (3*n - 2), при n > 1
Чему равно значение функции F(4)? В ответе запишите только целое число.

6) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = F(n–1) + F(n-2), при n > 1
Чему равно значение функции F(7)? В ответе запишите только целое число.

7) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = 2*F(n–1) + F(n-2), при n > 1
Чему равно значение функции F(6)? В ответе запишите только целое число.

8) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = F(n–1) + 2*F(n-2), при n > 1
Чему равно значение функции F(6)? В ответе запишите только целое число.

9) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = 3*F(n–1) - F(n-2), при n > 1
Чему равно значение функции F(6)? В ответе запишите только целое число.

10) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = F(n–1)*F(n-2)+1, при n > 1
Чему равно значение функции F(6)? В ответе запишите только целое число.

11) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = F(n–1)*F(n-2)+2, при n > 1
Чему равно значение функции F(5)? В ответе запишите только целое число.

12) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1, F(2) = 1
F(n) = F(n-2)*n, при n > 2
Чему равно значение функции F(7)? В ответе запишите только целое число.

13) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1, F(2) = 1
F(n) = F(n-2)*n + 2, при n > 2
Чему равно значение функции F(8)? В ответе запишите только целое число.

14) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1, F(2) = 1
F(n) = F(n-2)*(n-1), при n > 2
Чему равно значение функции F(7)? В ответе запишите только целое число.

15) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1, F(2) = 1
F(n) = F(n-2)*(n-1) + 2, при n > 2
Чему равно значение функции F(8)? В ответе запишите только целое число.

16) Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:
F(1) = 3; F(2) = 3;
F(w) = 5*F(w-l)- 4*F(w-2) при w > 2.
Чему равно значение функции F(15)?

17) Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:
F(1) = 4; F(2) = 5;
F(w) = 4*F(w-l)- 3*F(w-2) при w > 2.
Чему равно значение функции F(8)?

18) (http://ege.yandex.ru) Алгоритм вычисления значений функций F(w) и Q(w), где w - натуральное число, задан следующими соотношениями:
F(1) = 1; Q(1) = 1;
F(w) = F(w-l) + 2*Q(w-1) при w > 1
Q(w) = Q(w-l) - 2*F(w-1) при w > 1.
Чему равно значение функции F(5)+Q(5)?

19) Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:
F(1) = 1; F(2) = 2;
F(w) = 3*F(w-l)- 2*F(w-2) при w > 2.
Чему равно значение функции F(7)?

20) Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:
F(1) = 2; F(2) = 4;
F(w) = 4*F(w-l)- 3*F(w-2) при w > 2.
Чему равно значение функции F(7)?

21) (http://ege.yandex.ru) Алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующими соотношениями:
F(1) = 1; F(2) = 2;
F(n) = 5*F(n-l)- 6*F(n-2) при n > 2.
Чему равно значение функции F(7)?

22) (http://ege.yandex.ru) Алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующими соотношениями:
F(1) = 1; F(2) = 2; F(3) = 3
F(n) = F(n-3)*(n-1)/3 при n > 3.
Чему равно значение функции F(16)?

23) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 2; G(1) = 1;
F(n) = F(n–1) – G(n–1),
G(n) = F(n–1) + G(n–1), при n >=2
Чему равно значение величины F(5)/G(5)? В ответе запишите только целое число.

24) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = F(n–1) – G(n–1),
G(n) = F(n–1) + 2*G(n–1), при n >=2
Чему равно значение величины F(5)/G(5)? В ответе запишите только целое число.

25) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = F(n–1) – 2*G(n–1),
G(n) = F(n–1) + G(n–1), при n >=2
Чему равно значение величины G(5)/F(5)? В ответе запишите только целое число.

26) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = 2*F(n–1) – G(n–1),
G(n) = F(n–1) + 2*G(n–1), при n >=2
Чему равно значение величины G(5)+F(5)? В ответе запишите только целое число.

27) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = 2*F(n–1) – G(n–1),
G(n) = 2*F(n–1) + G(n–1), при n >=2
Чему равно значение величины F(5)-G(5)? В ответе запишите только целое число.

28) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = F(n–1) – 2*G(n–1),
G(n) = F(n–1) + 2*G(n–1), при n >=2
Чему равно значение величины G(5)-F(5)? В ответе запишите только целое число.

29) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = 3*F(n–1) – 2*G(n–1),
G(n) = F(n–1) + 2*G(n–1), при n >=2
Чему равно значение величины G(5)-F(5)? В ответе запишите только целое число.

30) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = 3*F(n–1) – 3*G(n–1),
G(n) = F(n–1) + 2*G(n–1), при n >=2
Чему равно значение величины F(5)-G(5)? В ответе запишите только целое число.
___________________________________________

31) Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*') ;
if n > 0 then begin
F(n-2);
F(n div 2);
F(n div 2);
end
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?

Пояснение:
Значок * будет печататься в этой программе ВСЕГДА вне зависимости от значения переменной n.
Остальные * после проверки условия могут быть, а могут и не печататься.

Решение:
1) Сначала составим рекуррентную формулу по фрагменту программы:
F(n) = 1 + F(n-2) + F(n div 2) + F(n div 2)
2) Упростим:
F(n) = 1 + F(n-2) + 2 * F(n div 2)
3) Распишем формулы "баяном" вниз, а затем соберём вычисления вверх:
F(5) = 1 + F(3) + 2 * F(2) = 1 + 13 + 2*10 = 34
F(3) = 1 + F(1) + 2 * F(1) = 1 + 4 + 2*4 = 13
F(2) = 1 + F(0) + 2 * F(1) = 1 + 1 + 2*4 = 10
F(1) = 1 + F(-1) + 2 * F(0) = 1 + 1 + 2*1 = 4

Ответ: 34
__________________________________________________________

32) Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*' ;) ;
if n > 0 then begin
F(n-2);
F(n-2);
F(n div 2);
end
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)?

33) Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*' ;) ;
if n > 0 then begin
F(n-3);
F(n div 2);
end
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

34) Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*' ;) ;
if n > 0 then begin
F(n-3);
F(n-2);
F(n div 2);
end
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

35) Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*' ;) ;
if n > 0 then begin
F(n-3);
F(n-2);
F(n div 2);
F(n div 2);
end
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)?

36) Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*' ;) ;
if n > 0 then begin
writeln('*' ;) ;
F(n-2);
F(n div 2);
end
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

37) Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*' ;) ;
if n > 0 then begin
writeln('*' ;) ;
F(n-2);
F(n div 2);
F(n div 2);
end
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

38) Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*' ;) ;
if n > 0 then begin
writeln('*' ;) ;
F(n-2);
F(n-2);
F(n div 2);
end
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)?

39) Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
if n > 0 then begin
F(n-2);
F(n-1);
F(n-1);
end;
writeln('*' ;) ;
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?

40) Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
if n > 0 then begin
writeln('*' ;) ;
F(n-2);
F(n-1);
F(n-1);
end;
writeln('*' ;) ;
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?

41) Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
if n > 1 then begin
F(n-2);
F(n-1);
F(n div 2);
end;
writeln('*' ;) ;
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

42) Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
if n > 2 then begin
writeln('*' ;) ;
F(n-2);
F(n-1);
F(n div 2);
end;
writeln('*' ;) ;
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)?

43) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1,
F(n) = F(n–1) + 2n-1, при n > 1
Чему равно значение функции F(12)? В ответе запишите только целое число.

44) Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n < 6 then begin
F(n+2);
F(n*3)
end
end;
Найдите сумму чисел, которые будут выведены при вызове F(2).

45) Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n < 5 then begin
F(n+2);
F(n*2)
end
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).


"Делай всё хорошо. Плохо само получится."

Материалы для заданий взяты с сайта К.Полякова http://kpolyakov.spb.ru/.
Спасибо ему за огромный труд нам в помощь!
 
pep-spbДата: Суббота, 10.12.2016, 14:08 | Сообщение # 2
Учитель
Группа: Модераторы
Сообщений: 141
Награды: 0
Репутация: 2
Статус: Offline
Ответы:
1. 360
2. 840
3. 315
4. 945
5. 280
6. 21
7. 99
8. 43
9. 89
10. 155
11. 87
12. 105
13. 306
14. 48
15. 191
16. 3
17. 1097
18. -14
19. 64
20. 730
21. 64
22. 120
23. 2
24. -2
25. -11
26. -14
27. -6
28. 12
29. 90
30. -105
31. 34
32. 58
33. 15
34. 55
35. 97
36. 31
37. 81
38. 77
39. 148
40. 197
41. 88
42. 33
43. 4095
44. 30
45. 53


"Делай всё хорошо. Плохо само получится."

Материалы для заданий взяты с сайта К.Полякова http://kpolyakov.spb.ru/.
Спасибо ему за огромный труд нам в помощь!
 
Seliverstov0000Дата: Пятница, 16.12.2016, 13:52 | Сообщение # 3
Ученик
Группа: Пользователи
Сообщений: 1
Награды: 0
Репутация: 0
Статус: Offline
https://cloud.mail.ru/home/%D0%9A%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B5%20%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D1%8B.docx

Добавлено (16.12.2016, 13:52)
---------------------------------------------
https://cloud.mail.ru/public/WKtD/PXcfGmSvo

 
ananastya_007Дата: Пятница, 16.12.2016, 23:36 | Сообщение # 4
Ученик
Группа: Пользователи
Сообщений: 4
Награды: 0
Репутация: 0
Статус: Offline
Кузина Анастасия 9в

https://cloud.mail.ru/public/5JSx/fJgHZCFZi
 
Школьный форум » Персональные страницы учителей » Попова Елена Петровна » Рекурсивные алгоритмы 9 класс
Страница 1 из 11
Поиск:


                 


Copyright Alex Corp © 2017