ГДЗ: Параграф § 9 / Информатика 11 класс

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

Вспомогательный алгоритм — это автономный алгоритм, который предназначен для использования в качестве цельного фрагмента внутри другого, основного алгоритма.

Метод последовательного уточнения, также известный как метод «сверху вниз», предполагает разработку программы пошагово. Сначала создается краткий набросок основной программы, где логически целые фрагменты заменяются временными подпрограммами — «заглушками». Затем эти заглушки последовательно заменяются реальными, работающими подпрограммами. Проверка правильности работы программы осуществляется на каждом уровне иерархии.

Ключевые этапы включают:

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

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

Определение периметра и выбор подпрограммы

Для решения задачи необходимо найти длины трех диагоналей граней, которые образуют стороны треугольника. Грани параллелепипеда имеют размеры \((a \times b)\), \((b \times c)\) и \((a \times c)\).

• Длина диагонали первой грани (через ребра \(a\) и \(b\)): \( d_1 = \sqrt{a^2 + b^2} \)
• Длина диагонали второй грани (через ребра \(b\) и \(c\)): \( d_2 = \sqrt{b^2 + c^2} \)
• Длина диагонали третьей грани (через ребра \(a\) и \(c\)): \( d_3 = \sqrt{a^2 + c^2} \)

Периметр треугольника \(P\) равен сумме этих длин: \( P = d_1 + d_2 + d_3 \).

Для вычисления длины диагонали, которая является единственным результатом, целесообразно использовать функцию. Функция будет принимать на вход две длины ребер и возвращать одно значение — длину диагонали, по формуле \( d(x, y) = \sqrt{x^2 + y^2} \).

Вычисление F(10)

Используем рекурсивное соотношение \( F(n) = F(n-2) + F(\lfloor n \div 2 \rfloor) + 1 \) при \( n > 0 \):

• \( F(1) = F(-1) + F(\lfloor 1 \div 2 \rfloor) + 1 = F(-1) + F(0) + 1 \). По базовому условию \( F(n) = 2 \cdot n \) при \( n \le 0 \): \( F(-1) = 2 \cdot (-1) = -2 \); \( F(0) = 2 \cdot 0 = 0 \). Тогда \( F(1) = -2 + 0 + 1 = -1 \).
• \( F(2) = F(0) + F(1) + 1 = 0 + (-1) + 1 = 0 \).
• \( F(3) = F(1) + F(\lfloor 3 \div 2 \rfloor) + 1 = F(1) + F(1) + 1 = (-1) + (-1) + 1 = -1 \).
• \( F(4) = F(2) + F(2) + 1 = 0 + 0 + 1 = 1 \).
• \( F(5) = F(3) + F(\lfloor 5 \div 2 \rfloor) + 1 = F(3) + F(2) + 1 = (-1) + 0 + 1 = 0 \).
• \( F(6) = F(4) + F(3) + 1 = 1 + (-1) + 1 = 1 \).
• \( F(7) = F(5) + F(\lfloor 7 \div 2 \rfloor) + 1 = F(5) + F(3) + 1 = 0 + (-1) + 1 = 0 \).
• \( F(8) = F(6) + F(4) + 1 = 1 + 1 + 1 = 3 \).
• \( F(9) = F(7) + F(\lfloor 9 \div 2 \rfloor) + 1 = F(7) + F(4) + 1 = 0 + 1 + 1 = 2 \).
• \( F(10) = F(8) + F(5) + 1 = 3 + 0 + 1 = 4 \).

Итоговое значение \( F(10) = 4 \).

Решение задачи о программах для исполнителя «Калькулятор»

• 1. Сколько разных программ преобразуют число 1 в число 20?

  Обозначим \(K(n)\) как количество программ, преобразующих 1 в \(n\). Задачу удобнее решать «обратным ходом», преобразуя \(n\) в 1.

  • Базовое условие: \(K(1) = 1\).
  • Рекуррентное соотношение (для \(n > 1\)): \(K(n) = K(n-1)\) (отмена команды +1) \(\begin{cases} + K(\lfloor n/2 \rfloor), & \text{если } n \text{ четно (отмена команды } \times 2) \ + 0, & \text{если } n \text{ нечетно} \end{cases}\)

  Правильный рекурсивный подход: \(K(n) = K(n-1) + K(n/2)\) (если \(n\) четно) или \(K(n) = K(n-1)\) (если \(n\) нечетно).

  Проведем расчет (обратным ходом):

  \(n\)	\(K(n)\) (путь от 1 до \(n\))	Расчет
  1	1	База
  2	1 + K(1)	\(K(1) + K(2/2) = 1+1 = 2\)
  3	K(2)	\(K(3-1) = 2\)
  4	K(3) + K(2)	\(2+2 = 4\)
  5	K(4)	\(4\)
  6	K(5) + K(3)	\(4+2 = 6\)
  7	K(6)	\(6\)
  8	K(7) + K(4)	\(6+4 = 10\)
  9	K(8)	\(10\)
  10	K(9) + K(5)	\(10+4 = 14\)
  11	K(10)	\(14\)
  12	K(11) + K(6)	\(14+6 = 20\)
  13	K(12)	\(20\)
  14	K(13) + K(7)	\(20+6 = 26\)
  15	K(14)	\(26\)
  16	K(15) + K(8)	\(26+10 = 36\)
  17	K(16)	\(36\)
  18	K(17) + K(9)	\(36+10 = 46\)
  19	K(18)	\(46\)
  20	K(19) + K(10)	\(46+14 = 60\)

  Всего программ, преобразующих 1 в 20: 60.

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

  Требуется найти количество программ, идущих из \(1 \to 15\) и умножить его на количество программ, идущих из \(15 \to 20\).

  • Количество программ \(1 \to 15\): \(K(15) = 26\).
  • Количество программ \(15 \to 20\): Используем \(K(n)\) для пути \(15 \to n\), где \(K(15)=1\).
    \(K(16) = K(15)+0 = 1\) (только +1)
    \(K(17) = K(16) = 1\)
    \(K(18) = K(17)+0 = 1\)
    \(K(19) = K(18) = 1\)
    \(K(20) = K(19) + K(\lfloor 20/2 \rfloor) = K(19) + K(10)\). Но \(K(10)\) не может быть использовано, так как \(10 \ne 15 \cdot 2\). Команда \(\times 2\) применима только, если \(15 \times 2 = 30 > 20\). То есть, из 15 в 20 можно попасть только командой +1.
    \(K(20) = K(19) = 1\).
    Программ \(15 \to 20\): \(K(15)=1, K(16)=1, K(17)=1, K(18)=1, K(19)=1, K(20)=1\). Итого 1 программа (15 \(\to\) 16 \(\to\) 17 \(\to\) 18 \(\to\) 19 \(\to\) 20).

  Общее количество программ: \(26 \cdot 1 = 26\).

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

  Общее количество программ \(1 \to 20\) — \(K(20) = 60\). Найдем количество программ, которые проходят через 12 (\(1 \to 12 \to 20\)), и вычтем их из общего числа.

  • Количество программ \(1 \to 12\): \(K(12) = 20\).
  • Количество программ \(12 \to 20\): \(K_{12 \to 20}\).
    \(K(12)=1\).
    \(K(13) = K(12) = 1\)
    \(K(14) = K(13) = 1\)
    \(K(15) = K(14) = 1\)
    \(K(16) = K(15) + K(\lfloor 16/2 \rfloor) = K(15) + K(8)\). Но \(8 \ne 12 \cdot 2\). Из 12 в 16: \(12 \xrightarrow{+1} 13 \xrightarrow{+1} 14 \xrightarrow{+1} 15 \xrightarrow{+1} 16\). 1 программа.
    \(K(17) = 1, \dots, K(20) = 1\).
    Всего программ \(12 \to 20\): \(1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 = 1\). (Только команда \(+1\) 8 раз)

  Количество программ, проходящих через 12: \(20 \cdot 1 = 20\).

  Количество программ, не проходящих через 12: \(60 - 20 = 40\).

Примеры рекурсивных синтаксических структур

Рекурсия в синтаксисе (вложение однотипных структур) и композиции (повторение или самоподобие элементов) может быть обнаружена в следующих примерах:

• 1. А. Блок «Двенадцать»: Рекурсивный элемент может проявляться в повторяющихся образах или фразах, которые возвращаются и видоизменяются, создавая структуру, где часть повторяет целое.
• 2. М. Лермонтов «Сон»: Рекурсия композиции может быть найдена в идее сна внутри сна или во вложенных повествовательных рамках, где один рассказчик упоминает другого.
• 3. М. Булгаков «Мастер и Маргарита»: Классический пример рекурсивной структуры — это роман в романе, то есть вложенный сюжет (история Пилата), который является частью основного сюжета и повторяет его темы.
• 4. Фольклор: Типичные примеры — это цепочечные (кумулятивные) сказки (например, «Теремок», «Репка», «Дом, который построил Джек»), где каждый новый элемент добавляется к предыдущей, постоянно повторяющейся структуре. Пример: «Это дом, который построил Джек. А это пшеница, которая в темном чулане хранится в доме, который построил Джек».

Геометрические Фракталы

Фракталы — это структуры, которые обладают свойством самоподобия (рекурсивной природой), то есть их части похожи на целое. Фракталы являются примерами бесконечных рекурсивных структур.

• Снежинка Коха: Получается из равностороннего треугольника путем бесконечного итеративного добавления новых меньших треугольников на среднюю треть каждой стороны. Имеет бесконечную длину периметра при конечной площади.
• T-квадрат и H-фрактал: Фракталы, построенные на основе квадратов или отрезков, где на каждой итерации к концам или углам добавляются уменьшенные копии исходной фигуры (буквы T или H), перпендикулярные им.
• Кривая Леви (C-кривая): Кривая, построенная из отрезка, который на каждой итерации заменяется двумя меньшими отрезками, соединенными под прямым углом, образуя подобие буквы 'С'.
• Драконова ломаная (Дракон Хартера-Хейтвея): Получается путем последовательного сгибания ленты. Ее можно построить, взяв отрезок и заменяя его двумя меньшими отрезками, расположенными под углом 90° к предыдущему.

Программа для вычисления F(n)

Функция задана соотношениями: \( F(n) = 1 \) при \( n \le 2 \); \( F(n) = F(n-1) + 3 \cdot F(n-2) \) при \( n > 2 \).

program CalculateF; var   n: integer;   function F(n: integer): integer;   begin     if n <= 2 then       F := 1     else       F := F(n-1) + 3 * F(n-2);   end; begin   n := 7;   writeln('F(7) = ', F(n)); end.

Значение \(F(7)\) вычисляется следующим образом:

• \( F(1) = 1 \)
• \( F(2) = 1 \)
• \( F(3) = F(2) + 3 \cdot F(1) = 1 + 3 \cdot 1 = 4 \)
• \( F(4) = F(3) + 3 \cdot F(2) = 4 + 3 \cdot 1 = 7 \)
• \( F(5) = F(4) + 3 \cdot F(3) = 7 + 3 \cdot 4 = 19 \)
• \( F(6) = F(5) + 3 \cdot F(4) = 19 + 3 \cdot 7 = 40 \)
• \( F(7) = F(6) + 3 \cdot F(5) = 40 + 3 \cdot 19 = 97 \)

Результат: \( F(7) = 97 \).

Программа для вычисления биномиального коэффициента

Для решения задачи удобно использовать две функции: рекурсивную функцию для вычисления факториала \(N!\) и основную функцию для вычисления \(C_n^k\).

program BinomialCoefficient;   function Factorial(n: integer): longint;   begin     if n = 0 then       Factorial := 1     else       Factorial := n * Factorial(n - 1);   end;   function Combinations(n, k: integer): longint;   begin     if (k < 0) or (k > n) then       Combinations := 0     else       Combinations := Factorial(n) div (Factorial(k) * Factorial(n - k));   end; var   n_val, k_val: integer;   result: longint; begin   n_val := 5;   k_val := 2;   result := Combinations(n_val, k_val);   writeln('C(', n_val, ', ', k_val, ') = ', result); // C(5, 2) = 10 end.

Используется рекурсивная функция Factorial для реализации факториала.

Анализ работы рекурсивной программы

Программа содержит процедуру rek(n), которая рекурсивно вызывает саму себя с аргументами \(n-4\) и \(n \div 3\). Базовое условие: \(n < 0\). Вызов начинается с rek(9).

• rek(9): \(9 \ge 0\). Вызывает:
  • rek(5): \(5 \ge 0\). Вызывает:
    • rek(1): \(1 \ge 0\). Вызывает:
      • rek(-3): \(-3 < 0\). Выход.
      • rek(0): \(0 \ge 0\). Вызывает:
        • rek(-4): \(-4 < 0\). Выход.
        • rek(0): \(0 \ge 0\). Вызывает:
          • rek(-4): Выход.
          • rek(0): Вызывает рекурсию бесконечно.
      • Выводит: 1
      • rek(0): \(0 \ge 0\). Вызывает:
        • rek(-4): Выход.
        • rek(0): Вызывает рекурсию бесконечно.
    • Выводит: 5
    • rek(2): \(2 \ge 0\). Вызывает:
      • rek(-2): Выход.
      • rek(0): Вызывает рекурсию бесконечно.
  • Выводит: 9

  В данной программе процедура rek(0) вызывает rek(0), создавая бесконечную рекурсию, поскольку условие \(n \le 0\) не срабатывает, а \(0 \div 3 = 0\). Программа либо вызовет ошибку переполнения стека, либо зациклится. Если бы программа работала только для положительных \(n\), результатом была бы последовательность выводимых чисел, но из-за rek(0) происходит зацикливание.