Задать вопрос
16 февраля, 01:44

Изначально на карточке были записаны два натуральных числа. Раз в минуту Мистер Робот берёт эту карточку и, если первое число было нечётным, пишет на доске второе число, в противном случае ничего не делает. После этого Мистер Робот выбрасывает старую карточку и делает новую, первым числом на которой является уменьшенное вдвое и округлённое до единицы вниз первое число с предыдущей карточки, а вторым - удвоенное второе число с предыдущей карточки. Когда Мистер Робот получил карточку, первое число на которой равно нулю, он подсчитал сумму всех чисел, записанных на доске. Что он получил?

Примечание к задаче: Задачу можно относить как к теме инвариантов, так и к теме систем счисления.

+3
Ответы (1)
  1. 16 февраля, 02:52
    0
    Он получил произведение исходных чисел.

    За странным описанием процесса по сути скрывается описание алгоритма умножения в столбик двоичных чисел: на 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.
Знаете ответ?
Сомневаетесь в ответе?
Найдите правильный ответ на вопрос ✅ «Изначально на карточке были записаны два натуральных числа. Раз в минуту Мистер Робот берёт эту карточку и, если первое число было ...» по предмету 📘 Информатика, а если вы сомневаетесь в правильности ответов или ответ отсутствует, то попробуйте воспользоваться умным поиском на сайте и найти ответы на похожие вопросы.
Смотреть другие ответы
Похожие вопросы по информатике
1) Десятичное число 4563 в двоичной системе счисления равно 2) Десятичное число 800 в восьмеричной системе счисления равно 3) Десятичное число 781 в шестнадцатеричной системе счисления равно 4) Двоичное число 1000000 в десятичной системе счисления
Ответы (1)
А) 1000001110 в двоичной системе счисления+1100110 в двоичной системе счисления б) 10001001 в двоичной системе счисления-1010101 в двоичной системе счисления в) 45 в восьмеричной системе счисления * 71 в восьмеричной системе счисления г) 1AF1 в
Ответы (1)
Какое из чиселa A B C D записанных в различных системах счисления является наибольшим если, A = 121 восмиричной системы счисления B = 82 десятеричной системы счисления C = 53 шестнадцатиричной системы счисления D = 1000000 двоичной системы счисления?
Ответы (1)
Некоторый алгоритм из одной цепочки десятичных цифр получает новую цепочку следующим образом. Сначала вычисляется сумма всех цифр в цепочке. Если сумма является нечетным числом, к цепочке справа дописывается цифра 1, в противном случае - цифра 0.
Ответы (1)
1. Выполните сложение в двоичной системе счисления: 101112 + 1011102 Результат запишите в двоичной системе счисления. 2. Выполните сложение в двоичной системе счисления: 11012 + 110112 Запишите ответ в двоичной системе счисления.
Ответы (1)