你猜我有多动心 2016-11-30 05:05 采纳率: 100%
浏览 3441
已采纳

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;

}

这个代码会超时,想知道怎么才能优化?
这个代码有写错的地方吗?还是只是因为算法太低效才会超时?

  • 写回答

8条回答 默认 最新

  • zjck1995 2016-11-30 10:39
    关注
    #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;
    }
    
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(7条)

报告相同问题?

悬赏问题

  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)