笱幼锾

像我这种donkey只能用笨方法解题了，有时候真羡慕大佬们惊为天人的思路，我咋就想不到呢，可能还是要继续沉淀吧。
###方法：深度优先搜索（DFS）
因为本题的数据量较小，所以考虑用DFS暴力搜索。
将所得数据保存在数组ip[i][0]中,例如有四个小朋友，两个一元两个两元，则ip[1][0]=1；ip[2][0]=1；ip[3][0]=2；ip[4][0]=2；而ip[i][1]的作用是在DFS时记录该值有无被用（有无被放入队列中），如果没有则为0，否则置1。
依题意如果要让服务员有零钱可找，则排在前面的1元小朋友的个数要大于等于2元小朋友，所以在DFS函数里用一个k值代表还可以接受2元小朋友的个数。

k = 已经入队的1元小朋友个数 - 已经入队的2元小朋友个数

接下来就是DFS了，具体细节看代码。
    #include<stdio.h>
    int ip[12][2];
    int way=0;    //用来记录可行的方式个数 
    int M,N,K;
    void dfs(int n,int m,int k)  //n代表当前小朋友的编号  m代表已经入队的小朋友个数  k代表已经入队的1元小朋友个数 减去已经入队的2元小朋友个数
    {
        if(m==M)      //m==M 即代表所有小朋友均已进入队列，则该方式可行，way自加1 
        {
            way++;
            return ;
        }
        
        int i; 
        for(i=1;i<=M;i++)         //遍历所有路径 
        {
            if(ip[i][1]==0)       //检测该值在该路径中没有重复，则进入下一步 
            {
                if(ip[i][0]==2&&k>0)    // 当为2元小朋友时要判断k是否大于0，因为只有当k大于0时服务员才有零钱可找 
                {
                    ip[i][1]=1;       //在该路径中将该值置1避免重复 
                    dfs(i,m+1,k-1);
                    ip[i][1]=0;      //退出该路径后置0，以供下一条路径判断使用 
                }
                if(ip[i][0]==1)      //1元则可以直接入队 
                {
                    ip[i][1]=1;
                    dfs(i,m+1,k+1);
                    ip[i][1]=0;
                }
            }
        }
    }
    int main()
    {
        int i;
        scanf("%d %d %d",&M,&N,&K);
        for(i=1;i<=M;i++)
        {
            if(i<=N)
            ip[i][0]=1;
            else
            ip[i][0]=2;
        }
        for(i=1;i<=M;i++)   //遍历所有情况 
        {
    		if(ip[i][0]==1)
    		{
           		ip[i][1]=1;
            	dfs(i,1,1);
           		ip[i][1]=0;
    		}
        }
        
        printf("%d",way);
        return 0;
    }

0.0分

4 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

杨鹏伟

赞

2020-09-19 10:22:05

笱幼锾

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C++代码）

蛇行矩阵（C语言代码）

字符串的输入输出处理（C语言代码）

排队买票-题解(C语言代码) 深度搜索暴力解法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

震宇大神的杀毒软件（C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

数组输出（C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

矩阵乘法（C++代码）

打水问题（C语言代码）

【亲和数】（C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

笱幼锾