排列(《算法竞赛入门经典》习题2-10)

本题(算法竞赛入门经典 第二章习题2-10)极水,我还写个解题报告,足以证明我有多弱菜了。

本题有多种做法,效率不一。下面介绍三种我使用的方法。
1、受本章开始的7744问题的启发,依次枚举abc,def,ghi,编写一个check()函数,用以判断这三个数是否把1~9的9个数字每个用了一遍,若是,则符合要求,输出。不幸的是,因为这样做不好判重(实际上也没有判重),用了5s左右才计算出所有四个解。舍弃之。
2、在网上搜索本题,发现真是有人把题目的最后一句(“提示:不必太动脑筋。”)理解得非常透彻,利用九重循环abcdefghi分别1~9,层层判重,最后一层判断是否合题目要求,是则输出。经我自己重新编写测试,出解大约需要0.85s。仔细阅读原程序后,发现有两个很好的优化:
(1)d可以直接从2a开始循环,g可以直接从3a开始循环,原因显而易见(a:b:c=1:2:3)。
(2)不必计算x=100a+10b+c,y=…,z=…然后判断xyz关系,直接用abcdefghi判断即可,这样可以节省大量时间。输出时用printf(“%d%d%d,%d%d%d,%d%d%d\n”,a,b,c,d,e,f,g,h,i);即可。
优化后,约0.15s出四解。

3、在网上偶然看到有人提出用回溯的思路,也为了复习一下回溯法,我编写了回溯的程序,大概是int visited[9],way[9]; trace(int step,int num);这样的。实验证明,这种方法出解的时间约为0.60s。有趣的是,可能是因为用了数组way[],此时判断1:2:3,计算出xyz再判断与直接用冗长的9个变量判断的效率竟然没有明显差别,都是0.60s。
其实这种题目贴代码的意义不大,但是如果读者确实需要,可以点此下载

Update 2012-10-3

今天又在网上看到了两个很好的解法。

1.设置数组a[1..9],枚举x(123~321),计算y=2x、z=3x,然后用这样一个东西:

a[x/100]=a[x/10]=a[x%10]=1分别用x、y、z三数的各位进行计算,根据“若三个数恰好用尽了9个数字,则必有a[0]+…+a[9]=9”可以判断出解,经测试,这个算法效率极高,在我的电脑上平均0.005s出解。

2.将检测方法改为:

分离每个数字的每个数位,计算这些数位的和与积,若和为45,积为362880(9!),则为正确解。

经测试,效率也很高,在我的电脑上平均0.008s出解。

看来即使是一个小题,也是有很大的研究价值的。

《排列(《算法竞赛入门经典》习题2-10)》有4个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注