一道排列组合问题的多种解法_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
一道排列组合问题的多种解法
上传于||暂无简介
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
你可能喜欢用户等级：小学二年级
注册时间：
在线时长：117 小时
等级：小学二年级
<em id="authorposton15-4-30 16:11
查看: 1943&
有10个苹果，12个生梨，11个香蕉，从中取6个水果，有多少种取法？
搞不懂什么时候能用隔板法，什么时候不能用
用户等级：高中一年级
注册时间：
在线时长：246 小时
元宝：1751
金币：2411
<em id="authorposton15-4-30 20:03
弱问，是93么
用户等级：高中一年级
注册时间：
在线时长：246 小时
元宝：1751
金币：2411
<em id="authorposton15-4-30 20:05
马甲之马甲 发表于
弱问，是93么不对，63
用户等级：版主
注册时间：
在线时长：8105 小时
金币：89681
<em id="authorposton15-4-30 23:15
有10个苹果，12个生梨，11个香蕉，从中取6个水果，有多少种取法？
由于每种水果都足够多，所以不用考虑某种水果不够取。
用隔板法。
6个水果再加3个水果（代表每种水果各一个），有8个空，用两块板分成三份。
C（8,2）=28 种。
用户等级：版主
注册时间：
在线时长：8105 小时
金币：89681
<em id="authorposton15-4-30 23:19
理解思路的话，可以将问题最简化。
例如如果只有两种水果（足够多），只要取两个，自己试试看用隔板法去做。
用户等级：小学五年级
注册时间：
在线时长：148 小时
<em id="authorposton15-5-1 08:37
提示: 作者被禁止或删除 内容自动屏蔽
用户等级：小学五年级
注册时间：
在线时长：148 小时
<em id="authorposton15-5-1 08:38
提示: 作者被禁止或删除 内容自动屏蔽
自然数解，可以取0个。
用户等级：高中一年级
注册时间：
在线时长：82 小时
金币：2493
<em id="authorposton15-5-1 14:26
skykiller 发表于
有10个苹果，12个生梨，11个香蕉，从中取6个水果，有多少种取法？
由于每种水果都足够多，所以不用考虑某 ...可是没说每种水果必需要有一个啊？为什么要加3个呢。
用户等级：高中一年级
注册时间：
在线时长：246 小时
元宝：1751
金币：2411
<em id="authorposton15-5-1 15:46
感觉自己像在菜市场讲价钱，汗
是33种吧？不一定每种都有
用户等级：版主
注册时间：
在线时长：8105 小时
金币：89681
<em id="authorposton15-5-1 19:07
evebingli 发表于
可是没说每种水果必需要有一个啊？为什么要加3个呢。
正是由于不必每种必需有一个，所以要加3个。否则就不用加了。
加了以后，如果隔板分出来的某种只有一个，看成0个。
比如说，9个用2块板分成：3+2+4，那么每种分别取的数目为：2/1/3；
如果分成：1+1+7，那么每种分别取的数目为：0/0/6；
用户等级：版主
注册时间：
在线时长：8105 小时
金币：89681
<em id="authorposton15-5-1 19:09
zhangyizy250 发表于
相当于x+y+z=6的不定方程有几组非零整数解自然数解，可以取0个。
用户等级：版主
注册时间：
在线时长：8105 小时
金币：89681
<em id="authorposton15-5-1 19:11
zhangyizy250 发表于
这题默认水果相同，如果水果不同，思路也不一样。
如果某种水果也有不同，那么所有的都不一样了，直接C（33,6）.
不过，一般同种水果都看成相同的。
用户等级：高中一年级
注册时间：
在线时长：246 小时
元宝：1751
金币：2411
<em id="authorposton15-5-1 19:30
排列组合高三学的，老师教的时候就说考大学不考。上了大学概率论又瞎混过去，这块是太薄弱了，惭愧。
穷举验证了下，是28。今晚就上网找个插板法的详细说明补个课。
用户等级：高中一年级
注册时间：
在线时长：82 小时
金币：2493
<em id="authorposton15-5-1 19:49
skykiller 发表于
正是由于不必每种必需有一个，所以要加3个。否则就不用加了。
加了以后，如果隔板分出来的某种只有一个 ...哦，看来我理解不对！我一直以为插两块板，如果一块板插在最左边的或者最右边的空档里，就代表0。变成是7个空里选2个。但想想是不对的。
用户等级：高中一年级
注册时间：
在线时长：82 小时
金币：2493
<em id="authorposton15-5-1 19:49
马甲之马甲 发表于
排列组合高三学的，老师教的时候就说考大学不考。上了大学概率论又瞎混过去，这块是太薄弱了，惭愧。
穷举 ...我就没印象自己学过，更绝！
灌水类文章达5篇以上者可申请
济南特色勋章
描述：济南地区用户专用勋章
Powered by1579人阅读
AC解 - 用动态规划解决一道排列组合计数问题（序关系计算）
原题如下：http://acm./problem.php?problem=1134
[同时请参考网友pandm发的帖子：http://topic.csdn.net/u//adf4d0b0-2b8e-4c0a-b8da-07b27f1711cc.html?seed=&r=#r_]
There are 13 possible orderings for three numbers, if we sort them with the& relation '&' and '=':
A = B = C , A = B & C , A & B = C ,A & B & C
A & C & B , A = C & B , B & A = C ,B & A & C
B & C & A , B = C & A , C & A = B ,C & A & B
Given an integer n, your task is to find the number of possible orderings& for any n real numbers.
There are several test cases. Each case contains only one integer n which is& between 1 and 50.
Output the number of different orderings for any n real numbers.
Sample Input
Sample Output
分析：首先理解题意，像A=B&C和B=A&C这样的关系在本题中应该算一种，而不能算成两 种。下面先推导递推公式：
设有三个元素A,B,C，如果用O代表（A,B,C）其中某个元素，那么使用=和&两个符号对 这三个元素进行排列的结果是：
总共四种(下面将这些排列叫做外部排列)，显然根据排列原理，对N个元素作这样的排 列，总共能得到2^(N-1)种，因为有N-1个中间位置。
根据题意，如果对这2^(N-1)种排列形式，分别计算出他们的内部排列数（剔除重复） ，累加这些内部排列数得到的结果就是答案。下面将沿着这条思路推出一个递推公式。
显然可以用x=1，y=2可以简单地表示出关系x&y；同样用x=1,y=1可以简单地表示出关系 x=y; 如果要表示x&=y=z这这样的关系，可以设定x=1,y=2,z=2。这样序关系可以转化为 数字的表示。
先考虑N比较小的几种情况(N=2,3,4):
在N=2时，可以得到的外部排列结果有两种：
如果用数字表示，对应为：
在N=3时，可以得到的外部排列结果有2^2种：
如果用数字表示，对应为：
在N=4时，可以得到的外部排列结果有2^3种：
如果用数字表示，对应为：
在N=4时，外部排列(1 1 2 2)对应的内部排列数可以这样来计算：
(1 1 2 2)可以看成是N=3的外部排列(1 1 2)的基础上附加了一个2。如果设(1 1 2)的 内部排列数为p,那么(1 1 2)的内部排列数为
p.(N/m)&&& ...........(公式1)
其中m为数字2在外部排列(1 1 2 2)中的重复数（这里等于2）。这个公式可以这样推出 :
N=3的外部排列(1 1 2)对应的内部排列数为(利用重排公式):
3!/(F.(m-1)!)，其中m-1等于(1 1 2)中2的重复次数。F为剩余的数字（这里只有1）的 重复次数阶乘的积。
这样N=4的外部排列(1 1 2 2)对应的内部排列数为:
4!/(F.m!)=3，其中m等于(1 1 2 2)中2的重复次数，即在N=3的重复次数基础上加1.
这个值=(3!*4)/(F.(m-1)!*m)=[3!/(F.(m-1)!)] * [4/m]，这里乘号前面就是上面得出 的N=3时内部排列数。
现在再次回到原题来，每次当N=n+1时，都可以看成是N=n的每个外部排列基础上附加一 个数字s和s+1，这里s等于N=n的相应外部排列最右边的数字。比如，当N=3的一个外部 排列为(1 1 2)时，在N=4时，会生成两个新的外部排列，分别为：
也就是说N=n+1情形下，它的外部排列数是N=n的外部排列数两倍，而且每个外部排列的 数字序列是递增的(虽然不是严格单调的)。（这也与上面结论相符：即共有2^(N-1)种 外部排列）
到此为止，先总结一下：我们的目的是计算内部排列总数，而N=n+1每个外部排列对应 的内部排列总数可以通过N=n的相应外部排列的内部排列总数得出，即p.(N/m)。
************************
在N=2时，对每个外部排列最右边数字统计一下它们出现的重复次数，并将重复次数按 顺序排序，可以得到下面的结果:
&&&&&&外部排列最右边数字重复次数统计=[1,2]
同样，在N=3时，可以得到下面的结果：
&&&&&&外部排列最右边数字重复次数统计=[1,1,2,3]
在N=4时，可以得到下面的结果：
&&&&&&外部排列最右边数字重复次数统计=[1,1,1,1,2,2,3,4]
例如N=4时的外部排列为：
其中第一个外部排列的最后一位为1,它的重复次数为4；第二个外部排列的最后一位为 2,它的重复次数为1；第三个外部排列的最后一位为2,它的重复次数为2.....等等。
根据上面的统计可以发现规律，当重复次数出现m时，在统计结果中出现的频次(即最右 边数字重复次数等于m对应的外部排列的总数)为2^(N-m-1) &
例如，N=4，m=1时出现的频次为4=2^(4-1-1)。当m=2时，出现的频次为2=2^(4-2-1)。 这个结论是由外部排序的生成规律造成的。
下面是一个比较重要的结论：
如果N=n的最右边数字重复次数等于m(m&1), 那么它在统计结果出现的频次等于： N=n -1中重复次数等于m-1出现的频次。但是当m=1，在N=n-1中重复次数m-1=0出现频次设为 它全排列的总数(原因见下面举例)。
看一下下面的例子就清楚了：
比如N=4时，重复次数等于m=1次（共4个外部排列），相当于在N=3的所有外部排列右边 添加s+1（设N=3对应的外部排列最右边数字为s）。即(上面结论中在N=3，m=0的情况) ：
(1 1 1) + (2) = (1 1 1 2)
(1 1 2) + (3) = (1 1 2 3)
(1 2 2) + (3) = (1 2 2 3)
(1 2 3) + (4) = (1 2 3 4)
重复次数等于m=2次（共2个外部排列），在N=3中只需要找出重复次数等于1(即m-1)的 外部排列，然后重复最右边的数字，就可以构造出N=4中的外部排列。即：
(1 1 2) + (2) = (1 1 2 2)
(1 2 3) + (3) = (1 2 3 3)
重复次数等于m=3次（共1个外部排列），在N=3中只需要找出重复次数等于2(即m-1)的 外部排列，然后重复最右边的数字，就可以构造出N=4中的外部排列。即：
(1 2 2) + (2) = (1 2 2 2)
重复次数等于m=4次（共1个外部排列），在N=3中只需要找出重复次数等于3(即m-1)的 外部排列，然后重复最右边的数字，就可以构造出N=4中的外部排列。即：
(1 1 1) + (1) = (1 1 1 1)
************************
接下来该轮到我们得出递推公式了：
设D(m,i)表示N=i时最右边数字重复次数等于m的所有外部排列对应的内部排列总数（注 意这里终于讨论到内部排列数了！）,那么有如下递推公式:
******************（公式2）******************
&&&&&&& i/m * D(m-1,i-1)&&&& (当m != 1, i&1)
&& &&&& [D(1,i-1) + D(2,i-1) + ... + D(i-1,i-1)] * i& (当m = 1，i&1)
满足1&=m&=i，初始条件：D(1,1) = 1。
*********************************************
下面讨论如何得出这个公式的：
还是拿简单的情况讨论，当i=4时,
外部排列最右边数字重复次数统计Q=[1,1,1,1,2,2,3,4]
当Q中值m等于2时，对应的i=3中的外部排列为(即重复次数为m-1=1的所有外部排列)：
(1 1 2) + (2) = (1 1 2 2)&&&&& .... (a)
(1 2 3) + (3) = (1 2 3 3)&&&&& .... (b)
即i=3时对应有两个外部排列。
记其中第一个外部排列(a)对应的内部排列数为P(1 1 2) ，那么根据上面(公式1) , P(1 1 2 2) = P(1 1 2) * i/m (i=4，m=2)。同样，第二个 外部排列的内部排列数：P(1 2 3 3)& = P(1 2 3) * i/m (i=4，m=2)。显然，这两个 内部排列计数中因子N/m是共用的，所以：
D(m,4) = P(1 1 2 2) + P(1 2 3 3)
&&&&&& = [P(1 1 2) + P(1 2 3)]& * i/m
&&&&&& = D(m-1,3) * i/m
依此类推。。。
但是这里还没有考虑当Q中值m等于1情况呢。
如果i=4，m=1，对应于i=3中的外部排列为(即重复次数为m-1=0的所有外部排列)：
(1 1 1) + (2) = (1 1 1 2)& .....(d)
(1 1 2) + (3) = (1 1 2 3)& .....(e)
(1 2 2) + (3) = (1 2 2 3)& .....(f)
(1 2 3) + (4) = (1 2 3 4)& .....(g)
即i=4,m=1时在i=3中对应它的所有外部排列。
记其中第一个外部排列(d)对应的内部排 列数为P(1 1 1)，那么根据上面(公式1) , P(1 1 1 2) = P(1 1 1) * i/m (i=4，m=1) 。同样，第二个外部排列的内部排列数：P(1 1 2 3)& = P(1 1 2) * i/m (i=4，m=1) 。第三个外部排列的内部排列数：P(1 2 2 3)& = P(1 2 2) * i/m (i=4，m=1)。第四 个外部排列的内部排列数：P(1 2 3 4)& = P(1 2 3) * i/m (i=4，m=1)。这四个内部 排列计数中因子N/m也是共用的，所以：
D(m,4) = P(1 1 1 2) + P(1 1 2 3) + P(1 2 2 3) + P(1 2 3 4)
&&&&&& = [P(1 1 1) + P(1 1 2) + P(1 2 2) + P(1 2 3)]& * i/m
&&&&&& = [D(1,3) + D(2,3) + D(3,3)] * i/m
&&&&&& = [D(1,3) + D(2,3) + D(3,3)] * i （因为m=1）
[注意，这里D(1,3) + D(2,3) + D(3,3)就是i=3的所有内部排列数。]
这样就验证了（公式2)
所以原题的序关系总数，即为所有内部排列的总数，等于：
Count = D(1,N) + D(2,N) + .... +& D(N,N)&& ...........(公式3)
注意到在(公式2)中i/m不要单独计算，如果除不尽, m可以通过D(m-1,i-1)约去。
这样，(公式2)和(公式3)就是我们编程实现中需要用到的公式，显然，用动态规划的做 法需要做两重循环，算法复杂度为O(n^2)。在具体实现中，考虑到N的范围为1-50，计 算结果会超出long integer范围，这里使用了BigInteger。
实现代码如下：
import java.math.BigI
import java.util.S
* @author ljs
* There are 13 possible orderings for three numbers, if we sort them with the relation '&' and '=':
* A = B = C , A = B & C , A & B = C ,A & B & C
* A & C & B , A = C & B , B & A = C ,B & A & C
* B & C & A , B = C & A , C & A = B ,C & A & B
* C & B & A
* Given an integer n, your task is to find the number of possible orderings for any n real numbers.
public class Main {
public static BigInteger solve(int n){
BigInteger[] D1 =
{new BigInteger(&1&),new BigInteger(&1&)};
for(int i=2;i&=n;i++){
BigInteger[] D2 = new BigInteger[i+1];
//D2[0] is not used
D2[1] = new BigInteger(&0&);
for(int j=1;j&D1.j++){
D2[1] = D2[1].add(D1[j]);
D2[1] = D2[1].multiply(new BigInteger(String.valueOf(i)));
for(int m=2;m&=i;m++){
BigInteger tmp = D1[m-1].multiply(new BigInteger(String.valueOf(i)));
D2[m] = tmp.divide(new BigInteger(String.valueOf(m)));
BigInteger count = new BigInteger(&0&);
for(int i=1;i&=n;i++){
count = count.add(D1[i]);
public static void main(String[] args) {
long start = System.currentTimeMillis();
int n = 50;
for(int i=1;i&=n;i++) {
BigInteger count = Main.solve(i);
System.out.format(&count(n=%d): %d%n&,i,count);
long end = System.currentTimeMillis();
double timeElapsed = (end-start)/1000.0;
System.out.format(&Time elapsed(sec): %.3f%n&, timeElapsed);
Scanner cin=new Scanner(System.in);
while(cin.hasNextInt()){
int n = cin.nextInt();
BigInteger count = Main.solve(n);
System.out.println(count);
测试结果：
count(n=1): 1
count(n=2): 3
count(n=3): 13
count(n=4): 75
count(n=5): 541
count(n=6): 4683
count(n=7): 47293
count(n=8): 545835
count(n=9): 7087261
count(n=10):
count(n=11):
count(n=12):
count(n=13):
count(n=14): 43
count(n=15): 853
count(n=16): 1355
count(n=17): 135901
count(n=18): 6845323
count(n=19):
count(n=20):
count(n=21):
count(n=22): 3
count(n=23): 13
count(n=24): 8875
count(n=25): 498141
count(n=26): 7539083
count(n=27):
count(n=28):
count(n=29):
count(n=30): 63
count(n=31): 973
count(n=32): 76395
count(n=33): 2589981
count(n=34):
count(n=35):
count(n=36):
count(n=37): 1
count(n=38): 723
count(n=39): 77533
count(n=40): 6591915
count(n=41):
count(n=42):
count(n=43):
count(n=44): 75
count(n=45): 5741
count(n=46): 73483
count(n=47): 3260093
count(n=48):
count(n=49):
count(n=50): 3
Time elapsed(sec): 0.528
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：309654次
积分：4063
积分：4063
排名：第5260名
原创：90篇
评论：103条
(1)(1)(2)(3)(8)(15)(19)(16)(25)(1)一道排列组合题的解法探讨--《数学通报》1997年07期
一道排列组合题的解法探讨
【摘要】：一道排列组合题的解法探讨李世信（湖北省钟祥师范学校４３１９００）贵刊刊载的《“插空法”应用系列》一文，读后深受启发?该文中有这样一道例题：有一楼梯共１０级，如果规定每次只能跨上一级或两级，要上第１０级，共有多少种不同走法？该文用“插空法”给出了解答，...
【作者单位】：
【关键词】：
【分类号】：G633.62【正文快照】：
一道排列组合题的解法探讨李世信（湖北省钟祥师范学校４３１９００）贵刊刊载的《“插空法”应用系列》一文，读后深受启发?该文中有这样一道例题：有一楼梯共１０级，如果规定每次只能跨上一级或两级，要上第１０级，共有多少种不同走法？该文用“插空法”给出了解答，这
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【相似文献】
中国期刊全文数据库
茅彭年;[J];宁夏大学学报(人文社会科学版);1981年01期
烟学敏;;[J];天津教育;1981年05期
;[J];中国远程教育;1982年02期
李孝堂;[J];齐齐哈尔大学学报(哲学社会科学版);1984年03期
张亮采;[J];东北师大学报(哲学社会科学版);1984年03期
杨泰良;;[J];数学教学通讯;1985年03期
马积祥;张连扬;;[J];数学教学通讯;1985年05期
刘励;;[J];现代远距离教育;1985年05期
朱定符;;[J];数学教学;1985年06期
彭年;[J];四川师范大学学报(社会科学版);1986年02期
中国重要报纸全文数据库
王玉池;[N];中国艺术报;2001年
中国人民大学博士生
傅郁林;[N];工人日报;2001年
王永胜;[N];云南日报;2001年
;[N];法制日报;2002年
本报记者 陈炳山;[N];新华日报;2002年
席斯;[N];财经时报;2003年
陈颐;[N];经济日报;2003年
裴圣毅;[N];中国档案报;2004年
肖理;[N];中国民族报;2004年
曾朝晖;[N];中国质量报;2004年
中国硕士学位论文全文数据库
刘凡镇;[D];郑州大学;2002年
李伟;[D];山西大学;2006年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 知识超市公司
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号一道排列组合的典型题!重点讲一下为何要除A33&
这是因为在分成4个小组的方法中,先出2个班去一个工厂实习,余下的已不需要再分了（就是每个班为一个组）.它这里因为3个组都是一个班,选 3、2、1与选[ 1、2、3]等,都是同样的分法（即每组1个班）,所以是算重了,故要除以重复数A（3,3）
为您推荐：
其他类似问题
扫描下载二维码}