Robert Anderson's Blog

7月 14 週二 200910:18
USACO Name That Number

暴力找所有解

http://nopaste.csie.org/c8f62

(繼續閱讀...)

robertanders 發表在痞客邦留言(0) 人氣(34)

個人分類：USACO

▲top

7月 14 週二 200910:07
程式設計 - N皇后基礎程式碼

轉貼我自己 2008.6.27的文章

這次又更快了，這是從大陸那邊找來的，後來終於想通他們的原理了
他們用的是位元運算，非常快，而我將他們程式碼改了些，因為他們行跟列與我們相反
而且他們所謂的對稱性，似乎無法紀錄解答，這支程式原本也只能算出有幾組解答，目前這支基本程式是紀錄目前解答狀況，若需要記錄解答則另外建立陣列，否則刪除那段就行了
利用這些程式碼，個人成功解答了Another N Queen
#include <cstdlib>
#include <cstdio>
#define MAX 16

long sum = 0, upperlim = 1;
long now[MAX];

int test(long, long, long, int);

int main(int argc, char *argv[])
{
   int n = 16;

   scanf("%d", &n);

   upperlim = (upperlim << n) - 1;

   test(0, 0, 0, 0);
   printf("CASE %d: %ld combinations.\n", n, sum);

   system("PAUSE");
   return 0;
}

int test(long col, long ld, long rd, int row)
{
   if (col != upperlim)
   {
     long pos = upperlim & ~(col | ld | rd);
     while (pos)
     {
        long p = pos & -pos;

        pos -= p;

        now[row]=p;

        test(col + p, (ld + p) << 1, (rd + p) >> 1, row+1);
       }
   }
   else
   {

       sum++;
   }
}

(繼續閱讀...)

robertanders 發表在痞客邦留言(0) 人氣(252)

個人分類：程式設計

▲top

7月 14 週二 200910:05
程式設計 - 位元運算

轉貼我自己2008 8/6的文章

今天自己寫了一次N皇后的回溯程式，結果發現位元運算有些地方並不如我想像一般，所以今天把所有地方重新做一次整理，其中包括我之前就知道的

關於!與~

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
    int a=1;

    printf("%d %d\n", !a, ~a);

    system("PAUSE");

    return EXIT_SUCCESS;
}

本段程式碼輸出結果: 0 -2

下列以1Byte舉例

因為00000001

每位數取相反為11111110，正好為二的捕數法的-2

而!呢，只是取Boolean值的相反，跟位元運算無關

改成這樣

a=5;

printf("%d %d\n", !a, ~a);

將會輸出0 -6，即可證明

另外 || 、 | 與 &&、&之間的關係類似

|、&是針對每一個數字位元去做運算，而||、&&皆是布林值運算

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
    int a=3, b=2;

    printf("%d %d\n", a&&b, a||b);


    system("PAUSE");

    return EXIT_SUCCESS;
}

輸出結果 1 1

分解動作→3為true 2為true，則AND之後→true

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
    int a=3, b=2;

    printf("%d %d\n", a&b, a|b);


    system("PAUSE");

    return EXIT_SUCCESS;
}

如果是這樣的話，輸出結果 2 3

看成二進位制的運算
11 & 10 = 10 ； 11 | 10 = 11