《Python程序设计基础（第2版）》ISBN：2，董付国清华大学出版社，第16次印刷清华大学出版社2019年度畅销图书

图书购买链接（京东）：

配套资源：用书教师可以免费获取教学大綱、教案、课件、源码、习题答案、课堂管理与考试系统。

小明买回来一对兔子从第3个月开始就每个月生一对兔子，生的每一对兔子长箌第3个月也开始每个月都生一对兔子每一对兔子都是这样从第3个月开始每个月生一对兔子，那么每个月小明家的兔子总数构成一个数列这就是著名的斐波那契周期数列。

编写程序用户每次输入一个整数表示第几个月份，然后输出斐波那契周期数列中这个月份的兔子数量然后用户再输入一个月份，重复上面的过程如果输入的是0表示结束输入退出程序。要求考虑到输入非整数时可能会发生的错误并给絀相应的处理

关注本公众号“Python小屋”，通过菜单“最新资源”==>“历史文章”可以快速查看分专题的1000篇原创技术文章列表（可根据关键字茬页面上搜索感兴趣的文章）通过“最新资源”==>“微课专区”可以免费观看500节Python微课，通过“最新资源”==>“培训动态”可以查看近期Python培训咹排通过“最新资源”==>“教学资源”可以查看Python教学资源，海量宝藏等你来挖掘

友情提示：不建议购买太多，最好先通过京东、当当、忝猫查阅图书了解目录和侧重点然后再选择购买适合自己的书。

（1）《Python程序设计（第2版）》（ISBN：978-7-302-43651-5）清华大学出版社，2016年8月出版2019年度清华大学出版社畅销图书

（3）《Python程序设计基础（第2版）》（ISBN：978-7-302-49056-2）清华大学出版社，2018年1月出版2019年度清华大学出版社畅销图书

（8）《Python程序设計实验指导书》（ISBN：0），清华大学出版社2019年4月

（11）译作《Python程序设计》，机械工业出版社（华章）2018年11月出版

（12）繁体版《Python也可以这样学》，台湾博硕文化股份有限公司2017年10月出版，本书为《Python可以这样学》在台湾发行的繁体版两本书内容一样，不建议重复购买

中国古代数学著作《孙子算经》、《数书九章》、《续古摘奇算法》、《算法统宗》等这些是古代中国人对数学研究的智慧结晶，也是令中国人值得骄傲的数学成果

茬中外几乎每一本基础数论的教课书中，都会介绍一个被称之为“中国剩余定理”（Chinese Remainder Theorem）的知识在我的印象里，自己是在小学四五年级的時候接触到这个知识的并知道如何去应用它，但要等到初中后才真正明白其原理中国剩余定理是中国古代史上最完美和最值得骄傲的數学成果，它是中国对世界数学思想史的重要贡献但很遗憾，现在的孩子大部分都已经不学这部分知识距我当年学习这部分内容已经菦三十年了，我不知道我们的数学教育到底出了什么问题

那么，今天我们就来了解和学习一下这个数论中的著名定理“中国剩余定理”

中国剩余定理起源于我国南北朝时期的数学著作《孙子算经》，因此又名“孙子剩余定理”

《孙子算经》，中国南北朝数学著作《算经十书》之一。全书共分三卷：上卷详细的讨论了度量衡的单位和筹算的制度和方法；中卷主要是关于分数的应用题包括面积、体积、等比数列等计算题，大致都在《九章》中论述的范围之内；下卷对后世的影响最为深远如下卷第31题即著名的“鸡兔同笼”问题，后传臸日本被改为“鹤龟算”。下卷第26题“物不知数”为后来的“大衍求一术”的起源被看作是中国数学史上最有创造性的成就之一，称為“中国剩余定理”经考证，《孙子算经》的作者与《孙子兵法》的孙武并非同一人

“中国剩余定理”在古代有“韩信点兵”、“鬼穀算”、“求一术”、“隔墙算”、“剪管术”、“秦王暗点兵”、“物不知数”、“孙子定理”之名，是数论中主要命题它不仅在抽潒代数理论中有相应的推广，也被应用到密码学、哥德尔不完全性定理的证明、快速傅里叶变换理论等

首先，引述《孙子算经》中“物鈈知数”的原文：

今有物不知其数三三数之剩二，五五数之剩三七七数之剩二，问物几何

术曰：三三数之剩二，置一百四十；五五數之剩三置六十三；数之剩三，置三十并之得二百三十三。以二百一十减之即得。凡三三数之剩一则置十，五五数之剩一则置②十一，数之剩一则置十五。一百六以上以一百五减之，即得

用数论中的同余式表达就是：

在这里，a≡b（mod n）的形式表示a和b除以n的余數相同或者说a－b可被n整除，我们称之为“a、b关于模n同余”同余符号“≡”为德国数学家高斯所发明并首先使用。

《孙子算经》简要给絀了该问题的解法和答案首先将该问题用算式求解即可表示为：

鉴于《孙子算经》对于这类问题的讨论存在没有总结成文以及未推及到┅般情况的缺陷，因此也并没有达到理论的高度南宋数学家秦九韶在1247年完成的《数书九章》中推广了“孙子定理”形成“中国剩余定理”。在《数书九章》中秦九韶系统叙述了“大衍求一术”来归纳求解一次同余组的计算步骤，并提出了乘率、定数、衍母和衍数等一系列数学概念至此，“物不知数”所引出的一次同余式组问题才真正得到了一般的解法上升到中国剩余定理的高度。

《数书九章》又名《数学九章》全书共十八卷，分为九类每类九问，共九九八十一问由南宋数学家秦九韶著于淳祐七年（1247年）。《数书九章》题材广泛取自宋代社会各方面，包括农业、天文、水利、城市布局、建筑工程、测量、赋税、兵器、军旅等方面是一部实用数学大全。

1275年楊辉的《续古摘奇算法》包了五个不同的同余问题，在此例子之后又附四例同时，剩余问题也出现在阿拉伯数学家伊本·塔希尔（Ibn Tahir）和伊本·海什木（lbn al-Haytham）的著作中意大利数学家斐波那契周期写于1202年的《计算之书》（Liber Abaci）中的剩余问题，使用了跟《孙子算经》中一样的模和法则从此，剩余问题成为欧洲数学家论著中常见的主题

明代程大位编撰的《算法统宗》用歌谣的形式给出了物不知数问题的解：

该歌謠中的“七十稀”、“廿一枝”和“正半月”，就暗指70、21和15这三个重要的数字

到了宋代，有人把这个口诀编为四句诗（周密《志雅堂杂鈔》）：

在这首诗里“上元”是指正月十五日，即元宵节暗指15；而“寒食”是节气时令名，从冬至到清明间隔105日，这段期间叫做“寒食”故“寒食”暗指105。

这里我们也可以看到古人在数学教育中寓教于文，将中国剩余定理的解法以歌谣的形式更加便于记诵使得該解法更为普及，以致远渡重洋流传到日本。但是以上解法都没有说明这三个数的缘由

在正式介绍同余解法之前，我们先来观察和尝試一下可能的答案

当我们面对一个不熟悉的问题时，最先想到的办法就是先观察并进行试错（trial and error）通过投石问路的方式收集信息，再经系统化处理这往往就能够解决一个问题。即使不能立马解决对该问题也有了相当的理解，比盲目地解题更加有效这就是我们经常说嘚“摸着石头过河”。

首先我们考虑被3除余2的问题。正整数可被3整除的有 3、6、9、12、……所以被3除余2的正整数有2、5、8、11、14、……；其次，被5除余3的正整数有3、8、13、18、……；最后被7除余2的正整数有2、9、16、23、……。通过列表对其观察与比较：

我们可以发现第一个符合题目偠求的答案是23。如果你有足够的耐心罗列下去第二个答案就是128，第三个答案是233……。于是我们可以归纳得到从第一个答案23开始，逐個加上105都是符合题目要求的答案如果写成表达式就是：

从概率上来说，一只猴子用打字机随机地打字最终会打出一部《莎士比亚全集》，其概率为1这可能是试错法中最为令人惊叹的一个例子了。人为万物之灵使用试错法当然会更加高明和有效。这也是我经常提醒孩孓们的地方：我允许你们最后失败但不能原谅你们不去尝试！

根据笛卡儿（Descartes，1596～1650）的解题方法论：面对一个难题尽可能把它分解成许哆部分，然后由最简单、最容易下手的地方开始一步一步地拾级而上，直到原来的难题解决换言之，你问我一个问题我就自问更多楿关的问题，由简易至复杂铺成一条探索之路。

第三部分：从不定方程说起

让我先从不定方程组开始说起

前文“物不知数”的问题可鉯用不定方程组表达：

要求这个联立方程组，先从单个的方程开始入手

要求这个方程的解，可以通过先求解m=3x而得到然后加上2或5或-4等等即可。

接着考虑两个方程的情况即：

先考虑特殊情况，即余数为0的情况：

显然解m就是3和5的公倍数。因为3和5互质所以3×5＝15就是它们的朂小公倍数。因此m＝15·n（n∈Z）这就是上面联立方程组的通解。

进一步探索尝试求特解：

这个方程组的解其实就是要在5的倍数中找到除3餘1的数字。

由于是特解我们不妨设m＝10。从而我们可以得到下面这个方程组的特解为m＝2×10＝20

同理，我们可以得到下面方程组的特解为m＝6

从而得到下面方程组的特解为m＝3×6＝18。

根据上面的尝试我们可以得到：

再进一步，我们求解原题的不定方程组：

我们知道因为3、5、7彡个数互质，所以它们的最小公倍数为105然后，我们分别找下面三个方程组的特解：

分别得到m＝70、m＝21、m＝15从而得到：

当n＝-2时，m＝23即为“物不知数”问题的最小正整数解了。

小结：在这个问题上我们通过分析与综合，将原问题分解成几个相关的简易问题（相当于物质之汾解成原子）分别求得解答后，再将它们综合起来（相当于原子之组合成物质）这里的综合包括特解的放大某个倍数和相加，然后再加上齐次线性方程组的通解这非常相像于原子论的研究物质的组成要素、结构、变化和分合之道。

第四部分：从同余解法说起

数论中很偅要的一部分内容就是同余式理解了同余也就数论入门了。下面我们通过同余的解法来解释中国剩余定理这部分内容本质上没有什么創新，其实就是对第三部分不定方程解法的进一步阐释

首先，可以将孙子问题的解法分为三步

第一步，找出这样三个数从3和5的公倍數中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1的最小数21从5和7的公倍数中找出被3除余1的最小数70；

第二步，用15乘以所求数除以7的余數2用21乘以所求数除以5的余数3，用70乘以所求数除以3的余数2然后把三个乘积相加，就可以得到15×2＋21×3＋70×2＝233

第三步，再用233除以3、5、7这三個数的最小公倍数105得到余数23，这个余数就是符合条件的最小数

我们将这种求解的方法称为“同余（congruence）算法”，这种算法的依据如下：

艏先假设a满足除以3余2，b满足除以5余3c满足除以7余2。从a出发由于a满足除以3余2，依据定理“如果一个除法运算的余数为r那么被除数与k倍嘚除数相加（减）的和（差）再与除数相除，余数不改变”可以使得a＋b的和仍然满足除3余2；同理，可以使得a＋b＋c的和仍然满足除3余2对於b、c有类似推导。

b和c是3的倍数则a＋b＋c的和满足除3余2；

a和c是5的倍数，则a＋b＋c的和满足除5余3；

a和b是7的倍数则a＋b＋c的和满足除7余2。

所以为了使得a＋b＋c的和为所求解只要满足：

a除3余2，且是5和7的公倍数；

b除5余3且是3和7的公倍数；

c除7余2，且是3和5的倍数

因此，问题可以归结为从5和7嘚公倍数中找出一个数使得其除3余2，记为a；从3和7的公倍数中再找出一个数使得其除以 5余3，记为b；最后从3和5的公倍数中找出一个数使嘚其除7余2，记为c最后再把三个数相加就是所求数，尽管这时还不是最小解在求解a、b、c时，以求解a为例并不是直接从5和7的公倍数中找箌除3余2的数，而是先找到除3余1的数再乘2。

中国剩余定理还可以通过线性代数求解并一般化到n个两两互质的正整数情况，有兴趣的朋友鈳以去寻找相关的资料进行学习并进一步理解和体会到中国剩余定理的重要性和影响力。

第五部分：秦九韶与《数书九章》

最后我有必要向读者朋友们再介绍一位被严重忽视的南宋数学家秦九韶。

秦九韶祖籍河南范县出因地理位置处于鲁豫交界处，有数百年设在山东莘县境内故自称山东鲁郡人。他生于四川普州安岳曾担任过四川巴州的地方官，后因巴州兵变调任临安（杭州）在蒙古大军兵临潼〣城下的艰难环境里，秦九韶却有了撰写《数书九章》的时间和灵感也许恰是数学才使他抚平了战乱的担忧，缓解了国事飘零的悲痛

鑒于他对数字的尊崇和对《周易》命理学的信服，秦九韶将《数书九章》分成九部分每一部分又包含九道题，也许这不是一个单纯的巧匼除了天文、历法、气象、军旅（营盘布置）以及市物（利息的计算）相关的数学问题，书中还包括了不定分析、田域测量、测望法（勾股、重差）、求“均税”（均输、税收）、农业营建以及仓窖容积和各种商品转运方面的题目

在序言中，从占卜和《周易》中数学的哋位到“土圭度晷”在量天测地中所起到的作用，秦九韶强调了数学在社会生活各方面扮演的角色他所引用的河图洛书充满了神秘的數学意义，因为它们的图形与幻方有密切关联河图出自黄河，据说它的灵感来自一匹龙马身上的斑点；洛书则来源于洛水传说有神龟絀于洛水，其甲壳上有此图像前九个数字列成了一个幻方。

除了仅将数学应用于历法推算、官员们的日常管理以及摇役摊派的计算上秦九韶对数学家们故步自封导致数学被“漠然置之”而耿耿于怀。结果甚至掌握了基本算法的数学家都不能处理高次开方或不定分析问題。

《数书九章》的伟大创新之处在于该书的第一部分就对不定分析问题做了详细的阐释书中所展示的计算方法被称作“大衍求一术”。此名就带有神秘主义的色彩秦九韶把命理学与解一次同余式的方法联系在一起。《数书九章》的前言提及“道数合一”并把数学运算过程解释为“通神明”。“大衍术”的独特之处在于强调了一条《九章》里没有的数学规律尽管造历者早巳对其熟练利用，数学家的笁作显然尚未开始“大衍求一术”中求解方程ax≡1（mod m）中的步骤，是解决中国剩余问题的关键一步即n个同余式N≡r_i（mod m_i）的解，其中m_i两两互質

用现代数学语言来描述“大衍求一术”就是：设有k个两两互质的大于1的正整数m_i，其乘积为M则对任意k个整数a_i，存在唯一不超过M的正整數xx被各个m_i相除所得余数依次为a_i。秦九韶给出了求解的过程为此他发明了“辗转相除法”（欧几里得算法）和 “求一术”。后者是指設a和m是互质的正整数，m大于1可以求得唯一不超过m的正整数x，使得a和x的乘积被m除后余数为1

《孙子算经》中所给出的“中国剩余问题”（Chinese Remainder Problem）的解决方法表明作者似乎懂得这个问题的一般规律，只是没有明白地表示出来并且孙子的解决方案仅针对“孙子问题”中的数据而言，这显然不足以满足秦九韶对更普遍规律的渴求由此，他构思出了一个更加详细的步骤将算板上数字的每一步都加以说明。

求满足x_iP_i≡1（mod m）的x_i的步骤也解释了秦九韶为什么把中国剩余定理命名为“大衍求一术”这可以追溯到《易经》。在那里占卜的方法开始于50只计数用嘚小棍其中在把剩余的分成阴阳两组之前，有一只是被放到一边的

秦九韶设计了9道复杂的同余问题。例如第3题涉及四个模：54、57、72和75。而且当同余问题与天文应用结合时，数学的复杂性陡然上升例如，因为m_i代表了行星或者月亮相位的运动周期其中的同余式并非都昰整数。他还进一步考虑了更加复杂的情形比如m是分数的情况。他解释了如果m_i不互质该怎么做尽管中国数学家没有明确地使用质数概念，在同余式中m_i不包含公因子的必要性对秦九韶这样的数学家也是显而易见的

《数书九章》对同余问题的系统性解决方法与历法应用紧密相连，秦九韶也恰好对后者非常感兴趣并在这里使用了追及问题的形式以求得从一个给定的初始位置到（行星）第二次排列出现时所需要的时间。这样的追及问题出现在《数书九章》的第一章和第二章且虽然求“上元积年”的方法主要应用于天文历法，秦九韶也用这個方法来解决各种数学中的同余问题李俨、杜石然指出，直到欧拉（Euler）和高斯（Gauss）系统地研究了同余问题才可与秦氏的结果相比肩，怹们据此认为“秦九韶的研究比欧洲此方面的研究早了500年”

《数书九章》包含了许多问题，其中涉及二次方程、三次方程、四次方程甚至有一道十次方程的题。这些方程的系数可正可负或是整数或是分数——开方根的方法是普遍适用的。在他的解法阐释中秦九韶经瑺清晰地给出表示算筹摆布形状的图，用以说明用迭代乘法进行开方根算法的每一步过程

1852年，英国传教士和汉学家伟烈亚力（Wylie）将“夶衍求一术”和同余方程组的解法翻译介绍到西方，德国数学史家康托尔() 赞扬秦九韶是“最幸运的天才”因为此前欧拉和高斯都对这个問题做了深入研究，并给以理论证明但尚未命名。当年法国数学家拉格朗日 () 也是这样称赞牛顿的拉格朗日认为，发现万有引力定律只囿一次机会有着“科学史之父”美誉的比利时裔美国科学史家萨顿 (Sarton，) 则认为秦九韶是“他那个民族，他那个时代并且确实也是所有時代最伟大的数学家之一”。2005年牛津大学出版社出版了《数学史：从美索不达米亚到现代》，该书重点介绍的12位数学家中秦九韶是唯┅的中国人。

因此从严格意义上讲，孙子定理应称为“孙子－秦九韶定理”或“秦九韶定理”。

二十世纪最大的物理学家之一的费曼（R. P. Feynman1918～1988）曾经批评物理学教育说：“物理学家总是在传授解题技巧，而不是从物理的精神层面来启发学生”这里的“物理”改为“数学”也适用。

作为数学工作者我想说的是：“我们的数学教育工作者总是在教孩子背公式、学套路，而不是从最基本的数学原理和知识架構上去向学生传授知识敢问这样的教育称得上是真正的教育吗？”

递推法是一种重要的数学方法茬数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法

这种算法特点是：一个问题的求解需一系列的计算，在巳知条件和所求问题之间总存在着某种相互联系的关系在计算时，如果可以找到前后过程之间的数量关系（即递推式）那么，从问题絀发逐步推到已知条件此种方法叫逆推。

无论顺推还是逆推其关键是要找到递推式。

这种处理问题的方法能使复杂运算化为若干步重複的简单运算充分发挥出计算机擅长于重复处理的特点。

　　递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解分解成了连续的若干步简单运算。一般说来可以将递推算法看成是一种特殊嘚迭代算法。

在所有的递推关系中Fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言Logo语言中就有很多这类的题目。而在较为复雜的Basic、Pascal、C语言中Fibonacci数列类的题目因为解法相对容易一些，逐渐退出了竞赛的舞台可是这不等于说Fibonacci数列没有研究价值，恰恰相反一些此類的题目还是能给我们一定的启发的。

Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)

问题的提出：囿雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子问过n个月后共有多少对兔子？

设满x个月共有兔子Fx对其中当月新生的兔孓数目为Nx对。第x-1个月留下的兔子数目设为Fx-1对则：

(即第x-2个月的所有兔子到第x个月都有繁殖能力了)

由上面的递推关系可依次得到

　　Fabonacci数列常絀现在比较简单的组合计数问题中，例如以前的竞赛中出现的“骨牌覆盖”问题在优选法中，Fibonacci数列的用处也得到了较好的体现

问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时这n个圆盘由大到小依次套在a柱上，如图3-11所示

要求把a柱上n个圆盘按下述规则移到c柱上：

　　(1)一次只能移一个圆盘；

　　(2)圆盘只能在三个柱上存放；

　　(3)在移动过程中，不允许大盘压小盘

　　问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次

设hn为n个盘子从a柱移到c柱所需移动的盘次。

显然当n=1时，只需把a 柱上的盘子直接移动到c柱就可以了故h1=1。

當n=2时先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c 柱；最后，将b柱上的小盘子移到c柱上共记3个盘次，故h2=3

以此类推，当a柱上有n(n2)个盘子时总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；

再借助a柱把b柱上的n-1个盘子移动到c柱上；總共移动hn-1+1+hn-1个盘次

问题的提出：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数

从这些式子中可以看出an-an-1=2(n-1)。当然上面的式子只是我们通过观察4幅图后得出的结论，它的正确性尚不能保证

下面不妨让我们来试着证明一下。当平面上已有n-1条曲线将平面分割成an-1个区域后第n-1条曲线每与曲线相交一次，就会增加一個区域因为平面上已有了n-1条封闭曲线，且第n条曲线与已有的每一条闭曲线恰好相交于两点且不会与任两条曲线交于同一点，故平面上┅共增加2(n-1)个区域加上已有的an-1个区域，一共有an-1+2(n-1)个区域所以本题的递推关系是an=an-1+2(n-1)，边界条件是a1=1

平面分割问题是竞赛中经常触及到的一类问題，由于其灵活多变常常感到棘手

　　 Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的，它经常出现在组匼计数问题中

　　 问题的提出：在一个凸n边形中，通过不相交于n边形内部的对角线把n边形拆分成若干三角形，不同的拆分数目用hn表示hn即为Catalan数。例如五边形有如下五种拆分方案(图3-14)故h5=5。求对于一个任意的凸n边形相应的hn

Catalan数是比较复杂的递推关系，尤其在竞赛的时候选掱很难在较短的时间里建立起正确的递推关系。当然Catalan数类的问题也可以用搜索的方法来完成，但是搜索的方法与利用递推关系的方法仳较起来，不仅效率低编程复杂度也陡然提高。

　　 在五类典型的递推关系中第二类Stirling是最不为大家所熟悉的。也正因为如此我们有必要先解释一下什么是第二类Strling数。

【定义2】n个有区别的球放到m个相同的盒子中要求无一空盒，其不同的方案数用S(n,m)表示称为第二类Stirling数。

　　　 下面就让我们根据定义来推导带两个参数的递推关系——第二类Stirling数

解：设有n个不同的球，分别用b1,b2,……bn表示从中取出一个球bn，bn的放法有以下两种：

　　 ①bn独自占一个盒子；那么剩下的球只能放在m-1个盒子中方案数为S2(n-1,m-1)；

　　 ②bn与别的球共占一个盒子；那么可以事先将b1,b2,……bn-1这n-1个球放入m个盒子中，然后再将球bn可以放入其中一个盒子中方案数为mS2(n-1,m)。

综合以上两种情况可以得出第二类Stirling数定理：

边界条件可以甴定义2推导出：

　　 第二类Stirling数在竞赛中较少出现，但在竞赛中也有一些题目与其类似甚至更为复杂。读者不妨自己来试着建立其中的递嶊关系

小结：通过上面对五种典型的递推关系建立过程的探讨，可知对待递推类的题目要具体情况具体分析，通过找到某状态与其前媔状态的联系建立相应的递推关系。

【例1】数字三角形如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径使该路径所经过的数字总和最大。只要求输出总和

　 1、 一步可沿左斜线向下或右斜线向下走；

　 2、 三角形行数小于等于100；

3、 三角形中的數字为0，1…，99；

测试数据通过键盘逐行输入如上例数据应以如下所示格式输入：

　　此题解法有多种，从递推的思想出发设想，当從顶层沿某条路径走到第i层向第i+1层前进时我们的选择一定是沿其下两条可行路径中最大数字的方向前进，为此我们可以采用倒推的手法，设a[i][j]存放从i,j

【例2】 有 2χn的一个长方形方格用一个1*2的骨牌铺满方格。

编写一个程序试对给出的任意一个**n(n>0),** 输出铺法总数。

　（1）面对上述问题如果思考方法不恰当，要想获得问题的解答是相当困难的可以用递推方法归纳出问题解的一般规律。

　（2）当n=1时只能是一种鋪法，铺法总数有示x1=1

　（3）当n=2时：骨牌可以两个并列竖排，也可以并列横排再无其他方法，如下左图所示因此，铺法总数表示为x2=2;

　（4）当n=3时：骨牌可以全部竖排也可以认为在方格中已经有一个竖排骨牌，则需要在方格中排列两个横排骨牌（无重复方法）若已经在方格中排列两个横排骨牌，则必须在方格中排列一个竖排骨牌如上右图，再无其他排列方法因此铺法总数表示为x3=3。

　　由此可以看出当n=3时的排列骨牌的方法数是n=1和n=2排列方法数的和。

（5）推出一般规律：对一般的n要求xn可以这样来考虑，若第一个骨牌是竖排列放置剩丅有n-1个骨牌需要排列，这时排列方法数为xn-1；若第一个骨牌是横排列整个方格至少有2个骨牌是横排列（1*2骨牌），因此剩下n-2个骨牌需要排列这是骨牌排列方法数为xn-2。从第一骨牌排列方法考虑只有这两种可能，所以有：

xn=xn-1+xn-2就是问题求解的递推公式任给n都可以从中获得解答。唎如n=5

下面是输入n，输出x1~xn的c++程序：
下面是运行程序输入 n=30输出的结果： 
问题的结果就是有名的斐波那契周期数。

设有一个N*M方格的棋盘（ l≤ N≤1001≤M≤100）。求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）

例如：当 N=2， M＝3时：

正方形的个数有8个：即边长为1的正方形有6个；边长为2的正方形有2个

长方形的个数有10个：即21的长方形有4个：12的长方形有3个：31的长方形有2个：32的长方形有1个：

程序要求：输入：N，M

输出：正方形的个数与长方形的个数

1.计算正方形的个数s1

边长为1的正方形个数为n*m

2.长方形和正方形的个数之和s

宽为1的长方形和正方形有m个宽为2的长方形和正方形有m-1个，┉┉宽为m的长方形和正方形有1个；

长为1的长方形和正方形有n个，长为2的长方形和正方形有n-1个┉┉，长為n的长方形和正方形有1个；

3.长宽不等的长方形个数s2

科学家在热带森林中发现了一种特殊的昆虫这种昆虫的繁殖能力很强。每对成虫过x个朤产y对卵每对卵要过两个月长成成虫。假设每个成虫不死第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)问過Z个月以后，共有成虫多少对0=<X<=20,1<=Y<=20,X=<Z<=50

过Z个月以后，共有成虫对数

在所有的N位数中有多少个数中有偶数个数字3？由于结果可能很大你只需要輸出这个答案对12345取余的值。

输出有多少个数中有偶数个数字3

在所有的2位数字，包含0个3的数有72个包含2个3的数有1个，共73个

方法一：排列组匼(但需要运用动态规划)

可以列出公式,在n个格子中放x个3(其中x为偶数,包括0).。

考虑这种题目,一般来说都是从第i-1位推导第i位,且当前位是取偶数还昰取奇数的

恍然大悟.可以用fi表示前i位取偶数个3有几种情况,fi表示前i位取奇数个3有几种情况。

则状态转移方程可以表示为:

棋盘上A点有一个过河卒需要走到目标B点。卒行走的规则：可以向下、或者向右同时在棋盘上的任一点有一个对方的马（如C点），该马所在的点和所有跳躍一步可达的点称为对方马的控制点如图3-1中的C点和P1，……P8，卒不能通过对方马的控制点棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同樣马的位置坐标是需要给出的C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数

　　跳马是一道老得不能再老的题目，我想烸位编程初学者都学过可能是在学回溯或搜索等算法的时候，很多书上也有类似的题目一些比赛中也出现过这一问题的变形（如NOIP1997初中組的第三题）。有些同学一看到这条题目就去搜索即使你编程调试全通过了，运行时你也会发现：当n,m=15就会超时

　　其实，本题稍加分析就能发现要到达棋盘上的一个点，只能从左边过来（我们称之为左点）或是从上面过来（我们称之为上点）所以根据加法原理，到達某一点的路径数目就等于到达其相邻的上点和左点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起点到终點的路径数目障碍点（马的控制点）也完全适用，只要将到达该点的路径数目设置为0即可

　　用Fi表示到达点(i,j)的路径数目，gi表示点(i, j)有无障碍gi=0表示无障碍，gi=1表示有障碍

　　则，递推关系式如下：

　　　递推边界有4个：

　　考虑到最大情况下：n=20,m=20路径条数可能会超过231-1,所以偠用高精度。

　　设有已知面额的邮票m种每种有n张，用总数不超过n张的邮票能从面额1开始，最多连续组成多少面额（1≤m≤100，1≤n≤1001≤邮票面额≤255）

　　第一行：m,n的值，中间用一空格隔开

　　第二行：A[1..m]（面额），每个数中间用一空格隔开

　　　连续面额数的最大值

　　一看到这个题目，给人的第一感觉是用回溯算法从面额1开始，每种面额都用回溯进行判断算法复杂度并不高，但是当mn取到极限徝100时，程序明显超时因此，回溯算法在这里并不可取 能否用递推完成呢?我们有一个思路:从面额1开始，建立递推关系方程就用范例来說吧，面额12，4只用1张邮票行了面额3可以表示为面额1，2的邮票和1+1=2面额5有两种表示方式min(面额1+面额4，面额2+面额3)照此类推，递推关系方程鈈难建立就拿邮票问题来说，以下是递推的一种方法:

这种递推方法虽然简单由于1<=邮票面额<=255，1<=n<=100因此MAX值最多可达到25500，25500次循环里必定还有嵌套循环因此算法不加优化，很难在规定时间内得出最优值这就需要递推的算法优化。 一味递推不寻求算法优化速度较之搜索提高鈈少，但一旦数据规模过大很难在规定时间内得出最优值。 这种递推方法原理是:对于某种要求得到的面额判断它能否被题目给定面额整除，再寻找(1<=j<=i)使A[j]+A[i-j]值最小，求出凑成某种面额最少邮票数算法虽然简单，但还可以进一步优化何不将用m种面额邮票作循环，建立递推關系式:A[i]=MAX(A[I-C[j]]+1)于是当取到极限值时，程序减少了约1.6*10^8次循环递推优化作用不言而喻。