Posted on 2009-03-08 11:35
杜仲当归 阅读(351)
评论(0) 编辑 收藏 引用
一道相当BT的搜索题,写了300+行数。更BT的是前前后后写了五六遍,几种搜索策略都离通过最后两个点差之毫厘,最终还是加了剪枝才过的。一道题写了1K行以上的代码量,也算是罕古未见了!
此题首先要明确搜索顺序。限制条件最多的是第五行和第五列,然后对角线也可以控制较多行列,之后是第一行和第一列,最后减法得到剩下四个数,判断即可。
但是这样仍然过不了23 7这样的数据。于是加入剪枝:在搜索完第五行第五列的同时,发现有四行已经填上了三个数,且都是X3X77这样的排列。因此可以预先建立表,判断出第2,4,5位已知的数是否可能为质数,不满足者剪枝。
在搜索每一行列的时候注意已填入的信息,为此要建立已知第1位,第3位,第5位的质数表。