算法思想借鉴网络,代码自编。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 }