每天一道C语言编程:排队买票

这篇具有很好参考价值的文章主要介绍了每天一道C语言编程:排队买票。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

有M个小孩到公园玩,门票是1元。其中N个小孩带的钱为1元,K个小孩带的钱为2元。售票员没有零钱,问这些小孩共有多少种排队方法,使得售票员总能找得开零钱。注意:两个拿一元零钱的小孩,他们的位置互换,也算是一种新的排法。(M<=10)

输入格式

输入一行,M,N,K(其中M=N+K,M<=10).

输出格式

输出一行,总的排队方案。

样例输入

4 2 2

样例输出

8
方法一:

题目分析:
由题目可知,必须满足条件N>=K,拆分这个条件:

N=K

N个小孩带的钱为1元,另外N个小孩带的钱为2元,即2N=M,可以直接用卡特兰数:

每天一道C语言编程:排队买票,c语言,开发语言

由于题目中说小孩交换位置算一种新的排队方式,所以还要再乘上 n 的全排列(乘两遍:N个小孩带的钱为1元,另外N个小孩带的钱为2元),即

每天一道C语言编程:排队买票,c语言,开发语言

N>K 

先将非法的排列方法筛选出来,再用总的排列方法-非法的排列方法,得最终排列的方法数:

总的排列方法:
因为由M人,所以总的排列方法有M!

非法的排列可以将其分为三个部分:

  • 前 2P 个小孩
  • 第 2P + 1 个小孩
  • 剩下的小孩,假设共 R 个(R = M - 2P - 1)

每天一道C语言编程:排队买票,c语言,开发语言

第一部分可以使用卡特兰公式进行运算,即,其中p在0~k范围内,但不能为K,因为第二部分必须为K中的一部分

其次,p可以为0,因为第二部分2p+1为持有2元的小孩,即第一个排队的人就是持有2元的小孩,也是非法的排列顺序:

由于第一部分已经用了k中的p个,第二部分有k-p个选择:

K-P

 第三部分随意排列,即r=m-2*p-1进行随意排列:

R!

所以合法的排列公式为:

用代码实现即:

 long long sum = 0;
        for (int p = 0; p <k; p++) {
            int r = m - 2 * p - 1;
            long long fail = catalan(p) * rank(k, p) * rank(n, p) * (k - p) * rank(r, r);
            sum += fail;
        }
        long long result = rank(m, m) - sum;
        printf("%lld\n", result);

所以完整的代码得,如果其中有一些小漏洞,请大佬们不吝赐教!💖💖

#include<stdio.h>

// 求排列数
long long rank(int a1, int a2) {
    if (a2 == 0) 
        return 1;
    a2--;//这里一定不能忘记,因为要排除rank(c1,c2)中,c1为0得情况
    long long pro = a1;
    for (int i = 0; i < a2; i++) {
        a1--;
        pro *= a1;
    }
    return pro;
}

// 求组合数
long long comb(int c1, int c2) {
    return rank(c1, c2) / rank(c2, c2);
}

// 求卡特兰数
long long catalan(int n) {
    return comb(2 * n, n) / (n + 1);
}

int main() {
    int m, n, k;
    scanf("%d %d %d", &m, &n, &k);
    if (n < k) {
        printf("Error: n must be greater than or equal to k.\n");
        return 0;
    }
    else {
        long long sum = 0;
        for (int p = 0; p <k; p++) {
            int r = m - 2 * p - 1;
            long long fail = catalan(p) * rank(k, p) * rank(n, p) * (k - p) * rank(r, r);
            sum += fail;
        }
        long long result = rank(m, m) - sum;
        printf("%lld\n", result);
    }
    return 0;
}
方法二

我在网上也看到一种更简便得方法,在这里分享给大家,我的理解如下:

他利用了数据结构中的next_permutation(a,a+N)方法进行全排列,不熟悉的可以看这篇文章:

http://t.csdn.cn/TREc9

我们可以把它理解为序列的字典序的前后,严格来讲,就是对于当前序列pn,他的下一个序列pn+1满足:不存在另外的序列pm,使pn<pm<pn+1

正确的排列方法为:每个2前面至少对应着一个1

用一个num记录,num如果有1就++,有2就- - ,如果过程中num<0则证明存在有一个2没有一个1对应。

代码为:

这里初始前面的1为0~K-1,后面的2为K~N-1 所以小于K的就相当于是1了,大于K的就相当于是2了,为了方便使用next_permutation()

 for (int i=0; i<K; i++) {
            a[i] = i;
        }
        for (int i=K; i<N; i++) {
            a[i] = i;
        }
        do {
            int flag = 0;
            // check每个全排列, num务必要初始化 
            int num = 0;
            for (int i=0; i<N; i++) {
                if (a[i] >= K) {
                    num--;
                } else {
                    num++;
                }
                if (num < 0) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0) {
//                for (int i=0; i<N; i++) {
//                    cout << a[i];
//                }
//                cout << "\n";
                res++;
            }

这还不够,需要判断类似1122的所有全排列包括重复的,因为初始前面的1为0~K-1,后面的2为K~N-1 ,对于0123的序列我们可以直接使用next_permutation(),完整代码如下:文章来源地址https://www.toymoban.com/news/detail-580262.html

#include <iostream>
#include <algorithm>
using namespace std;
int N, K, M;
int main() {
    while (cin >> N >> K >> M) {
        int a[N], res = 0;
        for (int i=0; i<K; i++) {
            a[i] = i;
        }
        for (int i=K; i<N; i++) {
            a[i] = i;
        }
        do {
            int flag = 0;
            // check每个全排列, num务必要初始化 
            int num = 0;
            for (int i=0; i<N; i++) {
                if (a[i] >= K) {
                    num--;
                } else {
                    num++;
                }
                if (num < 0) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0) {
//                for (int i=0; i<N; i++) {
//                    cout << a[i];
//                }
//                cout << "\n";
                res++;
            }
        } while (next_permutation(a,a+N));
        cout << res << "\n";
    }
    return 0;
}

到了这里,关于每天一道C语言编程:排队买票的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 中文编程开发语言工具构件说明:屏幕截取构件的编程操作

    屏幕截取 用于截取指定区域的图像。 图    标: 构件类型:不可视 重要属性 l        截取类型 枚举型,设置在截取屏幕时的截取类型。包括:全屏幕、指定区域、活动窗口三种。当全屏幕截取时相当于执行了硬拷屏(PrintScreenSysRq键)功能;指定区域截取则是通过矩形

    2024年02月07日
    浏览(57)
  • 中文编程开发语言工具编程实际案例:美发店会员管理系统软件编程实例

    中文编程开发语言工具编程实际案例:美发店会员管理系统软件编程实例 中文编程开发语言工具编程实际案例:美发店会员管理系统软件编程实例。 软件功能: 1、系统设置:参数设定,账号及权限设置,系统初始化,卡类型设置,积分清零等。 2、会员信息登记:可以刷卡

    2024年02月07日
    浏览(59)
  • day3 驱动开发 c语言编程

    通过ioctl(内核+应用层) 控制led灯三盏,风扇,蜂鸣器,小马达 头文件head.h 内核代码 ioctldev.c 应用层代码 ioctl.c

    2024年02月16日
    浏览(56)
  • 中文编程开发语言工具编程实际案例:台球棋牌混合计时计费软件使用的编程构件说明

    台球棋牌混合计时计费软件使用的编程构件说明 上图说明:该软件可以用于桌球和棋牌同时计时计费,在没有开台的时候,图片是处于等待状态,这使用编程工具中的固定图像构件,在正在计时的时候,图片自动变换为 进行中的状态,在编程中可以动态读取图片。 上图说明

    2024年02月08日
    浏览(54)
  • 中文编程开发语言工具编程案例:计时计费管理系统软件连接灯控器编程案例

    计时计费管理系统软件连接灯控器 计时计费管理系统软件连接灯控器编程案例

    2024年02月07日
    浏览(55)
  • APP开发入门:了解主流的编程语言

    在过去的几年里,有许多程序员开始学习和使用编程语言。这其中包括C、C++、 Java和 Python。尽管有许多语言可供选择,但大多数程序员都会选择最容易学习的编程语言。 如今,有很多编程语言供选择。程序员们在学习这些语言时可以自由地选择他们喜欢的方式,因为他们的

    2024年02月15日
    浏览(49)
  • 游戏开发的最佳编程语言及免费引擎推荐

    游戏至今仍然是人们重要的娱乐方式之一,那么哪种编程语言最适合游戏开发呢?这取决于要开发的游戏类型。例如,如果你想开发一个2D平台游戏,Lua脚本和JavaScript这样的语言比较方便。但是,如果想要开发大型3D第一人称射击游戏,那么用C++或C#之类的语言更加合适。 游

    2024年02月12日
    浏览(57)
  • 中文编程开发语言工具开发的实际软件案例:称重管理系统软件

    中文编程开发语言工具开发的实际软件案例:称重管理系统软件 中文编程开发语言工具开发的实际软件案例:称重管理系统软件,软件可以安装在电脑上,也可以安装在收银机上,支持触摸和鼠标点,想学编程可以关注系统化的编程课程。 中文编程系统化教程,不需英语基

    2024年02月07日
    浏览(80)
  • 初学编程入门基础教学视频,中文编程开发语言工具箱之豪华编辑构件,免费版中文编程软件下载

    初学编程入门基础教学视频,中文编程开发语言工具箱之豪华编辑构件,免费版中文编程软件下载  构件的其中一个属性、方法,查找内容,替换内容。 构件工具箱非常丰富,其中该构件在 文本件构件板菜单下。 编程系统化课程总目录及明细,零基础学中文编程视频教程,

    2024年02月07日
    浏览(82)
  • 中文编程开发语言工具系统化教程初级1上线

    中文编程系统化教程初级1 学习编程捷径:(不论是正在学习编程的大学生,还是IT人士或者是编程爱好者,在学习编程的过程中用正确的学习方法 可以达到事半功倍的效果。对于初学者,可以通过下面的方法学习编程,通过对成百上千个实例练习,则很快会成为编程 高手。

    2024年02月08日
    浏览(58)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包