如何用程序实现排列组合?
如何用程序实现排列组合?如:从一组数字1,2,3,4,...中抽出n(n=1,2,3,..)个不同的数,列出所有的组合. 问题点数：20、回复次数：8Top
1 楼xzjxu（糊涂神仙）回复于 2001-01-26 02:11:00 得分 0
穷举Top
2 楼baitianshi1981（oоО北天石）回复于 2001-01-26 10:29:00 得分 0
递归应该是最简单的解决方法Top
3 楼baitianshi1981（oоО北天石）回复于 2001-01-26 10:41:00 得分 0
递归应该是最简单的解决方法。Top
4 楼hyqryq（不知道叫什么好）回复于 2001-01-26 11:36:00 得分 0
基本办法是回朔。
用递推实现。Top
5 楼baitianshi1981（oоО北天石）回复于 2001-01-26 11:45:00 得分 0
对了，你还记得归纳法证明吧，呵呵。Top
6 楼rsh（rsh）回复于 2001-01-28 00:53:00 得分 0
有没有具体的程序？Top
7 楼zhangning111（比傻子还笨）回复于 2001-01-28 18:36:00 得分 20
从N个数中任取M个数的组合(M<=N)
为方便起见，我们把它记为c(N,M)。
容易想到，
c(N,1)
for(i=1;i<=N;i++)cout<<i<<endl;
c(N,2)
for(i=1;i<=N-1;i++)
for(j=i+1;j<=N;j++)
cout<<i<<"-"<<j<<endl;
c(N,2)可以理解为。组合包含1 再加上2~N个数中任取一个数
组合不包含1包含2 再加上3~N个数中任取一个数
组合不包含1，2包含3 再加上4~N个数中任取一个数
依此类推。
c(N,3)
for(i=1;i<=N-2:i++)
for(j=i+1;j<=N-1;j++)
for(k=j+1;k<=N;k++)
cout<<i<<"-"<<j<<"-"<<k<<endl;
c(N,3)可以理解为。组合包含1 再加上2~N个数中任取两个数
组合不包含1包含2 再加上3~N个数中任取两个数
组合不包含1，2包含3 再加上4~N个数中任取两个数
依此类推。
由此可归纳出c(N,M)
用num[1..M]存储M个数
num[s]
1 num[1]=i=1 to N-M+1
2 num[2]=j=i+1 to N-M+2
3 num[3]=k=j+1 to N-M+3
.
. num[s]=num[s-1]+1 to N-M+s
M
得,当s=1 num[1]=1 to N-M+s
当s>1 num[2]=num[s-1]+1 to N-M+s
#include <iostream.h>
#include <conio.h>
void main(void)
{
const int N=7,M=3;//从N个数中任取M个数的组合（M<N
int num[M+1],s,i;
num[1]=0;s=1;
while(s!=0)
{
if(s!=M)//取小于M个数
{
num[s]++;
if(num[s]>N-M+s)
s--;//回朔
else
{
s++;
num[s]=num[s-1];
}
}
else//取第M个数
{
num[s]++;
for(i=1;i<M;i++)cout<<num[i]<<"-";//输出
cout<<num[M];
cout<<endl;
if(num[s]==N-M+s)s--;//回朔
}
}
getch();
}
Top
8 楼rsh（rsh）回复于 2001-01-29 21:58:00 得分 0
thank you!Top
