【C++】角谷猜想问题分析与解答

💯前言

• 在算法学习的过程中，经典问题往往蕴含着丰富的逻辑思维训练。本文将对一道经典的编程题目——角谷猜想进行深入解析，并展示不同的解法，包括C++风格代码与C语言风格代码的实现。此外，我们将详细对比代码思路，找出其差异与优化之处，并对相关概念进行拓展，让读者全面理解问题的本质及其高效解决方案。
  C++ 参考手册
  

💯题目描述

B2077 角谷猜想

题目名称：B2077 角谷猜想

角谷猜想（Collatz Conjecture）是一个著名的数学问题，描述如下：

• 给定一个正整数 $N$，如果 $N$ 是奇数，则执行 $N=N\times 3+1$；
• 如果 $N$ 是偶数，则执行 $N=N/2$；
• 重复上述过程，直到 $N=1$ 为止。

输入格式
一个正整数 $N(N\le 2,000,000)$。

输出格式
从输入整数 $N$ 计算到 $1$ 的步骤，每一步输出计算过程，格式如：

5*3+1=16
16/2=8
8/2=4
4/2=2
2/2=1
End

若输入直接为 $1$，输出：

End

输入输出样例

💯我的初始做法

代码实现

下面是我最初的C++代码实现：

#include <iostream>
using namespace std;

int main() {
    int a;
    cin >> a;
    while (a != 1) {
        if (a % 2 != 0) {
            cout << a << "*3+1=" << a * 3 + 1 << endl;
            a = a * 3 + 1;
        }
        if (a % 2 == 0) {
            cout << a << "/2=" << a / 2 << endl;
            a = a / 2;
        }
    }
    cout << "End" << endl;
    return 0;
}

代码分析

1. 输入与输出：使用 cin 和 cout 进行数据输入和输出。
2. 逻辑结构：
   • 循环条件为 a != 1，即不断执行操作直到 $a=1$。
   • 判断奇偶性：
     • 如果 $a\%2\ne 0$（奇数），计算 a = a * 3 + 1 并输出结果；
     • 如果 $a\%2==0$（偶数），计算 a = a / 2 并输出结果。
3. 问题点：
   • 整数溢出：当 $a$ 较大时，a * 3 + 1 可能会超出 int 的表示范围，导致程序错误或无限循环。
   • 冗余判断：两个独立的 if 语句增加了不必要的判断。

💯优化后的做法

优化目标

为了解决程序可能的 时间超时 (TLE) 和 整数溢出 问题，我进行了以下优化：

1. 数据类型优化：将变量 int 改为 long long，以避免大数溢出；
2. 逻辑简化：使用 if-else 避免重复判断，提高执行效率。
3. 代码风格优化：保持简洁与高效。

优化后的C++代码

#include <iostream>
using namespace std;

int main() {
    long long a;
    cin >> a;
    while (a != 1) {
        if (a % 2 == 1) {
            cout << a << "*3+1=" << (a = a * 3 + 1) << endl;
        } else {
            cout << a << "/2=" << (a /= 2) << endl;
        }
    }
    cout << "End" << endl;
    return 0;
}

优化效果

1. 数据安全：long long 能处理更大的数值，解决了溢出问题。
2. 高效逻辑：使用 if-else 避免冗余判断。
3. 清晰输出：在一行中完成输出和赋值操作，简洁高效。

💯老师的做法

代码实现

老师提供了一种 C语言风格 的代码实现，具体如下：

#include <cstdio>

int main() {
    long long n = 0;
    scanf("%lld", &n);
    while (n != 1) {
        if (n % 2 == 1) {
            printf("%lld*3+1=%lld\n", n, n * 3 + 1);
            n = n * 3 + 1;
        } else {
            printf("%lld/2=%lld\n", n, n / 2);
            n /= 2;
        }
    }
    printf("End\n");
    return 0;
}

对比分析

1. 输入输出：
   • 老师使用 scanf 和 printf，这是 C语言 的输入输出方式，效率较高。
   • 我的代码使用 cin 和 cout，这更符合现代C++的编程习惯，但效率稍低。
2. 数据类型：
   • 老师同样使用了 long long，解决了溢出问题。
3. 逻辑结构：
   • 老师通过 if-else 避免了冗余判断。
   • 在一行中完成输出和赋值操作，使代码更为简洁。
4. 效率：
   • C语言的 printf 和 scanf 相对于 cout 和 cin 更快，适合数据量大的场景。

💯总结与扩展

思路总结

1. 角谷猜想的逻辑：
   • 奇数： $a=a\times 3+1$
   • 偶数： $a=a/2$
2. 数据类型的重要性：
   • 处理大数时，选择合适的数据类型（如 long long）非常关键。
3. 高效输入输出：
   • printf 和 scanf 比 cout 和 cin 更快，适用于对性能要求高的场景。
4. 逻辑简化：
   • 避免冗余判断，使用 if-else 提高代码效率。

代码优化技巧总结

• 减少冗余判断：使用 if-else 避免多次判断。
• 合并操作：输出和赋值可以在一行中完成，简化代码结构。
• 选择合适的数据类型：特别是在处理大数时，避免溢出。
• 输入输出优化：使用 printf 和 scanf 代替 cout 和 cin 提高效率。

拓展思考

• Collatz猜想的性质：
  角谷猜想虽然简单，但至今没有数学证明。无论输入什么正整数，最终都会收敛到 1，这也是该猜想的有趣之处。
• 时间复杂度：
  每次操作会将偶数减半，执行次数大致为 $O(\log N)$。
• 算法训练意义：
  本题锻炼了对 循环控制、条件判断 和 数据处理 的综合能力，是学习算法的良好入门题目。

💯小结

• 
  通过对角谷猜想问题的深入解析，我们了解了如何高效地解决该问题，并对C++风格和C风格的代码进行了对比。优化程序的核心在于选择合适的数据类型、优化逻辑结构以及提高输入输出的性能。这道题不仅帮助我们理解基础的循环与判断结构，也让我们体会到在不同编程风格下性能的差异。