笱幼锾

用户名：gyh0416

访问量：3342

签　名：

脑壳疼

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

　　自我简介：

TA的其他文章

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

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

你可能喜欢

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

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

　　作者: 笱幼锾　　　　发表时间：2020-03-20 17:00:29 浏览：472　|　评论：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 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

杨鹏伟

赞

2020-09-19 10:22:05

笱幼锾

TA的其他文章

你可能喜欢

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

不容易系列2 （C语言代码）

矩形面积交（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

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

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

评论区

精彩推荐

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

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

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

校门外的树（C语言代码）

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

循环入门练习5 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

1025题初学者，求帮忙看下,不知道哪错了

用getchar()函数接收字符，正序输入为什么会倒序输出

笱幼锾

TA的其他文章

你可能喜欢

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

不容易系列2 （C语言代码）

矩形面积交 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

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

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

评论区

精彩推荐

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

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

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）万恶的long long

校门外的树 （C语言代码）

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

循环入门练习5 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

1025题 初学者，求帮忙看下,不知道哪错了

用getchar()函数接收字符，正序输入为什么会倒序输出

矩形面积交（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

　　评论区

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

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

校门外的树（C语言代码）

1025题初学者，求帮忙看下,不知道哪错了