ЕГЭ 2019, не могу разобраться, помогите пожалуйста. №22 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Калькулятор – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 33 и при этом траектория вычислений содержит число 16 и не содержит числа 30? Можете максимально подробно расписать решение, объяснить что к чему? Заранее спасибо.

Ответ:22Объяснение:Понятно, что каждая из команд может только увеличить число.У нас обязательно есть число 16, из него есть два пути:1. сделать +12. сделать x2Если мы сделаем +1, то после этого уже точно не сможем сделать x2, т.к. 17 x 2 =  34, а 34 > 33, а уменьшить число мы не сможем. Если мы будем делать постоянно +1, то мы точно пройдём через 30.Значит не нужно делать +1, когда мы на числе 16, а надо делать x2.Следовательно, концовка у нас точно будет такая 16 -> 32 -> 33.Теперь надо посчитать, сколько различных способов получить 16 из 2. К любому такому способу мы допишем нашу концовку и получим программу подходящую под наши условия, и к тому же все программы, подходящие под данные условия, выглядят именно так.Считать сколькими способами можно получить 16 из 2 будет динамическим программированием.ans[i] - количество различных программ, которые получают i из 2.Очевидно, ans[2] = 1 (пустая программа).ans[3] = 1 (нужно сделать +1)ans[4] = ans[3] + ans[2] = 2 (можно сделать +1 к 3, а можно x2 к 2)Далее вычисления всегда следующие:ans[i] = ans[i - 1] + ans[i / 2] для чётных i (можно либо добавить +1 к числу i - 1, либо сделать x2 для числа i / 2)ans[i] = ans[i - 1] для нечётных i (можно получить только путём добавления +1 к числу i - 1)Итак, считаем:ans[2] = 1ans[3] = ans[2] = 1ans[4] = ans[3] + ans[2] = 2ans[5] = ans[4] = 2ans[6] = ans[5] + ans[3] = 4ans[7] = ans[6] = 4ans[8] = ans[7] + ans[4] = 6ans[9] = ans[8] = 6ans[10] = ans[9] + ans[5] = 8ans[11] = ans[10] = 8ans[12] = ans[11] + ans[6] = 12ans[13] = ans[12] = 12ans[14] = ans[13] + ans[7] = 16ans[15] = ans[14] = 16ans[16] = ans[15] + ans[8] = 22Значит 16 из 2 можно получить 22 способами. И столькими же способами можно получить 33 из 2 выполняя условия задачи.

Оценить ответ

Не нравится ответ?

Если ответ на твой вопрос отсутствует, или он не полный, то рекомендуем найти информацию через поиск на сайте.

Найти другие ответы

Загрузить картинку
Новые вопросы и ответы