B 1 У исполнителя Арифметик две команды, которым присвоены номера: прибавь 1, прибавь Первая из них увеличивает на 1 число на экране, вторая у

21 сентября 2013 / Разное

B 13. У исполнителя Арифметик две команды, которым присвоены номера:
1. прибавь 1,
2. прибавь 3.
Первая из них увеличивает на 1 число на экране, вторая увеличивает это число на 3.
Программа для Арифметика — это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 15?

мне важен ход решения

  • Нам нужно набрать 13 единицами и тройками.
    Если троек ноль, то способ 1.
    Если тройка одна, то всего потребуется (13 — 1 * 3) + 1 = 11 команд и +3 можно выполнить в любую из них, т. е. вариантов 11.
    Если тройки две, то всего команд (13 — 2 * 3) + 2 = 9. Количество различных постановок двух троек равно = 36 (см. http://ru.wikipedia.org/wiki/Биномиальный_коэффициент )
    Если тройки 3, то всего команд (13 — 3 * 3) + 3 = 7. По аналогичным соображениям, способов различных расстановок трёх троек = 35
    Если троек 4, то всего команд (13 — 3 * 4) + 4 = 5. И различных расстановок троек     = 5.

    Суммируя всё, получаем 1 + 11 + 36 + 35 + 5 = 88
    Это если я правильно понял условие, и одна последовательность команд отлична от другой, если они имеют различные длины или не совпадают хотя бы в одной позиции. Если же понимать, что последовательности различаются по количеству команд одного типа, то всего различных программ будет 5 (если 0 троек, если 1 тройка, если 2 тройки, 3 или 4 (5 быть не может (3 * 5 > 12)))


Добавить комментарий