Решайте задания по одному, проверяйте себя сразу и открывайте подсказки там, где нужно.
1. Возводит в квадрат
2. Прибавить 2
3. Умножить на 2Сколько существует программ, для которых при исходном числе 2 результатом является число 64 и
при этом траектория вычислений не содержит число 8?
Верный ответ: 99
Обозначим F(n) — число программ, которые переводят 2 в n и не проходят через 8. Число n могло получиться:
• из n − 2 командой «Прибавить 2»;
• из n / 2 командой «Умножить на 2», если n чётно;
• из √n командой «Возвести в квадрат», если n — полный квадрат.
Эти варианты нужно складывать. Даже если две разные команды переводят одно и то же исходное число в один результат, они образуют разные программы. Например, из 2 в 4 можно попасть и умножением на 2, и возведением в квадрат; вместе с путём 2→4 через «+2» это даёт F(4)=3.
Задаём F(2)=1 и F(8)=0, чтобы исключить все траектории через 8. Нечётные числа недостижимы. Последовательно получаем:
F(4)=3, F(6)=3, F(8)=0, F(12)=3, F(16)=6, F(24)=9, F(32)=18, F(36)=27, F(48)=48, F(56)=69, F(60)=81.
Для 64 складываются три возможных последнего шага: из 62 командой «+2» — 81 программа, из 32 командой «×2» — 18 программ, из 8 возведением в квадрат — 0 программ из-за запрета. Поэтому F(64)=81+18+0=99.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18946.
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3
Сколько существует программ, которые преобразуют исходное число 1 в число 38, и при этом
траектория вычислений содержит число 8 и не содержит чисел 10 и 11?
Верный ответ: 23374
Все команды увеличивают число, поэтому обязательное число 8 делит каждую программу на два независимых участка: 1 → 8 и 8 → 38. Запреты 10 и 11 относятся ко второму участку.
Для команд «+1», «+2», «×3» обозначим F(n) число программ в n. Последняя команда могла прийти из n − 1, из n − 2 или, если n делится на 3, из n / 3. Поэтому F(n) = F(n − 1) + F(n − 2) + F(n / 3), где третье слагаемое используется только при делимости на 3.
Участок 1 → 8.
При F(1)=1 получаем значения 1, 1, 3, 4, 7, 12, 19, 31 для чисел от 1 до 8. Значит, до 8 существует 31 программа.
Участок 8 → 38 без 10 и 11.
Начинаем новый расчёт с F(8)=1 и задаём F(10)=F(11)=0. После запретов первые новые пути появляются в 24 и 27 благодаря умножению на 3. Последовательный подсчёт даёт F(24)=1, F(27)=4, F(30)=16, F(33)=68, F(36)=288, F(38)=754.
Для каждого из 31 способов дойти до 8 существует 754 допустимых продолжения, поэтому 31 · 754 = 23374.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18919.
1. Прибавить 1
2. Сделай нечётноеВыполняя первую команду, исполнитель увеличивает число на 1, а выполняя вторую — из числа x получает число 2x + 1. Сколько существует программ, для которых при исходном числе 1 результатом является число 47 и при этом траектория вычислений не содержит числа 25 и 33?
Верный ответ: 227
Команды только увеличивают число, поэтому удобно считать количество способов получить каждое значение.
Обозначим F(n) — число допустимых программ из 1 в n. К числу n всегда можно прийти из n − 1 командой «Прибавить 1». Если n нечётно, к нему также можно прийти командой «Сделай нечётное» из числа (n − 1) / 2, поскольку 2 · ((n − 1) / 2) + 1 = n.
Получаем правило:
• для чётного n: F(n) = F(n − 1);
• для нечётного n: F(n) = F(n − 1) + F((n − 1) / 2).
Запрещённые числа нельзя включать в траекторию, поэтому принудительно задаём F(25)=0 и F(33)=0.
Последовательный расчёт даёт до первого запрета F(23)=47, F(24)=47, затем F(25)=F(26)=0. После этого F(27)=13, F(29)=26, F(31)=44, но в точке 33 снова ставим ноль. Далее получаем F(35)=23, F(37)=46, F(39)=76, F(41)=106, F(43)=143, F(45)=180 и F(47)=227.
Обнуление запрещённых точек важно: все программы, которые могли бы пройти через 25 или 33, автоматически перестают участвовать в последующих значениях.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18892.
1. Прибавить 1
2. Умножить на 2
Программа для исполнителя – это последовательность команд.
Верный ответ: 28
Обе команды увеличивают число, поэтому программа, траектория которой содержит 10, однозначно распадается на два независимых участка: сначала 1 → 10, затем 10 → 20. Количества программ на участках нужно перемножить.
Для подсчёта введём F(n) — число программ, приводящих к n. Последняя команда могла быть «+1», тогда предыдущее число n − 1. Если n чётно, последней могла быть команда «×2», тогда предыдущее число n / 2. Поэтому F(n) = F(n − 1) + F(n / 2) для чётного n и F(n) = F(n − 1) для нечётного.
Участок 1 → 10.
F(1)=1; далее получаем F(2)=2, F(3)=2, F(4)=4, F(5)=4, F(6)=6, F(7)=6, F(8)=10, F(9)=10, F(10)=14.
Участок 10 → 20.
Считаем заново с F(10)=1. До числа 19 существует по одному пути, а к 20 можно прийти либо из 19 командой «+1», либо из 10 командой «×2». Поэтому получаем 2 программы.
Итоговое количество равно 14 · 2 = 28.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18865.