Вначале на карточке были записаны два натуральных числа. Раз в минутку
Изначально на карточке были записаны два естественных числа. Раз в минутку Мистер Бот берёт эту карточку и, если 1-ое число было нечётным, пишет на дощечке второе число, в неприятном случае ничего не делает. После этого Мистер Бот выкидывает ветхую карточку и делает новую, первым числом на которой является уменьшенное в два раза и округлённое до единицы вниз первое число с предшествующей карточки, а вторым - двойное 2-ое число с предшествующей карточки. Когда Мистер Робот получил карточку, 1-ое число на которой одинаково нулю, он подсчитал сумму всех чисел, записанных на доске. Что он получил?
Примечание к задачке: Задачку можно относить как к теме инвариантов, так и к теме систем счисления.
Он получил творенье начальных чисел.
За странноватым описанием процесса по сущности прячется описание метода умножения в столбик двоичных чисел: на i-м шаге, если первое число нечетное (=если на i-м месте справа в первом числе стоит 1), к сумме прибавляется 2^(i - 1) * второе число (=если всё записано в двоичной системе счисления, умножение на степень двойки равносильно сдвигу числа влево).
Инвариант здесь таковой: в любой момент времени сумма всех чисел, записанных на дощечке, и произведения чисел, записанных на карточке, не меняется.
Поначалу на примере, если на карточке записаны 5 и 7:
- карточка: 5 и 7, сумма на дощечке: 0
- карточка: 2 и 14, сумма на доске: 7
- карточка: 1 и 28, сумма на доске: 7
- карточка: 0 и 56, сумма на дощечке: 7 + 28 = 35
В общем случае: пусть перед текущим шагом на дощечке числа a и b, сумма чисел на доске s; значение суммы ab + s. Есть два варианта:
- a = 2a'. Тогда на последующем шаге на карточке будет a' и 2b, на дощечке ничего не изменится. Значение суммы a' * 2b + s = 2a' * b + s = ab + s
- a = 2a' + 1. На следующем шаге на карточке a' и 2b, на доску добавится b. Значение суммы a' * 2b + s + b = (2a' + 1) b + s = ab + s
Изначально на дощечке выписаны числа суммой 0 (инвариант равен произведению чисел на карточке = p), в конце творение чисел на карточке одинаково 0, тогда сумма выписанных чисел одинакова p.
-
Вопросы ответы
Статьи
Информатика
Статьи
Экономика.
Экономика.
Русский язык.
Разные вопросы.
Математика.
Разные вопросы.
Математика.
Химия.
Русский язык.
Геометрия.