Задание 22
ТЕМА 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 = N2 → 8·M8 →11.
N2 → 8 – количество программ преобразующих число 2 в число 8.
M8 →11 - количество программ преобразующих число 8 в число 11.
Можно обозначить Nk - количество всевозможных программ с помощью которых можно получить число k из исходного. Тогда можно составить рекурентное соотношение, которое связывает число ki с предшествующими числами траектории. Число k можно получить с помощью следующих трех команд:
1. Увеличить на 1 число k-1;
2. Увеличить на 2 число k-2;
3. Умножить на 2 числа k/2 (справедливо для четных чисел);
Nk = Nk-1 + Nk-2 - для нечётных чисел
Nk = Nk-1 + Nk-2 +Nk/2 - для чётных чисел
Рассчитаем отдельно N2 → 8 и M8 →11 по рекурентным соотношениям:
N2 = 1 (нулевая пустая программа)
N3 = 1 (одна программа получения из цифры 2 цифры 3 прибавлением 1)
N4 = Nk-1 + Nk-2 +Nk/2 = N3 + N2 + N2 = 1 + 1 + 1 =3 (три программы получения цифры 4)
N5 = Nk-1 + Nk-2 = N4 + N3 = 3 + 1 = 4 (четыре программы получения цифры 5)
N6 = Nk-1 + Nk-2 +Nk/2 = N5 + N4 + N3 = 4 + 3 + 1 = 8 (восемь программ получения цифры 6)
N7 = Nk-1 + Nk-2 = N6 + N5 = 8 + 4 = 12 (двенадцать программ получения цифры 7)
N8 = Nk-1 + Nk-2 +Nk/2 = N7 + N6 + N4 = 12 + 8 + 3 = 23 = N2 → 8 (количество программ преобразующих цифру 2 в цифру 8)
Терерь определим M8 →11:
M8 = 1 (нулевая пустая программа)
M9 = 1 (одна программа получения из цифры 8 цифры 9 добавлением 1)
M10 = M9 + M8 = 1 + 1 = 2 (две программы получения цифры 10 из цифры 8)
M11 = M10 + M9 = 2 + 1 = 3 = M8 →11(количество программ преобразующих цифру 8 в цифру 11)
Значит, x = N2 → 8·M8 →11 = 23·3 = 69
Ответ: 69
Способ 2 (построение таблиц количества программ получения чисел в траектории).
Ответ: 69
Способ 3 (построение графов, отображающих количество программ получения чисел в траектории).
Найдем количество программ, с помощью которых можно получить из числа 11 цифру 8 (N11 → N8). Потом найдем количество программ которые получают из цифры 8 цифру 2 (N8 → N2) и перемножим найденные результаты.
1) N8 → N2 = 23
2) N11 → N8 = 3
x = N8→ 2·M11 →8 = 23·3 = 69
Ответ: 69
Пример 2
У исполнителя есть три команды, которым присвоены номера:
1. прибавь 1
2. умножь на 2
3. умножь на 3.
Первая из них увеличивает исходное число на экране на 1, вторая увеличивает это число в 2 раза, а третья - в 3 раза.
Программа для исполнителя — это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 15?
Решение
Способ 1 (метод рекурентных соотношений)
Можно обозначить Nk - количество всевозможных программ с помощью которых можно получить число k из исходного. Тогда можно составить рекурентное соотношение, которое связывает число ki с предшествующими числами траектории. Число k можно получить с помощью следующих трех команд:
1. Увеличить на 1 число k-1;
2. Умножить на 2 число k/2;
3. Умножить на 3 число k/3.
Исходя из заданных команд, все числа будут удовлетворять двум условиям, и можно составить рекуррентные соотношения:
- если число k не делится на 2 или на 3, тогда Nk = Nk-1, потому что можно лишь одной командой получить число k из числа k-1 (команда 1).
- если число k делится на 2 или на 3, тогда: Nk = Nk-1 + Nk/2 +Nk/3
Рассчитаем количество всех программ N1→15 в соответствии с составленными рекурентными соотношениями:
N1 = 1 (нулевая пустая программа)
N2 = 2 (две программы получения из цифры 1 цифры 2 прибавлением 1 и умножением на 2)
N3 = Nk-1 + Nk/2 + Nk/3 = N2 + N1 = 2 + 1 =3 (три программы получения цифры 3)
N4 = Nk-1 + Nk/2 = N3 + N2 = 2 + 3 = 5 (пять программ получения цифры 4)
N5 = N4 = 5
N6 = Nk-1 + Nk/2 + Nk/3 = N5 + N3 + N2 = 5 + 3 + 2 = 10 (десять программ получения цифры 6)
N7 = N6 = 10
N8 = Nk-1 + Nk/2 = N7 + N4 = 10 + 5 = 15 (пятнадцать программ получения цифры 8)
N9 = Nk-1 + Nk/3 = N8 + N3 = 15 + 3 = 18 (восемнадцать программ получения цифры 9)
N10 = Nk-1 + Nk/2 = N9 + N5 = 18 + 5 = 23 = N11
N12 = Nk-1 + Nk/2 + Nk/3 = N11 + N6 + N4 = 23 + 10 + 5 = 38 = N13
N14 = Nk-1 + Nk/2 = N13 + N7 = 38 + 10 = 48
N15 = Nk-1 + Nk/3 = N14 + N5 = 48 + 5 = 53
Значит N1→15 = 53
Ответ: 53
Способ 2 (построение таблиц количества программ получения чисел в траектории).
Способ 3 (построение графов, отображающих количество программ получения чисел в траектории).
Ответ: 53
Комментарии, отзывы и предложения Вы можете направить на e-mail, указанный в контактах или оставить в гостевой книге, указав тему вопроса: перейти в гостевую книгу