Задание 5. Информатика. ЕГЭ. Поляков-142

Просмотры: 9
Изменено: 19 сентября 2024

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

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

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа \(N\)) является двоичной записью искомого числа \(R\). Укажите такое наименьшее число \(R\), которое превышает \(43\) и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе счисления.

Решение:

C++


#include<iostream>
using namespace std;

unsigned int sum_digits(unsigned int N) {
    unsigned int sum = 0;
    while (N)
    {
        sum += N & 1;
        N >>= 1;
    }
    return sum;
}

unsigned int R(unsigned int N) {

    for (int i = 0; i < 2; i++) 
        N = (N << 1) + sum_digits(N) % 2;

    return N;
}

int32_t main() {

    unsigned int  Rmin = 10000;
    for (unsigned int N = 1; N < 1000; N++) {

        unsigned int ans;

        ans = R(N);
        if (ans > 43 && ans < Rmin) Rmin = ans;
            
    }
    cout << Rmin << '\n';
}

Ответ: \(46\)