Изначально на карточке были записаны два натуральных числа. Раз в минуту Мистер Робот берёт эту карточку и, если первое число было нечётным, пишет на доске второе число, в противном случае ничего не делает. После этого Мистер Робот выбрасывает старую карточку и делает новую, первым числом на которой является уменьшенное вдвое и округлённое до единицы вниз первое число с предыдущей карточки, а вторым - удвоенное второе число с предыдущей карточки. Когда Мистер Робот получил карточку, первое число на которой равно нулю, он подсчитал сумму всех чисел, записанных на доске. Что он получил?
Примечание к задаче: Задачу можно относить как к теме инвариантов, так и к теме систем счисления.
Примечание к задаче: Задачу можно относить как к теме инвариантов, так и к теме систем счисления.
More Questions From This User See All
Answers & Comments
Verified answer
Он получил произведение исходных чисел.
За странным описанием процесса по сути скрывается описание алгоритма умножения в столбик двоичных чисел: на i-м шаге, если первое число нечетное (=если на i-м месте справа в первом числе стоит 1), к сумме прибавляется 2^(i - 1) * второе число (=если всё записано в двоичной системе счисления, умножение на степень двойки равносильно сдвигу числа влево).
Инвариант тут такой: в любой момент времени сумма всех чисел, записанных на доске, и произведения чисел, записанных на карточке, не меняется.
Сначала на примере, если на карточке записаны 5 и 7:
В общем случае: пусть перед текущим шагом на доске числа a и b, сумма чисел на доске s; значение суммы ab + s. Есть два случая:
Изначально на доске выписаны числа суммой 0 (инвариант равен произведению чисел на карточке = p), в конце произведение чисел на карточке равно 0, тогда сумма выписанных чисел равна p.