void degr(int p[],int n)
{
int i,j;
while(1)
{
outp(p,n);
if(p[1]!=n)
{
i=0;
while(p[++i]!=n);
swap(p[i],p[i-1]);
}
else
{
i=1;
while(i<n)
{
if(p[i]!=p[i+1]+1) break;
i+=1;
}
if(i==n)break;
j=i;
while(p[i]!=p[j]-1)
i+=1;
swap(p[i],p[i-1]);
for(i=1;i<=n-j;)
p[i++]=p[i+j];
for (i=1;i<=j;i++)
p[n-i+1] =n-i+1;
}
}
}
void conv(int p[],int n)
{
long m=1;
for(int i=3;i<n;)
m=m*i++;
for(int i=1;i<m;i++)
{
outp(p,n);
for(int j=n;j>1;j--)
{
swap(p[j],p[j-1]);
outp(p,n);
}
swap(p[n],p[n-1]);
outp(p,n);
for(int j=1;j<n;j++)
{
swap(p[j],p[j+1]);
outp(p,n);
}
swap(p[1],p[2]);
}
}
bool test(int p[], int n)
{
bool b=false;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(p[i]==p[j])
{
b=true;
break;
}
return b;
}
void Nnum(int p[],int n)
{
while(n>0)
{
if (test(p,n)==false) outp(p,n);
p[n]+=n-1;
for(int j=n;j>1;j--)
{
if(p[j]>n)
{
p[j]%=n;
p[j-1]+=1;
if(p[1]>n)
{
n=0;
break;
}
}
}
}
}
void recu(int p[],int n,int k)
{
if(k==n)
outp (p,n);
else
{
for(int i=k;i<=n;i++)
{
swap (p[k],p[i]);
recu(p, n,k+1);
swap (p[k],p[i]);
}
}
}
void cyc(int p[],int n,int k)
{
if (k>n)
outp(p,n);
else
{
for(int i=0;i<k;i++)
{
int t=p[1];
for(int j=2;j<=k;j++)
p[j-1]=p[j];
p[k]=t;
cyc(p,n,k+1);
}
}
}
void remo(int p[],int n,int k)
{
bool b;
if (k>n)
outp (p,n);
else
{
for(int i=1;i<=n;i++)
{
b=false;
p[k]=i;
for(int j=1;j<k;j++)
if(i==p[j])
{
b=true;
break;
}
if(b==false) remo(p,n,k+1);
}
}
}
int main()
{
int i,j,m;
int p[maxn];
int n;
clock_t start,finish;
cout<<"输入排列元素总数n=";
cin>>n;
for(i=1;i<=n;i++)
p[i]=i;
cout<<"1——字典序法"<<endl;
cout<<"2——递增进位数制法"<<endl;
cout<<"3——递减进位数制法"<<endl;
cout<<"4——邻位交换法"<<endl;
cout<<"5——n进制数法"<<endl;
cout<<"6——递归生成法"<<endl;
cout<<"7——循环移位法"<<endl;
cout<<"8——回溯法"<<endl;
cout<<"请选择: ";
cin>>m;
start=clock();
switch (m)
{
case 1:dict(p,n);break;
case 2:incr(p,n);break;
case 3:degr(p,n);break;
case 4:conv(p,n);break;
case 5:Nnum(p,n);break;
case 6:recu(p,n,1);break;
case 7:cyc(p,n,1);break;
case 8:remo(p,n,1);
}
finish=clock();
cout<<"程序执行时间："
<<(double)(finish-start)/CLOCKS_PER_SEC<<"秒"<<endl;
system("pause");
return 0;
}
不知道大家有没有听说,明年起程序员考试就不分初,中,高级了,而我们软件专业明年就要过程序了,据说相当于考中程,或者还要难一些,虽然不知道消息的正确性,但这的确是我们的老师告诉我们的,所以老师就出一些题给我们练,下面是一道关于数学中全排列的算法的问题,编了我4天!真是的看起来容易,编起来难..........下面给出我的源代码,并给大家解释思路:
view plaincopy to clipboardprint?
#include "stdio.h"
void chang(char str[],int m) /*定义循环左移函数(我没有用左移函数)*/
{
int i,j;
char temp=str[0];
for (i=0;i<m;i++) str[i]=str[i+1];
str[i]=temp;
}
void pai(char str[],int m,int n) /*定义全排列函数*/
{
int k;
void chang(char str[],int m);
if (m<n) /* 定 义 递 归 调 用 出 口 */
{
for (k=0;k<=m;k++)
{
pai(str,m+1,n); /*递归调用*/
chang(str,m); /*调用左移函数*/
}
}
else printf("%s\t",str);
}
main()
{
char str[]="ABCD"; /*全排列字符,可以任意多个(相应的下面排列函数中参数"4"改成全排列字符的个数)*/
clrscr();
pai(str,0,4); /*这里参数0(下标)表示从第一个元素开始,4表示元素个数(不是下标)*/
getch();
}
#include "stdio.h"
void chang(char str[],int m) /*定义循环左移函数(我没有用左移函数)*/
{
int i,j;
char temp=str[0];
for (i=0;i<m;i++) str[i]=str[i+1];
str[i]=temp;
}
void pai(char str[],int m,int n) /*定义全排列函数*/
{
int k;
void chang(char str[],int m);
if (m<n) /* 定 义 递 归 调 用 出 口 */
{
for (k=0;k<=m;k++)
{
pai(str,m+1,n); /*递归调用*/
chang(str,m); /*调用左移函数*/
}
}
else printf("%s\t",str);
}
main()
{
char str[]="ABCD"; /*全排列字符,可以任意多个(相应的下面排列函数中参数"4"改成全排列字符的个数)*/
clrscr();
pai(str,0,4); /*这里参数0(下标)表示从第一个元素开始,4表示元素个数(不是下标)*/
getch();
}
大家看到了,以上就是一步一步循环左移就能得到所有全排列的数了.以上程序在Trubo C 2.0 中运行通过,如果大家还有什么疑问,请加我QQ:156301529,Email:rodgersnow@163.com,我们共同讨论.另外,我在想,如果是n个数或字符中取m个进行排列的话,该怎么改呢?
view plaincopy to clipboardprint?
char t;
if (m<n-1) {
permutation(a, m+1, n);
for (i=m+1;i<n;i++) {
t=a[m]; a[m]=a[i]; a[i]=t;
permutation(a, m+1, n);
t=a[m]; a[m]=a[i]; a[i]=t;
}
} else
{
printf("%s\n", a);
}
}
int main() {
char a[]="ABCDE";
permutation(a, 0,5);
return 0;
}
责任编辑：小草
您现在的位置： 