角谷猜想

GESP一级循环和基本运算练习，略有难度，尤其容易忽略数据类型选择的问题，难度★✮☆☆☆。

luogu-B2077

题目要求

题目描述

所谓角谷猜想，是指对于任意一个正整数，如果是奇数，则乘 $3$ 加 $1$，如果是偶数，则除以 $2$，得到的结果再按照上述规则重复处理，最终总能够得到 $1$。如，假定初始整数为 $5$，计算过程分别为 $16$ 、 $8$ 、 $4$ 、 $2$ 、 $1$。

程序要求输入一个整数，将经过处理得到 $1$ 的过程输出来。

输入格式

一个正整数 $N(N \le 2,000,000)$。

输出格式

从输入整数到 $1$ 的步骤，每一步为一行，每一部中描述计算过程。最后一行输出 End。如果输入为 $1$，直接输出 End。

样例输入 #1

5

样例输出 #1

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

题目分析

1. 输入处理：

   • 输入是一个正整数 ( $n$ )，该值的范围是 $( 1 \leq n \leq 2,000,000 )$，所以我们需要确保程序能够正确处理大范围的整数。
   • 由于进行乘法操作时，可能会产生较大的数值，因此我们选择使用 long long 数据类型来存储整数，避免溢出。

2. 处理过程：

   • 判断奇偶性：每次处理一个整数时，需要判断它是奇数还是偶数：
     • 如果是偶数，执行 n = n / 2，使数值减半。
     • 如果是奇数，执行 n = 3n + 1，使数值增加。
   • 输出每一步：在每次操作后，需要输出当前的数值和本次计算的过程。例如，若当前数值是奇数，则输出 n * 3 + 1；若是偶数，则输出 n / 2。
   • 终止条件：当 n 的值变为 1 时，停止循环，并输出 "End" 表示处理完成。

3. 核心算法：

   • 使用一个 while 循环来处理数值 n，直到它变为 1。
   • 在循环内部，判断 n 是奇数还是偶数，并根据不同的条件进行相应的计算。每次计算后，更新 n 的值，并输出当前的操作过程。
   • 当 n 变为 1 时，输出 "End" 并结束程序。

4. 数据类型：

   • 由于输入的整数可能非常大，且在计算过程中进行乘法和除法操作，选择 long long 类型来存储整数，以防止溢出。

{% include custom/custom-post-content-inner.html %}

示例代码

#include <cstdio>
#include <iostream>
using namespace std;

int main() {
    long long n;  // 用 long long 类型来存储输入的数，防止大数溢出
    scanf("%lld", &n);  // 读取输入的整数，使用 %lld 来处理 long long 类型

    long long ans = 0;  // ans 用来存储当 n 是奇数时 3n + 1 的结果
    long long sum = 0;  // sum 用来存储当 n 是偶数时 n / 2 的结果

    // 当 n 不等于 1 时，继续进行计算
    while (n != 1) {
        if (n % 2 != 0) {  // 如果 n 是奇数
            ans = n * 3 + 1;  // 奇数时执行 3n + 1
            cout << n << "*3+1=" << ans << "\n";  // 输出当前操作的过程
            n = ans;  // 更新 n 为计算后的值
        } else {  // 如果 n 是偶数
            sum = n / 2;  // n / 2
            cout << n << "/2=" << sum << "\n";  // 输出当前操作的过程
            n = sum;  // 更新 n 为计算后的值
        }
    }

    // 当 n == 1 时，输出 "End" 表示结束
    printf("End");
    return 0;
}

{% include custom/custom-post-content-footer.md %}

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

“luogu-”系列题目可在 洛谷题库 在线评测。

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

GESP/CSP 认证学习微信公众号