文章目录
- 一、问题：1241 - 角谷猜想
- 二、问题：1108 - 正整数N转换成一个二进制数
- 三、总结
- 四、感谢
一、问题：1241 - 角谷猜想
类型：有规律的循环、递归。
题目描述：
日本一位中学生发现一个奇妙的定理，请角谷教授证明，而教授无能为力，于是产生了角谷猜想。
猜想的内容：任给一个自然数，若为偶数则除以 2 ，若为奇数则乘 3 加 1 ，得到一个新的自然数后按上面的法则继续演算。若干次后得到的结果必为 1 。
请编写代码验证该猜想：求经过多少次运算可得到自然数 1 。
如：输入 22 ，则计算过程为。
22/2=11
11×3+1=34
34/2=17
17×3+1=52
52/2=26
26/2=13
13×3+1=40
40/2=20
20/2=10
10/2=5
5×3+1=16
16/2=8
8/2=4
4/2=2
2/2=1
经过 15 次运算得到自然数 1 。
输入：
一行，一个正整数 n 。（ 1≤n≤20000 )
输出：
一行，一个整数，表示得到 1 所用的运算次数。
样例：
输入：
22
输出：
15
1.分析问题
- 已知：一个正整数 n 。
- 未知：得到 1 所用的运算次数。
- 关系：角谷猜想。
2.定义变量
- 定义并读入一个整数n；
//二、数据定义
int n;
3.输入数据
//三、数据输入
cin>>n;
4.数据计算
-
定义全局变量c用于记录操作次数。
-
定义一个名为op的递归函数，参数为需要进行运算的整数n。
-
当n不等于1时，进入递归：
-
如果n是偶数，则对n进行除以2的操作，并以结果作为新的n调用op函数；
-
如果n是奇数，则对n进行乘以3再加1的操作，并以结果作为新的n调用op函数；
-
每进行一次上述操作（无论是除以2还是乘以3加1），全局计数器c加1。
int c=0;
void op(int n){
if(n!=1){
if(n%2==0){
op(n/2);
}else{
op(n*3+1);
}
++c;
}
}
- 调用op(n)开始执行角谷猜想的计算流程；
//四、数据计算
op(n);
5.输出结果
- 输出操作次数c，即从输入的n到达1所需经过的步骤数。
//五、输出结果
cout<<c;
return 0;
完整代码如下：
#include <bits/stdc++.h> // 引入C++标准库的头文件，包含大部分常用函数和数据结构
using namespace std; // 使用std命名空间，方便调用其中的标准库函数
int c = 0; // 定义全局变量c，用于记录执行操作（变换）的次数
// 定义递归函数op，参数为整数n
void op(int n) {
if (n != 1) { // 如果当前数值n不等于1，则继续进行以下操作
if (n % 2 == 0) { // 如果n是偶数
op(n / 2); // 将n除以2后作为新的输入值调用op函数（遵循角谷猜想的规则）
} else { // 否则，即当n是奇数时
op(n * 3 + 1); // 根据角谷猜想将n乘以3并加1后作为新的输入值调用op函数
}
++c; // 在每次执行完一次操作（无论是否改变n的值）后，计数器c增加1
}
}
int main() {
// 分析问题：实现角谷猜想（Collatz Conjecture），即对于任意正整数n，通过特定规则变换，最终都能到达1
int n; // 定义变量n，用于存储用户输入的初始数值
// 数据输入
cin >> n;
// 数据计算
op(n); // 调用op函数对给定的n执行角谷猜想的操作流程
// 输出结果
cout << c; // 输出从初始数值n到1所经历的操作次数
return 0; // 程序正常结束，返回0
}
思路二：累计计算递归次数，然后层层返回。思路一致，但这次op函数的实现有所不同，它返回从输入数值n到1所经历的操作步数。
#include <bits/stdc++.h> // 引入C++标准库头文件
using namespace std; // 使用std命名空间
// 定义递归函数op，参数为整数n，返回从n到达1所需的操作步数
int op(int n) {
if (n != 1) { // 如果当前数值n不等于1，则继续进行以下操作
if (n % 2 == 0) { // 如果n是偶数
return 1 + op(n / 2); // 将n除以2，并在返回结果上加1（表示这一步操作），然后调用op函数
} else { // 否则，即当n是奇数时
return 1 + op(n * 3 + 1); // 根据角谷猜想将n乘以3并加1，并在返回结果上加1，然后调用op函数
}
} else { // 当n等于1时，结束递归
return 0; // 返回0，因为从1开始无需额外的操作步数
}
}
int main() {
// 分析问题：实现角谷猜想，计算给定正整数n经过特定规则变换达到1所需要的步骤数
// 二、数据定义
int n, c; // 定义变量n存储用户输入的初始数值，c存储变换所需的操作步数
// 三、数据输入
cin >> n;
// 四、数据计算
c = op(n); // 调用op函数计算从n到1需要的操作步数，并将结果赋值给变量c
// 五、输出结果
cout << c; // 输出从n到1所经历的操作步数
return 0; // 程序正常结束，返回0
}
思路三：同样用于实现角谷猜想，与前一个版本相比，这次op函数多了一个参数c，用来记录递归过程中累计的操作步数。这样每次函数调用时可以直接传递和累加操作步数，无需全局变量来统计。
#include <bits/stdc++.h> // 引入C++标准库头文件
using namespace std; // 使用std命名空间
// 定义递归函数op，参数为整数n（当前数值）和c（累计操作步数）
int op(int n, int c) {
if (n != 1) { // 如果当前数值n不等于1，则继续进行以下操作
if (n % 2 == 0) { // 如果n是偶数
return op(n / 2, 1 + c); // 将n除以2，并在累计操作步数上加1，然后调用op函数
} else { // 否则，即当n是奇数时
return op(n * 3 + 1, 1 + c); // 根据角谷猜想将n乘以3并加1，并在累计操作步数上加1，然后调用op函数
}
} else { // 当n等于1时，结束递归
return c; // 返回累计的操作步数，表示从初始值到达1所需要的步骤数
}
}
int main() {
// 分析问题：实现角谷猜想，计算给定正整数n经过特定规则变换达到1所需要的步骤数
// 二、数据定义
int n, c = 0; // 定义变量n存储用户输入的初始数值，c初始化为0，用于存储变换所需的操作步数
// 三、数据输入
cin >> n;
// 四、数据计算
c = op(n, c); // 调用op函数计算从n到1需要的操作步数，第二个参数c作为累计步数传入，并接收最终结果
// 五、输出结果
cout << c; // 输出从n到1所经历的操作步数
return 0; // 程序正常结束，返回0
}
思路四：实现了角谷猜想的非递归版本。通过一个while循环来迭代地对输入的自然数n进行处理，直到n变为1为止，并在过程中累计进行了多少次运算。最后输出到达1所需的操作步数。
#include <iostream>
using namespace std;
int main() {
// 一、分析问题
// 已知：我们有一个自然数n
// 未知：需要计算从这个自然数开始，经过多少次运算（若为偶数则除以2，若为奇数则乘3加1）可以得到自然数1
// 关系：根据给定规则迭代变换数字n
// 二、数据定义
int n, count = 0; // 定义变量n存储用户输入的初始数值，count用于记录进行运算的次数
// 三、数据输入
cin >> n; // 输入待计算的自然数n
// 四、数据计算
while (n != 1) { // 当n不等于1时，继续执行循环内的操作
if (n % 2 == 0) { // 如果n是偶数
n /= 2; // 将n除以2
count++; // 操作次数加1
} else { // 若n是奇数
n = n * 3 + 1; // 根据角谷猜想将n乘以3并加1
count++; // 操作次数加1
}
}
// 五、输出结果
cout << count << endl; // 输出到达1所需的运算次数
return 0; // 程序正常结束，返回0
}
二、问题：1108 - 正整数N转换成一个二进制数
类型：字符串、进制转换
题目描述：
输入一个不大于 32767 的整数 n ，将它转换成一个二进制数。
输入：
输入只有一行，包括一个整数 n (0≤n≤32767)。
输出：
输出只有一行。
样例：
输入：
100
输出：
1100100
输入：
0
输出：
0
1.分析问题
- 已知：整数 n。
- 未知：转换成一个二进制数。
- 关系：进制转换、递归。
2.定义变量
- 定义一个字符串 s 来存储转换后的二进制数。
- 定义整数变量 n，用于接收用户输入的待转换的十进制数。
//二、数据定义
int n;
string s="";
3.输入数据
通过 cin>>n; 从标准输入读取一个十进制整数 n。
//三、数据输入
cin>>n;
4.数据计算
- 4.1定义一个名为binary的递归函数，接受一个整数n和一个空字符串s作为参数。
string binary(int n, string s){
char c; // 用于存储n对2取余的结果（0或1）并转换为字符
// 基本情况：当n等于0时，返回当前已经拼接好的二进制字符串s
if(0 == n){
return s;
}
// 递归步骤：当n不等于0时，计算n除以2的商，并将其与n对2取余的结果（c）一起传递给下一次函数调用
else{
c = n % 2 + '0'; // 将余数转换为字符'0'或'1'
return binary(n / 2, c + s); // 调用binary函数并将结果与当前的余数拼接到前边
}
}
- 4.2 调用binary函数进行二进制转换。
s=binary(n,s);
5.输出结果
- 判断字符串 s 是否为空（即 “”==s），如果为空说明输入的十进制数是0，则直接输出0；否则输出转换得到的二进制字符串 s。
//五、输出结果
if(""==s){
cout<<0;
}else{
cout<<s;
}
return 0;
完整代码如下：
#include <bits/stdc++.h> // 包含标准输入输出库
using namespace std; // 使用标准命名空间
// 定义一个名为binary的递归函数，接受一个整数n和一个空字符串s作为参数
string binary(int n, string s){
char c; // 用于存储n对2取余的结果（0或1）并转换为字符
// 基本情况：当n等于0时，返回当前已经拼接好的二进制字符串s
if(0 == n){
return s;
}
// 递归步骤：当n不等于0时，计算n除以2的商，并将其与n对2取余的结果（c）一起传递给下一次函数调用
else{
c = n % 2 + '0'; // 将余数转换为字符'0'或'1'
return binary(n / 2, c + s); // 调用binary函数并将结果与当前的余数拼接到前边
}
}
int main(){
// 数据定义部分
int n; // 输入的十进制整数
string s = ""; // 初始化一个空字符串，用于存储转换后的二进制数
// 数据输入部分
cin >> n; // 从标准输入读取一个整数赋值给n
// 数据计算部分
s = binary(n, s); // 调用binary函数进行二进制转换
// 输出结果部分
// 判断字符串 s 是否为空（即 ""==s），如果为空说明输入的十进制数是0，则直接输出0；.
if ("" == s){
cout << 0;
}
// 其他情况下，输出已转换好的二进制字符串s
else{
cout << s;
}
return 0; // 主函数返回0，表示程序正常结束
}
思路二：
非递归版本。
使用 while(n) 循环，在 n 不等于0的情况下持续进行以下操作：
- 计算 n 除以2的余数，并将其赋值给 x。
- 将 x 转换为字符，通过 c=x+‘0’;，这里利用了 ASCII 码中 ‘0’ 至 ‘9’ 的连续性。
- 将字符 c 添加到字符串 s 的开头，使用 s=c+s; 进行拼接，这样可以确保生成的二进制数是从低位到高位的顺序。
- 将 n 更新为其除以2的商，即 n/=2;。
完整代码如下：
#include <bits/stdc++.h> // 包含C++标准库中的所有头文件（不推荐在生产环境中使用，建议只包含所需头文件）
using namespace std; // 引入std命名空间以简化代码
int main() {
// 一、分析问题部分（注释中说明）
// 需要将一个已知的整数 n 转换成二进制形式表示。
// 二、数据定义
string s; // 定义一个字符串s用于存储转换后的二进制数
int n, x; // n为待转换的十进制整数，x为计算过程中暂存的余数
char c; // c用于将余数转换成字符'0'或'1'后添加到s中
// 三、数据输入
cin >> n; // 从标准输入读取十进制整数n
// 四、数据计算
while (n) { // 当n非零时进行循环
x = n % 2; // 计算n除以2的余数
c = x + '0'; // 将余数转换为对应的字符（0或1）
s = c + s; // 将字符c添加到字符串s的开头，这样得到的是逆序的二进制数
n /= 2; // 更新n为除以2的商，以便下一次循环继续求余操作
}
// 五、输出结果
if ("" == s) { // 如果转换后得到的二进制数为空（即n原来是0）
cout << 0; // 输出0
} else {
cout << s; // 否则输出转换得到的二进制字符串
}
return 0; // 程序正常结束，返回值为0
}
三、总结
- 递归版本：
-
优点：代码结构简洁清晰，直接体现了问题的递归特性。
-
缺点：如果输入的数值较大，可能会导致较深的递归栈，占用较多内存，甚至可能触发栈溢出。此外，递归版本对于理解递归过程和控制递归深度的要求较高。
- 非递归版本：
-
优点：不会因为递归深度过深而导致栈溢出问题，且对于循环次数有更直观的控制。同时，对于理解和调试代码而言，非递归版本有时更为直观易懂。
-
缺点：相比递归版本，代码量稍多一些，逻辑稍微复杂。
四、感谢
如若本文对您的学习或工作有所启发和帮助，恳请您给予宝贵的支持——轻轻一点，为文章点赞；若觉得内容值得分享给更多朋友，欢迎转发扩散；若认为此篇内容具有长期参考价值，敬请收藏以便随时查阅。
每一次您的点赞、分享与收藏，都是对我持续创作和分享的热情鼓励，也是推动我不断提供更多高质量内容的动力源泉。期待我们在下一篇文章中再次相遇，共同攀登知识的高峰！
