|
资源限制
时间限制：1.0s ? 内存限制：256.0MB
如果用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
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
其实这道题第一眼看过去以为是字典排序，其实认真观察一下就可以看出是字母的全排列，那么能想到这，这道题就简单多了，只不过还要注意一些小细节啦~~
#include<stdio.h>
#include<string.h>
char str[20],str1[20],a[25]; //用str来记录本身需要输入的字符串，str1用来全排列判断啥时候可以排列到str,数组a用来存字符串数组abcd...//
int b[25],length,flag=0; //b用来全排列时回溯用，length记录字符串的长度，flag记录目标字符串出现的位置//
void dfs(int step)
{
if(step==length)
{
if(strcmp(str,str1)==0) //比较当前全排列的字符串和目标字符串是否相等//
{
printf("%d",flag);
}
flag++; //不相等就+1，题目是从0开始记录的，所以在这里咱们也从0开始记录//
return;
}
for(int i=0; i<length; i++)
{
if(b[i]==1) //这里就是正常的全排列过程//
{
b[i]=0;
str1[step]=a[i];
dfs(step+1);
b[i]=1;
}
}
return;
}
int main()
{
gets(str); //用gets输入该字符串是为了不讲回车换行符合输入进去，以免判断的时候比较麻烦//
length=strlen(str);
for(int i=0; i<length; i++)
{
a[i]='a'+i; //将a和b进行初始化//
b[i]=1;
}
dfs(0);
return 0;
}
|