ТЕМА 22

"Анализ результата исполнения алгоритма"

Пример 1

У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

3. Умножить на 2

Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает его на 2.

Программа для исполнителя – это последовательность команд. Сколько существует таких программ, которые исходное число 2 преобразуют в число 11 и при этом траектория вычислений программы содержит число 8?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 5 траектория будет состоять из чисел 10, 11, 13

Решение

Способ 1 (метод рекурентных соотношений).

Общее количество программ x, которые преобразуют число 2 в число 11, с учетом того что траектория вычислений содержит число 8 будет определятся как произведение количества программ: x = N_{2 → 8}·M_{8 →11.}

N_{2 → 8} – количество программ преобразующих число 2 в число 8.

M_{8 →11} - количество программ преобразующих число 8 в число 11.

Можно обозначить N_k - количество всевозможных программ с помощью которых можно получить число k из исходного. Тогда можно составить рекурентное соотношение, которое связывает число k_i с предшествующими числами траектории. Число k можно получить с помощью следующих трех команд:

1. Увеличить на 1 число k-1;

2. Увеличить на 2 число k-2;

3. Умножить на 2 числа k/2 (справедливо для четных чисел);

N_k = N_k-1 + N_k-2 - для нечётных чисел

N_k = N_k-1 + N_k-2 +N_k/2 - для чётных чисел

Рассчитаем отдельно N_{2 → 8} и M_{8 →11} по рекурентным соотношениям:

N₂ = 1 (нулевая пустая программа)

N₃ = 1 (одна программа получения из цифры 2 цифры 3 прибавлением 1)

N₄ = N_k-1 + N_k-2 +N_k/2 = N₃ + N₂ + N₂ = 1 + 1 + 1 =3 (три программы получения цифры 4)

N₅ = N_k-1 + N_k-2 = N₄ + N₃ = 3 + 1 = 4 (четыре программы получения цифры 5)

N₆ = N_k-1 + N_k-2 +N_k/2 = N₅ + N₄ + N₃ = 4 + 3 + 1 = 8 (восемь программ получения цифры 6)

N₇ = N_k-1 + N_k-2 = N₆ + N₅ = 8 + 4 = 12 (двенадцать программ получения цифры 7)

N₈ = N_k-1 + N_k-2 +N_k/2 = N₇ + N₆ + N₄ = 12 + 8 + 3 = 23 = N_{2 → 8} (количество программ преобразующих цифру 2 в цифру 8)

Терерь определим M_{8 →11}:

M₈ = 1 (нулевая пустая программа)

M₉ = 1 (одна программа получения из цифры 8 цифры 9 добавлением 1)

M₁₀ = M₉ + M₈ = 1 + 1 = 2 (две программы получения цифры 10 из цифры 8)

M₁₁ = M₁₀ + M₉ = 2 + 1 = 3 = M_{8 →11}(количество программ преобразующих цифру 8 в цифру 11)

Значит, x = N_{2 → 8}·M_{8 →11} = 23·3 = 69

Ответ: 69

Способ 2 (построение таблиц количества программ получения чисел в траектории).

Ответ: 69

Способ 3 (построение графов, отображающих количество программ получения чисел в траектории).

Найдем количество программ, с помощью которых можно получить из числа 11 цифру 8 (N₁₁ → N₈). Потом найдем количество программ которые получают из цифры 8 цифру 2 (N₈ → N₂) и перемножим найденные результаты.

1) N₈ → N₂ = 23

2) N₁₁ → N₈ = 3

x = N_{8→ 2}·M_{11 →8} = 23·3 = 69

Ответ: 69

Пример 2

У исполнителя есть три команды, которым присвоены номера:

1. прибавь 1

2. умножь на 2

3. умножь на 3.

Первая из них увеличивает исходное число на экране на 1, вторая увеличивает это число в 2 раза, а третья - в 3 раза.

Программа для исполнителя — это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 15?

Решение

Способ 1 (метод рекурентных соотношений)

Можно обозначить N_k - количество всевозможных программ с помощью которых можно получить число k из исходного. Тогда можно составить рекурентное соотношение, которое связывает число k_i с предшествующими числами траектории. Число k можно получить с помощью следующих трех команд:

1. Увеличить на 1 число k-1;

2. Умножить на 2 число k/2;

3. Умножить на 3 число k/3.

Исходя из заданных команд, все числа будут удовлетворять двум условиям, и можно составить рекуррентные соотношения:

• если число k не делится на 2 или на 3, тогда N_k = N_k-1, потому что можно лишь одной командой получить число k из числа k-1 (команда 1).
• если число k делится на 2 или на 3, тогда: N_k = N_k-1 + N_k/2 +N_k/3

Рассчитаем количество всех программ N_1→15 в соответствии с составленными рекурентными соотношениями:

N₁ = 1 (нулевая пустая программа)

N₂ = 2 (две программы получения из цифры 1 цифры 2 прибавлением 1 и умножением на 2)

N₃ = N_k-1 + N_k/2 + N_k/3 = N₂ + N₁ = 2 + 1 =3 (три программы получения цифры 3)

N₄ = N_k-1 + N_k/2 = N₃ + N₂ = 2 + 3 = 5 (пять программ получения цифры 4)

N₅ = N₄ = 5

N₆ = N_k-1 + N_k/2 + N_k/3 = N₅ + N₃ + N₂ = 5 + 3 + 2 = 10 (десять программ получения цифры 6)

N₇ = N₆ = 10

N₈ = N_k-1 + N_k/2 = N₇ + N₄ = 10 + 5 = 15 (пятнадцать программ получения цифры 8)

N₉ = N_k-1 + N_k/3 = N₈ + N₃ = 15 + 3 = 18 (восемнадцать программ получения цифры 9)

N₁₀ = N_k-1 + N_k/2 = N₉ + N₅ = 18 + 5 = 23 = N₁₁

N₁₂ = N_k-1 + N_k/2 + N_k/3 = N₁₁ + N₆ + N₄ = 23 + 10 + 5 = 38 = N₁₃

N₁₄ = N_k-1 + N_k/2 = N₁₃ + N₇ = 38 + 10 = 48

N₁₅ = N_k-1 + N_k/3 = N₁₄ + N₅ = 48 + 5 = 53

Значит N_1→15 = 53

Ответ: 53

Способ 2 (построение таблиц количества программ получения чисел в траектории).

Способ 3 (построение графов, отображающих количество программ получения чисел в траектории).

Ответ: 53

• Примеры, рассмотренные на этой странице в формате pdf: скачать
• Решенные задачи по теме других авторов: скачать
• Смотреть видеоуроки по теме: видео 1, видео 2, видео 3

Комментарии, отзывы и предложения Вы можете направить на e-mail, указанный в контактах или оставить в гостевой книге, указав тему вопроса: перейти в гостевую книгу