首页 > ACM题库 > 九度OJ > 九度-1120-全排列[解题代码]
2013
12-12

九度-1120-全排列[解题代码]

题目来源:2008年北京大学图形实验室计算机研究生机试真题

题目描述:

给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。
我们假设对于小写字母有’a’ < ‘b’ < … < ‘y’ < ‘z’,而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入:

输入只有一行,是一个由不同的小写字母组成的字符串,已知字符串的长度在1到6之间。

输出:

输出这个字符串的所有排列方式,每行一个排列。要求字母序比较小的排列在前面。字母序如下定义:
已知S = s1s2…sk , T = t1t2…tk,则S < T 等价于,存在p (1 <= p <= k),使得
s1 = t1, s2 = t2, …, sp – 1 = tp – 1, sp < tp成立。

样例输入:
abc
样例输出:
abc
acb
bac
bca
cab
cba
提示:

每组样例输出结束后要再输出一个回车。


cpp 代码如下:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
 char str[7];
 while(scanf("%s", str) != EOF)
 {
  int len = strlen(str);
  do
  {
   printf("%s\n", str);
  }
  while(next_permutation(str, str + len));
  printf("\n");
 }
 return 0;
}
/**************************************************************
	Problem: 1120
	User: coder
	Language: C++
	Result: Accepted
	Time:330 ms
	Memory:1020 kb
****************************************************************/


  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;