有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。

递归算法：

设：从0-8级台阶X种走法，从0-9级台阶Y种走法
因为走到第10级，最后一步必须是1或2，即从第8级或第9级开始，
所以走到第10级的走法共有X+Y种，即：F(10)=F(9)+F(8)
以此类推：

F(10)=F(9)+F(8)=34F(2)+21F(1)=68+21=89
F(9)=F(8)+F(7)=21F(2)+13F(1)=55
F(8)=F(7)+F(6)=13F(2)+8F(1)=34
F(7)=F(6)+F(5)=8F(2)+5F(1)=21
F(6)=F(5)+F(4)=5F(2)+3F(1)=13
F(5)=F(4)+F(3)=3F(2)+2F(1)=8
F(4)=F(3)+F(2)=2F(2)+F(1)=5
F(3)=F(2)+F(1)=3
F(2)=2
F(1)=1

 

动态规划算法:

自底向上计算,只需记住上次和上上次的走法数即可

 

数列1，2，3，5，8，13，21，34是有名的斐波那契数列。将第一个数加上第二个数得到第三个数，以此类推。

C(8,4)=8X7X6X5/4X3X2X1=70

伯努利-欧拉装错信封问题

某人想邀请朋友来家中聚会，写好了5封请柬，需要装入5个信封，结果因为粗心把请柬全部装错了信封。请问：装错的可能会有多少种呢？

这个问题可以描述为一个排列组合问题：n个元素的序列，要求在排列中没有一个元素处于它原有的位置。

递推公式法程序实现

瑞士著名数学家欧拉按一般情况给出了一个递推公式，分析如下。

用A、B、C……表示写着ｎ位友人名字的信封，a、b、c……表示ｎ份相应的写好的信纸。把错装的总数为记作D(n)。假设把ａ错装进Ｂ里了，包含着这个错误的一切错装法分两类：

(1)b装入Ａ里，这时每种错装的其余部分都与A、B、a、b无关，应有F(n－2)种错装法。　　　　

(2)ｂ装入A、B之外的一个信封，这时的装信工作实际是把（除a之外的）n－1份信纸ｂ、ｃ……装入（除B以外的）n－1个信封A、C……，显然这时装错的方法有F(n－1)种。

总之在ａ装入B的错误之下，共有错装法F(n－2)＋F(n－1)种。

a装入C，装入D……的n－2种错误之下，同样都有F(n－1)＋F(n－2)种错装法，因此F(n)＝(n－1)[F(n－1)＋F(n－2)]

这是递推公式。令ｎ＝1、2、3、4、5逐个推算就能求出多个装错信封的解。

F(1)＝0，

F(2)＝1，

F(3)＝2*（+0）=2，

F(4)＝3*（2+1）=9，

F(5)＝4*（9+2）=44.

假如1-10球和10个碗分别是1-10碗，把10个小球随机放入碗里，然后端起一个碗，碗是几号对应几号球，出现这种情况的概率是多少？例如端起5号碗，碗里放着是5号球。

端起任何1个碗，里面的是任何一个球的概率都是1/10。

连续端起任何2个碗，碗号与球号对应的概率是（1/10）*（1/9）。

连续端起任何3个碗，碗号与球号对应的概率是（1/10）*（1/9）*（1/8）。

连续端起任何4个碗，碗号与球号对应的概率是（1/10）*（1/9）*（1/8）*（1/7）。

连续端起任何5个碗，碗号与球号对应的概率是（1/10）*（1/9）*（1/8）*（1/7）*（1/6）。

连续端起任何6个碗，碗号与球号对应的概率是（1/10）*（1/9）*（1/8）*（1/7）*（1/6）*（1/5）.

连续端起任何7个碗，碗号与球号对应的概率是（1/10）*（1/9）*（1/8）*（1/7）*（1/6）*（1/5）*（1/4）

连续端起任何8个碗，碗号与球号对应的概率是（1/10）*（1/9）*（1/8）*（1/7）*（1/6）*（1/5）*（1/4）*（1/3）

连续端起任何9个碗，碗号与球号对应的概率是（1/10）*（1/9）*（1/8）*（1/7）*（1/6）*（1/5）*（1/4）*（1/3）*（1/2）

连续端起任何10个碗，碗号与球号对应的概率是（1/10）*（1/9）*（1/8）*（1/7）*（1/6）*（1/5）*（1/4）*（1/3）*（1/2）*（1/1）=1/10！。

插空法:

插空法数学术语，是用来解决某些元素不相邻的排列组合题，即不邻问题。在解决对于某几个元素要求不相邻的问题时，先将其它元素排好，再将指定的不相邻的元素插入已排好元素的间隙或两端位置，从而将问题解决的策略。用这种方法解题思路清晰、简便易懂。

下面举例说明。（1）例1：把1，2，3，4，5组成没有重复数字且数字 1，2不相邻的五位数，则所有不同排法有多少种？解析：本题直接解答较为麻烦，因为可先将 3，4，5三个元素排定，共有A³₃种排法，然后再将 1，2插入四个空位共有A²₄

种排法，故由乘法原理得，所有不同的五位数有A²₄A³₃=72种。

（2）例2：在一张节目单中原有六个节目，若保持这些节目的相对顺序不变，再添加进去三个节目，则所有不同的添加方法共有多少种？

解析： -o – o – o – o – o – o – ，即六个节目算上前后共有七个空位，那么加上的第一个节目则有A¹₇种方法；

此时有七个节目， 再用第二个节目去插八个空位有A¹₈种方法；

此时有八个节目， 用最后一个节目去插九个空位有A¹₉种方法。

由乘法原理得，所有不同的添加方法为：A¹₇A¹₈A¹₉=7X8X9=504种。

插板法

基本题型

基本题型为：n个相同元素，不同个m组，每组至少有一个元素；则只需在 n 个元素的n-1 个间隙中放置 m-1 块隔板把它隔成 m 份，求共有多少种不同方法？

其解题思路为：将 n 个相同的元素排成一行， n 个元素之间出现了（ n-1 ）个空档，现在我们用（ m-1 ）个 “档板 ”插入（ n-1 ）个空档中，就把 n 个元素隔成有序的 m 份，每个组依次按组序号分到对应位置的几个元素（可能是 1 个、2 个、 3 个、 4 个、 ….），这样不同的插入办法就对应着 n 个相同的元素分到 m 组的一种分法，这种借助于这样的虚拟 “档板 ”分配元素的方法称之为插板法。

例题：共有 10 完全相同的球分到 7 个班里，每个班至少要分到一个球，问有几种不同分法？

解析：我们可以将 10 个相同的球排成一行， 10 个球之间出现了 9 个空隙，现在我们用 6 个档板 ”插入这 9个空隙中，就 “把 10 个球隔成有序的 7 份，每个班级依次按班级序号分到对应位置的几个球（可能是 1 个、2 个、 3 个、 4 个），这样，借助于虚拟 “档板 ”就可以把 10 个球分到了 7 个班中。

基本题型的变形

（1）变形1：有 n 个相同的元素，要求分到 m 组中，问有多少种不同的分法？

解题思路：这种问题是允许有些组中分到的元素为 “0”，也就是组中可以为空的。对于这样的题，我们就首先将每组都填上 1 个，这样所要元素总数就 m 个，问题也就是转变成将（ n+m ）个元素分到 m 组，并且每组至少分到一个的问题，也就可以用插板法来解决。

例题：有 8 个相同的球放到三个不同的盒子里，共有（ ）种不同方法 。

解答：题目允许盒子有空，则需要每个组添加 1 个，则球的总数为 8+3 ×1=11，此题就有 C（10 ，2） =45（种）分法了。

（2）变形2：有 n 个相同的元素，要求分到 m 组，要求各组中分到的元素至少某个确定值 S（ s>1，且每组的 s值可以不同） ，问有多少种不同的分法？

解题思路： 这种问题是要求组中分到的元素不能少某个确定值 s，各组分到的不是至少为一个了。 对于这样的题，我们就首先将各组都填满，即各组就填上对应的确定值 s 那么多个，这样就满足了题目中要求的最起码的条件，之后我们再分剩下的球。这样这个问题就转变为上面提到的变形1的问题了，也就可以用插板法来解决。

例题：15 个相同的球放入编号为 1、2、 3 的盒子内，盒内球数不少于编号数，有几种不同的放法？

解析：编号 1：至少 1 个，符合要求；编号 2：至少 2 个：需预先添加 1 个球，则总数 -1 ；编号 3：至少 3 个，需预先添加 2 个，才能满足条件，后面添加一个，则总数 -2 ；则球总数 15-1-2=12 个放进 3 个盒子里，所以 C（11，2）=55 （种）。

插空法是填充，隔板法是分组。

隔板法就是在n个元素间插入（b-1）个板，即把n个元素分成b组的方法，而插空法在解决对于某几个元素要求不相邻的问题时，先将其它元素排好，再将指定的不相邻的元素插入已排好元素的间隙或两端位置，从而将问题解决的策略。

列题解析：

将20个大小形状完全相同的小球放入3个不同的盒子，允许有盒子为空，但球必须放完，有多少种不同的方法？

分析：本题中的小球大小形状完全相同，故这些小球没有区别，问题等价于将小球分成三组，允许有若干组无元素，用隔板法。

解析：将20个小球分成三组需要两块隔板，因为允许有盒子为空，不符合隔板法的原理，那就人为的再加上3个小球，保证每个盒子都至少分到一个小球，那就符合隔板法的要求了（分完后，再在每组中各去掉一个小球，即满足了题设的要求）。

然后就变成待分小球总数为23个，球中间有22个空档，需要在这22个空档里加入2个隔板来分隔为3份，共有C（22，2）=231种不同的方法。

假定第一个盒为0个，第二盒为21种可能，

假定第一个盒为1个，第二盒为20种可能，

假定第一个盒为2个，第二盒为19种可能，

假定第一个盒为3个，第二盒为18种可能，

假定第一个盒为4个，第二盒为17种可能，

假定第一个盒为5个，第二盒为16种可能，

假定第一个盒为n个，第二盒为21-n种可能，

假定第一个盒为19个，第二盒为2种可能，

假定第一个盒为20个，第二盒为1种可能，

总共为：21+20+19+18+…+2+1=21+(20+1)*10=21+210=231

扩展资料
水果分篮问题：例：有广西橘子，烟台苹果，莱阳梨若干，从中随版意取出四个，问共有多少种不同取法？
问题等价于将四个水果放入三个不同的水果篮，且允许篮子为空，{这里是逆向思维逻辑}将4+3=7个水果分为3个组，分组需2个隔板权，隔板共有6个放置位置，故有C（4+2， 2）个选择，即15种。

假定第一个篮为0个，第二蓝为5种可能，

假定第一个篮为1个，第二蓝为4种可能，

假定第一个篮为2个，第二蓝为3种可能，

假定第一个篮为3个，第二蓝为2种可能，

假定第一个篮为4个，第二蓝为1种可能，

总共为：5+4+3+2+1=15

捆绑法:

所谓捆绑法，指在解决对于某几个元素要求相邻问题时，先整体考虑，将相邻元素视作一个整体参与排序，然后再单独考虑这个整体内部各元素间顺序。注意：其首要特点是相邻，其次捆绑法一般都应用在不同物体的排序问题中。

例题：6个不同的球放到5个不同的盒子中，要求每个盒子至少放一个球，一共有多少种方法?

解答：根据题目要求，则其中一个盒子必须得放 2 个，其他每个盒子放 1 个球，所以从 6 个球中挑出 2 个球看成一个整体，则有C²₆，这个整体和剩下 4 个球放入 5 个盒子里，则有A⁵₅。方法是C²₆A⁵₅。

假设有12个乒乓球，其中1个是次品，除了次品以外所有球的重量都相同（次品一定偏轻或偏重）。现有一架无砝码的天平，请设计一种使用天平称重的方式，使得一定能在3次称重之内找出次品，并能判断次品是偏轻还是偏重。

猜密码：有一个5位数的密码由0-9组成，密码数字不重复，每猜一次会知道其中有几个数字是正确的但位置不正确，有几个数字正确且位置也正确。
解题思路：
分析1、任意猜5个数1次，结果如下：
1.0、数字全对，位置也全对，走了狗屎运，哈哈，最少一次猜出结果。
1.1、数字对5个，位置先不考虑，转分析4；
1.2、数字对4个，位置先不考虑，转分析3；
1.3、数字对3个，位置先不考虑，转分析2；
1.4、数字对2个，位置先不考虑，那么剩下的数字对3个，转分析2；
1.5、数字对1个，位置先不考虑，那么剩下的数字对4个，转分析3；
1.6、数字对0个，位置先不考虑，那么剩下的数字对5个，转分析4；

分析2、数字对3个一组叫前组，剩下数字对2个一组叫后组，取前组其中任意一个数字与后组的任意4数字对换4次猜前组，即可确认后组5个数字和前组其中一个数字的属性，再取后组正确密码的一个数字与前组剩余任意三个数字交换再猜前组，即可得出正确的5个数字出来。最多为4+3猜7次。

分析3、数字对4个一组叫前组，剩下数字对1个一组叫后组，取前组其中任意一个数字与后组的任意4数字对换4次猜前组，即可确认后组5个数字和前组其中一个数字的属性，再取后组正确密码的一个数字与前组剩余任意三个数字交换猜前组，即可得出正确的5个数字出来。最多为4+3猜7次。

分析4、已知5个正确数字叫前组，剩下的5个数字叫组，后组数字肯定不对。从前组任意取出一个数字与后组任意取出4个数字进行猜测，最多4次，可确认前组1个数字的位置，再重复上述步骤，最多3次，可确认前组2个数字的位置，再重复上述步骤，最多2次，可确认前组3个数字的位置，再猜测1次，5个数字的位置可全部确认。最多为4+3+2+1猜10次。

结果为：最少1次出结果，最多1+7+10=18次出结果。

学习小组的4名女生和3名男生站成一排拍照：
1、共有多少种不同的排队方法。
2、男生之间互不相邻，共有多少种不同的排队方法。
3、女生之间互不相邻，共有多少种不同的排队方法。
4、男生之间互不相邻，女生之间也互不相邻，共有多少种不同的排队方法。

正确答案：
（1）共有A(7,7)=7！=5040种。
（2）女生先排有4！=24种，男生后排，就是5个空位排3人，有A(5,3)=5*4*3=60种，相乘为24*60=1440种。
（3）男生先排有3！=6种，女生后排，就是4个空位排4人，有A(4,4)=4*3*2=24种，相乘为6*24=144种。
（4）同上为144种。

1×1=16
2×2=16+3=19
3×3=2
4×4=9
6×6=4
8×8=1
16+19+2+9+4+1=51

答案应该是1*26*26+25*26+25＝1351，或者反过来算更简单，BZZ+1等于CAA即2*26*26等于1352，减一就是1351
十进制的数位是这样的：
…10^2 10^1 10^0 10^-1 10^-2…
百 十 个 十分之一 百分之一
所以十进制数356=3×10^2 +5×10^1 +6×10^0
同理，二十六进制的数位是这样的
…26^2 26^1 26^0 26^-1…
那么二十六进制数
BZZ=B×26^2+ Z×26^1 +Z×26^0

蒙提霍尔问题：

在某个电视节目比赛环节中，参赛者会看见三扇关闭了的门，其中一扇的后面有一辆汽车，选中后面有车的那扇门可赢得该汽车，另外两扇门后面则各藏有一只山羊。参赛者选定了一扇门，但未开启它，随后节目主持人蒙提霍尔（Monty Hall）开启了剩下的两扇门中的一扇并且发现后面是一只山羊，此时主持人会给予选手重新选择的机会。问题是：此时参赛者换另一扇门会否增加赢得汽车的机率？

我们先玩三个游戏吧。

游戏1.有三个盒子，一个盒子里有钻石，其它两个什么都没有。你先选了一个盒子，放在你的书包里。主持人把另外两个放在他的书包里。这时候问你，要不要用你的书包换主持人的书包？

分析：你的书包只有一个盒子，主持人的书包有两个，很显然，主持人的书包里有钻石的可能性更大。所以应该选择换！

游戏2.有三个盒子，一个盒子里有钻石，其它两个什么都没有。你先选了一个盒子，放在你的书包里。主持人把另外两个放在他的书包里。然后主持人从他的书包里扔掉一个没有钻石的盒子。这时候问你，要不要用你的书包换主持人的书包？

分析：主持人从他的书包里扔掉一个没有钻石的盒子，这个行为并不会改变书包里有钻石的概率。所以既然游戏1要换，那么游戏2同样要换。

游戏3.有三个盒子，一个盒子里有钻石，其它两个什么都没有。你先选了一个盒子。然后主持人从另外两个盒子中扔掉一个没有钻石的盒子。这时候问你，要不要用你的盒子换剩下的那个盒子？

分析：游戏2相对于游戏3，唯一的不同是增加了“书包”这个概念，但其实有没有把盒子装入书包，并不会对结论产生影响，本质上游戏3和游戏2是同一个游戏。所以游戏3同样要换。

而游戏3就是题目中所描述的蒙提霍尔问题。因此结论只有一个字：换。

兔妈妈采了一些蘑菇，平均分给9只小兔，每只小兔分到的蘑菇和剩下的一样多，兔妈妈最多采了多少蘑菇？

答：因为有9只小兔，所以最多剩下8个蘑菇，总共有（9+1）*8=80个蘑菇。

2的倍数：末尾02468
3的倍数：各位数字之和能被3整除
4的倍数：后两位数是4的倍数
5的倍数：末尾是0或5
6的倍数：同时满足2的倍数和3的倍数特征
7的倍数：割去末尾数字，用剩下的数字与割去数字的二倍做差（大减小），反复进行最后是7的倍数则原数为7的倍数（百位×2加十位×3加个位能被7整除）
8的倍数：后三位是8的倍数
9的倍数：各位数相加能被9整除
10的倍数：末尾数字为0

甲乙丙三人制作工艺品，花束和花瓶（一支花束和一个花瓶配成一套），若甲每小时能制作10支花或11个花瓶，乙每小时能制作11支花或12个花瓶，丙每小时能制作12支花或13个花瓶，若他们共同工作了23小时，则最多能制作出多少套？请说出你的方案。

假设甲做花x小时，做瓶（23-x）小时，乙做花y小时，做瓶（23-y）小时，丙做花z小时，做瓶（23-z）小时。
显然3人共做花10x+11y+12z,三人共做瓶11*（23-x）+12*（23-y）+13*（23-z）
若花数与瓶数相等，则可列出不定方程
10x+11y+12z=11*（23-x）+12*（23-y）+13*（23-z）
整理得 21x+23y+25z=828
而828=2^2*3^2*23=36*23
可以算出828是23的倍数，根据余数在结合题意是x=z或者，x=0，z=23或者x=23，z=0
当x=z时，2x+y=36，则10x+11y+12z=11(2x+y)=11*36=396(套)。
当x=0，z=23时，y=36-25=11，则10x+11y+12z=11*11+12*23=121+276=397(套)。
当x=23，z=0时，y=36-21=15，则10x+11y+12z=10*23+11*15=230+165=395(套)。
所以当x=0，z=23，y=11时，最多能制作出397套。