C/C++

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу:
a) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
b) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы алгоритма больше 45.
В ответе это число запишите в десятичной системе счисления.
Михаил Аболихин
Михаил Аболихин
80
Никаких программ для перебора тут не нужно. А первый ответчик, которому ты поставил лайк, вообще написал галиматью от нейросети. Его ответ очевидно неверен, учитывая, что результат больше исходного числа в 4+ раза, и значит, исходное нужно искать где-то в районе [45/ 4] = 11, а никак не 23.

Представим число 46 (наименьшее, которое мы можем получить, чтобы выполнить условие задачи) в двоичной системе:
 101110
Без двух последних разрядов это будет
 1011
(десятичное 11)
По указанному алгоритму нужно приписать справа 1 и 0, по чётности количества единиц, так что в итоге мы и получим 46.

Осталось понять, что с меньшими числами.
Исходная десятка (1010) приведёт к числу 40 (101000), девятка - к ещё меньшему, т.к. мы в результате потеряем третий и более высокие разряды.
Поэтому ответ: десятичное
 11
Алексей Владимиров
Алексей Владимиров
54 053
Лучший ответ
Условия задачи означают, что:
R = 4 * N, если двоичная запись N содержит чётное число единиц;
R = 4 * N + 2, если двоичная запись N содержит нечётное число единиц.

N = 10 гарантировано даст значение меньше 45 (40 или 42), N = 12 гарантировано даст значение больше 45 (48 или 50), надо проверить только N = 11 (44 или 46):
N = 11₁₀ = 1011₂ => три единицы => R = 11 * 4 + 2 = 46 - ответ получен.
Александр Ssaan
Александр Ssaan
57 497 
 #include  

#include  

#include 



using namespace std;



bool result(unsigned n, unsigned x) { 

    auto r = n
Дмитрий Ганин
Дмитрий Ганин
70 683
Дмитрий Ганин Возможно следует решить так:
 #include  

#include 



using namespace std; 



bool result(unsigned n, const unsigned x) { 

    auto r = n
Вот алгоритм на Python, который вычисляет число R для заданного числа N:
 def compute_R(N): 

    binary_N = bin(N)[2:] 

    sum_of_digits = sum(int(digit) for digit in binary_N) 

    binary_N += str(sum_of_digits % 2) 

    sum_of_digits = sum(int(digit) for digit in binary_N) 

    binary_N += str(sum_of_digits % 2) 

    R = int(binary_N, 2) 

    return R
Теперь мы можем использовать этот алгоритм, чтобы найти наименьшее число N, для которого результат работы алгоритма больше 45. Мы можем сделать это, перебирая все возможные значения N, начиная с 1, и проверяя значение R для каждого из них:
 N = 1 

while True: 

    R = compute_R(N) 

    if R > 45: 

        break 

    N += 1 

 

print(N)
Если мы запустим этот код, мы увидим, что наименьшее число N, для которого результат работы алгоритма больше 45, равно 23.
Вадим Инкин
Вадим Инкин
25 860
Не лучше ли такие вопросы задавать в Домашние задания: Информатика?
Алексей Филиппов
Алексей Филиппов
2 616

Похожие вопросы