Форум » Теория игр » [C3] Пример решения » Ответить
[C3] Пример решения
deaidko: Здравствуйте! Можете ли указать в моём решении некоторые упущения или ошибки, и потянет ли это решение хотя бы на 2 балла? Обращаюсь сюда из-за безысходности, так как в моём небольшом городке нет нормального учителя по информатике, приходится учиться "онлайн". Заранее благодарю. C3-9 (задание из вашего сборника). У исполнителя Калькулятор три команды, которым присвоены номера: 1. прибавь 1 2. прибавь 3 3. умножь на 4 Сколько есть программ, которые число 1 преобразуют в число 18? Ответ обоснуйте. 1) Заметим, что все команды увеличивают число, значит рассматриваем только числовой отрезок [1;18]. 2) Обозначим K(n) как количество программ для получения числа n. 3) Очередное число n можно получить через программы, последней командой которого является +1 | +3 | *4. 4) Таким образом, K(n) есть сумма K этих трёх программ (исключая третий случай, когда число не делится на 4). 5) Для вычисления очередного K(n) есть две рекуррентные формулы: a) K(n) = K(n-1) + K(n-3) [когда число не кратно 4]. b) K(n) = K(n-1) + K(n-3) + K(n/4) [когда число кратно 4]. 6) Построим таблицу нахождения K(n): {тут идёт таблица, 18 столбцов, 2 строки, n и K(n) , ответ 572} Для n<4 формулы неприменимы, так что заполним вручную. K(1)=1 (пустая команда) K(2)=1 (1+1) K(3)=1 (1+1+1) Ответ: 572. PS. Знаю, что осталось мало времени, готовиться начал всего с марта, но на сегодняшний день дошел до C3 и появились вопросы.
Ответов - 3
KaLaboOk: извиняюсь, а разве второй случай не будет исключаться тоже, когда прибавлять нечего, ибо если написать по плану в какой-либо программе, может выскочить ошибка
Поляков: deaidko пишет: Можете ли указать в моём решении некоторые упущения или ошибки Мысли правильные. Ваше решение, по крайней мере, на 2 балла. Скорее всего - на 3. Пункт 4 написан корявым русским языком, сложно понять. Очередное число можно получить командой "+1" - для всех, больших 1; командой "+3" - для всех, больших 3; и командой "*4" - для всех, кратных четырём. Других вариантов нет, поэтому мы рассмотрели все возможные программы. Желательно, чтобы эта фраза прозвучала.
Zealot: здравствуйте,моя задача была такой: 2 команды: 1)увеличивает на 1 2) увеличивает все цифры в числе на 1(кроме чисел,оканчивающихся на 9),сколько вариантов получения из числа 14 число 37 мое решение: 1)Заметим,что число увеличивается при выполнении любой команды 2) Разберем простые случаи. Для числа 15 существует 1 программа,14+1=15,аналогично для чисел 16,17,18..24 Для числа 25 существует 2 программы 14+11=25 и 24+1=25,аналогично для чисел 26,27,28,29,31...37 3)Таким образом получаем,что для чисел 14-24,30 имеем Кn=K(n-1) а для чисел 25-29,31-37 имеем Kn=K(n-1)+K(n-11) Заполним вручную таблицу с 25 по 37(так как для чисел 14-24 имеется только 1 программа) 25-2 26-3 27-4 28-5 29-6 30-6 31-7 32-8 33-9 34-10 35-11 36-13 37-16 Ответ: 16 за это мне поставили 1 балл,стоит ли идти на апелляцию?(заранее прошу прощение,если написал не в ту тему)
полная версия страницы