11 класс Информатика ГДЗ учебник Босова Параграф 9

11 класс Информатика ГДЗ учебник Босова Параграф 9. Структурное программирование — Глава 2. Алгоритмы и элементы программирования

Стр.129-131.

1) Суть структурного программирования и его преимущества

Решение. Идея — строить программу из трёх базовых схем: последовательность, ветвление и цикл, избегая «прыжков» и запутанных переходов. Код разбивается на небольшие подпрограммы с чёткими входами/выходами.

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

2) Что называют вспомогательным алгоритмом?

Решение. Это подзадача, решающая типовую операцию и вызываемая из основного алгоритма. В программах — это процедура/функция (подпрограмма), которую можно использовать многократно.

3) Метод последовательного уточнения («сверху вниз»)

Решение. Сначала формулируется общая задача на крупном уровне, затем по шагам декомпозируется на подзадачи более низкого уровня до простых реализаций. Другие названия: декомпозиция, top-down-проектирование, пошаговая детализация.

4) Основные шаги разработки программы методом «сверху вниз»

Определить цель и интерфейс (вход/выход).
Разбить задачу на крупные подзадачи (модули).
Для каждой подзадачи уточнить алгоритм и данные.
Выделить вспомогательные подпрограммы, определить их контракты.
Реализовать и протестировать модули по отдельности, затем весь проект.

5) Параллелепипед с рёбрами a, b, c. Периметр треугольника из диагоналей граней

Решение. Диагонали трёх попарно перпендикулярных граней имеют длины:
d_ab = √(a² + b²), d_ac = √(a² + c²), d_bc = √(b² + c²).
Периметр искомого треугольника:
P = d_ab + d_ac + d_bc.

Вспомогательный алгоритм: функция hyp(p, q) = √(p² + q²) (гипотенуза по двум катетам), которую вызываем три раза и суммируем результаты.

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

Решение. Рекурсивный алгоритм — тот, в котором подпрограмма вызывает саму себя на меньшем аргументе. Граничное (базовое) условие — случай(и), при котором рекурсия не продолжается и подпрограмма сразу возвращает ответ. Назначение — остановить бесконечные вызовы и задать исходные значения (например, 0! = 1).

7) Рекуррентная функция F(n). Найдите F(10)

Дано. F(n)=2 при n≤0; при n>0: F(n)=F(n−2)+F(n−1)+F(n div 2).

Ответ. F(10) = 1486.

Шаблон-код (Pascal):

function F(n: longint): longint;
begin
  if n <= 0 then F := 2
  else F := F(n-2) + F(n-1) + F(n div 2);
end;
begin
  writeln(F(10));
end.

function F(n: longint): longint;

begin

if n <= 0 then F := 2

else F := F(n-2) + F(n-1) + F(n div 2);

end;

begin

writeln(F(10));

end.

8) Исполнитель «Калькулятор»: команды «+1» и «×2»

Сколько программ переводят 1 → 20? 60. (DP по формуле ways[n]=ways[n−1]+(n чётное? ways[n/2]:0), ways[1]=1.)
С обязательным промежуточным результатом 15? 26 (все пути 1→15; из 15 в 20 путь единственный — пять раз «+1»).
Никогда не получая 12? 40 (всего 60 минус 20 путей через 12; из 12 до 20 тоже только «+1»).

Замечание. Пересчёт удобно делать динамикой «снизу вверх».

9) Примеры рекурсивных синтаксических структур в литературе и фольклоре

Поэзия: строфы, где внутри рефрена повторяется мотив/фраза с включением изменённой копии (вложенный повтор).
Проза: «история в истории» (вложенный рассказ персонажа).
Фольклор: сказочная цепочка «пошёл он к… который…» — каждый новый фрагмент содержит предыдущий целиком.

10) Кратко о фракталах: Снежинка Коха, T-квадрат, H-фрактал, кривая Леви, Дракон

Снежинка Коха: на каждой стороне треугольника вырастает «зубчик» из 4 отрезков — бесконечный периметр при конечной площади.
T-квадрат: квадрат делят на 4, затем в определённых позициях оставляют «T»-образные блоки и повторяют процесс.
H-фрактал: от буквы «H» на концах растут меньшие «H» — самоподобная структура.
Кривая Леви: рекурсивная замена отрезка ломаной «уголком» 45°; при пределе получается непрерывная, нигде не дифференцируемая кривая.
Дракон Хартера–Хайтуэя: излом, где каждый отрезок заменяется двумя под прямым углом; даёт «драконью» форму.

11) Программа для F(n) из «пример 4» и вычисление F(7)

Решение. Формула «пример 4» в книге не приведена на скане, поэтому ниже — универсальный шаблон рекурсивной функции. Подставьте тело в соответствии с вашим «примером 4». Для демонстрации показан вариант с формулой из п.7.

function F(n: longint): longint;  { замените тело по вашему примеру 4 }
begin
  if n <= 0 then F := 2
  else F := F(n-2) + F(n-1) + F(n div 2);
end;
begin
  writeln(F(7));
end.

function F(n: longint): longint; { замените тело по вашему примеру 4 }

begin

if n <= 0 then F := 2

else F := F(n-2) + F(n-1) + F(n div 2);

end;

begin

writeln(F(7));

end.

Для формулы из п.7 получится значение F(7)=394.

12) Вычисление C(n, k) = n! / ( (n−k)!·k! ) с подпрограммой

function Fact(x: longint): qword;
var i: longint; r: qword;
begin
  r := 1;
  for i := 2 to x do r := r * i;
  Fact := r;
end;

function C(n, k: longint): qword;
begin
  if (k < 0) or (k > n) then C := 0
  else C := Fact(n) div (Fact(k) * Fact(n-k));
end;

begin
  writeln(C(10, 3));  { пример: 120 }
end.

function Fact(x: longint): qword;

var i: longint; r: qword;

begin

r := 1;

for i := 2 to x do r := r * i;

Fact := r;

end;

function C(n, k: longint): qword;

begin

if (k < 0) or (k > n) then C := 0

else C := Fact(n) div (Fact(k) * Fact(n-k));

end;

begin

writeln(C(10, 3)); { пример: 120 }

end.

Оптимизация: можно сократить умножения, считая произведение от n−k+1 до n и деля на k!.

13) Что напечатает программа с рекурсией F(9)?

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

if n > 0 then

begin

F(n-4);

writeln(n);

F(n div 3);

end;

begin

F(9);

end.

Решение (порядок вывода): 1, 5, 1, 9, 3, 1. Объяснение: дерево вызовов —
F(9) → F(5) → F(1) → печать 1 → печать 5 → F(1) → печать 1 → печать 9 → F(3) → печать 3 → F(1) → печать 1.

§ 9