递归经典问题-（2）

1.下楼梯

从楼上走到楼下共有h个台阶，其中每一步有3种走法：走1个台阶；走2个台阶；走3个台阶。问共有多少种下楼方案？

int f(int h)
{
    if(h==1) return 1;
    if(h==2) return 2;
    if(h==3) return 4;
    return f(h-1)+f(h-2)+f(h-3);
}

2.分书

有编号为0~4的5本书，准备分给5个人A,B,C,D,E。每个人的阅读兴趣用一个二维数组描述，公式如下：

like[i][j]=1：i喜欢j书； 0：i不喜欢j书

写一程序，输出所有分书方案，让人人皆大欢喜。假定5个人对5本书的阅读兴趣如下：

0 1 2 3 4

A 0 0 1 1 0

B 1 1 0 0 1

C 0 1 1 0 1

D 0 0 0 1 0

E 0 1 0 0 1

思路：这道题跟全排列有点类似，见：递归经典问题（1）-简单题 3.①全排列-手写递归

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int like[5][5] = {
        {0,0,1,1,0},
        {1,1,0,0,1},
        {0,1,1,0,1},
        {0,0,0,1,0},
        {0,1,0,0,1}
};

int select[5];//select[i]表示i选的书;i从0~4表示A~E五个人
bool vis[5];//表示第i本书是否已被选

//判断是否“皆大欢喜”
bool judge()
{
    for(int i = 0; i < 5; i++){
        if(!like[i][select[i]]) return false;
    }
    return true;
}

void fun(int s)
{
    if(s>=5){
        if(judge()){
            for(int i = 0; i < 5; i++){
                printf("%d ",select[i]);
            }
            printf("\n");
        }
        return;
    }
    for(int i = 0; i < 5; i++){
        if(!vis[i]){
            select[s] = i;
            vis[i] = true;
            fun(s+1);
            vis[i] = false;//回溯
        }

    }
}

int main()
{
    fun(0);
	return 0;
}

3.蓝桥杯-出栈次序

X星球特别讲究秩序，所有道路都是单行线。一个甲壳虫车队，共16辆车，按照编号先后发车，夹在其它车流中，缓缓前行。路边有个死胡同，只能容一辆车通过，是临时的检查站，如图【p1.png】所示。X星球太死板，要求每辆路过的车必须进入检查站，也可能不检查就放行，也可能仔细检查。如果车辆进入检查站和离开的次序可以任意交错。那么，该车队再次上路后，可能的次序有多少种？为了方便起见，假设检查站可容纳任意数量的汽车。显然，如果车队只有1辆车，可能次序1种；2辆车可能次序2种；3辆车可能次序5种。

现在足足有16辆车啊，亲！需要你计算出可能次序的数目。

递归经典问题-（2）

分三种情况：

①wait=0：则此时只有一种出栈次序

②check=0：此时有f(wait-1,1)种出栈次序（check=0，则wait中第一辆进入胡同中check，即wait=wait-1,check=1）

③wait和check均不为0：此时有f(wait-1,check+1)+f(wait,check-1)种出栈次序（wait中第一辆进入胡同，或者胡同中出去一辆）

代码如下：

int f(int wait,int check)
{
    if(wait==0)//所有车都进了胡同
        return 1;
    if(check==0)//所有车都出了胡同
        return f(wait-1,1);
    return f(wait-1,check+1)+f(wait,check-1);
}
/*
35357670
*/

另一种解法：Catalan数。卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。卡塔兰数的一般公式为 C(2n,n)/(n+1)。

见链接：https://blog.****.net/Li_Hongcheng/article/details/82818616

4.未完待续

递归经典问题-（2）

相关推荐