|
Знаю довольно короткое решение задачи, особенно 3 пункт. Просьба если решение вам очевидно - его не писать, а дать решить задачу новым людям. На доске написано число 8, за один ход на доску можно записать либо число с доски умноженное на 2, либо сумму 2 чисел с доски.
задан 18 Апр '12 21:41 
Balon |
|
Думаю, тут хорошо использовать двоичное представление числа. Тогда 0 соответствует умножение, а 1 - прибавление чисел.
Например, 832=8*104, а 104(dec) = 1101000 (bin). Поэтому можно предложить такой алгоритм. Первая 1 соответствует исходному числу, далее нулю соответствует умножение на 2, 1 - умножение на 2 и прибавление первого числа. Получаем для 104: $%8\to (16\to 24)\to48\to(96\to104)\to208\to416\to832$% Ясно, что таким образом можно получить число вида 8k за m шагов, где m = (число цифр в двоичном представлении k) + (число единиц в этом представлении) - 2. Вычитаем 2, так как первая 1 не учитывается. Но почему это число шагов нельзя уменьшить - пока неясно. Это еще надо додумать. По сути предложенный алгоритм повторяет схему Горнера для вычисления значений многочленов. Как известно, она - самая экономная в вычислительном смысле для многочлена с произвольными коэффициентами. Хотя для некоторых конкретных многочленов есть более быстрые схемы. отвечен 19 Апр '12 23:41 
DocentI По моему мнению, двоичная система об'ясняет минимальность ходов. Так как умножение на 2 приписывает ноль справа, а прибавление другого числа либо складывает количество единиц , либо приписывает ноль справа. Если честно аналогию со схемой Горнера не понял, можно , пожалуйста , поподробней про неё .
(21 Апр '12 20:26)
Balon
Что такое позиционная запись числа? Это, по сути многочлен от основания системы счисления. Например, $%110100_2=1\cdot 2^5+1\cdot 2^4 + 1\cdot 2^2$%. Ну, а значение многочлена можно подсчитать по схеме Горнера. Например, число $%104=110100_2$% можно подсчитать так. Первую 1 "сносим". Потом умножаем ее на 2 и прибавляем 1. Потом снова умножаем на 2 и прибавляем 1. Далее стоит коэффициент 0, так что только умножаем на 2, и т.д. Т.е. все сводится к операциям, предложенным Вами.
(21 Апр '12 22:29)
DocentI
|
Дополнение (доказательство минимальности 8 шагов в п.3). Рассмотрим максимальные числа, которые можно получить за $%n$% шагов. Наибольшее из таких чисел равно $% N_0(n) = 8 \cdot 2^n = 2^{n+3}$%, следующее по величине $% N_1(n) = N_0(n-1) + N_0(n-2) = 2^{n+2} + 2^{n+1} = 3 \cdot 2^{n+1}$%. За $%n$% шагов невозможно получить число, большее, чем $% N_0(n)$%, а также находящееся в диапазоне от $% N_1(n)$% до $% N_0(n)$%. Из первой части этого утверждения следует, что число 832 нельзя получить менее, чем за 7 шагов, из второй части следует, что число 832 нельзя получить за 7 шагов, т.к. $% N_1(7) < 832 < N_0(7) $%, следовательно, число 832 невозможно получить менее, чем за 8 шагов. А то, что за 8 шагов получить можно, доказывает приведенный пример. отвечен 19 Апр '12 1:46 
Андрей Юрьевич В 3 пункте наиболее интересно доказательство минимальности ходов, ответ 8 ходов верен
(19 Апр '12 22:48)
Balon
Это доказательство очевидно. Первые 6 шагов обеспечивают максимальный рост числа, на седьмом шаге максимальный рост даст перебор, используем "предмаксимальный", восьмой шаг - единственно возможный.
(19 Апр '12 23:05)
Андрей Юрьевич
Новое доказательство хоршее. Однако его трудно распространить на произвольное число, а хотелось бы. Подозреваю, что двоичная структура числа здесь важна.
(20 Апр '12 17:06)
DocentI
Да, но это уже другая задача "За какое минимальное число шагов можно получить заданное число". Если так обобщить задачу, то тогда и начальное значение нужно брать либо произвольное, либо 2, иначе непонятно, чем 8 лучше других чисел?
(20 Апр '12 17:34)
Андрей Юрьевич
Да, это другая задача, но она гораздо интереснее. Лучше брать за начальное число 1.
(20 Апр '12 20:05)
DocentI
Думаю, что n-разрядное двоичное число, содержащее k единиц можно получить из единицы за n+k-2 шагов.
(21 Апр '12 18:00)
Андрей Юрьевич
Да, можно, я так и написала в своем ответе. Но вот можно ли за меньшее число шагов? Ведь по условию можно прибавлять не только 1, но и другие промежуточные числа.
(21 Апр '12 22:52)
DocentI
Я предложил схему, при которой на каждом шаге получается максимально большое число - сначала умножение на 2 (наибольшее возможное число раз), потом заполнение "внутренними" единицами. Эта схема наиболее быстрая в "локальном" смысле - каждый ее шаг дает максимальное увеличение числа. Думаю, она в "глобальном" смысле самая быстрая (или одна из нескольких самых быстрых).
(22 Апр '12 14:46)
Андрей Юрьевич
показано 5 из 8
показать еще 3
|
Можно ли писать число, которое уже есть на доске? Например, после 8, 16, снова написат 16 (как 8*2)?
Числа повторяться могут