#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;
}