Начните с n. Если оно чётное, разделите его на 2; если нечётное — умножьте на 3 и прибавьте 1. Повторяйте процесс, пока значение не станет равным 1. В ответе укажите как начальное значение, так и финальную 1.
Реализуйте функцию collatz_sequence(n).
Входные данные
n: Положительное целое число, с которого начинается последовательность.
Выходные данные
Верните всю последовательность в порядке следования.
Ограничения
1 ≤ n ≤ 10 000. Для всех входных данных из этого диапазона последовательность по этому правилу достигает 1; все значения последовательности помещаются в знаковый 64-битный целый тип.
Примеры
Ввод:
n = 6
Ожидаемый вывод:
expected = [6, 3, 10, 5, 16, 8, 4, 2, 1]Ввод:
long long n = 6;
Ожидаемый вывод:
std::vector<long long> expected = {6, 3, 10, 5, 16, 8, 4, 2, 1};Ввод:
long n = 6;
Ожидаемый вывод:
long[] expected = new long[] {6, 3, 10, 5, 16, 8, 4, 2, 1};Пояснение
6 — чётное, поэтому становится 3. Затем 3 превращается в 10. Продолжайте применять правило, пока не получите 1.
Ввод:
n = 1
Ожидаемый вывод:
expected = [1]Ввод:
long long n = 1;
Ожидаемый вывод:
std::vector<long long> expected = {1};Ввод:
long n = 1;
Ожидаемый вывод:
long[] expected = new long[] {1};Пояснение
Начальное значение уже равно 1, поэтому преобразования не требуются.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Последовательность строится повторным применением одного правила в зависимости от того, чётное текущее число или нечётное.
Подсказка 2
Добавляйте каждое новое значение, пока не дойдёте до 1.
Подсказка 3
Помните, что исходное значение и финальная 1 должны обе попасть в результат.
Ожидаемая сложность
O(k) по времени, O(k) доп. памяти, где k — длина последовательности
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.