Просто УрокТест · информатика
Динамическое программирование: число программ из A в B
Отвечай кликом — после каждого вопроса пояснение. 10 вопросов, 4 варианта, 3–5 минут. Без таймеров и регистрации.
Отвечено 0 из 10 · Верно: 0
1/10
Что вычисляется в задаче динамического программирования «число программ из A в B»?
Пояснение. В этой задаче считается именно количество различных последовательностей команд, приводящих из A в B. Минимальное число команд — это другая задача.
2/10
Если разрешены команды +1 и *2, чему обычно равно dp[A]?
Пояснение. Существует ровно одна пустая программа, которая оставляет число A без изменений. Поэтому dp[A] = 1.
3/10
Для команд +1 и *2 чему равно dp[x], если x > B?
Пояснение. Из чисел, больших B, уже нельзя вернуться к B командами +1 и *2. Поэтому такие значения не учитываются и равны 0.
4/10
Для команд +1 и *2 при чётном x > A какой переход верен?
Пояснение. В x можно прийти либо из x-1 командой +1, либо из x/2 командой *2. Поэтому количества программ складываются.
5/10
В каком порядке заполняют массив dp для команд +1 и *2?
Пояснение. Значение dp[x] зависит от меньших чисел x-1 и x/2. Поэтому массив заполняют от A к B по возрастанию.
6/10
Команды +1 и *2, A = 3, B = 7. Сколько существует программ из 3 в 7?
Пояснение. Есть две программы: 3→4→5→6→7 и 3→6→7. Других подходящих последовательностей нет.
7/10
Команды +1 и *2, A = 1, B = 5. Сколько существует программ из 1 в 5?
Пояснение. Подходят четыре программы: ++++, +*+, *+++ и **+. Поэтому ответ 4.
8/10
Как изменится переход для dp[x], если к командам +1 и *2 добавить команду *3?
Пояснение. Команда *3 добавляет переход из x/3, но только когда x делится на 3. Аналогично *2 учитывается только для чётного x.
9/10
Почему для больших B перебор всех программ обычно неэффективен?
Пояснение. Количество программ быстро растёт, поэтому прямой перебор всех последовательностей становится слишком долгим. Динамическое программирование считает ответ за меньшее время.
10/10
Как учитывается команда *2 при вычислении dp[x] для команд +1 и *2?
Пояснение. Если x чётно, то в x можно прийти из x/2 командой *2. Тогда к ответу добавляется dp[x/2].
Разобрать тему перед пересдачей: статья на нашем сайте.
Важно. Тесты носят информационно-образовательный характер и не являются публичной офертой (ст. 437 ГК РФ) или аттестацией. Возможны неточности — сверяйтесь с официальными источниками (ФИПИ, учебники). Заметили ошибку — напишите нам.