【GESP】C++三级练习 luogu-P5727 【深基5.例3】冰雹猜想

GESP C++三级练习，一维数组练习，难度★★☆☆☆。

luogu-P5727 【深基5.例3】冰雹猜想

题目要求

题目描述

给出一个正整数 $n$，然后对这个数字一直进行下面的操作：如果这个数字是奇数，那么将其乘 $3$ 再加 $1$，否则除以 $2$。经过若干次循环后，最终都会回到 $1$。经过验证很大的数字（$7\times10^{11}$）都可以按照这样的方式比变成 $1$，所以被称为“冰雹猜想”。例如当 $n$ 是 $20$，变化的过程是 $20\to 10\to 5\to 16\to 8\to 4\to 2\to 1$。

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

输入格式

输入一个正整数 $n$。

输出格式

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

输入输出样例 #1

输入 #1

20

输出 #1

1 2 4 8 16 5 10 20

说明/提示

数据保证，$1 \le n\le 100$。

---

题目分析

解题思路

本题的解题思路如下：

1. 问题本质：
   • 根据给定规则对数字进行变换，直到得到1
   • 需要记录整个变换过程并倒序输出
2. 解题关键：
   • 按规则判断数字的奇偶性并进行相应变换
   • 记录每一步变换后的数字
   • 最后倒序输出整个变换序列
3. 实现思路：
   • 使用数组或向量存储变换序列
   • 对输入数字不断进行如下操作：
     • 如果是偶数，除以2
     • 如果是奇数，乘3加1
   • 直到数字变为1为止
   • 最后从后向前遍历数组，输出整个序列
4. 复杂度分析：
   • 时间复杂度：$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;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。