【GESP】C++一级练习 luogu-B2077, 角谷猜想

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

15

样例输出 #1

15*3+1=16
216/2=8
38/2=4
44/2=2
52/2=1
6End

题目分析

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 类型来存储整数，以防止溢出。

示例代码

1#include <cstdio>
2#include <iostream>
3using namespace std;
4
5int main() {
6    long long n;  // 用 long long 类型来存储输入的数，防止大数溢出
7    scanf("%lld", &n);  // 读取输入的整数，使用 %lld 来处理 long long 类型
8
9    long long ans = 0;  // ans 用来存储当 n 是奇数时 3n + 1 的结果
10    long long sum = 0;  // sum 用来存储当 n 是偶数时 n / 2 的结果
11
12    // 当 n 不等于 1 时，继续进行计算
13    while (n != 1) {
14        if (n % 2 != 0) {  // 如果 n 是奇数
15            ans = n * 3 + 1;  // 奇数时执行 3n + 1
16            cout << n << "*3+1=" << ans << "\n";  // 输出当前操作的过程
17            n = ans;  // 更新 n 为计算后的值
18        } else {  // 如果 n 是偶数
19            sum = n / 2;  // n / 2
20            cout << n << "/2=" << sum << "\n";  // 输出当前操作的过程
21            n = sum;  // 更新 n 为计算后的值
22        }
23    }
24
25    // 当 n == 1 时，输出 "End" 表示结束
26    printf("End");
27    return 0;
28}