@[TOC]

Contest100000583 - 《算法笔记》4.3小节——算法初步->递归

4.3 递归理论与例题

4.3.1 分治

在这里插入图片描述

4.3.2 递归

在这里插入图片描述

递归求解n的阶乘

//4.3.2 递归
//递归求解n的阶乘
#include <cstdio>
int F(int n)
{
    if(n==0)
        return 1;//递归边界 
    else
        return F(n-1)*n;//递归表达式 
} 
int main()
{
    int n;
    scanf("%d",&n);
    printf("%d\n",F(n));
    return 0;
} 
 

在这里插入图片描述
在这里插入图片描述

//求斐波那契(Fibonacci)数列的第n项
#include <iostream>
#include <cstdio>
int F(int n)
{
    if(n==0||n==1)
        return 1;//递归边界
    else
        return F(n-1)+F(n-2);//递归式 
} 

int main()
{
    int n;
    scanf("%d",&n);
    printf("%d\n",F(n));
    return 0;
}

在这里插入图片描述

全排列

在这里插入图片描述

//感觉理解不透，还需琢磨 
//全排列，n=3时 
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 11;
//P为当前排列，hashTable记录整数x是否已经在P中
int n,P[maxn] = {false};
//当前处理排列的第index号位
void generateP(int index) 
{
    if(index == n+1)//递归边界，已经处理完排列的1~n位
    {
        for(int i=1;i<=n;i++)
        {
            printf("%d",P[i]);//输出当前排列 
        }
        printf("\n");
        return;
    }
    for(int x=1;x<=n;x++)//枚举1~n，试图将x填入P[index] 
    {
        if(hashTable[x] == false)//如果x不在P[0]~P[index-1]中 
        {
            P[index] = x;//令P的第index位为x，即把x加入当前排列
            hashTable[x] = true;//记x已在P中
            generateP(index+1);//处理排列的第index+1号位
            hashTable[x] = false;//已处理完P[index]为x的子问题，还原状态 
        }
    }
} 

int main()
{
    n=3;//欲输出1~3的全排列额
    generateP(1);//从P[1]开始填 
    return 0;
} 

n皇后问题

在这里插入图片描述

//n皇后问题暴力法 
//基本思想：全组合考虑去除同行同列的情况，转化为全排列，然后判断合法性，暴力法 
//主要代码如下：

int count = 0;
void generatrP(int index)
{
    if(index == n+1)//递归边界，生成一个排列 
    {
        bool flag = true;//flag为true表示当前排列为一个合法方案
        for(int i=1;i<=n;i++)//任意遍历两个皇后
        for(int j=i+1;j<=n;j++)
        {
            if(abs(i-j) == abs(P[i]-P[j]))//如果在一条对角线上
            {
                flag = false;//不合法  
            } 
        }
    }   
    if(flag)
        count++;//若当前方案合法，令count加1
    return; 
} 
for(int x=1;x<=n;x++)
{
    if(hashTable[x] == false)
    {
        P[index] = x;
        hashTable[x] = true;
        generateP(index+1);
        hashTable[x] = false;
    }
}

//n皇后问题回溯法 
void generateP(int index)
{
    if(index == n+1)//递归边界，生成一个合法方案 
    {
        count++;//能到达这里的一定是合法的
        return; 
    }
    for(int x=1;x<=n;x++)//第x行
    {
        if(hashTable[x] == false)//第x行还没有皇后
        {
            bool flag = true;//flag为true表示当前皇后不会和之前的皇后冲突
            for(int pre = 1;pre<index;pre++)//遍历之前的皇后 
            {//第index列皇后的行号为x，第pre列皇后的括号为P[pre] 
                if(abs(index - pre) == abs(x - P[pre]))
                {
                    flag = false;//与之前的皇后在一条对角线，冲突
                    break; 
                }
            }   
            if(flag)//如果可以把皇后放在第x行
            {
                P[index] = x;//令第index列皇后的行号为x
                hashTable[x] = true;//第x行已被占用
                generateP(index + 1);//递归处理第index+1行皇后
                hashTable[x] = false;//递归完毕，还原第x行为未占用 
            } 
        }   
    } 
}

Codeup习题练习

100000583 《算法笔记》4.3小节——算法初步->递归
http://codeup.cn/contest.php?cid=100000583

1907-ProblemA-吃糖果

http://codeup.cn/problem.php?cid=100000583&pid=0

//1907ProblemA 吃糖果
#include <iostream>
#include <cstdio>
using namespace std;
int candy_method(int n)
{
    if(n==1)//递归边界条件 
        return 1;
    else if(n==2)
        return 2;
    else//递归式 
        return candy_method(n-1)+candy_method(n-2);
}

int main()
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
        printf("%d\n",candy_method(n)); 
    }
    return 0;
}

2018-ProblemB-数列

http://codeup.cn/problem.php?cid=100000583&pid=1

//2018ProblemB数列
#include <iostream>
#include <cstdio>
using namespace std;
int Fib(int n)//斐波那契数列 
{
    if(n==0)//递归边界条件 
        return 0;
    if(n==1)
        return 1;
    else//递归式 
        return Fib(n-1)+Fib(n-2);
}

int main()
{
    int m;
    scanf("%d",&m);
    while(m--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<2*(n-i-1);j++)
                printf(" ");
            for(int k=0;k<2*i+1;k++)
            {
                printf("%d ",Fib(k));   
            } 
            printf("\n");
        }
        
    }
    return 0;
}

2044-ProblemC-神奇的口袋

题目链接：http://codeup.cn/problem.php?cid=100000583&pid=2

//2044ProblemC神奇的口袋
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 25;
int arr[MAXN];
int select(int sum,int i)//从前i个数中选择数和为sum
{
    //边界条件 
    if(sum==0)//和为0，啥都不用取 
        return 1;
    if(i==0)//i为0表示已经没有数了，没有找到符合条件的 
        return 0;
    //递归表达式 
    return select(sum-arr[i],i-1)+select(sum,i-1);  
//select(sum-arr[i],i-1)
//表示取最后一个数arr[i]，转换为取钱i-1个数，和为sum-arr[i] 
//select(sum,i-1)表示不取最后一个数arr[i]，   
}

int main()
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
        for(int i=1;i<=n;i++)//读入数组数据 
        {
            scanf("%d",&arr[i]);
        }
        int result = select(40,n);
        printf("%d\n",result);
    } 
    return 0;
} 

2046-ProblemD-八皇后

题目链接：http://codeup.cn/problem.php?cid=100000583&pid=3

//2046ProblemD八皇后
//参考前面讲解里面的八皇后回溯法 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const  int maxn=105;
int N,cnt=0,P[maxn];
char result[105][15]={0};
bool hashTable[maxn] = {false};

void generateP(int index)
{
    //递归边界 
    if(index == N+1)//若是排列的n位已经处理完，则递归结束
    {
        cnt++;
        for(int i=1;i<=N;i++)//存储结果，形式为字符串 
        {
            result[cnt][i-1] = P[i]+'0'; //形式为字符串
        }
        return;
    }
    //递归表达式
    for(int x=1;x<=N;x++)//枚举1~n，试图将x填入P[index] 
    {
        if(hashTable[x] == false)//如果x不在P[0]~P[index-1]中,第x行还没有皇后 
        {
            bool flag=true;//flag为true表示当前皇后不会和之前的皇后冲突 
            for(int pre=1;pre<index;pre++)//遍历之前的皇后
            {//第index列皇后的行号为x，第pre列皇后的行号为P[pre]
                if(abs(index-pre) == abs(x-P[pre]))//此处的判别条件？？ 
                {
                    flag = false;//与之前的皇后在一条对角线，冲突 
                    break;
                }
            } 
            
            if(flag)//如果可以把皇后放在第x行
            {
                P[index] = x;//令P的第index位为x，即把x加入当前排列 
                hashTable[x] = true;//记录x已在P中 
                generateP(index+1); //递归表达式，递归处理下一位 
                hashTable[x] = false;//当递归返回时已处理完P[index]的子问题，还原状态 
            } 
        }   
    }    
}

int main()
{
    N=8;
    generateP(1);
    int n;
    while(scanf("%d",&n) != EOF)
    {
        while(n--)
        {
            int m;
            scanf("%d",&m);
            printf("%s\n",result[m]);
        }
    }
    return 0;
}

总结下：

递归思想很重要，将复杂问题思路变简单，虽然耗时很大，因为有许多重复计算；后面搜索专题DFS还会涉及