ACM程序设计课内实验（5）递归

偏执的太偏执、 2024-04-17 13:42 68阅读 0赞

## 前言 ##

> 定义：自己调用自己（需要调用栈来执行）  
> 两个基本要素：边界条件（何时结束）和 递归模式（大问题如何转化为小问题）  
> 关键：根据递推关系式写程序（用数学归纳法证明）  
> 注意：递归算法在数据量特别大的时候会出现段错误（例如：递归运算100000000！时）

## 1.[汉诺塔-递归][-] ##

> #### Description ####
> 
>     从前有一座庙，庙里有三个柱子，柱A柱 B柱 C。柱A有64个盘子，从上往下盘子越来越大。要求庙里的老和尚把这64个盘子全部移动到柱子C上。移动的时候始终只能小盘子压着大盘子。而且每次只能移动一个。
>     现在问题来了，老和尚相知道将柱A上面前n个盘子从柱A搬到柱C搬动方法。要求移动次数最少。
> 
> #### Input ####
> 
>     输入有多组，每组输入一个正整数n(0<n<16)
> 
> #### Output ####
> 
>     每组测试实例，输出每一步的步骤，输出“number..a..form..b..to..c”。表示将第a个盘子从柱b搬到柱c.
> 
> #### Sample Input ####
> 
>     2
> 
> #### Sample Output ####
> 
>     number..1..form..A..to..B
>     number..2..form..A..to..C
>     number..1..form..B..to..C
> 
> #### Hint ####

#include <iostream>
    
    using namespace std;
    
    void hanoi(int n, char A, char B, char C) {
        if (n == 1) {
            printf("number..%d..form..%c..to..%c\n",n, A, C);
        } else {
            hanoi(n - 1, A, C, B);
            printf("number..%d..form..%c..to..%c\n",n, A, C);
            hanoi(n - 1, B, A, C);
        }
    }
    
    int main() {
        int n;
        ios::sync_with_stdio(false);
        while (scanf("%d", &n) != EOF) {
            hanoi(n, 'A', 'B', 'C');
        }
        return 0;
    }

## 2.[幂次方-递归][- 1] ##

> #### Description ####
> 
>     任何一个正整数都可以用2的幂次方表示。例如
>     137=2^7+2^3+2^0 
>     由此可知，137可表示为：
>     2(7)+2(3)+2(0)
>     而7又可以表示为：2(2)+2+2(0)
>     3可以表示为：2+2(0)
>     因此137最终表示为：
>     2(2(2)+2+2(0))+2(2+2(0))+2(0)
> 
> #### Input ####
> 
>     一个正整数n(n≤20000)。
> 
> #### Output ####
> 
>     符合约定的n的0,2表示(在表示中不能有空格)
> 
> #### Sample Input ####
> 
>     1315
> 
> #### Sample Output ####
> 
>     2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

#include <iostream>
    using namespace std;
    
    // 递归函数，将正整数n表示为2的幂次方的形式
    void dfs(int n) {
        if (n == 0) { // 如果n为0，表示已经表示完成，直接返回
            return;
        }
        if (n == 1) { // 如果n为1，表示2^0，直接输出2(0)
            cout << "2(0)";
            return;
        }
        if (n == 2) { // 如果n为2，表示2^1，直接输出2
            cout << "2";
            return;
        }
        int k = 0, t = n;
        // 计算n可以表示为2的几次幂
        while (t > 1) {
            t /= 2;
            k++;
        }
        if (k == 1) { // 如果k为1，表示2^1，直接输出2
            cout << "2";
        } else {
            cout << "2("; // 否则输出2(，表示2的幂次方
            dfs(k); // 递归计算k的2的幂次方表示
            cout << ")"; // 输出)
        }
        if (n - (1 << k) > 0) { // 如果n减去2^k后大于0，表示还有余数需要继续表示
            cout << "+"; // 输出+
            dfs(n - (1 << k)); // 递归计算n减去2^k后的表示
        }
    }
    
    int main() {
        int n;
        cin >> n; // 输入正整数n
        dfs(n); // 调用递归函数表示n的2的幂次方形式
        cout << endl;
        return 0;
    }

## 3.[数的计算-递归][- 2] ##

> #### Description ####
> 
>     我们要求找出具有下列性质数的个数(包含输入的自然数n):
>     
>     先输入一个自然数n(n≤500),然后对此自然数按照如下方法进行处理:
>     
>     1、不作任何处理;
>     
>     2、在它的左边加上一个自然数,但该自然数不能超过原数的一半;
>     
>     3、加上数后,继续按此规则进行处理,直到不能再加自然数为止.
> 
> #### Input ####
> 
>     1个自然数n(n≤500)
> 
> #### Output ####
> 
>     1个整数，表示具有该性质数的个数。
> 
> #### Sample Input ####
> 
>     6
> 
> #### Sample Output ####
> 
>     6
> 
> #### Hint ####
> 
>     满足条件的数为
>     6，16，26，126，36，136
> 
> #### Source ####
> 
>     洛古

#include <bits/stdc++.h>
    using namespace std;
    int num=0;
    int dfs(int n)
    {
        for(int i=1; i<=n/2; i++)
        {
            num++;
            dfs(i);
        }
        return 0;
    }
    int main()
    {
        int n;
        cin>>n;
        dfs(n);
        cout<<num+1<<endl;
        return 0;
    }

## 4.[数的计算加强版-递推][- 3] ##

> #### Description ####
> 
>     我们要求找出具有下列性质数的个数(包含输入的自然数n):
>     
>     先输入一个自然数n(n≤10000),然后对此自然数按照如下方法进行处理:
>     
>     1、不作任何处理;
>     
>     2、在它的左边加上一个自然数,但该自然数不能超过原数的一半;
>     
>     3、加上数后,继续按此规则进行处理,直到不能再加自然数为止.
> 
> #### Input ####
> 
>     1个自然数n(n≤10000)
> 
> #### Output ####
> 
>     1个整数，表示具有该性质数的个数。（64位的整数范围）
> 
> #### Sample Input ####
> 
>     6
> 
> #### Sample Output ####
> 
>     6
>     例子二：
>     输入：10
>     输出：14
> 
> #### Hint ####
> 
>     对于例子一满足条件的数为
>     6，16，26，126，36，136
> 
> #### Source ####
> 
>     洛古

#include <bits/stdc++.h>
    using namespace std;
    
    long long a[10001]; // 定义一个数组a，用来存储具有指定性质的数的个数
    
    int main() {
        int n;
        cin >> n; // 输入自然数n
        a[0] = a[1] = 1; // 初始化a[0]和a[1]为1，表示0和1都满足条件
        for (int i = 1; i <= n; i++) { // 从1到n中遍历每个自然数
            if (i & 1) { // 如果i为奇数，说明不能加自然数，直接继承前一个数的结果
                a[i] = a[i - 1];
            } else { // 如果i为偶数，可以加上前面的数或者前面的数除以2
                a[i] = a[i - 1] + a[i / 2];
            }
        }
        cout << a[n] << endl; // 输出具有指定性质的数的个数
        return 0;
    }

## 5.[数字分段-递归][- 4] ##

> #### Description ####
> 
>     给你N个正整数，把这些正整数分成一些段，顺序不能乱，每段的数字和最大为K；请你输出每段的开始下标和结束下标；前面的段和尽量小（也就是后面的和尽量大）；
> 
> #### Input ####
> 
>     第一行输入N和K，（1<=n,k<=1000）;
>     第二行是这n个数a[i],（1<=a[i]<=100）;
>     k大于任意a[i];
> 
> #### Output ####
> 
>     输出每段的起点和终点的下标（从1开始）；
> 
> #### Sample Input ####
> 
>     6 20
>     1 6 5 10 15 20
> 
> #### Sample Output ####
> 
>     1 2
>     3 4
>     5 5
>     6 6

> 这是一个贪心算法的问题，我们可以从左到右遍历数组，每次尽可能多地取数，直到当前段的和大于K。然后输出当前段的开始下标和结束下标，接着从下一个位置重新开始计算新的段。0

#include <bits/stdc++.h>
    using namespace std;
    
    int a[100];
    int n, k;
    
    // 递归函数，用于查找每个段的起点和终点下标
    int dfs(int r, int l) {
        int s = 0;
        for (int i = r; i >= l; i--) {
            s += a[i];
            if (s > k) {
                dfs(i, l); // 递归调用，查找下一个段的起点和终点下标
                cout << i + 1 << " " << r << endl; // 输出当前段的起点和终点下标
                return 0;
            }
        }
        cout << 1 << " " << r << endl; // 输出最后一个段的起点和终点下标
    }
    
    int main() {
        cin >> n >> k; // 读取输入的N和K
        for (int i = 1; i <= n; i++)
            cin >> a[i]; // 读取输入的N个正整数a[i]
        dfs(n, 1); // 调用递归函数，从最后一个数字开始查找每个段的起点和终点下标
        return 0;
    }

## 6.[FBI树-递归][FBI_-] ##

> #### Description ####
> 
>     我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
>     
>     FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2^N
>      的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
>     
>     1) T的根结点为R，其类型与串S的类型相同；
>     
>     2) 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S_1 和S_2	 ；由左子串S_1 构造R的左子树T_1，由右子串S_2 构造R的右子树T_2。
>     
>     现在给定一个长度为2^N
>      的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。
> 
> #### Input ####
> 
>     第一行是一个整数N(0≤N≤10)，
>     
>     第二行是一个长度为2^N 的“01”串。
> 
> #### Output ####
> 
>     一个字符串，即FBI树的后序遍历序列。
> 
> #### Sample Input ####
> 
>     3
>     10001011
> 
> #### Sample Output ####
> 
>     IBFBBBFIBFIIIFF

> 解析：首先需要根据输入的字符串长度N，计算出字符串的长度为2^N。然后根据题目要求，构造一棵FBI树，并输出它的后序遍历序列。

#include <iostream>
    #include <string>
    using namespace std;
    
    // 递归构造FBI树的函数
    void dfs(string s, int start, int end) {
        // 当子串长度为1时，根据字符输出对应的B结点或I结点
        if (start == end) {
            if (s[start] == '0') {
                cout << "B";
            } else {
                cout << "I";
            }
        } else {
            // 将子串分为左右两部分
            int mid = (start + end) / 2;
            // 递归构造左右子树
            dfs(s, start, mid);
            dfs(s, mid + 1, end);
            
            // 统计左右子树中0和1的个数
            int count0 = 0, count1 = 0;
            for (int i = start; i <= end; i++) {
                if (s[i] == '0') {
                    count0++;
                } else {
                    count1++;
                }
            }
            // 根据左右子树的类型输出当前结点的类型
            if (count0 == 0 && count1 > 0) {
                cout << "I";
            } else if (count1 == 0 && count0 > 0) {
                cout << "B";
            } else {
                cout << "F";
            }
        }
    }
    
    int main() {
        int n;
        string s;
        cin >> n >> s;
        // 从根节点开始递归构造FBI树并输出后序遍历序列
        dfs(s, 0, (1 << n) - 1);
        cout << endl;
        return 0;
    }

## 7.[数的划分-递归][- 5] ##

> #### Description ####
> 
>     将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。
>     例如：n=7k=3，下面三种分法被认为是相同的。
>     1 1 5
>     1 5 1
>     5 1 1
>     问有多少种不同的划分方法？
> 
> #### Input ####
> 
>     输入 n,k(n<=200, 2<=k<=6)
> 
> #### Output ####
> 
>     一个整数，划分的方法！
> 
> #### Sample Input ####
> 
>     7 3
> 
> #### Sample Output ####
> 
>     4
> 
> #### Hint ####
> 
>     四种分法为：
>     1,1,5;
>     1,2,4;
>     1,3,3;
>     2,2,3.

#include <iostream>
    using namespace std;
    
    int countPartitions = 0;
    
    // 递归计算整数n分成k份的不同划分方法
    void dfs(int n, int k, int start, int count, int sum) {
        // 当划分数达到k时，如果sum等于n，则找到一种划分方法
        if (count == k) {
            if (sum == n) {
                countPartitions++;
            }
            return;
        }
    
        // 从start开始尝试不同的划分
        for (int i = start; i <= n - sum; i++) {
            dfs(n, k, i, count + 1, sum + i);
        }
    }
    
    int main() {
        int n, k;
        cin >> n >> k;
    
        dfs(n, k, 1, 0, 0);
    
        cout << countPartitions << endl;
    
        return 0;
    }

##  ##

[-]: http://acm.nefu.edu.cn/problemShow.php?problem_id=564
[- 1]: http://acm.nefu.edu.cn/problemShow.php?problem_id=1754
[- 2]: http://acm.nefu.edu.cn/problemShow.php?problem_id=1755
[- 3]: http://acm.nefu.edu.cn/problemShow.php?problem_id=1756
[- 4]: http://acm.nefu.edu.cn/problemShow.php?problem_id=1759
[FBI_-]: http://acm.nefu.edu.cn/problemShow.php?problem_id=1773
[- 5]: http://acm.nefu.edu.cn/problemShow.php?problem_id=1809