博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
由火车进站引出的问题
阅读量:5815 次
发布时间:2019-06-18

本文共 3355 字,大约阅读时间需要 11 分钟。

1,2,3,4,5列火车进站出站,有哪些组合方式?对于进出站的方式与数据结构中的栈相同。如果
有n 列火车通过调度站,请设计一个算法,输出所有可能的调度结果。 
 

解题思路:栈具有先进后出、后进先出的特点,因此,任何一个调度结果应该是1 ,2 ,3 ,4全排列中的一个元素。由于进栈的顺序是由小到大的,所以出栈序列应该满足以下条件:对于序列中的任何一个数其后面所有比它小的数应该是倒序的。据此,本题可以通过算法产生n 个数的全排列,然后将满足出栈规则的序列输出。

那么第一个问题就是对火车出战可能顺序的全排列:

对于一个系列的全排列有一下几种方法:

number 1:

借助于STL库中的next_permutation函数。next_permutation的作用就是计算全排列。

next_permutation(str,str+strlen(str))是一个求str数组元素的下一个排列的函数。如果要走遍所有的排列数组元素必须已经有小到大有序!还有一个prev_permutation,要求由大到小有序。

  1. #include <iostream>  
  2. #include <algorithm>  
  3. using namespace std;  
  4. int array[] = {1, 2, 3, 4};  
  5. const int iArraySize = sizeof(array)/sizeof(int);  
  6. int main()
  7. {  
  8.     int iCnt = 0;  
  9.     cout << iArraySize << endl;  
  10.     sort(array, array + iArraySize);  //这里就是要求数组元素有小到大有序
  11.     do  
  12.     {  
  13.         for(int i = 0; i < iArraySize; i++)  
  14.         {  
  15.             cout << array[i];   
  16.         }  
  17.         cout << " ";  
  18.         iCnt++;  
  19.     } while (next_permutation(array, array + iArraySize));  
  20.       
  21.     cout << endl;  
  22.     cout << "Total number: " << iCnt << endl;  
  23.     return 0;  
  24. }  

number2:

不用STL函数,利用递归思想进行排列

  1. #include <iostream>  
  2. #include <vector>  
  3. #include <string>  
  4. using namespace std;  
  5. int array[] = {1, 2, 3, 4};  
  6. const int iArraySize = sizeof(array)/sizeof(int);  
  7. //删除str的第n个字符  
  8. void DeleteCharAt(string& str, int n)  
  9. {  
  10.     if (n < 0 || n >= str.length())  
  11.     {  
  12.         return;  
  13.     }  
  14.     string tmpStr(str.substr(n + 1));  
  15.     str = str.substr(0, n) + tmpStr;  
  16. }  
  17. //base 以该字符串作为基础字符串,进行选择性组合。   
  18. //buff 所求字符串的临时结果   
  19. //result 存放所求结果   
  20. void ListAll(string& strBase, string strBuff, vector<string>& result)  
  21. {  
  22.     if (strBase.length() <= 0)  
  23.     {  
  24.         result.push_back(strBuff);  
  25.     }  
  26.     for(int i = 0; i < strBase.length(); i++)  
  27.     {  
  28.         string tmp(strBase);  
  29.         DeleteCharAt(tmp, i);  
  30.         ListAll(tmp, strBuff + strBase[i], result);    
  31.     }  
  32. }  
  33. int main(){  
  34.     int iCnt = 0;  
  35.     string str = "1324";  
  36.     vector<string> vResult;  
  37.     ListAll(str, "", vResult);  
  38.     //Output the result  
  39.     for (int i = 0; i < vResult.size(); ++i)  
  40.     {  
  41.         cout << vResult[i] << " ";  
  42.     }  
  43.     cout << "/n";  
  44.     cout << "Total number: " << vResult.size() << endl;  
  45.     return 0;  
  46. }  
第二个问题就是判断排列组合能不能按栈的方式实现:

  1.     int i,j,k,l,m,flag=1,b[2];   
  2.     for(i=0;i<n;i++)    /* 对每个str[i] 判断其后比它小的数是否为降序序列*/   
  3.     {  
  4.         m=0;   
  5.         for(j=i+1;j<n&&flag;j++)
  6. {   
  7.             if (str[i]>str[j])  
  8.             {  
  9.                 if (m==0) b[m++]=str[j];//记录str[i]后比它小的数   
  10.                 else   
  11.                 {  
  12.                     //如果之后出现的数比记录的数还大,改变标记变量   
  13.                     if (str[j]>b[0]) flag=0;  
  14.                     //否则记录这个更小的数   
  15.                     else b[0]=str[j];   
  16.                 }   
  17.             }  
  18.         }   
  19.     }   

最后就可以输出满足条件的组合了。

非递归方法求全排列:

1、算法简述

要考虑全排列的非递归实现,先来考虑如何计算字符串的下一个排列。如"1234"的下一个排列就是"1243"。只要对字符串反复求出下一个排列,全排列的也就迎刃而解了。

如何计算字符串的下一个排列了?来考虑"926520"这个字符串,我们从后向前找第一双相邻的递增数字,"20"、"52"都是非递增的,"26 "即满足要求,称前一个数字2为替换数,替换数的下标称为替换点,再从后面找一个比替换数大的最小数(这个数必然存在),0、2都不行,5可以,将5和2交换得到"956220",然后再将替换点后的字符串"6220"颠倒即得到"950226"。

如果达到这个数的最大,比如1234-à4321,这个时候就结束整个循环。

如果输入是一个非最小数,如1324,则将它转换为最小数,如1234,再进行排序。排序算法用快排,可以自己写一个,如果快排不会的话,就先看会再来接着看,或者自己想一个靠谱的算法,也可以直接用VC库中的qsort(s , n , sizeof(s[0]) , cmp);各参数是什么意思就自己在下面多花点时间吧。

OK,下面看代码分析

2、代码分析

1 Prem( char *s )   //全排列函数 2 { 3     char *pEnd = s + strlen(s) - 1; 4     char *p = pEnd;  //p代表替换点 5     //q代表替换点的下一个数 ,pMax 代表替换点后比替换点大的最小数 6     char *q = new char,*pMax = new char;  //注意初始化!!! 7     while (p !=  s)          //p == s 就结束循环 8     { 9         q = p;10         p--;11         if (*p < *q)12         {13             pMax = FindMaxForOne(p,pEnd);  //找与替换点交换的点14             Swap(p,pMax);         //交换15             Reverse(q,pEnd);       //将替换点后所有数进行反转16             Print(s);              //输出17             p = pEnd;             //将替换点置最后一个点,开始下一轮循环18         }19         if (s == p) break;           //结束条件20     }21 }

转载于:https://www.cnblogs.com/fangyan5218/p/10618265.html

你可能感兴趣的文章
Spark之SQL解析(源码阅读十)
查看>>
Android图片添加水印图片并把图片保存到文件存储
查看>>
比特币系统采用的公钥密码学方案和ECDSA签名算法介绍——第二部分:代码实现(C语言)...
查看>>
海贼王十大悲催人物
查看>>
BigDecimal 舍入模式(Rounding mode)介绍
查看>>
开源 免费 java CMS - FreeCMS1.2-标签 infoSign
查看>>
开源 免费 java CMS - FreeCMS1.9 移动APP生成栏目列表数据
查看>>
git reset 三种用法总结
查看>>
虚拟机新增加硬盘,不用重启读到新加的硬盘
查看>>
Java IO流详尽解析
查看>>
邮件服务系列之四基于虚拟用户的虚拟域的邮件系统(安装courier-authlib以及部分配置方法)...
查看>>
Linux VSFTP服务器
查看>>
DHCP中继数据包互联网周游记
查看>>
Squid 反向代理服务器配置
查看>>
Java I/O操作
查看>>
Tomcat性能调优
查看>>
项目管理心得
查看>>
Android自学--一篇文章基本掌握所有的常用View组件
查看>>
灰度图像和彩色图像
查看>>
通过vb.net 和NPOI实现对excel的读操作
查看>>