2020-06-29
73
Согласно алгоритму:
S(n)=n+S(n+2)+S(n*3) при n<6,
S(n)= n,n>=6
2) аккуратно и последовательно выполним вычисления:
s(2)=2+s(4)+S(6), т.е необходимо найти S(4) и s(6).
s(4)=4+s(6)+s(12)
s(6)=6
s(12)=12
s(4)=4+6+12=22
s(2)=2+22+6=30
Ответ 30.
Рассмотрим еще один рекурсивный алгоритм:
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)?
Обозначим через Z(n) количество звездочек, которые выводит программа при вызове F(n)
Из программы видим, что
Z(n) = 1 при всех n <= 0
Z(n) = 1 +Z(n-2) + Z(n div 2) + Z(n div 2) при n > 0
N div 2– это частное от деления n на 2
4) попробуем начать с нуля:
Z(0) = 1
Z(1) = 1 + Z(-1) + Z(0) + Z(0) = 1 + 1 +2* 1 =4
Z(2) = 1 + Z(0) + Z(1) + Z(1) = 1 + 1 + 2*4 = 10
Z(3) = 1 + Z(1) + Z(1)+ Z(1) = 1 +3* 4 = 13
Z(4) = 1 + Z(2) + Z(2) + Z(2) = 1 + 3*10 = 31
Z(5) = 1 + Z(3) + Z(2) + Z(2) = 1 + 13 +2*10 = 34
Можно анализировать с конца, как в предыдущей задаче, ответ будет таким же.
Ответ:34
Следующая задача:
Определите, что выведет на экран программа при вызове F(9).
procedure F(n: integer);
Begin
if n > 0 then begin
write(n);
F(n - 4);
F(n div 2)
end
end;
Решение:
1. при вызове F(9) условие n>0 выполняется, распечатывается 9, затем вызывается F(n-4) = F(5), затем вызывается F(n div 2) = F(4); т.е. можно записать, что F(9)= 9 F(5) F(4)
Аналогично рассматриваем F(5) и F(4)
F(5)= 5 F(1) F(2)
F(4)= 4 F(0) F(2)
Теперь неизвестны F(2), F(1)
3. F(2)= 2 F(-2) F(1)
F(1)= 1 F(-3) F(0)=1, т.к при n<=0 ничего не выводится
F(2)= 2 F(-2) F(1) =2 1
F(4)= 4 F(0) F(2) =4 2 1
F(5)= 5 F(1) F(2)=5 1 2 1
F(9)= 9 F(5) F(4)=9 5 1 2 1 4 2 1
Учащимся проверить данную задачу на компьютере, выполнив следующую программу:
program rekyrsia;
procedure F(n: integer);
Begin
if n > 0 then begin
write(n);
F(n - 4);
F(n div 2)
end
end;
Begin
f(9);
readln;
End.
Последовательность будет аналогичной.
Задачи, разобранные в теоретическом материале желательно набрать в ABCPascal и проанализировать.
Домашнее задание:
Составить программу в ABCPascal для решения задачи и присоединить в ВШ.
Задача. Написать программу вычисления членов геометрической прогрессии через рекурсию (функцию или подпрограмму).
.
МЕСТО ВСТАВКИ ВЫПОЛНЕННОГО ДОМАШНЕГО ЗАДАНИЯ
Напоминаю. В четверг 21.05 2020 видеоурок с использованием Zoom. Ссылку выложу в whatsapp 21.05 перед уроком. Начало в 9.00.
ПРИМЕЧАНИЕ
Нужно скачать и иметь у себя дома Электронный учебник, которым мы пользовались на уроке, и программу ABCPascal. Это все находится на Яндекс диске по ссылкам:
- учебник (занимает 3,13 Мб) https://yadi.sk/d/5YNwdkJFVqXL0w
- программа для установки ABCPascal (занимает 84,4 Мб) https://yadi.sk/d/uT4dRKgYj1JX6A
Вопросы можно задать по адресу a-lvr@yandex.ru, или в WhatsApp +7(9205646603) 7 мая 2020 года с 9.00 до 10.00 (время фактического проведения урока 1-ая и 2-ая группа), или 13 мая 2020 года в среду с 15.15 до 16.00 (часы неаудиторной занятости, проведение индивидуальной консультации).
