Question

Автомат обрабатывает натуральное число N по следующему алгоритму: 1. Строится двоичная запись числа N. 2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления полученной суммы на 2. 3. Предыдущий пункт повторяется для записи с добавленной цифрой. 4. Результат переводится в десятичную систему и выводится на экран. Сколько различных чисел, принадлежащих отрезку [90; 160], могут появиться на экране в результате работы автомата?​

Answer 1

                                     PascalABC.NET                                      

Ответ:

• function ToBinary (x:integer):string;
• begin
• if (x>0) then ToBinary := ToBinary(x div 2) + (x mod 2).ToString;
• end;
• function FromBinary (x:string):integer;
• begin
• if (x.Length>0) then FromBinary := FromBinary(x.Substring(1)) + x[1].ToDigit*Round(Power(2,x.Length-1));
• end;
• function func (x:integer):integer;
• begin
• var s := ToBinary(x);
• loop 2 do s += s.AsEnumerable.Sum(c->c.ToDigit) mod 2;
• func:=FromBinary(s);
• end;
• begin
• Println('f(N):',func(ReadInteger('N:')));
• Println('Количество:',(1..160).Count(x->func(x) in 90..160));
• end.

Примечание:

Если к числу в двоичной системе счисления приписывать в конец цифры, то число увеличивается и никак не может уменьшится. Поэтому, n<f(n). Следовательно, перебор различных чисел, принадлежащих отрезку [90;160], можно смело ставить до 160 (можно и меньше, но лень расписывать вычисления).

ToBinary - функция перевода числа из десятичной СС в двоичную. Можно писать любой алгоритм, необязательно в точности использовать мой.

FromBinary - функция перевода числа из двоичной СС в десятичную. Можно писать любой алгоритм, необязательно в точности использовать мой.

func - функция, которая выполняет преобразования числа согласно условию (пункты 1, 2, 3, 4).

Код кажется большим только из-за процедур и begin/endов. Без них - всего то 7 строчек :). В скринах можно проверить, действительно ли 19 (40-22+1).

Пример работы:

Answer 2

Давайте рассмотрим этот алгоритм на примере, чтобы понять, какие числа могут появиться на экране в результате его работы.

Пусть N = 90. Его двоичная запись - 1011010. Сумма цифр: 1 + 0 + 1 + 1 + 0 + 1 + 0 = 4. Остаток от деления на 2: 4 % 2 = 0. Таким образом, к числу добавится 0, и новая двоичная запись будет 10110100.

Повторим для новой записи: сумма цифр 1 + 0 + 1 + 1 + 0 + 1 + 0 + 0 = 5. Остаток от деления на 2: 5 % 2 = 1. Новая запись: 101101001.

Переведем полученное число 101101001 из двоичной системы в десятичную: 361.

Повторим этот процесс для всех чисел в диапазоне [90; 160] и посмотрим, какие числа могут появиться на экране:

• Для N = 90: 361
• Для N = 91: 362
• ...
• Для N = 159: 569
• Для N = 160: 570

Таким образом, на экране в результате работы автомата могут появиться различные числа: 361, 362, ..., 569, 570. Всего 570 - 361 + 1 = 210 различных чисел.