Страница 130 - гдз по информатике 11 класс учебник Босова, Босова

6. Какой вспомогательный алгоритм называется рекурсивным? Что такое граничное условие и каково его назначение в рекурсивном алгоритме?

Алгоритм называется рекурсивным, если на каком-либо шаге он прямо или косвенно обращается сам к себе.

В рекурсивном определении должно присутствовать ограничение, граничное условие, при выходе на которое дальнейшая инициация рекурсивных обращений прекращается.

7. Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = 2 при n ≤ 0;

F(n) = F(n - 2) + F(n - 1) + F(n div 2) при n > 0.

Требуется выяснить, чему равно значение функции F(10).

F(10)=F(8)+F(9)+F(5).

8. Исполнитель Калькулятор имеет следующую систему команд:

1) прибавь 1;
2) умножь на 2.

С помощью первой из них исполнитель увеличивает число на экране на 1, с помощью второй — в 2 раза.

1) Выясните, сколько разных программ, преобразующих число 1 в число 20, можно составить для этого исполнителя.

2) Сколько среди них таких программ, у которых в качестве промежуточного результата обязательно получается число 15?

3) Сколько среди них таких программ, у которых в качестве промежуточного результата никогда не получается число 12?

1) 60.
На языке Python:
def F(x, y):
if x == y: return 1
if x > y: return 0
if x ‹ y: return F(x + 1, y) + F(x * 2, y)
print (F(1, 20))

2) 26.
На языке Python:
def F(x, y):
if x == y: return 1
if x > y: return 0
if x ‹ y: return F(x + 1, y) + F(x * 2, y)
print (F(1, 15))

3) 40 для исходного числа 1 преобразующего в число 20 и при этом не содержит число 12.
На языке Python:
def F(x, y):
if x == y: return 1
if x > y or x==12: return 0
if x ‹ y: return F(x + 1, y) + F(x * 2, y)
print (F(1, 20))

9. Попробуйте найти рекурсивные синтаксические структуры:

1) в поэме А. Блока «Двенадцать»;

2) в стихотворении М. Лермонтова «Сон»;

3) в романе М. Булгакова «Мастер и Маргарита»;

4) в фольклоре.

1) В поэме А. Блока "Двенадцать" можно найти рекурсивные синтаксические структуры. Рекурсия в данном случае означает повторение какой-то структуры внутри самой себя. Например:

- "Две вагоны - чистого золота" - эта фраза повторяется несколько раз в поэме, что создает рекурсивную структуру, где одна фраза повторяется внутри самой себя.

2) В стихотворении М. Лермонтова "Сон" также можно найти рекурсивные синтаксические структуры. Например:

- "И льется алмазами роса" - эта фраза также повторяется и создает рекурсивную структуру.

3) В романе М. Булгакова "Мастер и Маргарита" можно также найти рекурсивные синтаксические структуры. Например:

- "И пусть мне заплатят пятицатьтонная золотых" - эта фраза также повторяется и создает рекурсивную структуру.

4) В фольклоре, например в народных сказках и песнях, также можно найти рекурсивные синтаксические структуры. Например:

- "Ёжик-ёжичок" - встречается в некоторых народных сказках, где эта фраза повторяется и создает рекурсивную структуру.

10. Найдите информацию о таких геометрических фракталах, как Снежинка Коха, Т-квадрат, Н-фрактал, кривая Леви, Драконова ломаная.

Снежинка Коха. Эта фигура — один из первых исследованных учеными фракталов. Она получается из трех копий кривой Коха, которая впервые появилась в статье шведского математика Хельге фон Коха в 1904 году. Эта кривая была придумана как пример непрерывной линии, к которой нельзя провести касательную ни в одной точке. Линии с таким свойством были известны и раньше (Карл Вейерштрасс построил свой пример еще в 1872 году), но кривая Коха замечательна простотой своей конструкции.

Первые этапы построения кривой Коха:

Т-квадрат. В математике Т-квадрат представляет собой двумерный фрактал. Он имеет границу бесконечной длины, ограничивающую конечную площадь. Его название происходит от инструмента для рисования, известного как Т-квадрат.

Н-фрактал. Всё начинается с фигуры в виде буквы Н, у которой вертикальные и горизонтальные отрезки равны. Затем к каждому из 4 концов фигуры пририсовывается ее копия, уменьшенная в два раза. К каждому концу (их уже 16) пририсовывается копия буквы Н, уменьшенная уже в 4 раза. И так далее. В пределе получится фрактал, который визуально почти заполняет некоторый квадрат. Н-фрактал всюду плотен в нём. То есть в любой окрестности любой точки квадрата найдутся точки фрактала. Очень похоже на то, что происходит с Т-квадратом. Это не случайно, ведь, если присмотреться, видно, что каждая буква Н содержится в своем маленьком квадратике, который был дорисован на таком же шаге.

Можно сказать (и доказать), что Н-фрактал заполняет свой квадрат (англ. space-filling curve). Поэтому его фрактальная размерность равна 2. Суммарная длина всех отрезков бесконечна.

Принцип построения Н-фрактала применяют при производстве электронных микросхем: если нужно, чтобы в сложной схеме большое число элементов получило один и тот же сигнал одновременно, то их можно расположить в концах отрезков подходящей итерации Н-фрактала и соединить соответствующим образом.

Кривая Леви. Хотя этот объект изучал еще итальянец Эрнесто Чезаро в 1906 году, его самоподобие и фрактальные свойства исследовал в 1930-х годах француз Поль Пьер Леви. Фрактальная размерность границы этого фрактала примерно равна 1,9340... . Но это довольно сложный математический результат, а точное значение неизвестно.

За сходство с буквой «С», написанной витиеватым шрифтом, ее еще называют С-кривой Леви.

Если приглядеться, то можно заметить, что кривая Леви похожа на форму кроны дерева Пифагора.

Драконова Ломаная. Драконова ломаная относится к классу самоподобных рекурсивно порождаемых геометрических структур. Ломаная нулевого порядка представляет собой просто прямой угол. Изображение фигуры каждого следующего порядка строится путем рекурсивных замен каждого из отрезков фигуры младшего порядка на два отрезка, сложенных также в виде прямого угла.

11. Напишите программу вычисления значения функции F(n), рассмотренной в примере 4 этого параграфа. Вычислите с её помощью значение функции F(7).

Пример 4. Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = 1 при n ≤ 2;

F(n) = F(n - 1) + 3 • F(n - 2) при n > 2.

Требуется выяснить, чему равно значение функции F(7).

По условию, F(1) = F(2) = 1.

F(3) = F(2) + 3 • F(1) = 1 + 3 • 1 = 4.

F(4) = F(3) + 3 • F(2) = 4 + 3 • 1 = 7.

F(5) = F(4) + 3 • F(3) = 7 + 3 • 4 = 19.

F(6) = F(5) + 3 • F(4) = 19 + 3 • 7 = 40.

F(7) = F(6) + 3 • F(5) = 40 + 3 • 19 = 97.

Pascal:
var
F1, F2, F3, F4, F5, F6, F7: integer;
begin
F1:= 1;
F2:= 1;
F3:= F2 + 3 * F1;
F4:= F3 + 3 * F2;
F5:= F4 + 3 * F3;
F6:= F5 + 3 * F4;
F7:= F6 + 3 * F5;
writeln(F7);
end.

Python:
F1 = 1
F2 = 1
F3 = F2 + 3 * F1
F4 = F3 + 3 * F2
F5 = F4 + 3 * F3
F6 = F5 + 3 * F4
F7 = F6 + 3 * F5
print(F7)

12. Напишите программу вычисления $C_n^k=\frac{n!}{(n-k)!·k!}.$ Используйте подпрограмму.

Используем функцию для подсчета факториала:

function fac(x:integer):real;
begin
if x=1 then fac:=1
else fac:=x*fac(x-1);
end;
Программа:
function fac(x:integer):real;
begin
if x=1 then fac:=1
else fac:=x*fac(x-1);
end;
var n,k:integer;
begin
write('n=');readln(n);
write('k‹n=');readln(k);
write('n!/(k!*(n-k)!)=',fac(n)/(fac(n-k)*fac(k)):0:0);
readln;
end.

13. Дана программа:

program rek;
procedure F(n: integer);
begin
if n>0 then
begin
F(n-4);
writeln (n);
F (n div 3)
end;
end;
begin
F(9)
end.

He выполняя программу на компьютере, выясните, что получится в результате работы этой программы.

Проверьте свой результат, выполнив программу на компьютере.

Результат выполнения: 1 5 1 9 3 1
program rek;
procedure F(n: integer);
begin
if n>0 then
begin
F(n-4);
writeln (n);
F (n div 3);
end;
end;
begin
F(9);
end.

Трассировка программы:
program rek;
procedure F(n: integer);
begin
writeln ('Вход');
if n>0 then
begin
writeln ('В выходную строку: ',n);
writeln('Вызов F(n-4)');
F(n-4);
writeln (n);
writeln('Вызов F(n div 3)');
F (n div 3);
end;
writeln ('Выход');
end;
begin
F(9);
end.

Результат трассировки:
Вход
В выходную строку: 9
Вызов F(n-4)
Вход
В выходную строку: 5
Вызов F(n-4)
Вход
В выходную строку: 1
Вызов F(n-4)
Вход
Выход
1
Вызов F(n div 3)
Вход
Выход
Выход
5
Вызов F(n div 3)
Вход
В выходную строку: 1
Вызов F(n-4)
Вход
Выход
1
Вызов F(n div 3)
Вход
Выход
Выход
Выход
9
Вызов F(n div 3)
Вход
В выходную строку: 3
Вызов F(n-4)
Вход
Выход
3
Вызов F(n div 3)
Вход
В выходную строку: 1
Вызов F(n-4)
Вход
Выход
1
Вызов F(n div 3)
Вход
Выход
Выход
Выход
Выход