【C++】c++入门之递归上 数值类-二、例题讲解

问题一：1002 - 编程求解1+2+3+…+n

类型：简单循环

---

题目描述：

编程求解下列式子的值： S=1+2+3+⋯+n。

输入：

输入一行，只有一个整数 n(1≤n≤1000) 。

输出：

输出只有一行（这意味着末尾有一个回车符号），包括 1 个整数。

样例：

输入：

100

输出：

5050

---

1.分析问题

1. 已知：给定一个整数n。
2. 未知：计算从1累加到n的和。
3. 关系：递归。

2.定义变量

• 定义变量n用于存储用户输入的数值。
• 定义变量sum用于存储计算结果。

  int n, sum; 

3.输入数据

• 通过标准输入（cin）接收用户输入的整数n。

 cin>>n;

4.数据计算

• 4.1定义一个名为mySum的递归函数，接受一个整数n作为参数

int mySum(int n){
    // 基本情况：当n等于1时，返回1（因为1+0=1）
    if(n==1){
        return 1;
    } 
    // 递归步骤：当n不等于1时，返回n加上mySum(n-1)的结果
    // 这意味着每次调用mySum都会将问题规模缩小为n-1，并不断递归直到达到基本情况
    else{
        return n + mySum(n - 1);
    }
}

• 4.2 调用mySum函数计算累加和，并将结果存入sum

    sum = mySum(n); 

5.输出结果

• 将计算得到的累加和输出到标准输出。

    cout << sum;  
    // 主函数结束，返回0表示程序执行成功
    return 0; 

完整代码如下：

#include <bits/stdc++.h> // 包含标准输入输出库
using namespace std; // 使用标准命名空间

// 定义一个名为mySum的递归函数，接受一个整数n作为参数
int mySum(int n){
    // 基本情况：当n等于1时，返回1（因为1+0=1）
    if(n==1){
        return 1;
    } 
    // 递归步骤：当n不等于1时，返回n加上mySum(n-1)的结果
    // 这意味着每次调用mySum都会将问题规模缩小为n-1，并不断递归直到达到基本情况
    else{
        return n + mySum(n - 1);
    }
}

int main(){
    // 数据定义部分
    int n, sum; // 定义整数变量n表示要累加到的数值，sum用于存储计算结果

    // 数据输入部分
    cin >> n; // 从标准输入读取一个整数赋值给n

    // 数据计算部分
    sum = mySum(n); // 调用mySum函数计算累加和，并将结果存入sum

    // 输出结果部分
    cout << sum; // 将计算得到的累加和输出到标准输出

    return 0; // 主函数返回0，表示程序正常结束
}

---

问题二：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.分析问题

1. 已知：一个正整数 n 。
2. 未知：得到 1 所用的运算次数。
3. 关系：角谷猜想。

2.定义变量

• 定义并读入一个整数n；

	//二、数据定义 
	int n;

3.输入数据

	//三、数据输入 
	cin>>n;

4.数据计算

1. 定义全局变量c用于记录操作次数。

2. 定义一个名为op的递归函数，参数为需要进行运算的整数n。

3. 当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
}

问题三：1108 - 正整数N转换成一个二进制数

类型：字符串、进制转换

---

题目描述：

输入一个不大于 32767 的整数 n ，将它转换成一个二进制数。

输入：

输入只有一行，包括一个整数 n (0≤n≤32767)。

输出：

输出只有一行。

样例：

输入：

100

输出：

1100100

输入：

0

输出：

0

---

1.分析问题

1. 已知：整数 n。
2. 未知：转换成一个二进制数。
3. 关系：进制转换、递归。

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，表示程序正常结束
}

问题四：1088 - 求两个数M和N的最大公约数

类型：需要找规律的循环。

---

题目描述：

求两个正整整数 M 和 N 的最大公约数(M，N都在长整型范围内）

输入：

输入一行，包括两个正整数。

输出：

输出只有一行，包括1个正整数。

样例：

输入：

45 60

输出：

15

---

1.分析问题

1. 已知：两个正整数。
2. 未知：最大公约数。
3. 关系：递归 、辗转相除法原理（即欧几里得算法），gcd(m, n) = gcd(n, m % n)。

2.定义变量

• 定义变量m、n存储输入的两个整数，result用于存储计算得到的最大公约数。

	//二、数据定义 
	long long int m,n,result;

3.输入数据

	//三、数据输入
	cin>>m>>n; 

4.数据计算

• 4.1 调用gcd函数计算m和n的最大公约数

	//四、数据计算 
	result=gcd(m,n);

• 4.2 定义一个名为gcd的递归函数，接受两个长整型参数m和n

long long int gcd(long long int m, long long int n){
    // 基本情况：当m能被n整除时（即m%n等于0），返回n作为最大公约数
    if(0 == m % n){
        return n;
    } 
    // 递归步骤：当m不能被n整除时，继续调用gcd函数，并将n和m对n取余的结果作为新的参数传递给下一次函数调用
    else{
        return gcd(n, m % n); // 调用gcd函数，此时的问题规模变为了求解n和m%n的最大公约数
    }
}

5.输出结果

• 输出计算得到的最大公约数。
• 主函数返回0，表示程序正常结束。

	//五、输出结果 
	cout<<result;
	return 0;	

完整代码如下：

#include <bits/stdc++.h> // 包含标准输入输出库
using namespace std; // 使用标准命名空间

// 定义一个名为gcd的递归函数，接受两个长整型参数m和n
long long int gcd(long long int m, long long int n){
    // 基本情况：当m能被n整除时（即m%n等于0），返回n作为最大公约数
    if(0 == m % n){
        return n;
    } 
    // 递归步骤：当m不能被n整除时，继续调用gcd函数，并将n和m对n取余的结果作为新的参数传递给下一次函数调用
    else{
        return gcd(n, m % n); // 调用gcd函数，此时的问题规模变为了求解n和m%n的最大公约数
    }
}

int main(){
    // 数据定义部分
    long long int m, n, result; // 定义变量m、n存储输入的两个整数，result用于存储计算得到的最大公约数

    // 数据输入部分
    cin >> m >> n; // 从标准输入读取两个正整数赋值给m和n



    // 数据计算部分
    result = gcd(m, n); // 调用gcd函数计算m和n的最大公约数

    // 输出结果部分
    cout << result; // 输出计算得到的最大公约数

    return 0; // 主函数返回0，表示程序正常结束
}