Форум » Выполнение и анализ алгоритмов для исполнителей » № 3910 » Ответить
№ 3910
inform_lesson: Добрый день. Можно ли № 3910 решить без программирования? Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1) Строится двоичная запись числа N. 2) Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3) Шаг 2 повторяется ещё два раза. 4) Результат переводится в десятичную систему счисления. При каком наибольшем исходном числе N < 100 в результате работы алгоритма получится число, которое делится на 4 и не делится на 8?
Ответов - 2
Поляков: inform_lesson пишет: Можно ли № 3910 решить без программирования? Легко. 1) Число N < 100, поэтому его двоичный код содержит не более 7 знаков. 2) Если результат делится на 4, но не делится на 8, двоичный код заканчивается на 100. 3) Если бы при 2-м и 3-м выполнении шага 2 алгоритма дописывалась последняя цифра, то код заканчивался бы на 111, но это не так. 4) Поэтому два последних приписанных нуля вызваны тем, что в числе после приписывания первой 1 стало меньше нулей. 5) Следовательно, в числе N - равное количество нулей и единиц и оно заканчивается на 1. 6) Наибольшее такое число в двоичной системе имеет шесть знаков (не более 7!), три нуля и три единицы, причем заканчивается на 1. 7) Наибольшее такое число - 1100012 = 49.
inform_lesson: Гениально. Спасибо большое
полная версия страницы