全排列-按从大到小-time limited

时间:2021-10-15 22:59:27

  算法思想借鉴网络,代码自编。poj提交time limited,望各位后生不要再折腾这个算法了,wa就已经把它挂掉了!

  准备下一个用递归思想去解决全排列,希望时间可以低于1000ms。

  总结:写程序莫着急,心急吃不了热豆腐,算法一定是第一位!小算怡情,大算伤身,强算樯橹灰飞烟灭………………哈哈

  下次一定要分析好时间的可行性…………避免time limited。

 1 #include<stdio.h>
 2 #include<conio.h>
 3 #include<string.h>
 4 #include<iostream>
 5 using namespace std;
 6 #define N  6
 7 bool flag;
 8 int main(){
 9     char a[N];
10     gets(a);//获取排列
11     cout<<a<<endl;
12     int L=strlen(a);
13     while(1){//死循环,break
14         int m=0,n=0;//m:从数组左侧开始寻找,找到第一个比相邻右边小的元素
15             //m记录此元素下标;n:m下标右侧比a[m]大的元素中最小值
16         //计算m值
17         for(int i=L-2;i>=0;i--){
18             if(a[i]<a[i+1]){
19                 m=i;
20                 break;
21             }
22             else if(i==0)
23                 flag=true;
24         }
25         if(flag==true)
26             break;
27 
28         //计算n值
29         for(int i=m+1;i<=L-1;i++){
30             int max=127;
31             if(a[i]>a[m]&& a[i]<max){
32                 max=a[i];
33                 n=i;
34             }
35         }
36         
37         //swap
38         char t_2;
39         t_2=a[m];
40         a[m]=a[n];
41         a[n]=t_2;
42         
43         //倒叙m之后的排列
44         char t;//中间变量
45         int j=(L-m)/2;
46         for(int i=0;i<j;i++){
47             t=a[m+i+1];
48             a[m+i+1]=a[L-1-i];
49             a[L-1-i]=t;
50         }
51 
52         //产生下一个排列
53         cout<<a<<endl;
54     }
55     getch();
56     return 0;
57 }