Вычти 2

Прибавь 3,

вычти 2.

Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются).

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

Решение (1 способ, построение полного графа решения):

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

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

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

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

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

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

5) и пятый – 6 решений:

6) Ответ: 6.

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

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

2) Ответ: 6.

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

1) для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения

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

3) Ответ: 6.

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

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

Date: 2015-07-22; view: 316; Нарушение авторских прав