графы / Графы 2.3

Определение количества результатов после выполнения программы из N команд

B13. У исполнителя Кузнечик две команды:

1.прибавь 7,

2.вычти 5.

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

«Кузнечик»

Результат выполнения алгоритма для исполнителя Кузнечик зависит только от количества команд «прибавь 7» и «вычти 5», а не от того, в каком порядке выполняются команды. Так, например, если в программе пять команд сложения и две команды вычитания, то результат будет равен 125 независимо от порядка следования команд в программе. Поскольку количество команд в программе фиксировано, то результат однозначно определяется количеством команд одного из двух возможных видов, например, команд сложения. Если в программе N+ команд сложения, то число команд вычитания будет N- = 7 - N+. В программе из 7 команд может присутствовать только 0, 1, 2, 3, 4, 5, 6 или 7 команд сложения, т.е. возможно всего 8 возможных результатов.