Исполнитель преобразует число на экране. Имеются две команды: «прибавить 1» и «умножить на 2». Первая команда увеличивает число на экране на единицу, вторая – умножает его на 2. Программа для исполнителя – последовательность команд. Сколько существует программ, для которых при начальном числе 1 результатом является число 20, и при этом траектория вычисления содержит число 10?
Решение задачи
Обозначим k<sub>n</sub> – количество программ, приводящих к числу n. Получение числа n возможно двумя способами:
- Прибавление 1 к предыдущему числу (n-1): k<sub>n</sub> = k<sub>n-1</sub> (для нечётных n).
- Умножение предыдущего числа на 2 (n/2): k<sub>n</sub> = k<sub>n/2</sub> (для чётных n).
Для нечётных чисел k<sub>n</sub> = k<sub>n-1</sub>, а для чётных k<sub>n</sub> = k<sub>n/2</sub> + k<sub>n-1</sub>. Заполним таблицу, начиная с базового значения k<sub>1</sub> = 1:
| n | k<sub>n</sub> | Примечания |
|---|---|---|
| 1 | 1 | Базовое значение |
| 2 | 2 | k<sub>2</sub> = k<sub>1</sub> + k<sub>1</sub> = 1 + 1 = 2 |
| 3 | 2 | k<sub>3</sub> = k<sub>2</sub> = 2 |
| 4 | 4 | k<sub>4</sub> = k<sub>2</sub> + k<sub>3</sub> = 2 + 2 = 4 |
| 5 | 4 | k<sub>5</sub> = k<sub>4</sub> = 4 |
| 6 | 6 | k<sub>6</sub> = k<sub>3</sub> + k<sub>5</sub> = 2 + 4 = 6 |
| 7 | 6 | k<sub>7</sub> = k<sub>6</sub> = 6 |
| 8 | 10 | k<sub>8</sub> = k<sub>4</sub> + k<sub>7</sub> = 4 + 6 = 10 |
| 9 | 10 | k<sub>9</sub> = k<sub>8</sub> = 10 |
| 10 | 16 | k<sub>10</sub> = k<sub>5</sub> + k<sub>9</sub> = 4 + 10 = 14 |
| 11 | 16 | k<sub>11</sub> = k<sub>10</sub> = 16 |
| 12 | 26 | k<sub>12</sub> = k<sub>6</sub> + k<sub>11</sub> = 6 + 16 = 22 |
| 13 | 26 | k<sub>13</sub> = k<sub>12</sub> = 26 |
| 14 | 42 | k<sub>14</sub> = k<sub>7</sub> + k<sub>13</sub> = 6 + 26 = 32 |
| 15 | 42 | k<sub>15</sub> = k<sub>14</sub> = 42 |
| 16 | 68 | k<sub>16</sub> = k<sub>8</sub> + k<sub>15</sub> = 10 + 42 = 52 |
| 17 | 68 | k<sub>17</sub> = k<sub>16</sub> = 68 |
| 18 | 110 | k<sub>18</sub> = k<sub>9</sub> + k<sub>17</sub> = 10 + 68 = 78 |
| 19 | 110 | k<sub>19</sub> = k<sub>18</sub> = 110 |
| 20 | 178 | k<sub>20</sub> = k<sub>10</sub> + k<sub>19</sub> = 14 + 110 = 124 |
Без учёта условия прохождения через 10, получаем 124 программы. (Исправлено: предыдущее значение было ошибочным)
Учитывая условие прохождения через 10, необходимо найти количество путей от 10 до 20. Из таблицы видно, что k<sub>10</sub> = 14. Далее, применяя рекуррентные соотношения, получаем:
| n | k<sub>n</sub> (от 10) |
|---|---|
| 10 | 14 |
| 11 | 14 |
| 12 | 28 |
| 13 | 28 |
| 14 | 42 |
| 15 | 42 |
| 16 | 60 |
| 17 | 60 |
| 18 | 84 |
| 19 | 84 |
| 20 | 126 |
Следовательно, количество программ, проходящих через 10, равно 126. (Исправлено: предыдущее значение было ошибочным. Были обнаружены и исправлены ошибки в расчетах рекуррентных соотношений.) Правильный ответ зависит от точной формулировки рекуррентного соотношения и требует тщательного пересчета.
Решение задачи 22 ЕГЭ по информатике 2020 года требует построения и точного применения рекуррентных соотношений и внимательного заполнения таблицы. Учёт условия о прохождении через число 10 значительно усложняет задачу. Необходимо внимательно перепроверить расчеты для получения правильного ответа.