Форум » Динамическое программирование » Задача 22-94 » Ответить
Задача 22-94
aln1947: Не понял задачу 22-94. Помогите решить. Заранее благодарен. Александр Наймушин
Ответов - 3
Поляков: aln1947 пишет: Не понял задачу 22-94. Сначала решаем стандартную задачу с первыми двумя командами: "-1" и "-3". Получается так:[pre2] 22: 1 21: 1 20: 1 19: 2 18: 3 17: 4 16: 6 15: 9 14: 13 13: 19 12: 28 11: 41 10: 60 9: 88 8: 129 7: 189 6: 277 5: 406 4: 595 3: 872 2: 1278[/pre2] Теперь подключаем третью команду: взять остаток от деления на 4. Тут может получиться только число меньше, чем 4, из интересующих нас - это 2 и 3. Тройка получается из всех чисел, которые дают 3 в остатке при делении на 4:[pre2] 19: 2 15: 9 11: 41 7: 189[/pre2]Таким образом, значение для тройки нужно увеличить на 2+9+41+189=241. Двойка получается из всех чисел, которые дают 2 в остатке при делении на 4:[pre2] 22: 1 18: 3 14: 13 10: 60 6: 277[/pre2]Таким образом, значение для двойки нужно увеличить на 1+2+13+60+277=354, и еще плюс 241, которые перешли с тройки по команде "-1". В итоге для двойки получаем[pre2]1278+241+354=1873.[/pre2]
Teacher78: Поляков пишет: Теперь подключаем третью команду: взять остаток от деления на 4. Тут может получиться только число меньше, чем 4, из интересующих нас - это 2 и 3. Почему не берем остатки =1?
Поляков: Teacher78 пишет: Почему не берем остатки =1? Потому что конечное число - 2. А из 1 в 2 никак не попасть, обе доступные команды уменьшают число.
полная версия страницы