2019亚洲杯生栈顺序 与 卡特兰数(Catalan)的干。从《编程的美》买票找零题材说自,娓娓道来卡特兰数——兼爬坑指南。

平,问题讲述

引子:

吃得一个因字符串形式表示的入栈序列,请求出一起发生略种可能的出栈顺序?如何输出所有可能的出栈序列?

  大约有数个月前,我以练习一些招聘的笔试题中,有平等鸣和卡特兰数相关。那时还没有赶趟开始精心看《编程的美》,就优先翻至那一章节,草草地扣押了生购买票索零底例证和验证并将书及之2019亚洲杯 1背下去了。当然,只因此姿势是可以解决一些题材的,但不知是《编程的美》的撰稿人有意挖的陷阱来鉴别所谓的“Poser”,还是大意了未曾越讨论,又或者是为限于篇幅而用再度精神之东西留给感兴趣的读者来打通,对于能用一般卡特兰数缓解的题材,这个特殊的架子是解决不了的。当然,做也同样论上市了很多年之写,《编程的美》上的逐一问题在网络上还能够找到相关的座谈以及文章,更不要说卡特兰数——自发现至今已有200年左右——的相干材料更加数不胜数。因此,本文的显要目的不是为读者更同浅地介绍卡特兰数的性与采取,而是帮助读者跨越《编程的美》留下的骗局,找寻更一般化的卡特兰数的公式,从而化解还相像的题目。

据入栈序列为:1 2 3  ,则发出库序列一共来五种植,分别如下:1 2 3、1 3 2、2
1 3、2 3 1、3 2 1

 

 

内容提要(点击跳转;博文右下角的回来顶部之链接,可归本页):

仲,问题浅析

  • 读书建议(请预看这里!)
  • 《编程的美》的卡特兰数
    • 题材引入和剖析
    • 业余的认证
    • 母函数法证明
    • 扩展问题
      • 入栈出库问题
      • 矩阵连乘问题
      • 街区对角线问题
      • 圆上点对互相连题目
  • 诚如的卡特兰数
    • “狭隘”的卡特兰数不适用于多方形划分问题、(非满/满)二叉树构造问题
    • 相似的卡特兰数推导方式并缓解多边形划分问题、(非满/满)二叉树构造问题
    • n层阶梯分割问题及引申
    • 填数问题/照相问题
  • 程序实现
    • 公式法
    • 递推法
    • 区区种植算法比较
  • 参考资料

先期介绍几单规律:

 

①**于生库序列中之各级一个数字,在它背后的、比她有点的装有数字,一定是按部就班递减顺序排列的。**

 开卷建议:

遵照入栈顺序为:1 2 3 4。

  • 读过《编程的美》?正而引子提到的,本文希望能而少到《编程的美》的骗局里的读者能顺利爬坑。如果您从未丢坑里,恭喜你,我们好一并交流下这坑是哪的。不过对于街区不超过对角线问题,不懂得乃是否以及己同一多思量了相同接触东西?
  • 不曾念了《编程的美》?那么你就待提高警惕,文中会告知您坑在何,而休是受您先跳下来再攀出来。
  • 从没攻了母函数凡是什么和怎么动?那么用母函数证明的经过即不用太在了了,其实用数学归纳法也堪作证。我将证写以点的重要性缘由是增强读者的信念:这些东西并无是凭空而来。
  • 事先读了卡特兰数,想一直开练习?没关系,如果做题的经过被发现自己理解有问题得以重复夺文中相应的说去看嘛。
  • 思念直接询问怎么编程解决?没问题,最后出有限段落很好理解的代码,捎带进行了解析。

出库顺序:4 3 2 1是合法的,对于数字 4 而言,比她稍微之后边的数字是:3 2
1,且这个顺序是递减顺序。同样地,对于数字 3 而言,比它稍微的尾的数字是:
2 1,且是顺序是递减的。….

  [回来索引 或累看]

生库顺序:1 2 3 4 也是官的,对于数字 1
而言,它背后没有比较她重粗的数字。同样地,对于数字 2
而言,它后呢绝非比较她再次粗之数字。

 

有库顺序:3 2 4 1 乎是法定的,对于数字 3 而言,它后比 3 小之数字有: 2
1,这个顺序是递减的;对于数字 2 而言,它后的比她 小之数字只有
1,也算是符合递减顺序;对于数字 4
而言,它背后的可比它稍微的数字呢唯有生1,因此为适合递减顺序。

《编程的美》的卡特兰数

起库顺序:3 1 4 2 是不合法的,因为于数字 3
而言,以3背后的比3小之数字来:1
2,这个顺序是一个递增的相继(1–>2)。

  先简单概括一下《编程的美》是怎么样引入和介绍卡特兰数的。

 

题目(《编程的美》4.3置票摸零):2n个体排队打票,其中n个人拿50首届,n个人拿100首批。每张票50首位,且同人数特打同一布置票。初始时售票处没有零钱找零。请问这2n个体共计发生微微种排队顺序,不至于使售票处找不上马钱?

就此,当为一定一个队时,通过是原理 可以轻松地认清
哪些序列是官的,哪些序列是伪的。

分析1:队伍的序号标为0,1,…,2n-1,并把50首批作为左括如泣如诉,100首位当右括号,合法序列即括号能够形成交配之阵。对于一个法定的队列,第0独肯定是左括如泣如诉,它必将与有右括号配对,记其职为k。那么由1至k-1、k+1到2n-1吧各自是零星个合法序列。那么,k必然是奇数(1顶k-1一共有奇迹数独),设k=2i+1。那么剩余括如泣如诉的官方序列数为**f(2i)\f(2n-2i-2)个。取i=0到n-1累加,*

 

又令f(0)=1,再由组成数C(0,0)=0,可得

②给一定一个入栈顺序:1  2  3 ….
n,一共有稍许种合法的出栈顺序?参考:百度百科卡特兰数

2019亚洲杯 2

答案是 卡特兰数。即凡来:h(n)=c(2n,n)/(n+1) 种合法的出栈顺序。

至于怎么推导,《编程的美》就不曾详尽地证明,而是用另外一个角度来说明,这个说类似于《计算机程序设计方(卷一)》2.2.1节习题4的解答提到的优质解法“反射原理”,下面是对准那的不外乎(我所知道之极端早的出处是:http://bbs.csdn.net/topics/320099239)

假设仅仅只有待要求来一起发些许种合法的出栈顺序,其实就算是要出做
C(2n,n)就可了。而求解C(2n,n),则可以用动态规划来求解,具体而参照:
排和重组的有定律

 

 

题目大意是用S表示入栈,X表示出栈,那么合法的队列有小个(S的个数为n)
显著起c(2n,
n)个含S,X各n个的班,剩下的凡精打细算不允许的序列数(它含对个数的S和X,但是违背任何条件).

于外不容许的阵中,定有使得X的个数超过S的个数的第一个X的职务。然后在导致并包括这X的有班中,以S代替所有的X并为X代表有的S。结果是一个闹(n+1)个S和(n-1)个X的阵。反过来,对同耻辱一种植档次的每个阵,我们且能够逆转这个历程,而且找来招她的眼前同种类型的免允序列。例如XXSXSSSXXSSS必然来自SSXSXXXXXSSS。这个相应说明,不允许的阵的个数是c(2n,
n-1),因此an = c(2n, n) – c(2n, n-1)。

老三,代码实现

 

为一定一个入栈顺序,比如 1 2 3 ,如何输出所有可能的出栈顺序?

以此解法正好能适用于同种植异常情况,以下是对准那的叙说:

思路①:先求出入栈顺序的保有排列(即全列),并以排列保存到一个LinkedList<String>中,然后逐一遍历每一个序列,判断该队是否是法定的排。

n+m个人排队买票,并且满足2019亚洲杯 3,票价为50头条,其中n个人各手执相同布置50头钞票,m个人每手执相同摆100元纸币,除此之外大家身上没有其它其他的钱,并且开始时候售票窗口没有钱,问有小种排队的情屡屡能够为大家还买到票。

所谓合法的排,就是满足上面的规律1:对有库序列中之各个一个数字,在其背后的、比她稍微的保有数字,一定是遵照递减顺序排列的。
关于什么求解一个序列的通通列,可参看:JAVA求解全排列 

 

圆代码实现如下:(实现得不得了,感觉比较复杂)

夫问题是Catalan数的变形,不考虑人口跟食指之差距,如果m=n的讲话那就是是我们开始的Catalan数问题,也尽管是将手握紧50初次的人数当做是+1,手握紧100首届之人口看成是-1,任前k个数值的跟还非负的序列数。

2019亚洲杯 42019亚洲杯 5

 

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;

public class AllStackPopOrder {


    public static LinkedList<String> allPermutation(String str){
        if(str == null || str.length() == 0)
            return null;
        //保存所有的全排列
        LinkedList<String> listStr = new LinkedList<String>();

        allPermutation(str.toCharArray(), listStr, 0);

        //print(listStr);//打印全排列
        return listStr;
    }


    private static void allPermutation(char[] c, LinkedList<String> listStr, int start){

        if(start == c.length-1)
            listStr.add(String.valueOf(c));
        else{
            for(int i = start; i <= c.length-1; i++)
            {
                //只有当没有重叠的字符 才交换
                if(!isSwap(c, start, i))
                {
                    swap(c, i, start);//相当于: 固定第 i 个字符
                    allPermutation(c, listStr, start+1);//求出这种情形下的所有排列
                    swap(c, start, i);//复位
                }
            }
        }
    }

    private static void swap(char[] c, int i, int j){
        char tmp;
        tmp = c[i];
        c[i] = c[j];
        c[j] = tmp;
    }

    private static void print(LinkedList<String> listStr)
    {
        Collections.sort(listStr);//使字符串按照'字典顺序'输出
        for (String str : listStr) {
            System.out.println(str);
        }
        System.out.println("size:" + listStr.size());
    }

    //[start,end) 中是否有与 c[end] 相同的字符
    private static boolean isSwap(char[] c, int start, int end)
    {
        for(int i = start; i < end; i++)
        {
            if(c[i] == c[end])
                return true;
        }
        return false;
    }

    public static LinkedList<String> legalSequence(LinkedList<String> listStr){
        Iterator<String> it = listStr.iterator();
        String currentStr;
        while(it.hasNext())//检查全排列中的每个序列
        {
            currentStr = it.next();
            if(!check(currentStr))
                it.remove();//删除不符合的出栈规律的序列
        }
        return listStr;
    }
    //检查出栈序列 str 是否 是合法的出栈 序列
    private static boolean check(String str){
        boolean result = true;
        char[] c = str.toCharArray();
        char first;//当前数字.
        int k = 0;//记录 compare 数组中的元素个数
        char[] compare = new char[str.length()];
        for(int i = 0; i < c.length; i++)
        {
            first = c[i];
            //找出在 first 之后的,并且比 first 小的数字
            for(int j = i+1; j < c.length; j++)
            {
                if(c[j] > first)
                    continue;
                else
                {
                    compare[k++] = c[j];//将比当前数字小的 所有数字 放在compare数组中
                }
            }
            if(k == 0)
                continue;
            else{
                for(int m = 0; m < k-1; m++)//判断 compare 数组是否是 递减的顺序
                {
                    if(compare[m] < compare[m+1])
                    {
                        result = false;//不符合递减顺序
                        return result;
                    }
                }
            }
            k=0;
        }
        return result;
    }

    //hapjin test
    public static void main(String[] args) {
        String str = "1234";
        LinkedList<String> listStr = legalSequence(allPermutation(str));
        print(listStr);
    }
}

本条题材区别就是在于n>m的情事,此时咱们照样可用本的验证方法考虑,假而我们设的景屡屡凡2019亚洲杯 6,无法给每个人还买到之状态屡屡凡2019亚洲杯 7,那么就算发出2019亚洲杯 8,此时咱们呼吁2019亚洲杯 9,我们如果最早买无顶票底口编号是k,他亲手握紧之是100首批又售票处没有钱,那么用前k个人的钱打50头版成100头条,从100第一变为50第一,这时候就发出n+1个人手执50头,m-1个手握紧100元的,所以尽管获取2019亚洲杯 10,于是我们的结果就是就此赢得了,表达式是2019亚洲杯 11

View Code

(出处:http://daybreakcx.is-programmer.com/posts/17315.html 作者daybreakcx

 

 

思路②:直接呼吁来官的出栈序列。【而无是比如说思路①那样:先求来富有可能的出栈序列(求全排列),然后还找找来官方的出栈序列。】

 

待完成。

为有利于下面的证明,我以这边用母函数计推导一下。由于公式不便在HTML里排版,我当Word里推导完直接截了个图贴上来。

 

2019亚洲杯 12  2019亚洲杯 13

季,参考资料

  周密的读者或许发现了骗局所在:f(2n)这个姿势可以求解f(0)、f(2)、f(4)等等所有2n形式之高频,但是对f(1)、f(3)等奇数是无定义之。但即便你心闪了及时等同志灵感,但您为不确定这嫌疑是否发含义:原题本身既要求了50初以及100初是成对的哟?对于f(2n+1)这种,根本就是从未定要求解嘛。我早已为这么怀疑了,也早已拟这样说服自己:记住公式足够了;但当自身起研究延伸的题材经常发现,这还不够。

JAVA求解全列

  不过当更为的推理前,先来探视这个“狭义”的款式会化解什么问题吧。

有库顺序(卡特兰数)

入栈出库问题(经典问题):

或许的出栈顺序

  对于一个不过好的仓库,一共n个元素,请问有几乎种植合法的入栈出栈形式?

分析:

  直接用f(2n)来求解即可。不过好小心到,对于买入票找零题材,一共是2n私房,排的凡人的顺序;对于入栈出栈,是n个元素,2n不成操作,排的凡操作的一一。究竟将谁数代入,不要混淆。

 

矩阵连乘问题(《编程的美》4.3扩张问题1):

  P = a1 * a2 *
a3 * … *
an,其中ai举凡矩阵。根据乘法结合律,不改变矩阵的相顺序,只用括号表示成对的乘积,试问一共来几种植括号化方案?

分析:

  n独矩阵需要连乘(n-1)次,因此待(n-1)对括号。且这里的括号只是为了使矩阵两少结合,而非是只有为加括号要加括号,像( (a1)
*
(a2)),这里将片个矩阵分别括起来是未符合要求的。因此此而确定了括号的各个,那么矩阵的结缘顺序吗会见规定,如(()())对应了(( a1*  a2) * (a3
*
a4))。注意到是(n-1)对括号,即(n-1)个左括号和(n-1)个右括号,那么该使用f[2(n-1)]来计算。

 

街区对角线问题(《编程的美》4.3恢弘问题2类似题目1):

  某个城市的某某居民,每天他必须走过2n只街区去上班(他当其寓所以北n个街区及坐东n单街区处工作)。如果他无越(但足以遇到)从下及办公的指向角线,那么闹略条可能的道路?

分析:

  (图片来源于维基)

2019亚洲杯 14

  为了不超越对角线,向东移动的步数时刻要盖等于为北平移的步数,这些点还是高居对角线以下的。可以看路线序列由n次向东及n次向北做,且从第一只元素开始之任意子序列中于东次频繁不少于向北次数。因此方法一共是f(2n)种。

  等等,似乎产生啊不针对。对于网及自己所展现了之解答,都是到者结束;但自觉得这里发生只圈套。如果要求无越,并且初始点便在针对角线上,这显然是只边界条件,完全好仅走方一半,不失“不超过对角线”的要求,即向北位移之步数时刻大于等于向东面移动的步数,那么真实的解应该是2*f(2n)。当然,如果此题材的确出现于面试中了,你可和面试官探讨一下,问问这么活动是否合法?注意边界条件,应该会吗面试加分。

 

圆上点对相互连题目(《编程的美》4.3扩张问题2类似题目1):

  每当圆上选择2n只点,将这些点成对连接起来,且所得n条线段非交,求中的办法数。

分析:

  乍一拘禁无可知像面三志题那样直接套公式。那么,先进行一下解析,将完善上之触发依次标为P0,P1,…P2n-1。为了避免混淆,使用F(2n)表示2n只点只是连成的线数,选择Pk与P0相连(0<k<n),同样地好看看,k必为奇数,否则1顶k-1之间产生单数独点,不容许变为对连成直线。同样地把k设为2i+1,那么线段P0Pk把多余的点分为了1…2i和2i+2…2n-1,且新的连线不克同0k相交,它们只能属于0k将公园划分有之即简单个区域之一。即F(2n)
= ∑F(2i)*F(2n-1-(2i+2)+1) = ∑F(2i)*F(2n-2i-2),其中i = 0 …
n-1。这时,又转向成为熟悉的款型了。

  但是,这道题还是跟方面几乎道有些区别。前几鸣题你连能够分别哪些因素/操作是均等像样,其余的凡其他一样近似;而之题材而怎么区分这些看起来是同样模一样的2n个点吗?怕是只有从剖析入手、发现了那递推公式与卡特兰数的联系,从而才敢动的吧?什么,直接看看2n不怕沿用公式?再或者,根据2n是特性,想生这样一栽解释:2n只点并成线,那么把这n个线段看作有来头的,起点和顶峰各起n个,线段从起点出发,到达极限;为了要线段之间互不交叉,那么随意两个尾点和首点之间必然产生当量之首点和尾点,这样还真又足以如法炮制公式了。这么说当然是可以的,但是明显不如上面几乎鸣题那么直观了,而下的题目而就是非克如此解决了,这就是自身所谓的《编程的美》挖的坑。(当然为起或它的解释太过分肤浅以至于自己从未悟出,有趣味之读者可试用点的说明方式尝试解释下两单问题套用公式的来头)

 

貌似的卡特兰数

多头形划分问题(《编程的美》4.3恢宏问题2):

  将大举形划分为三角形问题。求一个凸多边形区域分成三角形区域的法数。

 

二叉树构造问题(《编程的美》4.3扩展问题3):

  n只结点可组织多少个例外的二叉树。(结点之间从来不分)

  怎么样,这里n就未自然是偶数,还敢直接生搬硬套上面的公式么?当然,这里要吐槽下《编程的美》这里让人蛋疼的地方:明明扩展问题2之接近题材1跟2比它自己简单,后少题可以直接套用正文的公式要原题要稍费点心思,却使这样组织习题的编排顺序,真是别有用心。

  为了解决再相像的题目,满足吃f(2n)的计量方式看来是生了。为和维基齐保持一致,下面用Cn来代表卡特兰数,不过自己弗思量直接引入抽象概念,还是由地方两鸣具体的题目出发吧。

多边形划分问题的剖析:

  设边数为n,且n>=3,并为终端依次编号也1,…,n。选定任意一修边作为第一个三角的底限,如P1Pn,此时再度为她选择一个顶点k,2<=k<=n-1,此时,n边型被分成了一个k边型(顶点编号由1暨k)、一个三角(顶点编号吧1、k、n)、一个n-k+1边型(顶点编号由k到n)。设F2(n)为n边型的划分数,那么

  F2(n) =
∑F2(k)F2(n-k+1),其中n>=3,k=2,…,n-2,并且对三角形可知,F2(3)
= 1。F2(n)可代表也:

  F2(n)
=F2(2)F2(n-1) + F2(3)F2(n-2)


  • + F2(n-2)F2(3) + F2(n-1)F2(2),这个姿势看上去已死通用了,然而对于F2(1)和F2(2)的取值怎么要为?当然为得以像面一样先做如再谈谈,但是这里转化一下思路,把题目简化一下。既然讨论所谓的“1边型”、“2边型”其实历来没意义,“3边型”及以上才发含义,而且3是n的胚胎值,那么不妨令Cn意味着n+2边型的分数,这样就算从C1=1开始,而Cn=F2(n+2)= F2(2)F2(n+1)
    + F2(3)F2(n) + …
    + F2(n)F2(3) + F2(n+1)F2(2),这样就是来

Cn=C0Cn-1+C1Cn-2+…+Cn-2C1+Cn-1C0=∑CkCn-k,(n>=1,k=0,…,n-1)

一定给将原先无意义的状规避掉了,但是C0反之亦然让人纠结。为了使C1=C0C1否能满足是公式,只有令C0=1了。用母函数的计好求得

2019亚洲杯 15

  是无是与《编程的美》的2019亚洲杯 16颇像?可能您晤面说,“这是盖,在是题材里生n个顶点和n个边,一个终极和同样漫漫边做了一个三角,为了要其能划分分有的三角,顶点数应该挺当边数;对于选定的限,选择一个顶点k后拿n边型划分成一个k边型和n-k+1边型,递归地分开”。但可见到,与前面几只问题不同,这种分方式连接合理之序列,也就是说,这样是在已经了解总是合法的情下进展,而不像前几乎个问题,先判断哪些划分合法,再来分。当然,这种理解自己哉无否认,但假如开其跟眼前几乎单问题之牵连、搞懂其中的不等,确实如消费点心思。如果是为套用公式要勉强凑合来的诠释,那下面的题目即使又糟糕办了。同时,Cn的表达式看上去比f(2n)要通用多矣,虽然它其实是一个姿态,后者以采取时总是要管代入的2n除为2得到n之后才实施,难免遗漏。对于之前分析了之题材,所有用f(2n)的地方还好用Cn来代替。

  进一步地,结合维基,把卡特兰数的递推关系总结也:

2019亚洲杯 17

  这时候解决n个结点的二叉树个数问题就概括了。从递推公式出发,记否F3(n),选出一点呢彻底,k个点作为左子树,n-k-1只点作为右子树。那么F3(n)
= ∑F3(k)F3(n-k-1),k=0,…,n-1。容易观察出Cn=F3(n)。这里可以视,这个题材根本没必要找有“n个元素以及另n独因素变为对”这种模式下,这片种植因素分别对应问题遭到之呦事物。

  同时,这个题材尚好引申为“2n+1单结点构成的满二叉树个数为Cn单,这是对原题结果吃所来二叉树(无论是否为充满二叉树)的外结点补及不够失之子结点的结果。

  国内有教材以及国外的满载二叉树定义不等同,本文采取下的概念,同维基百科、《算法导论》一致。更多细节可以参见有关二叉树,我们的中华特点:

 

  • full binary tree is a tree in which every node in the tree
    has either 0 or 2 children.
     -Wikipedia

 

n层阶梯切割问题

解法来自http://blog.csdn.net/duanruibupt/article/details/6869431

  n层的台阶切割为n个矩形的切法数也是2019亚洲杯 18。如下图所示:

    2019亚洲杯 19

  这个证是怎进行的为?我们先绘制如下的如出一辙布置图,即n为5之时节的台阶:

2019亚洲杯 20

  我们注意到每个切割出的矩形都必不可少包括同样块标示为\的稍刚好方形,那么我们这儿枚举每个*与#标记的片比赛作为矩形,剩下的有数独稍阶梯就是咱的星星个还粗的分问题了,于是我们的2019亚洲杯 21留神到此地的架势就是我们前的性质3,因此这就是是咱们所请的结果了。*

  我的补充说明:这里的枚举,是分开方法;将本来图中枚举的每个以*和#为有限竞的矩形挖去,将见面剩下零星只又粗之阶梯(或者一个轻重为0的台阶和一个高低非0的台阶)。同时,从夫路上可以获取启发,此题可以描述也:4只矩形纸片,大小分别吗1*4、2*3、3*2、4*1,把它摆成达图的台阶,一共有几种植互相覆盖的顺序?(是C4=14栽使非是4!=24种,如果想不掌握可以为此n=3来枚举理解)

 

填数问题/照相排队问题(阿里、腾讯笔试题)

在一个2*n的格子中填入1顶2n这些数值使得每个格子外之数值都于该下手和底下的富有数值都小之情形屡屡;

12个高矮不同的人数,排成稀排除,每排必须是起低到大排列,而且第二免去比相应之首先消的人略胜一筹,问排列方式有稍许种?

分析:

  这2n个数选择n个当率先实施,剩下的n个在其次实践,并且每行都是自小到好排列。比如00001111就对准诺了1、2、3、4当第一尽,5、6、7、8以其次行。为了使第一行于第二实行针对诺位置有些,换句话说,要力保序列合法,那么其他从第一独因素的开端之任意子序列中0的个数要盖等于1底个数。这即转发成了Cn。

  对于拍问题,n=6,C=
132。

  (顺便取一下,第一单问题不怎么像2*n的杨氏矩阵构造问题。对于一般的用相同雨后春笋元素构造杨氏矩阵的章程,可以看http://stackoverflow.com/questions/17501540/all-solutions-for-a-matrix-sorting/17501739#17501739)

 

程序实现

  这同组成部分来谈谈解题的程序实现。你或许会见说,上面的演绎都这样详细了,没必要写程序啊?我本也是这般想的,不外乎先从问题遭受泛出用求用的卡特兰数Cn中n的价值,然后计算组合数。这里就管什么什么记忆化优化、递归实现了,就是单独从概念出发求解,随手写了只函数:

//select m elements from n
unsigned long long comb(int n,int m) {
    unsigned long long res;
    if((m==0)||(m==n))
        res = 1;
    else {
        int i;
        long long numerator=1,denominator=1;
        if(m>n-m) 
            m = n- m;
        for(i=1;i<=m;i++)
            denominator *=  i;
        for(i=0;i<=m-1;i++)
            numerator *= n-i; 
        res = numerator/denominator;
    }
    return res;
}

  那么,用此函数计算Cn时,需要展开2n浅乘法和2次除法。但是在计算分子的时刻,你可能就非放心了:如果溢起怎么收拾?即使对long
long型,溢起也未是免容许。

  现在退而求其次,使用递推公式来求Cn。这里用了一个数组保存上次测算的结果,计算时Cn,不必再度计算前面的C0~Cn-1,从而避免了递归的开发和测算的荒废。下面是整体的程序代码:

#include <stdio.h>
#include <stdlib.h>
#define MAXN 36
unsigned long long catalan(unsigned long long *array,int n) {
    static int MaxIndex = -1;
    if(n<=MaxIndex)
        return array[n];
    if(MaxIndex == -1){ //haven't been initialized.
        array[0] = 1;
        MaxIndex = 0;
    }
    //for calculating C[n] with C[0],...,C[n-1]
    //there are C[0],...,C[MaxIndex]
    while(MaxIndex<n) {
        int i;
        MaxIndex++;
        array[MaxIndex] = 0;
        for(i=0;i<MaxIndex;i++)
            array[MaxIndex] += array[i] * array[MaxIndex-1-i];
    }
    return array[MaxIndex];
}


int main() {
    int n;
    unsigned long long *array;
    array = malloc((MAXN+1) * sizeof(unsigned long long));
    while(1) {
        scanf("%d",&n);
        if(n<0) {
            printf("[error]negative number.\n");
            return -1;
        }
        else if(n>=MAXN) {
            printf("[error]larger than 35.\nan unsigned long long can't store it.\n");
            return -1;
        }
        printf("C%d %lld\n",n,catalan(array,n));
    }
}

  现在针对当时有限个算法进行比较,前者采用做数计算的算法本身叫公式法,后者以数组保存先前因素、计算所要元素时更遵照需创新的自我叫作递推法。它们都未曾应用递归。 

  1. 从今取值范围来拘禁,递推法要大得差不多。注释上已经证实了这顺序所能非常成的极其老卡特兰数的n为35,大于35常,unsigned
    long long就未克表示了。而之所以组合数来计量,虽然也是unsigned long
    long型,但由大多独大整数连续相乘的存,最要命之n只支持14,再特别的下结果就是非得法了。假设有某种容器能保存更老的整数,可以拿数组也做成动态增长的,随需随扩,而不用预先算好待分配的数目,相关的编制就算无以这边研究了。
  2. 自运行速度来拘禁,公式法计算了2n蹩脚乘法和2次除法。递推法情况比较复杂,最好状态是计算n时,0…n-1通通就转移,那么用n次乘法和n-1次于加法,规模也O(n);最深情况是前面的且并未成形,规模是O(n2);同时这算法还得更进一步优化:注意到Cn=C0Cn-1+C1Cn-2+…+Cn-2C1+Cn-1C0=∑CkCn-k(n>=1,k=0,…,n-1)中,求与凡横针对性如之,也即C0Cn-1=Cn-1C0,这样实在运算时开的乘法数目可减去一半。这样一来,后者的平均性应跟前者类似。
  3. 由适用性来拘禁,公式法只适合卡特兰数计算,而递推法可以为此来化解还广大的题目,比如把Cn=C0Cn-1+C1Cn-2+…+Cn-2C1+Cn-1C0改写成Cn=C0Cn-2+C1Cn-3+…+Cn-3C1+Cn-2C0。这是个自随手写的架子,如果再开始用母函数来演绎,费时费力,而且未必有能简单表示的铲除。而采用递推法,只待根据是递推公式稍微在次里改变一下哪怕能用了,适用性强的无是一点半点。

  看来,直接用程序来解决,未必比进行紧密地演绎得出结论要不等。当然,这半栽方式会完美控制才是极度不了。

 

后记:

  这首稿子大概花了零星从早到晚的岁月来完成,边写边收拾思路。而这首文章纪念写就杀长远了,有图也证实:

2019亚洲杯 22

自然,这个草稿里直到当下周周一时且仅仅是零星个链接而已,中间没怎么关心。写之前从没悟出会写这么长,不过当下要比较满意的:对于卡特兰数,从突出到一般,不拘泥于《编程的美》上的形式,把广大问题还解决了一如既往布满,并为此母函数进行推理,而且丰富了程序实现。虽然未敢说打了什么新东西,但是将团结原来混乱的笔触被优秀整理了瞬间,也如愿从坑中爬起,涨了重重涉,为了便利阅读,本文加了大量锚点和花标识,并且尽量用非极端单调的言语编写,希望读者为能够抱有收获。

 

参考资料:

  1. 《编程的美》4.3:特殊的卡特兰数形式、买票找零题目、矩阵连乘问题、多边形划分三角形问题、街区上班问题、圆上点对互联问题、二叉数布局问题
  2. 维基百科卡塔兰数:标准的卡特兰数形式、除了上述几乎种植问题他的盈二叉树问题、矩形覆盖问题
  3. 凸多边形的三角形划分解题报告(作者莫名堂堂主):唤起了自己本着母函数解法的回忆(这首博文里的演绎结果未是维基的规范形式,建议为维基为仍)、同时被了本人编程解法的启迪。
  4. Catalan数——卡特兰数(作者Hackbuteer1):当初头条看的参考资料,提供了拍照问题之铲除。不过像整理起奸淫阿里巴巴一个画试题(楼主baihacker)。对于原帖的NIM问题现在曾掌握(最简单易行的了解在该帖43楼),准备之后总结,不过若是产生问题可留言给本人。
  5. 《计算机程序设计方(卷一)》:其实自己只是不思量人提也说而翻书确认了一下Knuth援引的卡特兰数通项的认证方法;以前也已经说过,这个大部头现在凡从未有过时间深入研讨了,目前只是当工具书,用到了就算查实而已。
  6. 小思卡特兰数(作者daybreakcx):矩形覆盖问题跟其它没败的题目的解,还有拿摄像排队问题一般化成填数问题的剖析、以及n>m时买票索零题目之解析。

相关文章