Помогите пожалуйста решить не программно!! Нужно вручную! Очень очень нужно
Автомат обрабатывает натуральное число N по следующему алгоритму: 1. Строится двоичная запись числа N. 2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления полученной суммы на 2. 3. Предыдущий пункт повторяется для записи с добавленной цифрой. 4. Результат переводится в десятичную систему и выводится на экран. Сколько различных чисел, принадлежащих отрезку [90; 160], могут появиться на экране в результате работы автомата?
Ответы
Ответ:
92 93 96 97 100 101 104 105 108 109 112 113 116 117 120 121 124 125 128 129 132 133 136 137 140 141 144 145 148 149 152 153 156 157 160
Объяснение:
Согласно второму пункту, после перевода в двоичный вид, если кол-во едениц четное дописываем в его конец 0, если нечетное, то 1. Значит: если кол-во едениц БЫЛО четным, то оно не изменится и останется четным, если же оно нечетное, то добавится одна единица и их кол-во СТАНЕТ четным. Основная мысль этого пункта: Кол-во едениц в записи после него всегда четно. Перейдём к 3 пункту и увидим, что действия такие же как и в пункте 2, только с добавленной цифрой в конце, но мы то знаем, что после 2 пункта наша запись всегда будет иметь четное кол-во едениц, а значит в 3 пункте у нас всегда будет выполняться условие с четностью суммы цифр в записи т.е. мы будем дописать в конец числа еще один 0. Перед тем как перейдём к 10-чным числам нужно более точно поговорить о нашей полученной записи: мы дописали к изначальному двоичному представлению десятичного натурального числа две цифры причем вторая всегда 0, т.е. наше запись всегда будет заканчиваться на 00 или 01. В целом вот и вся задача, осталось только выбрать те десятичные числа из диапазона [90;160], двоичная запись которых оканчивается на 00 или 01, ведь остальная (предшествующая 00 и 01) часть нас не интересует, ведь в бесконечном множество натуральных чисел всегда найдется такое, двоичная запись которого будет совпадать с предшествующая 00 и 01 частью у чисел из нашего диапазона.
Для определения этих чисел достаточно перевести число 90 в двоичную систему исчисления:
90 - 1011010
Будем смотреть на первые два разряда (т.е. последние две цифры):
91 - 1011011
92 - 1011100
93 - 1011101
94 - 1011110
95 - 1011111
Заметим, что они чередуются в порядке 00 01 10 11 00 01 и т.д. (Вообще, конечно, это неправильно называть каким-то интересным замечанием чередования, ведь так работает двоичная система счисления, просто я не подобрал более подходящего словосочетания :) ) Т.е. нас интересуют числа 92, 93, 96, 97 ... Иными словами, нас будут интересовать 2 числа через 2 начиная с 92.
Успехов!