笱幼锾

用户名：gyh0416

访问量：3053

签　名：

脑壳疼

等　　级
排　　名	10585
经　　验	1016
参赛次数	0
文章发表	6
年　　龄	0
在职情况	学生
学　　校	湖北文理学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-大数加法-题解(C语言代码) 字符数组保存大数
浏览：377

蓝桥杯算法提高-能量项链-题解(C语言代码)
浏览：292

你可能喜欢

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

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

　　作者: 笱幼锾　　　　发表时间：2020-03-20 17:00:29 浏览：434　|　评论：1　

原题链接：排队买票

像我这种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 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

杨鹏伟

赞

2020-09-19 10:22:05

笱幼锾

TA的其他文章

你可能喜欢

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

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

C语言训练-求素数问题（C语言代码）

C语言考试练习题_排列（C语言代码）

剔除相关数（C语言代码）

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

评论区

精彩推荐

【回文数(二)】（C语言代码）

ASCII帮了大忙

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

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

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

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

蚂蚁感冒（C语言代码）

用筛法求之N内的素数。（C语言代码）

单词个数统计（C语言代码）

拆分位数（C语言代码）

笱幼锾

TA的其他文章

你可能喜欢

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

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

C语言训练-求素数问题 （C语言代码）

C语言考试练习题_排列 （C语言代码）

剔除相关数 （C语言代码）

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

评论区

精彩推荐

【回文数(二)】 （C语言代码）

ASCII帮了大忙

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

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

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

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

蚂蚁感冒 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

单词个数统计 （C语言代码）

拆分位数 （C语言代码）

C语言训练-求素数问题（C语言代码）

C语言考试练习题_排列（C语言代码）

剔除相关数（C语言代码）

　　评论区

【回文数(二)】（C语言代码）

蚂蚁感冒（C语言代码）

用筛法求之N内的素数。（C语言代码）

单词个数统计（C语言代码）

拆分位数（C语言代码）