2019暑假集训（第四天）- 递归算法

怼烎@ 2024-04-17 15:23 44阅读 0赞

### 1. 斐波拉契数列（fbi） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70]

#include <bits/stdc++.h>
    
    using namespace std;
    int fbi(int n)
    { 
     
    			if(n<=1) 
    	            return n;
    	        else
    	        	return fib(n-1)+fib(n-2);
    	 
    }
    int main()
    { 
     int n;
     cin>> n;
     cout<< fib(n) << endl;
      return 0;
    }

*  参考文章：https://blog.csdn.net/tanjie\_123/article/details/53005466

### 倒序数（num） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 1]

#include <iostream>
    using namespace std;
    
    int  main()
    { 
        int a,b=0;
        cin>>a;
        while(a>0)//简直太简便了，都无法用言语来解释，参考下面图片
        { 
            b=10*b+a%10;
            a/=10;//即 a=a/10
        }
        cout<<b<<endl;
    }

*  参考文章：https://blog.csdn.net/Sherry\_Yue/article/details/83240568

### 3. 十进制转换成八进制（change） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 2]

#include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int n;
    void change(int x)
    { 
        int r = x % 8;
        x /= 8;
        if(x != 0) change(x);
        printf("%d", r);
    }
    int main()
    { 
        scanf("%d", &n);
        change(n);
        return 0;
    }

*  参考文章：https://www.cnblogs.com/mrclr/p/8325692.html

### 求N!的值（ni） ###

![在这里插入图片描述][20190827215232880.png]

#include<iostream>
    using namespace std;
    int main(){ 
        int n;
        cin >> n;
        int s[n + 10];
        s[1] = 1;
        s[2] = 2;
        for (int i = 3; i <= n; i++) { 
            s[i] = s[i - 1] * i;
        }
        cout << s[n];
        return 0;
    }//仅供参考

*  参考文章：https://blog.csdn.net/qq\_43398760/article/details/83096054

### 求最大公约数（gcdmax） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 3]

#include <bits/stdc++.h>
    using namespace std;
    int Gcd(int a,int b)
    { 
        if(b == 0) return a;
        return Gcd(b,a%b);
    } 
    
    int main()
    { 
     int a, b;
     cin>> a >> b;
     cout<< Gcd(a, b) << endl;
    
      
    }

*  参考文章：https://blog.csdn.net/yang8627/article/details/83311114

### 双色汉诺塔问题（hanoi） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 4]

#include<stdio.h>
    int ct=1;//记录步数,在步骤中输出
    void move(int n,char from,char to)
    { 
        printf("第 %2d 步：把第 %d 个盘子： %c >>>>>>> %c\n",ct++,n,from,to);
    }
    int hanoi(int n)//输出步数：
    { 
        int cnt = 2,ans = 1;
        if(n == 1)
            return 1;
        else
            return 2* hanoi(n-1) +1;
    }
    void hanoi_tower(int n,char x,char y, char z) //输出步骤
    { 
        if(n==1)
            move(1,x,z);
        else{ 
            hanoi_tower(n-1,x,z,y);
            move(n,x,z);
            hanoi_tower(n-1,y,x,z);
        }
    }
    int main()
    { 
        int n;//盘子个数
        printf("输入盘子个数:\n");
        scanf("%d",&n);
        char x = 'A',y = 'B',z = 'C';
        int t = hanoi(n);
        printf("一共需要%2d步。\n",t);
        hanoi_tower(n,x,y,z);
        return 0;
    }

*  参考文章：https://blog.csdn.net/qq\_42815188/article/details/88856085

### 背包问题 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 5]

*  https://www.cnblogs.com/jlyg/p/10353142.html
 *  https://www.cnblogs.com/shoulinniao/p/9502828.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/b3e2daffe1a444e98cac015e3976393d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/b76e323918e84fd79d7c90a25e9e1388.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/f9c44626294c48519d03d5ff77bda90e.png
[20190827215232880.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/a7b646f256c04d8a9e1b3429a44a3dae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/d214fbebc1a146a3b6ad022d27c1b0c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/68d69383f6f647a9a5a7e26caaaa6d4e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/30ca32dd58fa4f6bb2ba63912c9b8132.png