蓝桥杯——排列序数

蓝桥杯——排列序数

标题：排列序数   如果用a b c d这4个字母组成一个串，有4!=24种，如果把它们排个序，每个串都对应一个序号：  abcd  0  abdc  1  acbd  2  acdb  3  adbc  4  adcb  5  bacd  6  badc  7  bcad  8  bcda  9  bdac  10  bdca  11  cabd  12  cadb  13  cbad  14  cbda  15  cdab  16  cdba  17  ...    现在有不多于10个两两不同的小写字母，给出它们组成的串，你能求出该串在所有排列中的序号吗？【输入格式】一行，一个串。【输出格式】一行，一个整数，表示该串在其字母所有排列生成的串中的序号。注意：最小的序号是0。例如：输入：bdca程序应该输出：11再例如：输入：cedab程序应该输出：70资源约定：峰值内存消耗 < 256MCPU消耗  < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意: main函数需要返回0注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

分析：将输入的字符串进行全排列，按字典序进行排序编号并存在string型数组中，然后遍历string数组，相同则输出该数组的下标即可。

代码：

#include #include #include #include char ch[15];using namespace std;int f(int x)//求阶乘{ if(x==1) return 1; return f(x-1)*x;}string a[3700000];//10的阶乘为3628800int main(){ cin>>ch; string q=(string)ch; int len=strlen(ch); int maxx=f(len);//最大编号//cout<

样例数据：

边界数据：

思路二：只需要遍历字符串中的每一个字符，然后找出每个字符后面有多少个比它小的，也就是逆序的，然后乘以后面字符个数的阶乘，每一步的结果相加即可。

#include#includeusing namespace std;int a[20];int main(){ a[1]=1; for(int i=2;i<13;i++) { a[i]=a[i-1]*i; } char str[15]; cin>>str; int len=strlen(str),index=0,num; for(int i=0;i

第二种解法更好一点。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。