#include <vector>
#include <iostream>
std::vector<int> v;
// Функция дописывает в вектор v
// суммы цифр ненулевых префиксов двоичного представления числа x,
// начиная с самого длинного префикса
// например для числа 5 = 0b101, в вектор будет записано {2, 1, 1}, префиксами будут: {101, 10, 1}
//
// Возвращает сумму цифр самого длинного префикса - то есть самого числа в двоичной записи. Для 5 вернёт 2.
int f(const int x)
{
// рекурсивная реализация
if(x != 0) {
// временно дописываем в конец вектора x % 2 (последний бит числа)
// чтобы зарезервировать место для ответа
v.push_back(x % 2);
// запоминаем элемент в векторе, который нужно будет позже вычислить
const size_t i = v.size() - 1;
// вызываем рекурсивно функцию для x / 2, она обработает все мЕньшие префиксы
// и вернёт ответ для наибольшего из них
// нам нужно лишь добавить этот ответ к v[i],
// самый младший бит уже был push_back-нут несколькими строками ранее
v[i] += f(x / 2);
// возвращаем ответ
return v[i];
}
else {
// тривиальный случай
return 0;
}
}
int main()
{
// запускаем функцию для проверки
f(5);
// выводим ответ
for(size_t i = 0; i < v.size(); ++i) {
std::cout << v[i] << ' ';
}
std::cout << std::endl;
return 0;
}
Yet another тест на знание языка=)
Что выведет программа и почему?
