程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 更多編程語言 >> 編程解疑 >> 優化-c語言字典序全排列高效算法(非遞歸)

優化-c語言字典序全排列高效算法(非遞歸)

編輯:編程解疑
c語言字典序全排列高效算法(非遞歸)

#include
void swap(int a[100],int j,int k)
{
int temp;
temp=a[j];
a[j]=a[k];
a[k]=temp;
}
void reverse(int a[100],int j,int n)
{ int i,y;
for(i=j+1,y=0;i {swap(a,i,n-y);}
}
void print(int a[100],int n)
{
int i;
for(i=1;i {
printf("%d ",a[i]);
}
printf("\n");
}
int fac(int n)
{
int anw;
if(n==1||n==0)
anw=1;
else
anw=n*fac(n-1);
return anw;
}
void fin(int a[100],int n)
{
int i,j,k;
for(i=n-1;i>=1;i--)
{
if(a[i]<a[i+1])
{j=i;break;}
}
for(i=0;i<n;i++)
{
if(a[j]<a[n-i])
{k=n-i;break;}
}
swap(a,j,k);
reverse(a,j,n);
print(a,n);
}
int main()
{
int i,n,m,y;
int a[100];
scanf("%d",&n);
for(i=1;i<=n;i++)
a[i]=i;
print(a,n);
for(m=1;m<=fac(n)-1;m++)
{fin(a,n);}

return 0;

}

這個代碼會超時,想知道怎麼才能優化?
這個代碼有寫錯的地方嗎?還是只是因為算法太低效才會超時?

最佳回答:


#include<stdio.h>
using namespace std;
const int N =105;
int n,m;
int a[N];
void out(){
    for(int i=1;i<=n;i++) printf("%d",a[i]);
    puts("");
}
void swap(int& a,int& b){
    int tmp = a;a=b;b=tmp;
}
void rev(int left,int right){
    while(left<=right){
        swap(a[left],a[right]);
        left++,right--;
    }
}
bool change(){
    int j=n-1;
    for(;j>=1;j--){
        if(a[j]<a[j+1]) break;
    }
    if(j<1) return false;
    int k=n;
    while(a[k]<a[j]) k--;
    swap(a[k],a[j]);
    rev(j+1,n);
    return true;
}
int main()
{
    while(scanf("%d",&n)==1){
        for(int i=1;i<=n;i++) a[i]=i;
        out();
        while(change()) out();
    }
    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved