ГДЗ: Параграф § 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) происходит зацикливание.