1~20个数字排列组合排成圈,求满足任意相邻2组数字和为质数,求解。
刚拿到这个题目起初我还以为此题无解,但既然有这样的题目,那就应该是有对应的方法的吧,遂写code测试之。
很明显的递归类型题目,呵呵,可能因为很久没写递归程序的缘故吧,从开始写到穷举完所有解前后竟然花费了我一个小时时间, 汗! 看来以后要多多做这方面的trainning了。
结果很令人大跌眼镜。 此题竟然有6309300个解, 穷解所有解并写到磁盘文件前后竟然花费了180sec,看来算法效率还是需要提升啊。
附上最后的10组解:
6309293: 1 18 19 12 17 20 11 8 15 16 13 10 7 6 5 14 9 4 3 2
6309294: 1 18 19 12 17 20 11 8 15 16 13 10 9 2 3 14 5 6 7 4
6309295: 1 18 19 12 17 20 11 8 15 16 13 10 9 2 5 14 3 4 7 6
6309296: 1 18 19 12 17 20 11 8 15 16 13 10 9 4 7 6 5 14 3 2
6309297: 1 18 19 12 17 20 11 8 15 16 13 10 9 14 3 2 5 6 7 4
6309298: 1 18 19 12 17 20 11 8 15 16 13 10 9 14 3 4 7 6 5 2
6309299: 1 18 19 12 17 20 11 8 15 16 13 10 9 14 5 2 3 4 7 6
6309300: 1 18 19 12 17 20 11 8 15 16 13 10 9 14 5 6 7 4 3 2
Total find result:
6309300 (总共的解的个数)
附上我写的测试源代码:
源代码解压缩密码是 hello