Сколько различных чисел можно получить из числа 1 с помощью программы

Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:

1. Удвоить
2. Удвоить и прибавить

Первая команда умножает число на экране на 2, вторая – умножает его на 2, а затем прибавляет 1.
Программа для исполнителя – это последовательность команд. Например, программа 121 при исходном числе 3 последовательно получит числа 6, 13 и 26. Результатом программы будет число 26.

Сколько различных результатов можно получить из исходного числа 1 после выполнения программы, содержащей ровно 9 команд?

СтатГрад Вариант ИН2010502 26.04.2021– задание №23

Решение:

Источник: informatikaexpert.ru

infoegehelp.ru

У исполнителя Кузнечик две команды:
1. прибавь 3,
2. вычти 2.
Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются). Программа для Кузнечика – это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд?

Сколько различных чисел можно получить из числа 3

Решение:

Изобразим ход выполнения команд:

Всего потенциально возможных чисел: 2 5 =32. Количество чисел уменьшилось за счет сокращения расчетов. Если при выполнении команды получились одинаковые значения, одно из них не учитываем в дальнейших расчетах (число перечеркнуто).

Изобразим ход выполнения команд с помощью графа:

Источник: infoegehelp.ru

B13 (повышенный уровень, время – 7 мин)

Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются).Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд?Решение (1 способ, построение полного графа решения):

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

1. теперь посмотрим, что удается получить за 2 шага; учитывая, что (-2+3)=(+3-2), одно из значений повторяется: мы можем получить -1 + 3 = 2 и 4 – 2 = 2, то есть получается не дерево, а граф:

так с помощью программ, содержащих ровно 2 команды, можно получить 3 различных числа

1. строим еще уровень: программы из 3-х команд дают 4 разных числа:

обратим внимание, что числа на каждом уровне отличаются друг от друга на 5 =(+3-(-2), то есть они не могут повторяться

1. четвертый уровень дает 5 различных чисел:

1. и пятый – 6 решений:

1. Ответ: 6.

Решение (2 способ, краткий):

1. как следует из приведенных построений, если система команд исполнителя состоит из двух команд сложения/ вычитания, то все возможные программы, содержащие ровно N команд , дают N+1 различных чисел
2. Ответ: 6.

Решение (3 способ, Л.В. Зенцова, лицей № 36 ОАО «РЖД» г.Иркутска):

1. для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения
2. поэтому существует всего 6 возможных программ, состоящих ровно из 5 команд (с точностью до перестановки): 11111 11112 11122 11222 12222 22222
3. Ответ: 6.

Ещё пример задания:

У исполнителя Калькулятор две команды: 1. прибавь 1

Сколько различных чисел можно получить с помощью программы

2. Умножь на 2.

Первая из них увеличивает число на экране на 1, вторая – удваивает его.Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 4 команд?Решение (1 способ, построение полного графа решения):

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

1. теперь посмотрим, что удается получить за 2 шага:

в отличие от предыдущей задачи, здесь порядок выполнения операций влияет на результат, поэтому пока все числа получаются разные

1. делаем 3-й шаг, получаем 8 разных чисел:

1. на 4-ом шаге рассматриваем все возможные программы из 4-х команд, получаем числа

6, 10, 9, 16, 8, 14, 13, 24, 7, 12, 11, 20, 10, 18, 17, 32

1. здесь всего 16 чисел, но одно из них (10) повторяется 2 раза, а остальные встречаются по 1 разу, поэтому получаем 15 различных чисел

Ответ: 15. Ещё пример задания (ege.Yandex.Ru):

1. Прибавь 6

Источник: studfile.net