排列(《算法竞赛入门经典》习题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出四解。
继续阅读“排列(《算法竞赛入门经典》习题2-10)”