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

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

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

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

Решение:

C++


#include<iostream>
#include<set>

using namespace std;

int sum_digits(int N) {
    int sum = 0;

    for(; N; sum += N & 1, N >>=1) ;

    return sum;
}

int R(int N) {
   int q = 2;

   while(q--)
       N = (N << 1) + sum_digits(N) % 2;

   return N;
}

int32_t main() {
   set<int> S;

   for(int N = 1; N < 100; N++) {
       int res = R(N);

       if (res < 100)
           S.insert(res);
   }

   cout << S.size() << '\n';
}

Ответ: \(24\)