Re: [問題]神奇的200

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

1609死會寢 wrote:
> 是做出一個NP_hard的問題嗎？
> 最近剛學到NP，可應該還沒紮好根
> 可否請版上的強者幫忙？

如果你仔細去算複雜度, 光算 n! 本身就是 NP_hard (EXPTIME)
輸入 n 個 integer, 去排序, 輸出排序好的 n 個數, 是 O(n log n) 也就是在 P
但是輸入 n, 印出 1~n, 是在 EXPTIME

橘 向日葵 wrote:
> 其實200皇后應該就可以搞死一堆電腦了吧XD
> 類似這類目前只能以Back-tracking解題(而且sub-solution又沒重複)的問題
> 有一大票都是問題描述簡單
> 但是問題本身缺乏設計出快速求解的演算法的要素
> 所以目前存在於世界上的求正確解演算法都快不起來
> 遇到這類問題
> 頂多只能在Back-tracking的基礎上加些要素,減少搜尋解空間
> 不然就是用一些近似演算法在合理時間求得接近最佳解的解

n-queen problem 有兩種
一種是只要產生一組解, 這樣200就可以算
#include <iostream>
using namespace std;
int main(void)
{
        int N,c,i,j;
        cin >> N; c=N%12;
        if (N!=1 && N<=3) { cout << "none" << endl; return 0; }
        if (c==3 || c==9) for (i=2;i<=N;i+=2) cout << (i+2<=N?i+2:2) << " ";
        else for (i=2 ; i<=N ; i+=2) cout << i << " ";
        if (c==8) for (i=1,j=2;i<=N;i+=2,j=-j) cout << (i+j<=N?i+j:i) <<
" ";
        else if (c==2) {cout << "3 1 "; for (i=1;i<=N;i+=2) cout << i <<
" ";
                if (N>=5) cout << "5 "; }
        else if (c==3 || c==9) { for (i=5;i<=N;i+=2) cout << i << " ";
                if (N>=1) cout << "1 "; if (N>=3) cout << "3 "; }
        else for (i=1;i<=N;i+=2) cout << i << " ";
        cout << endl;
        return 0;
}

另外一種是要輸出所有解, 甚至也不用輸出所有解,
只要輸出有幾組解, 就夠頭大了...

- --
                                                PaulLiu(劉穎駿)
E-mail address:[e-mail]
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)
Comment: Using GnuPG with Debian - http://enigmail.mozdev.org

iD8DBQFDvlEyoQj7xTSiaUYRAsDFAJ9p3zUHccynWnQquzxyYti8xwQu5wCfd03M
QVx6N0DK7JXhwvXw0pCQ/CY=
=UKFZ
-----END PGP SIGNATURE-----