** вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R...

Question

На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом: 1. Строится двоичная запись числа 2N. 2. Складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). 3. Над полученной записью производятся действия - справа дописывается остаток от деления суммы цифр на 2. Например, двоичная запись 101 числа 5 будет преобразована в 101000. Полученная таким образом запись является двоичной записью искомого числа R. Укажите минимальное число N, для которого результат работы алгоритма будет больше 131. В ответе это число запишите в десятичной системе. ПОМОГИТЕЕЕ!!!!!!!!!!!!

Comments

а, это задача, понял

---

язык?

Answer 1

Ответ:

17

Объяснение:

Рассмотрим работу алгоритма:

1. Умножить двоичное число на 2 — всё равно что приписать ноль справа (по аналогии с десятичной системой — при умножении на 10 приписываем 0). Значит, если было число X₂, на первом шаге оно превращается в X0₂.

2. Остаток от деления на 2 — показатель чётности. Если сумма цифр чётна, остаток равен нулю, если нет — единице. Так как приписанный ноль не влияет на сумму цифр, всё зависит от суммы цифр X₂. Значит, на этом шаге число имеет вид X00₂ или X01₂.

3. Вновь повторяется данное действие. Если сумма цифр была чётна, то в конце на втором шаге приписаны два нуля, что это не влияет на сумму цифр, то есть она всё ещё чётна. Если сумма цифр была нечётна, то в конце были приписаны 0 и 1, единица в сумме с остальными цифрами (дающими нечётное число) даёт чётное число. Значит, на этом шаге в любом случае будет приписан 0, число будет иметь вид X000₂ или X010₂.

Наименьшее число R = 132₁₀ = 10000100₂. На 100 число оканчиваться не может, значит, будем прибавлять по единице, пока число не станет оканчиваться на 000. Число станет равным 10001000₂. Такое может быть при N = 10001₂ = 17₁₀. Сумма цифр чётна, поэтому в конце приписываем три нуля.