Question

C++求排列组合，帮忙看看到底错在哪，怎么改？

//给定两个自然数n（1~9）和r（n>r），请编程输出从1~n中按降序排序取r个自然数的所有组合。如n=5,r=3时，输出结果为：543，542，541，532，531，432，431，421，321。（递归函数
#include<iostream>
#include<cstring>
using namespace std;
int C(int n,int k) //计算从n各种选k个的取法
{
int product=1;
for(int x=n;x>n-k;x--) product*=x;
for(int x=1;x<=k;x++) product/=x;
return product;
}
void combination(int n,int r,char *a[])
{
if(r==1)//r=1的情况
{
for(int i=0;i<n;i++) a[i][0]=n-i+'0';
}
else if(n==r)//n=r时，只有一种排列方式
{
a[0][0]=n+'0';
for(int i=1;i<n;i++)
//把n-1个只含一个字符（不计'\0'）的字符串拼起来
{
char *p=new char[1];
p[0]=n-i+'0';
strcat(a[0],p);
delete[] p;
}

}
else //一般情况，利用C(n,r)=C(n-1,r-1)（即第一个元素为n,再从1至n-1中挑r-1个）+C(n-1,r)（从1至n-1中挑r个）
{
//为此种情况做准备：C(n,r)=C(n-1,r-1)（即第一个元素为n,再从1至n-1中挑r-1个）

char **p=new char*[C(n-1,r-1)];
for(int i=0;i<C(n-1,r-1);i++) p[i]=new char[r-1];
//为此种情况做准备：C(n-1,r)（从1至n-1中挑r个）

char **q=new char*[C(n-1,r)];
for(int i=0;i<C(n-1,r);i++) q[i]=new char[r];

//第一种情况
combination(n-1,r-1,p);
for(int i=0;i<C(n-1,r-1);i++)
{
a[i][0]=n+'0';
a[i]=strcat(a[i],p[i]);
}
for(int i=0;i<C(n-1,r-1);i++) delete[] p[i];
delete[] p;
//第二种情况
combination(n-1,r,q);
for(int i=C(n-1,r-1);i<C(n,r);i++) strcpy(a[i],q[i]);
for(int i=0;i<C(n-1,r);i++) delete[] q[i];
delete[] q;
}
}
int main()
{
//输入
int n,r;
do
{
cout<<"请输入两个自然数n（1~9）和r（n>r），以编程输出从1~n中按降序排序取r个自然数的所有组合："<<endl;
cin>>n>>r;
}while(n<=r||r<1||n>9);

//处理
char **a=new char*[C(n,r)];
for(int i=0;i<C(n,r);i++) a[i]=new char[r];
combination(n,r,a);

//输出
cout<<"组合方式如下："<<endl;
for(int i=0;i<C(n,r);i++)
{
for(int j=0;j<r;j++) cout<<a[i][j];
cout<<"\t";
}

//善后
for(int i=0;i<C(n,r);i++) delete[] a[i];
delete[] a;
return 0;
}

Answer 1

主要有两个问题：
1.是字符串操作。每个字符串末尾都必须有个结束符\0，否则strcat()就将数组越界从而搞乱内存。另外分配内存时你也要多分配一个字节来存放结束符\0，改动的地方很多，你可以对照原来的程序看改了的地方。

2.在函数combination中倒数第4行
for(int i=C(n-1,r-1);i<C(n,r);i++) strcpy(a[i],q[i]);
应该改为
for(int i=C(n-1,r-1);i<C(n,r);i++) strcpy(a[i],q[i-C(n-1,r-1)]);

最后，我把你的例如for(int i=0.....)全改成for(i=0...),为的是我的编译器能通过。
以下为修改后的程序，编译调试通过，结果正确。
#include<iostream>
#include<cstring>
using namespace std;
int C(int n,int k) //计算从n各种选k个的取法
{
int x;
int product=1;
for(x=n;x>n-k;x--) product*=x;
for(x=1;x<=k;x++) product/=x;
return product;
}
void combination(int n,int r,char *a[])
{
int i;
if(r==1)//r=1的情况
{
for(i=0;i<n;i++) {a[i][0]=n-i+'0'; a[i][1]=0;}
}
else if(n==r)//n=r时，只有一种排列方式
{
a[0][0]=n+'0';a[0][1]=0;
for(i=1;i<n;i++)
//把n-1个只含一个字符（不计'\0'）的字符串拼起来
{
char pp[2];
pp[0]=n-i+'0';pp[1]=0;
strcat(a[0],pp);
}

}
else //一般情况，利用C(n,r)=C(n-1,r-1)（即第一个元素为n,再从1至n-1中挑r-1个）+C(n-1,r)（从1至n-1中挑r个）
{
//为此种情况做准备：C(n,r)=C(n-1,r-1)（即第一个元素为n,再从1至n-1中挑r-1个）

char **p=new char*[C(n-1,r-1)];
for(i=0;i<C(n-1,r-1);i++) {p[i]=new char[r];p[i][r-1]=0;}
//为此种情况做准备：C(n-1,r)（从1至n-1中挑r个）

char **q=new char*[C(n-1,r)];
for(i=0;i<C(n-1,r);i++) {q[i]=new char[r+1];q[i][r]=0;}

//第一种情况
combination(n-1,r-1,p);
for(i=0;i<C(n-1,r-1);i++)
{
a[i][0]=n+'0';a[i][1]=0;
a[i]=strcat(a[i],p[i]);
}
for(i=0;i<C(n-1,r-1);i++) delete[] p[i];
delete[] p;
//第二种情况
combination(n-1,r,q);
for(i=C(n-1,r-1);i<C(n,r);i++) strcpy(a[i],q[i-C(n-1,r-1)]);
for(i=0;i<C(n-1,r);i++) delete[] q[i];
delete[] q;
}
}
int main()
{
//输入
int i,n,r;
do
{
cout<<"请输入两个自然数n（1~9）和r（n>r），以编程输出从1~n中按降序排序取r个自然数的所有组合："<<endl;
cin>>n>>r;
}while(n<=r||r<1||n>9);

//处理
char **a=new char*[C(n,r)];
for(i=0;i<C(n,r);i++) {a[i]=new char[r+1];a[i][r]=0;}
combination(n,r,a);

//输出
cout<<"组合方式如下："<<endl;
for(i=0;i<C(n,r);i++)
{
for(int j=0;j<r;j++) cout<<a[i][j];
cout<<"\t";
}

//善后
for(i=0;i<C(n,r);i++) delete[] a[i];
delete[] a;
return 0;
}

Answer 2

递归太难看懂，还是用别的方法吧：
#include<iostream>
using namespace std;
int main()
{
int i, j, k,c = 0;
int *num, *bin;
int base, com;
bool flag = 1;

cout << "输入两个整数a，b(1~9, a>=b)：" << endl;
cin >> base >> com;

if(base == com)
{
for(i = 1; i <= base; i++)
cout << i;
cout << endl << "共有" << 1 << "种" << endl;;
return 0;
}

num = new int[base];
bin = new int[base];

for(i = 0; i < base; i++)
num[i] = i + 1;
for(i = 0; i < base - com; i++)
bin[i] = 0;
for(; i < base; i++)
bin[i] = 1;

while(1)
{
k = 0;
for(i = 0; i < base; i++)
{
if(bin[i])
k++;
}
if(k == com)
{
c++;
for(i = 0; i < base; i++)
{
if(bin[i])
cout << num[i];
}
cout << endl;
}
if(!flag)
break;
j = 1;
for(i = base - 1; i > -1; i--)
{
k = bin[i] + j;
bin[i] = k % 2;
j = k / 2;
}
for(i = 0; i < com; i++)
{
if(bin[i])
continue;
break;
}
if(i == com)
flag = 0;
}

cout << "共有" << c << "种" << endl;
delete []bin;
delete []num;
return 0;
}