再次優(yōu)化過的8皇后問題-創(chuàng)新互聯(lián)

其實(shí)我沒有做到記憶一些已經(jīng)判定過的狀態(tài)，增加trace來記憶已判定狀態(tài)，去掉重復(fù)判斷

#include <stdio.h>

#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<N; i++) printf("%d", q[i]);

    printf("
");

return;
}

int can_put(int m, int n) {
int i,j;

    sum++;

//row is ok
//colume  for (i=0; i<m; i++) {
if (q[i] == n) return 0;
    }

//left-up  for (i=m-1,j=n-1; i>=0 && j>=0; i--,j--) {
if (q[i] == j) return 0;
    }

//right-up  for (i=m-1,j=n+1; i>=0 && j<N; i--,j++) {
if (q[i] == j) return 0;
    }

return 1;
}

void next_qn() {
while (trace >= 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<N; trace++) {
if (!can_put(trace, q[trace])) break;
        }

if (trace == N) {
            cnt++;
//print_q();            trace--;
            next_qn(N-1);
        }else {
            next_qn();
        }
    }

    printf("CNT: %d, times: %d
", cnt, sum);

return 0;
}

再次執(zhí)行就好看多了

創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供余杭網(wǎng)站建設(shè)、余杭做網(wǎng)站、余杭網(wǎng)站設(shè)計、余杭網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計與制作、余杭企業(yè)網(wǎng)站模板建站服務(wù)，10年余杭做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價值的思路和整體網(wǎng)絡(luò)服務(wù)。

CNT: 352, times: 72378

real    0m0.007s
user    0m0.004s
sys    0m0.000s

我們可以看到判定次數(shù)已經(jīng)和遞歸一樣，也就是說已經(jīng)成功的用循環(huán)替代了遞歸，并且執(zhí)行的時間少了0.001s，這大概是省在來回搬棧上了。

N = 16，跑了12m，再大，估計我的機(jī)器跑不動了。不過這個算法的時間復(fù)雜度怎么算呢？

CNT: 14772512, times: 842815472

real    12m26.208s
user    12m25.835s
sys    0m0.028s

大概這是我的最終答案了，找時間去網(wǎng)上找找經(jīng)典問題的經(jīng)典解，或許能學(xué)到更有趣的事情。

文章標(biāo)題：再次優(yōu)化過的8皇后問題-創(chuàng)新互聯(lián)
URL鏈接：http://www.muchs.cn/article14/deosge.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站收錄、云服務(wù)器、網(wǎng)站設(shè)計、網(wǎng)站維護(hù)、企業(yè)網(wǎng)站制作、網(wǎng)頁設(shè)計公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)