再次优化过的8皇后问题-创新互联
其实我没有做到记忆一些已经判定过的状态,增加trace来记忆已判定状态,去掉重复判断
网页题目:再次优化过的8皇后问题-创新互联
新闻来源:http://pwwzsj.com/article/deosge.html
#include
#define N 9
int q[N] = {0};
int not_end = 1;
int trace = 0;
int cnt = 0;
int sum = 0;
void print_q() {
int i;
for (i=0; i=0 && j>=0; i--,j--) {
if (q[i] == j) return 0;
}
//right-up for (i=m-1,j=n+1; i>=0 && j= 0) {
if (q[trace] < N-1) {
q[trace]+=1;
break;
}
q[trace]= 0;
trace--;
}
if ( trace < 0) {
not_end= 0;
}else {
int i = trace + 1;
while (i < N) {
q[i]= 0;
i++;
}
}
return;
}
int main(int argc, char* argv[]) {
while (not_end) {
int i;
for (trace; trace
再次执行就好看多了
创新互联专业为企业提供余杭网站建设、余杭做网站、余杭网站设计、余杭网站制作等企业网站建设、网页设计与制作、余杭企业网站模板建站服务,10年余杭做网站经验,不只是建网站,更提供有价值的思路和整体网络服务。CNT: 352, times: 72378
real 0m0.007s
user 0m0.004s
sys 0m0.000s
我们可以看到判定次数已经和递归一样,也就是说已经成功的用循环替代了递归,并且执行的时间少了0.001s,这大概是省在来回搬栈上了。
N = 16,跑了12m,再大,估计我的机器跑不动了。不过这个算法的时间复杂度怎么算呢?
CNT: 14772512, times: 842815472
real 12m26.208s
user 12m25.835s
sys 0m0.028s
大概这是我的最终答案了,找时间去网上找找经典问题的经典解,或许能学到更有趣的事情。
网页题目:再次优化过的8皇后问题-创新互联
新闻来源:http://pwwzsj.com/article/deosge.html