GESP C++三级编程实战：洛谷P5727冰雹猜想算法与数组实现解析

题目要求

题目描述

给出一个正整数 ( n )，然后对这个数字一直进行下面的操作：如果这个数字是奇数，那么将其乘 3 再加 1；如果是偶数，则除以 2。经过若干次循环后，最终都会回到 1。这个规律被称为“冰雹猜想”。例如当 ( n = 20 ) 时，变化的过程是 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1。

根据给定的数字 ( n )，验证这个猜想，并从最后的 1 开始，倒序输出整个变化序列。

输入格式

输入一个正整数 ( n )。

输出格式

输出若干个由空格隔开的正整数，表示从最后的 1 开始倒序的变化数列。

输入输出样例 #1

输入 #1

20

输出 #1

1 2 4 8 16 5 10 20

说明/提示

数据保证 ( 1 \leq n \leq 100 )。

题目分析

冰雹猜想，也称为 Collatz 猜想，是一个经典的算法问题，在编程练习中常用于训练逻辑思维和数组操作能力。本题要求验证猜想并输出倒序序列，核心在于模拟变换过程并记录中间结果。

解题思路

问题的本质是根据规则对输入数字进行迭代变换，直到结果为 1，同时记录每一步的变化值。解题的关键步骤如下：

1. 规则判断与变换：对于当前数字 ( n )，如果它是偶数，则除以 2；如果是奇数，则乘 3 加 1。重复此过程直到 ( n ) 变为 1。
2. 序列记录：在每次变换后，将新值存储到数组或向量中，以便后续倒序输出。
3. 倒序输出：由于需要从 1 开始反向输出序列，在记录完成后，从存储容器的末尾向前遍历即可。

实现时可以使用静态数组或动态向量。静态数组需提前分配足够空间（根据数据范围 ( n \leq 100 )，变换次数有限），而向量则更灵活。复杂度方面，时间复杂度为 ( O(k) )，其中 ( k ) 是变换次数；空间复杂度为 ( O(k) )，用于存储序列。

示例代码

使用静态数组实现

#include <iostream>

// 定义一个大小为105的整型数组，用于存储冰雹猜想的数列变化过程
// 初始化所有元素为0
int result_ary[105] = {0};

int main() {
    // 读取输入的数字
    int n;
    std::cin >> n;

    // 将初始数字存入数组第一个位置
    result_ary[0] = n;

    // 用于记录数组当前位置的索引
    int idx = 1;

    // 根据冰雹猜想规则不断变换数字，直到得到1
    while (n != 1) {
        // 如果是偶数，除以2
        if (n % 2 == 0) {
            n /= 2;
        } 
        // 如果是奇数，乘3加1
        else {
            n = n * 3 + 1;
        }
        // 将变换后的数字存入数组
        result_ary[idx] = n;
        idx++;
    }

    // 从后向前遍历数组，倒序输出整个变化序列
    for (int i = idx - 1; i >= 0; i--) {
        std::cout << result_ary[i] << " ";
    }

    return 0;
}

使用向量（vector）实现

向量版本更动态，适合不确定变换次数的情况。

#include <iostream>
#include <vector>

// 定义一个整型向量ary，用于存储冰雹猜想的数列变化过程
std::vector<int> ary;

int main() {
    // 读取输入的数字
    int n;
    std::cin >> n;

    // 将第一个数字加入向量
    ary.push_back(n);

    // 根据规则生成数列直到得到1
    while (n != 1) {
        // 如果是偶数则除以2
        if (n % 2 == 0) {
            n /= 2;
        } 
        // 如果是奇数则乘3加1
        else {
            n = n * 3 + 1;
        }
        // 将新生成的数字加入向量
        ary.push_back(n);
    }

    // 从后向前遍历向量，输出所有数字
    for (int i = ary.size() - 1; i >= 0; i--) {
        std::cout << ary[i] << " ";
    }

    return 0;
}

以上代码演示了如何在 C++ 中处理冰雹猜想问题，通过数组或向量存储中间状态，并利用循环和条件判断实现变换逻辑。这种练习有助于加深对算法和数据结构基础的理解。