GLORY | 学习·记录

coding for life

《算法竞赛入门经典》学习笔记-枚举

除法

输入正整数n,按从小到大的顺序输出所有形如 abcde/fghij=n的表达式,其中a~j恰好为数字0~9的一个排列,2<=n<=79。
样例输入:
62
样例输出:
79546/01283=62
94736/01528=62

如何解决这个问题?

2010-7-16更新
上面的问题让我一下子想到了如何求一个序列的全排列的问题,于是顺着这个思路摸索了一下。Google到了一个算法。

递归
例说明如何编写全排列的递归算法。
1、首先看最后两个数4, 5。 它们的全排列为4 5和5 4, 即以4开头的5的全排列和以5开头的4的全排列。由于一个数的全排列就是其本身,从而得到以上结果。
2、再看后三个数3, 4, 5。它们的全排列为3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六组数。
即以3开头的和4,5的全排列的组合、以4开头的和3,5的全排列的组合和以5开头的和3,4的全排列的组合.
从而可以推断,设一组数p = {r1, r2, r3, ... ,rn}, 全排列为perm(p),pn = p - {rn}。
因此perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), ... , rnperm(pn)。当n = 1时perm(p} = r1。
为了更容易理解,将整组数中的所有的数分别与第一个数交换,这样就总是在处理后n-1个数的全排列。

posted on 2010-07-15 22:02 meglory 阅读(525) 评论(0)  编辑 收藏 引用 所属分类: Algorithms


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

随笔分类

随笔档案

最新评论