Фокус с C++

#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 тест на знание языка=)
Что выведет программа и почему?
  • Вопрос задан
  • 3223 просмотра
Решения вопроса 1
Похоже, push_back реаллоцирует память, поэтому ссылка, полученная из v[i] после возврата из рекурсии становится неправильной. Легко увидеть, если сравнить &v[i] до и после рекурсивного вызова. Если заранее зарезервировать место в массиве, все будет работать как надо. Интересно, правда, почему программа не вылетает с ошибкой, когда происходит запись в неправильную память. Ну и можно было бы ожидать, что вектор по умолчанию резервирует хотя бы десяток элементов (вроде, некоторые варианты string так делают).
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Paul
@Paul
Спасибо за задачку, давно хотел написать про способы отладки таких ошибок, а тут вы такой замечательный пример подбросили. Написал.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы