Задание 5. Информатика. ЕГЭ. Шастин. 29.08.2024

Просмотры: 207
Изменено: 24 ноября 2024

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

  1. Строится двоичная запись числа \(N\).
  2. Далее эта запись обрабатывается по следующему правилу:
    а) если сумма цифр двоичной записи числа чётная, то к этой записи справа дописывается \(11\);
    б) если сумма цифр двоичной записи числа нечётная, то к этой записи справа дописывается \(01\);
    Полученная таким образом запись является двоичной записью искомого числа \(R\).
  3. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа \(4 = 100_2\) результатом является число \(10001_2 = 17\), а для исходного числа \(5 = 101_2\) это число \(10111_2 = 23\).

Укажите минимальное число \(R\), большее \(61\), которое могло получиться в результате работы данного алгоритма.

В ответе запишите это число в десятичной системе счисления.

Решение:

Python


def R(N):
    t = bin(N)[2:]
    q = t.count('1')
    t += '01' if q % 2 else '11'
    return int(t, 2)

ans = 10*10
for N in range(6, 100):
    if R(N) > 61:
        ans = min(ans, R(N))
        
print(ans)

C++ (через побитовые операции)


#include<iostream>

using namespace std;

int digs(int N) {
    int d = 0;
    while (N) {
        d += N & 1;
        N >>= 1;
    }
    return d;
}

int R(int N) {
    N <<= 2;
    N += (digs(N) & 1) ? 1 : 3;
    return N;
}

int32_t main() {
    int min_R = 1000000;
    for(int i = 6; i < 100; i++)
        if(R(i) > 61)
            min_R = min(R(i), min_R);
    cout << min_R << '\n';
}

Ответ: \(63\)