主题:[讨论]一个关于排列组合的问题
各位大虾,我在编写C程序时遇到一个问题,我想对几组数进行排列组合,比如有三组数:
第一组:1,2,3,4,5,6,7,
第二组:11,12,13,14,15,16,17,
第三组:21,22,23,
现在我想从第一组中取出3个数,从第二组取出3个数,从第三组取出3个数,则第一组有35个结果,第二组有35个结果,第三组有1个结果,
然后再将每一组的各个组合和其它组的组合再组合起来,共计1225个组合结果,然后将这1225个组合结果保存到文件中。以下是我的C源程序,
但是总不能输出正确的结果,运行到后面就会出乱码,哪位好心人可否帮忙指教一下?在此先行谢过!
#include <stdio.h>
#include <stdlib.h>
fact(rr)
int rr;
{long f;
if (rr==0||rr==1) f=1;
else f=fact(rr-1)*rr;
return(f);
}
cnm(a,b)
int a,b;
{long c;
if (a<b) return(0);
else {c=fact(a)/fact(b)/fact(a-b);return(c);}
}
main()
{ int a[20],r,max_val,j;
static int seq[20]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18};
int nm[20],kk,tnm=1;
int fenduan,k,i,m,n,lp,mn;
int data[18][35];
int geshu[15],cc[15],ge[15];
int f[8][40][10];
int df[3276][10];
int wei[10],xuanshu;
FILE *fp;
/*输入分段数及每段的数据,并计出每段的数据个数wei[i]。*/
printf("Pls input duanshu :");
scanf("%d",&fenduan);
for(i=1; i <= fenduan; i++)
{j=1;k=1;
while (k!=0)
{printf("pls input shuju:");
scanf("%d",&data[i][j]);
if (data[i][j]==0) k=0; j=j+1;}
wei[i]=j-2;
}
/*输出每段的数据*/
for(i=1; i <= fenduan; i++)
{printf("Gong %3d ge shu.----",wei[i]);
printf("Di %d zhu shu: ",i);
for(j=1;j<=wei[i];j++)
printf("%3d, ",data[i][j]);
printf("\n");}
/*输入每段需要选出的个数geshu[i],并计出总共选出的个数xuanshu。*/
xuanshu=0;
for(i=1;i <= fenduan; i++)
{printf("Pls input Di %d zhu shuo xu ge shu:",i);
scanf("%d",&geshu[i]);
xuanshu=xuanshu+geshu[i];}
printf("Gong xuan chu %3d ge shu",xuanshu);
printf("\n");
/*取每一段的各种组合,并计出每段的组合数nm,各段组合数相乘为总组合数tnm*/
/*fp=fopen("c.txt","w");*/
for(kk=1; kk <= fenduan; kk++)
{n=wei[kk]; m=geshu[kk];nm[kk]=cnm(n,m); tnm=tnm*nm[kk];nm[0]=cnm(xuanshu, 7);printf("nm[0]= %d. ",nm[0]);/*奇怪的是这个nm[0]总是会等于-5,不知什么原因*/
for (i=0;i<m;i++)
a[i]=seq[i];
for (i=0; i<m; i++)
{f[kk][1][i+1]=data[kk][a[i]];printf("%3d, ",a[i]);}
for (k=1;k<nm[kk];k++)
{
max_val=seq[n-1];
r=m-1;
while(a[r]==max_val)
{
r-=1;
max_val-=1;
}
a[r]+=1;
for( j=r+1;j<m;j++)
a[j]=a[j-1]+1;
for (i=0; i<m; i++)
f[kk][k+1][i+1]=data[kk][a[i]];
}
for (i=1;i<=nm[kk];i++)
{printf("%3d: ",i);/*fprintf(fp,"%3d: ",i);*/
for (j=1;j<=m;j++)
{printf("%3d, ",f[kk][i][j]);fprintf(fp,"%3d, ",f[kk][i][j]);}
printf("\n");/*fprintf(fp,"\n");*/
}
}/*每段组合运行结束*/
/*各段合成总组合*/
for (i=1; i<=fenduan; i++) {cc[i]=1; ge[i]=0;}
for (i=1; i<fenduan; i++)
for (j=i+1; j<=fenduan; j++)
cc[i]=cc[i]*nm[j];
for (i=2; i<=fenduan; i++)
for (j=1; j<i; j++)
ge[i]=ge[i]+geshu[j];
geshu[0]=0;k=1;r=1;cc[0]=0;
for(i=1; i<=fenduan; i++)
{ lp=0;
en2: for (r=1; r<=nm[i]; r++)
for (kk=(cc[i]*(r-1+lp)+1); kk<=(cc[i]*(r+lp)); kk++)
{k=1;
for (j=(ge[i]+1); j<=(ge[i]+geshu[i]); j++)
{df[kk][j]=f[i][r][k];k=k+1; }
}
if (kk<tnm) {lp=lp+nm[i]; goto en2;}
}
/*排序*/
kk=1;
while (kk<=tnm)
{for (i=1; i<xuanshu; i++)
{k=i;
for (j=i+1; j<=xuanshu; j++)
if (df[kk][k]>df[kk][j])
k=j;
if (k!=i)
{r=df[kk][i]; df[kk][i]=df[kk][k]; df[kk][k]=r;}
}
kk++;
}
/*输出结果 */
fp=fopen("c.txt","w");
for (kk=1;kk<=tnm;kk++)
{printf("%6d: ",kk);fprintf(fp,"%6d: ",kk);
for (k=1;k<=xuanshu;k++)
{printf("%3d, ",df[kk][k]);fprintf(fp,"%3d",df[kk][k]);}
printf("\n");fprintf(fp,"\n");
}
fclose (fp);
}
[fly]来啊来啊[/fly]
第一组:1,2,3,4,5,6,7,
第二组:11,12,13,14,15,16,17,
第三组:21,22,23,
现在我想从第一组中取出3个数,从第二组取出3个数,从第三组取出3个数,则第一组有35个结果,第二组有35个结果,第三组有1个结果,
然后再将每一组的各个组合和其它组的组合再组合起来,共计1225个组合结果,然后将这1225个组合结果保存到文件中。以下是我的C源程序,
但是总不能输出正确的结果,运行到后面就会出乱码,哪位好心人可否帮忙指教一下?在此先行谢过!
#include <stdio.h>
#include <stdlib.h>
fact(rr)
int rr;
{long f;
if (rr==0||rr==1) f=1;
else f=fact(rr-1)*rr;
return(f);
}
cnm(a,b)
int a,b;
{long c;
if (a<b) return(0);
else {c=fact(a)/fact(b)/fact(a-b);return(c);}
}
main()
{ int a[20],r,max_val,j;
static int seq[20]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18};
int nm[20],kk,tnm=1;
int fenduan,k,i,m,n,lp,mn;
int data[18][35];
int geshu[15],cc[15],ge[15];
int f[8][40][10];
int df[3276][10];
int wei[10],xuanshu;
FILE *fp;
/*输入分段数及每段的数据,并计出每段的数据个数wei[i]。*/
printf("Pls input duanshu :");
scanf("%d",&fenduan);
for(i=1; i <= fenduan; i++)
{j=1;k=1;
while (k!=0)
{printf("pls input shuju:");
scanf("%d",&data[i][j]);
if (data[i][j]==0) k=0; j=j+1;}
wei[i]=j-2;
}
/*输出每段的数据*/
for(i=1; i <= fenduan; i++)
{printf("Gong %3d ge shu.----",wei[i]);
printf("Di %d zhu shu: ",i);
for(j=1;j<=wei[i];j++)
printf("%3d, ",data[i][j]);
printf("\n");}
/*输入每段需要选出的个数geshu[i],并计出总共选出的个数xuanshu。*/
xuanshu=0;
for(i=1;i <= fenduan; i++)
{printf("Pls input Di %d zhu shuo xu ge shu:",i);
scanf("%d",&geshu[i]);
xuanshu=xuanshu+geshu[i];}
printf("Gong xuan chu %3d ge shu",xuanshu);
printf("\n");
/*取每一段的各种组合,并计出每段的组合数nm,各段组合数相乘为总组合数tnm*/
/*fp=fopen("c.txt","w");*/
for(kk=1; kk <= fenduan; kk++)
{n=wei[kk]; m=geshu[kk];nm[kk]=cnm(n,m); tnm=tnm*nm[kk];nm[0]=cnm(xuanshu, 7);printf("nm[0]= %d. ",nm[0]);/*奇怪的是这个nm[0]总是会等于-5,不知什么原因*/
for (i=0;i<m;i++)
a[i]=seq[i];
for (i=0; i<m; i++)
{f[kk][1][i+1]=data[kk][a[i]];printf("%3d, ",a[i]);}
for (k=1;k<nm[kk];k++)
{
max_val=seq[n-1];
r=m-1;
while(a[r]==max_val)
{
r-=1;
max_val-=1;
}
a[r]+=1;
for( j=r+1;j<m;j++)
a[j]=a[j-1]+1;
for (i=0; i<m; i++)
f[kk][k+1][i+1]=data[kk][a[i]];
}
for (i=1;i<=nm[kk];i++)
{printf("%3d: ",i);/*fprintf(fp,"%3d: ",i);*/
for (j=1;j<=m;j++)
{printf("%3d, ",f[kk][i][j]);fprintf(fp,"%3d, ",f[kk][i][j]);}
printf("\n");/*fprintf(fp,"\n");*/
}
}/*每段组合运行结束*/
/*各段合成总组合*/
for (i=1; i<=fenduan; i++) {cc[i]=1; ge[i]=0;}
for (i=1; i<fenduan; i++)
for (j=i+1; j<=fenduan; j++)
cc[i]=cc[i]*nm[j];
for (i=2; i<=fenduan; i++)
for (j=1; j<i; j++)
ge[i]=ge[i]+geshu[j];
geshu[0]=0;k=1;r=1;cc[0]=0;
for(i=1; i<=fenduan; i++)
{ lp=0;
en2: for (r=1; r<=nm[i]; r++)
for (kk=(cc[i]*(r-1+lp)+1); kk<=(cc[i]*(r+lp)); kk++)
{k=1;
for (j=(ge[i]+1); j<=(ge[i]+geshu[i]); j++)
{df[kk][j]=f[i][r][k];k=k+1; }
}
if (kk<tnm) {lp=lp+nm[i]; goto en2;}
}
/*排序*/
kk=1;
while (kk<=tnm)
{for (i=1; i<xuanshu; i++)
{k=i;
for (j=i+1; j<=xuanshu; j++)
if (df[kk][k]>df[kk][j])
k=j;
if (k!=i)
{r=df[kk][i]; df[kk][i]=df[kk][k]; df[kk][k]=r;}
}
kk++;
}
/*输出结果 */
fp=fopen("c.txt","w");
for (kk=1;kk<=tnm;kk++)
{printf("%6d: ",kk);fprintf(fp,"%6d: ",kk);
for (k=1;k<=xuanshu;k++)
{printf("%3d, ",df[kk][k]);fprintf(fp,"%3d",df[kk][k]);}
printf("\n");fprintf(fp,"\n");
}
fclose (fp);
}
[fly]来啊来啊[/fly]