毛豆

用户名：liuyt

访问量：16842

签　名：

等　　级
排　　名	1025
经　　验	3310
参赛次数	3
文章发表	34
年　　龄	22
在职情况	学生
学　　校	燕山大学
专　　业	计算机

　　自我简介：

TA的其他文章

肺炎大作战-题解(C++代码)
浏览：186

你可能喜欢

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

球迷购票问题c++

　　作者: 毛豆　　　　发表时间：2019-10-13 20:06:57 浏览：398　|　评论：0　

题目背景
盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。
按售票处规定，每位购票者限购一张门票，且每张票售价为50元。在排成长龙的球迷中有N个人手持面值50元的钱币，另有N个人手持面值100元的钱币。假设售票处在开始售票时没有零钱。试问这2N个球迷有多少种排队方式可使售票处不致出现找不出钱的尴尬局面。
题目描述
例如当n=2是，用A表示手持50元面值的球迷，用B表示手持100元钱的球迷。则最多可以得到以下两组不同的排队方式，使售票员不至于找不出钱。
第一种:A A B B
第二种:A B A B
[编程任务]
对于给定的n (0≤n≤20),计算2N个球迷有多少种排队方式，可以使售票处不至于找不出钱。
输入输出格式
输入格式：
一个整数，代表N的值
输出格式：
一个整数，表示方案数
输入输出样例
输入样例#1：
2
输出样例#1：
2
说明
必开QWORD
测试：N=15
回溯:1秒（超时）
模拟栈：大于10分钟
递归算法：1秒（超时）
动态规划：0 MS
组合算法：16 MS

这道题目给出的方向已经很明确了（说明都给你测试了）
很显然，可行的操作只有动规和组合算法。
但是！不信邪的摸鱼酱用没有回溯的DFS跑了一遍感觉还行，20组数组超时了4组（17,18,19,20）
代码：
    1.	#include<bits/stdc++.h>
    2.	using namespace std;
    3.	int n,cnt;
    4.	void dfs(int a,int b,int step)
    5.	{
    6.	    if(b<a)return;
    7.	    if(a<0||b<0)return;
    8.	    if(step==2*n)
    9.	    {
    10.	        cnt++;
    11.	        return;
    12.	    }
    13.	    dfs(a-1,b,step+1);
    14.	    if(b>=a)dfs(a,b-1,step+1);
    15.	}
    16.	int main()
    17.	{
    18.	    cin>>n;
    19.	    dfs(n,n,0);
    20.	    cout<<cnt<<endl;
    21.	    return 0;
    22.	}
    
思路很清晰，来50的或者来100的，不符合情况直接return，代码也很简单。
但是终究是A不了啊！

自学了卡特兰数， 。
用到了上面链接那篇博客的公式②，想了解的可以去看一下。
代码没想到比DFS还要简单...
DFS 21行，这个只有11行
极简代码：
    1.	#include<bits/stdc++.h>
    2.	using namespace std;
    3.	long long h[20+2]={1,1},n;
    4.	int main()
    5.	{
    6.	    cin>>n;
    7.	    for(int i=2;i<=n;i++)
    8.	        h[i]=h[i-1]*(4*i-2)/(i+1);
    9.	    cout<<h[n]<<endl;
    10.	    return 0;
    	}

0.0分

13 人评分

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

毛豆

TA的其他文章

你可能喜欢

C语言训练-亲密数（C语言代码）

模拟计算器（Java代码）

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

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

C语言训练-斐波纳契数列（C语言代码）

球迷购票问题c++

评论区

精彩推荐

C语言训练-大、小写问题（C语言代码）

C语言训练-自由落体问题（C语言代码）

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

哥德巴赫曾猜测（C语言代码）

蛇行矩阵（C语言代码）

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

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

出圈】指针malloc版

字符逆序（C语言代码）

神奇的fans （C语言代码）

毛豆

TA的其他文章

你可能喜欢

C语言训练-亲密数 （C语言代码）

模拟计算器 （Java代码）

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

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

C语言训练-斐波纳契数列 （C语言代码）

球迷购票问题c++

评论区

精彩推荐

C语言训练-大、小写问题 （C语言代码）

C语言训练-自由落体问题 （C语言代码）

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

哥德巴赫曾猜测 （C语言代码）

蛇行矩阵 （C语言代码）

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

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

出圈】指针malloc版

字符逆序 （C语言代码）

神奇的fans （C语言代码）

C语言训练-亲密数（C语言代码）

模拟计算器（Java代码）

C语言训练-斐波纳契数列（C语言代码）

　　评论区

C语言训练-大、小写问题（C语言代码）

C语言训练-自由落体问题（C语言代码）

哥德巴赫曾猜测（C语言代码）

蛇行矩阵（C语言代码）

字符逆序（C语言代码）