2009年10月31日 星期六

陣列下界

 
為何c語言的陣列索引是由0開始?

我們很難揣測 Ritchie 當年的心意,我的想法是:
當時一些可自訂陣列上下界的語言,如 Fortran,
在計算陣列元素位址時,需先扣去下界。

由於當時組合語言尋址範圍有限,最差情況可能只有
+-32768,當下界太大 (>32768) 或太小 (<-32768) 時,
下界無法在 Compiler time 靜態議決使之轉成 0 以加快元素存取速度,
只能每次存取時,實實在在的減去下界,這會拖慢存取速度。

於是,有 2 種解法:

(1) 設下語法限制,限定上下界範圍。
(2) 直接規定下界為 0。

選擇 (2) 可令陣列與指標間,具備合適的語法對應:
由於 C 中,「無索引標記的陣列名稱」會自動轉成
「指向陣列第一個元素的指標常數」,如:

        short a[1];

單用 a 時,其值為 &a[下界],
亦為 &(*((a)+(下界))) 或 &(*((下界)+(a))),

令下界 = 0,則如下形式為等「值」:

        a == &a[0] == &(*(a+0)) == &(*(0+a))

其中,deref (*) 與 addrof (&) 可相消解:

        &(*(a+0)) == &*(a+0) == a+0 == a

又因 a == &a[0],消去 & 得:

        *(a+0) == *a == a[0]        

由於 *a 中的 a 視為「指向陣列第一個元素的指標常數」,
對其 dereference 必為「陣列第一個元素」,
而 *a 又相當於 *(a+0),為滿足 *(a+x) ~ a[x],
故令 x = 0。

當然,直接由 *(a+x) ~ a[x] 這個對應關係,
也可以推想出 x = 0 的合理性,但「含意」會比較少 :p

以「陣列指標」觀點來看 (pointer to array,
如:Type (*a)[n]) 則問題可簡化至指標。

由於我們允許,並限定: *(a+0) 等值於 *a
當 pointer 的 offset 起始值為 0 時,才能滿足此限定,
否則形成矛盾:*(a + low_boundary) == *a

漸層字


#include <windows.h>

enum {W=800, H=600};
HBITMAP hBmp;
HWND    hwnd;
HDC     hdc, hdcMem;
UCHAR*  pic;


//將 c1 與 c2 以 nc1:nc-nc1 比例混色, 傳回 BGR 格式

inline int mixColor (int c1, int c2, int nc1, int nc)
{
   int a = nc - nc1; typedef UCHAR U;
   int r = (U(c1>>16)*nc1 + U(c2>>16)*a)/ nc;
   int g = (U(c1>>8) *nc1 + U(c2>>8) *a)/ nc;
   int b = (U(c1)    *nc1 + U(c2)    *a)/ nc;
   return (b<<16)|(g<<8)|r;
}

//在 (tx, ty) 處秀出字型=face, 大小=size 的文字 s, 顏色由 c1 過渡到 c2,

void show_text (int tx, int ty, wchar_t* s, int c1, int c2,
                int size=24, wchar_t* face = L"標楷體")                           
{   
    static int bits = GetDeviceCaps (hdc, BITSPIXEL) *
                      GetDeviceCaps (hdc, PLANES);
    HFONT   font    = CreateFont (size,0,0,0,FW_BOLD,0,0,0,0,0,0,0,0,face);
    HGDIOBJ oldFont = SelectObject (hdcMem, font);
    SetBkColor (hdcMem,0);
    SetTextColor (hdcMem, 93);
    TextOut (hdcMem, 0,0, s, wcslen(s));
    SelectObject (hdcMem, oldFont);     
    DeleteObject (font);
   
    int p,x,y, h = size, w = size * wcslen(s);
    if (w > W) w = W;
    if (h > H) h = H;

    BITMAPINFO info0 = {{40, w, h, 1, bits, 0,0,0,0,0,0}, {{0}}};
    GetDIBits (hdcMem, hBmp, 0, h, pic, &info0, DIB_RGB_COLORS);

    if (bits == 32) {
        int *o = (int*) pic;
        for (p=y=0; y<h; ++y, p+=w)
            for (x=0; x<w; ++x)
                if (RGB(0,0,93) == o[p+x])
                    o[p+x] = mixColor (c1,c2, y,h);
                else o[p+x] = 0;            
    }
    BITMAPINFO info = {{40, w, h, 1, bits, 0,0,0,0,0,0}, {{0}}};
    SetDIBitsToDevice (hdc, tx,ty,w,h, 0,0,0,h, pic, &info, DIB_RGB_COLORS);
}

void init()
{
    SetConsoleTitle (L"Conso");
    SMALL_RECT size = {0, 0, W-1, H-1};      
    SetConsoleWindowInfo (GetStdHandle (STD_OUTPUT_HANDLE), TRUE, &size);  
   
    hdc    = GetDC (hwnd = FindWindowW (0, L"Conso"));
    hdcMem = CreateCompatibleDC (hdc);
    hBmp   = CreateCompatibleBitmap (hdc, W, H);     
    pic    = new UCHAR[W*H];
    SelectObject (hdcMem, hBmp);   
}
void free()
{
    delete[] pic;
    ReleaseDC (hwnd, hdc);
    DeleteObject (hBmp);
    DeleteDC (hdcMem);   
}

int main (/* daviddr 081104 */)
{
    init();   
    show_text (30,80, L"漸層字!", RGB(255,10,10), RGB(255,250,50));
    show_text (30,120, L"這是48號字體", RGB(55,10,220), RGB(255,90,90), 48);
    system ("pause");
    free();
    return 0;
}

反編譯

 
  「由執行檔轉回 C++ 碼!?」

欲取 VC 資源可用 eXeScope 一類的東西,
欲得知原始碼大略寫法的話:
Dcc,EXE2C,REC,Boomerang,都是 for C...
IDA pro 的 plugin Hex-Rays 可轉出類似 C 的語法。
或許 SourceForge 上有其他更瘋狂的東西 XD

原理是先將 binary code 反組譯 (形如 sourcer、dumpbin、
IDA pro、w32dasm),再將 asm 解釋成 C。

但...

假設無 platform, endianness 等問題,反編譯仍是困難重重。
由於符號表可能不存在,code 可能因 optimization 或 (C++的)
inline 而變更佈局,且反編譯為一對多映射,C++ 另有 mangle,
vtbl, 模版代換 等問題,產生的結果將比 Perl2C 還難懂 ==;

對 C++ 而言,與其 decompile,不若 rewrite 之。

若是 C# 就容易多了,他的 MSIL 和 Java 的 b-code 一樣,
原始資訊盡在其中 (這樣才能被 interpreter 正確解譯)。
一堆工具如 Ildasm, Reflector, salamande 都可以反編譯出可讀性高的碼。

求根

 
以下程式輸出為:
0.962398
-0.040659
預測值已跨出區間!
0.000000

前兩者在 [0,1] 「附近」找過零點,並不保證不越區。
此函式在那附近正好有兩個: 0.962398 與 -0.040659
Secant 根據給出的初始域,往 -0.040659 靠。
至於 Newton-Raphson 就更不可靠了,因發生越區而傳回 0。
若將初始域放大, Newton-Raphson 便可找到根值。

typedef double DF;              //double float
typedef DF (*FP)(DF);

DF abs (DF f) {if (f<0) f=-f; return f;}

//以精確度 accuracy, 在 loop 次迭代內求 f 在 [x1,x2] 中的根,
//注意! 參數需滿足 x2>x1, 且 [x1,x2] 中至少包含一根

DF false_pos (FP f, DF x1, DF x2, DF accuracy, int loop=64)
{
    DF acc, x,y, y1 = f(x1), y2 = f(x2);

    for (int i=0; i<loop; ++i) {
        y = f (x = x1 + (x2-x1) * y1/(y1-y2));
        if (y < 0) acc=x1-x, x1=x, y1=y;
        else       acc=x2-x, x2=x, y2=y;
        if (abs(acc) < accuracy || 0==y) return x;
    }
    puts ("root not be found!");
    return 0;
}

DF secant (FP f, DF x1, DF x2, DF accuracy, int loop=64)
{
    DF acc, dx, x = x2, y1 = f(x1), y = f(x2);
    if (abs(y1) < abs(y)) x=x1, x1=x2, dx=y1, y1=y, y=dx;

    for (int i=0; i<loop; ++i) {        
        dx = (x1-x) * y/(y-y1);
        x1 = x;
        y1 = y;
        x += dx;
        y = f (x);
        if (abs(dx) < accuracy || 0==y) return x;
    }
    puts ("root not be found!");
    return 0;
}

//df 為 f 的導函數
DF newton (FP f, FP df, DF x1, DF x2, DF accuracy, int loop=64)
{
    DF acc, dx, x = (x1+x2)*.5;   
    for (int i=0; i<loop; ++i) {        
        x -= dx = f(x) / df(x);
        if ((x1-x)*(x-x2) < 0) {puts("\n預測值已跨出區間!"); return 0;}
        if (abs(dx) < accuracy) return x;
    }
    puts ("root not be found!");
    return 0;
}

DF f (DF x) { return (((230*x+18)*x+9)*x-221)*x-9; }
DF df(DF x) { return ((230*x+18)*x+9)*x-221; }

int main()
{
    printf ("\n%f", false_pos (f, 0,1, 1e-6));
    printf ("\n%f", secant (f, 0,1, 1e-6));
    printf ("\n%f", newton (f, df, 0,1, 1e-6));
    return 0;
}

Fractal

 
底下秀出 4 種圖:

1.Koch curve
2.Sierpinski’s Gasket
3.Tree curve
4.Julia set

其中,sierpinski 外緣線需自行接上,
Julia set 觀察窗需手動調整:

#include <windows.h>
#include <math.h>
#include <complex>

#define RGB(r,g,b) (b<<16)|(g<<8)|r
enum {W=800, H=600};
HDC hdc;
HANDLE  hwnd, hIn, hOut;

namespace Turtle
{
    //--------------------- 作圖 -----------------------

    const float rd = 3.1415927/180.0;
    int* pic, X, Y, A, ang, step, C;   //定義: 畫布, 座標, 角度, 步距, 顏色
    float scale;
    float branch;

    void clear ()
    {
        int i = W*H; while (i--) pic[i] = 0;
    }
    void show ()                //注意: 顯示器色彩格式需為 32-bits
    {
        BITMAPINFO info = {{40, W, -H, 1,32,0,0,0,0,0,0}, {{0}}};
        SetDIBitsToDevice 
           (hdc, 0,0,W,H, 0,0,0,H, pic, &info, DIB_RGB_COLORS);
    }
    void set (int x, int y, int d=0, int a=0) {X=x; Y=y; ang=a; step=d;}
    void setxy (int x, int y) {set(x,y);}
    void pixel (int x, int y, int c)                //繪點
    {
        if (x<0 || y<0 || x>=W || y>=H) return;
        pic[y*W+x] = c;
    }  
    void line (int x, int y, int x2, int y2, int c=0xffffff)
    {
        int dx= x2-x, dy= y2-y, dirx=1, diry=1, b=0;
        if (dx < 0)  {dx = -dx; dirx= -1;}           
        if (dy < 0)  {dy = -dy; diry= -1;}           
        pixel (x,y,c);
        if (dx<=1 && dy<=1)  return;                 //兩點間隔太小,不予處理
        if (dx < dy) {                               //以Y軸為基準繪製線段
            int hy= dy>>1, dotn= dy-2, n=1;
            do {b += dx;   if (b > hy)  {b -= dy; x += dirx;}
                y += diry; pixel (x,y,c); n++;
            }while (dotn--);
        }else{                                       //以X軸為基準繪製線段
            int hx= dx>>1, dotn= dx-2, n=1;
            do {b += dy;   if (b > hx)  {b -= dx; y += diry;}
                x += dirx; pixel (x,y,c); n++;
            }while (dotn--);
        }
    }
    void move (int n, int c=0xffffff)
    {
        int x = n* cos (rd*A), y = n* sin (rd*A);
        line (X, Y, X+x, Y+y, c);
        X+=x; Y+=y;
    }
    void mov (int c=0xffffff) {move (step,c);}
    void turn (int a)
    {
        A+=a;
        if (A>360) A-=360;
        else if (A<360) A+=360;
    }

    //--------------------- 碎形 -----------------------

    void koch (int n)
    {
        if (0==n) {mov(); return;}
        koch (n-1);  turn (-60);
        koch (n-1);  turn (120);
        koch (n-1);  turn (-60);
        koch (n-1);
    }
    void sierpinski (int n)
    {
        if (0==n) {mov(); return;}
        sierpinski (n-1); turn(-120);
        sierpinski (n-1); turn(120);
        sierpinski (n-1); turn(120);
        sierpinski (n-1); turn(-120);
        sierpinski (n-1);
    }
    void tree (int n, int x, int y, float len, float ang)
    {
        if (0==n) return;
        setxy(x,y); A=-ang;  move(len); x=X; y=Y;
        tree (n-1, x,y, len/scale, ang-branch);
        tree (n-1, x,y, len/scale, ang+branch);
    }
    void julia (int n)
    {
        // z = x+iy,  F(z) = z^2+C,  |F(z)| = x^2+y^2
        int i, k;
        float v,xp,yp, x0,y0,x1,y1,x,y,z,cx,cy;
        cx=-0.5;  cy=0.5;
        for (x0=-2.0; x0<=2.0; x0+=0.005)
            for (y0=-2.0; y0<=2.0; y0+=0.005){
                for (x = x0, y = y0, k = 0;
                    x*x+y*y<4.0 && k<n; ++k){    //迭代 n 次,直到數列發散
                    x1 = x*x - y*y + cx;
                    y1 = 2*x*y + cy;
                    x = x1; y = y1;
                }
                xp = W/4*x0+W/2;
                yp = -H/4*y0+H/2;
                v = x*x + y*y;
                if (v < 4.0) {
                    i = v*64;
                    pixel (xp, yp, RGB (100,220,i));
                }else
                    pixel (xp, yp, RGB (30,100,200));
            }
    }
};
using namespace Turtle;


int main (/* daviddr 081020 */)
{
    SetConsoleTitle (L"Conso");
    hdc  = GetDC (FindWindowW (0, L"Conso"));
    hIn  = GetStdHandle (STD_INPUT_HANDLE);
    hOut = GetStdHandle (STD_OUTPUT_HANDLE);
    SMALL_RECT size = {0, 0, W-1, H-1};      
    SetConsoleWindowInfo (hOut, TRUE, &size);   //變更視窗大小
    Turtle::pic = new int[W*H];    //畫布
   
    clear ();
    set (20,380, 8);  koch (4);   
    show ();
    system ("pause");

    clear ();
    set (20,380, 8);  sierpinski (5);   
    show ();
    system ("pause");

    clear ();
    scale = 1.3;
    branch = 23;
    tree (8, 200,380, 64, 80);   
    show ();
    system ("pause");

    clear();
    julia(32);
    show ();
    system ("pause");

    delete [] Turtle::pic;
    DeleteDC (hdc);
    CloseHandle (hIn);
    CloseHandle (hOut);

    return 0;
}
sierpinski 外緣線由小而大逐次爬行的作法,
很難排除累計誤差,無法形成正三角。
可改為由外而內,用內插方式來算落點:

private:
    void sierpinski (int n, int x1, int y1, int x2, int y2, int x3, int y3)   
    {
        if (0 == n) {            
            setxy (x1, y1);
            mov(); turn (-120);
            mov(); turn (-120);
            mov(); turn (-120);
            return;
        }
        sierpinski (n-1, x1,y1, x3,y1, (x1+x3)/2, (y1+y3)/2);
        sierpinski (n-1, x3,y1, x2,y2, (x2+x3)/2, (y2+y3)/2);
        sierpinski (n-1, (x1+x3)/2, (y1+y3)/2, (x2+x3)/2, (y2+y3)/2, x3, y3);
    }

public:
    void sierpin2 (int n)                       //自頂至底
    {
        int d = step * (1<<n);
        sierpinski (n, X,Y, X+d,Y, X+d/2, int(float(Y)-1.72384*d/2));
    }

下面是呼叫 koch (4), sierpin2 (5), tree (8,..) 的結果:


1除以0

 
Y=1/X, X 趨近0時, Y 是多少?

if x -> +0 then 1/x = +∞
if x -> -0 then 1/x = -∞
but +∞ ≠ -∞ , paradox

If take it as unsigned infinity, 1/0 = ∞
但此處的「0」意指「無窮小量」,與 1 的「位階」不同。
由於「1」非無窮小,故結果為 ∞
這種定義有個好處是,在 plane of complex numbers z=x+iy
上加入無窮遠點 ∞ = 1/0,則 z 可在球面上表達出來。

也就是說,在 complex plane C 上,

令 S = C∪{∞}
f(z) = z, z ∈ {∞}
g(z) = 1 / z, z ∈ {0}

並定義 1/∞ = 0
則 { f, g } 為 S 之相容圖集,且 S 形成球面。
由於 C 是一種 Riemann surface (1D complex manifold)
此球面便稱為 Riemann sphere。

Riemann sphere 是緊致的,
相當於閉合且有界的歐幾裡德空間子集,
緊空間可以某種方式類似於有限集合,
且定義在緊集上的連續實值函數一致連續,
因而可施以微積分運算。


唉呀我到底在說啥..XD

JPEG編碼流程

 
若不牽扯到 Jpeg2000 或 Progressive JPEG,只針對 JFIF 基礎標準,
或是只採用 YCbCr + Baseline 模式 + Huffman 編碼的 TIFF 標準,
其作法可簡述如下:

將圖的長寬 zero padding 成 8 的倍數,
以 8x8 區塊為處理單位,理由是:
1. 做成晶片時省材料費 (開玩笑的?),
2. 程式師偏好 2 的冪次方以利記憶體對齊並加速運算 (半開玩笑的..),
3. 一般圖像的連續色調常侷限於 17x17 的區塊裡...

將 RGB 轉到均勻色彩空間 YCbCr (最常用的 YUV 一族),
由於綠光在可見光譜中所佔範圍較大,導致人視網膜上紅藍細胞較少,
加上柱狀細胞占多數,因此我們可保留 Y,而捨棄一些 Cb Cr 訊息,
Jpeg 可施行 4:4:4、4:2:2、4:2:0 3 種 downsampling (三選一)。

之後,將 Y、Cb、Cr 值正規化至 -128~127 (一般,Y 要扣掉 128),
再分別進行 Forward DCT 變換該矩陣的底基向量
(這部份有許多加速法,例如將 8x8 DCT 分解成 x, y 方向的兩個 1D DCT,
或是用 AA&N 並搭配他們的量化表),然後將各值除以quantization table
(如 CCIR 601)中對應的值,再取 round。
採用 DCT 而不用 FFT,是因為他能以較少的係數來逼近連續性資料。
(圖釋: http://www.cs.cf.ac.uk/Dave/Multimedia/node231.html)

為了將盡可能多的 0 靠在一起,以利壓縮資料,
需將量化後表中的 AC 值以 Zig-Zag 順序重新編排,
(相當於從低頻排到高頻) 以 EOB 標籤 (1010) 取代尾端那些 0。
至於中間的 0,可用 RLE 壓縮掉,
RLE 中每組值分成 high 4-bits 與 low n-bits 兩部分,
high 4-bits 表示 0 的連續個數,(這和 Jpeg 標籤採用 4-bits 有關)
low bits 表示接在連續 0 後的值,以 Huffman 編碼表之。
low bits 表示的值有可能是 0,因為 high 4-bits 最多只能紀錄
15 個連續的 0,若有 15 個以上的連續 0,low bits 便是 0 了。

因為相鄰兩方塊的平均色彩 (也就是 DC 值) 一般很接近,
也就是說他們的差值很小,可用少量 bits 表示,
便以 DPCM 對區塊間的 DC 值進行 Predictive coding。

最後在各資料前頭貼標籤,存檔。
處理 jpg 檔中的眾多標籤也是件麻煩工作。

如何正確做 Jpeg Canonical Huffman Code 對應的說法很雜,
你可以用 ISO/IEC 10918-1 中給出的 DC, AC 預設編碼表試試看。
Jpeg codec 要寫的完善是件苦工喔...


簡單說來,對 8x8 區塊裡的 63 個 AC 值,以及區塊間 DC 的差值,
分別使用不同的 Huffman 表去編碼。而且 Y 與 CbCr 各有其編碼表,
所以總共有 4 份碼表。

以 Y 成分的 DC 差值為例,將每組差值表示成如下形式:
(Huffman識別碼, 差值的 binary code)

底下用「HI」簡稱「Huffman識別碼」,
用「DL」簡稱「差值 binary code 的長度」。
其碼表為:
DL HI長度 HI ----------------------- 0 2 00 1 3 010 2 3 011 3 3 100 4 3 101 5 3 110 6 4 1110 7 5 11110
若現在 Y 成分有 3 個區塊,其 DC 值分別是 58, 50, 53
安插 0 到最前端,便利差值運算,形成 0, 58, 50, 53。
將串列中元素,後者減前者,得差值為:

58 -8 3

差值為負時,先取絕對值,再將位元反相,故得:

111010 0111 11

111010 長度是 7,對照碼表得 HI 為 11110,故編碼成 11110 111010
0111 長度是 4,對照碼表得 HI 為 101,故編碼成 101 0111
11 長度是 2,對照碼表得 HI 為 00,故編碼成 00 11
最後寫入:

11110 111010 + 63個AC編碼
101 0111 + 63個AC編碼
00 11 + 63個AC編碼

為何要安插1個0到最前端做運算?
因為解碼時需要知道第一個 DC 值,才能將之後的 DC 值還原回來,
否則只憑 -8, 3,並無法還原回 58, 50, 53,之後的 IDCT 亦會出錯。

進制轉換

 
10進位小數轉2進位:
//這種版本是刻意為之的 :-)

char* float_to_binary (float f)             //進制轉換
{
    const int N = 128;
    static char s[N];     
    char *p = s;
    int b=0, i=N, n=f;                      //b 將指向整數部分
                                            //最右端的位置
    while (i--) s[i] = '0';

    if (f < 0)  {++b; *p++='-'; n= f= -f;}  //處理負數
    if (n == 0) {++b; p++;}                 //若是 0
   
    if (n) {                                //算整數部分
        i = n; while (i>>=1) ++b;            
        p = s + b;
        i = n; do *p--+= i&1; while (i>>=1); 
        p = s + b + 1;
    }   
    *p++ = f-n ?'.': 0;                     //是否加小數點
    while (f -= n) *p+++= n = f*=2;         //算小數部分
    *p = 0;
    return s;
}

int main()
{
    cout << float_to_binary (-20.375);
}
若不處理小數:
#include <stdio.h>
int main () 
{
    for (int m,i=0; i<257 && printf("\n%3d\t",i); ++i)
        for (m=512; m=m>>1; putchar(i&m?49:48));
}
或者這樣:(注意: 在不同環境裡會有 Big/Little Endian 與 bit align 問題)
#include <stdio.h>
int main() 
{
    union {
        unsigned n;
        struct {unsigned a:1,b:1,c:1,d:1,e:1,f:1,g:1,h:1,i:1;};
        void pnt() {
            printf ("\n%3d\t%d%d%d%d%d%d%d%d%d", n,i,h,g,f,e,d,c,b,a);
        }
    } b = {0}; 
    while (++b.n<257) b.pnt();
}

NULL

 
當指標不指向任何東西時,呈 nil 狀態,可用 0 表示。
早期,C 程式師不喜歡見到意味不明的 magic number,
何況 0 身兼多義,既是 0、0x0、00、0.f、0u、'\0',
也是 (void*)0,
故偏好使用巨集 NULL 來描述 (void*)0 這個狀態。

*註:雖然上述表示都可視為 0,
但他們的資料型別並不相同。
在 32 bits OS 上,「常見」的規格為:
'\0' 為 char,占 1 Byte。
0, 00, 0x0 為 int,占 4 Byte。
0u 為 unsigned int,占 4 Byte。
0.f 為 double,占 4 Bytes。
0.0 為 double,占 8 Bytes。

而早期寫 C++ 程式的前輩們,多數偏好以 0 來表示
const null pointer,因為看起來較簡潔。
因此在 C++ 中便做了如下定義:
#ifdef __CPLUSPLUS #define NULL 0 #else #define NULL (void *)0 #endif
而 C++ 0x 則多了新關鍵字 nullptr 來描述 null pointer,
目前較新的 Compiler 皆有支援此 keyword。

------

C++ 中,因以往 C 的 NULL 定義會轉成像 int* p1 = (void*)0;
造成型別不相容,故便將 NULL 定成 0。

為何是 0? 因為 0 具有常數性,其指涉至 invalid memory,
對這區域中的 I/O 存取,皆被檢驗為不合法,
此時程式被中斷,秀出出錯原因 (與程式碼段)。
(在 JVM 上便是丟出 NullPointerException)

而 (void*)0 並不具常數性,仍可對位址 0 進行 I/O 存取,
如 Christopher McGee 列舉的:
*(NULL) NULL->member NULL[1] NULL->function() strcpy( NULL, "abc" ) *(NULL)(params);
之後可能造成記憶體毀損,程式 broken,
顯示「記憶體存取錯誤」的 dialog。

若您用的是 C++ 編譯器,直接打 0、NULL,
或 Herb Sutter 提出的 nullptr 都沒問題,
視之個人習慣,只要讓 pointer 不 dangling 便行。
除非你所處的多人合作環境中,對處理 null pointer 已有共識,
這時理應遵循此共識。

若是用 C++/CLR,由於 Object^ obj = 0;
會產生 implicit boxing of 0,也就是隱含的實體物件。
為方便追蹤 obj 的初始化與指派行為,
需寫成 Object^ obj = nullptr;
表示 refer to no object。

迷宮



#include <stdio.h>
#include <time.h>

enum {U=1, L=2, R=4, D=8};
int  w=32, h=28;
char mz[256][256];
char inv[4] = {3,2,1,0};
char yd[4] = {-1,0,0,1}; 
char xd[4] = {0,-1,1,0};
char *cell = "  │─┘─└─┴││┐┤┌├┬└";  //內部牆壁類型

void link (int x, int y)
{
    int i=0, d, dir = rand()%4;                 //連結牆壁
    do{
        d = (dir+i) & 3;                        
        if ((mz[x][y] & 1<<d) ||                //若此方向已選過
            mz [x + xd[d]][y + yd[d]]) {        //或此方位已有牆壁
            i++; continue;                      //便選擇其他方向    
        }
        mz[x][y] |= 1<<d;                       //記錄所選方向
        x += xd[d];                             //朝此方向移動 
        y += yd[d];
        if (x<0 || x>w || y<0 || y>h) break;    //若出界則返回
        mz[x][y] |= 1<<inv[d];                  //紀錄舊點連結方向
        dir = rand()%4; i = 0;                  //隨機選擇方向
    }
    while (i < 4);
}

void main ()
{
    srand (time(0));
    int i,j, u=0, r=w, d=h, l=0;
    for (i=0;i<=w*h;i++) mz[0][i] = 0;          //設定cell的允許方向   
    for (i=0;i<=w;i++) {mz[i][0] |= L+R; mz[i][h] |= L+R;}
    for (j=0;j<=h;j++) {mz[0][j] |= U+D; mz[w][j] |= U+D;}

    while (u<d && l<r) {                        //對每個位置下種子
        for (i=l; i<=r; i++) link (i,u); u++;   //填充迷宮內部
        for (i=u; i<=d; i++) link (r,i); r--;
        for (i=r; i>=l; i--) link (i,d); d--;
        for (i=d; i>=u; i--) link (l,i); l++;
    }
    for (i=0; i<=h; i++, puts(""))              //印出迷宮
        for (j=0; j<=w; j++) {
            r = mz[j][i]*2;
            if (j==0 && r==22) r-=4; 
            if (i==0) r==14? r-=6: r==30? r=20:0;
            if ((i==h || j==w) && (r==26 || r==28)) r-=24;
            printf("%c%c", cell[r], cell[r+1]);
        }
        getch();
}
輸出:
┐───┬──────┬────┬──────┬────────┐ ││┌─┘┌┐─┐┌─┘┌──┐│┌────┐│┌┬─┬─┐┌┐│ ││└──┘└─┘├┬┐└─┐│└┘┌─┐┌┘└┘└┐└┐││││ │└┐┌─┐┌─┐│││──┘│┌┬┘│├┘┌┐┌─┘┌┘││││ │┌┘│┌┘│┌┘└┐├┐┌┬┘│└─││┌┤└┘┌─└┐└─┘│ ││┌┘└─┘││┌┘│├┘└┐└──┘││├┬─└──┘│┌┬┤ │││┌───│└┘┌┤└─┐├──┌┬─┘││┌┬──┐││││ │└┴┴─┌─┘┌─┘└─┐│├─┌┘│┌┐│┌┘│┌┐│└┘││ ││┌──┴──│┌──┬┘││┌┤│││└┬┘─┐││└┐┌┘│ │││─┐┌┐┌┘│┌┐│┌┘│││└┘└┐└─┌┘│└┐└┘││ │││┌┴┘││─┘│├─┘┌┘└──┐┌┘┌─┘┌┘┌┤┌─┤│ │├┴┘┌┐│└┐┌┘└┬┐│┌┬─┌┘└─┘┌┐│─┘│└┐└┤ ││┌┐││└┐││┌┐││└┘│┌┘────┘│└┐┌┘─┴─│ │└┘└┘└┐││││└┐└─┐││┌───┐┌┤─┤└───┬┤ │┌────┘│└┐││└┐─┘┌┘└┐┌─┘││┌┘─┬┐┌┘│ ├┘┌─┌──┐┌┘│└┐│┌┐└─┐│└───┘└──┘││┌┤ │││┌┘┌─┘│┌┴─││││┌┐└┘───┬──┐┌┐┌┘││ ││││─┘┌┐┌┘┌┐│││└┘└┐│┌┐┌┘─┬┘││└─┐│ │├┘└┐┌┘│└┐│└┤└┘│┌┐│││││┌┬┘┌┘│┌─┘│ │├──┘└┐┌┐└┘┌┘┌┐└┘││││┌┘││┌┘┌┘│┌┐│ │├┐┌┬─└┘│┌─┘┌┘│┌─┤└┤├┘─┐││┌┘┌┘│││ ││││└───┘└─┐└┐│└─└┐│└─┐││││┌┘─┘││ │││├─────┌─┘─┘└┐┌┐│└─┐└┘││└┘─┬─┘│ ││││┌┐│┌┐└─────┘│└┤─┐││┌┘└───┘│┌┤ │┌┘└┘└┤│└┐┌┐┌┐┌┐└─│┌┤│││┌────┐│││ │├───┐││┌┘│└┘│││┌┐││││├┴┘│┌──┘└┘│ ││──┐└┴┘└───┐│┌┴┘└┘│││└──┤│┌┐┌┐┌┤ │└──┤───────┘├┘─┬──┘│└───┘└┘└┘└┘│ └───┴────────┴──┴───────────────└

Leet

 
多年前剛接觸 C++ 時寫的程式,
用來將輸入字串轉成 Hacker 用語,
code 很舊了,不包含近來的替換形式,
基本轉換規則見: http://wapedia.mobi/zh/Leet

#include <iostream.h>
#include <stdio.h>
#include <time.h>

typedef short int S2B;

class Leet
{
   static long int s_;          
   static int _(int n) {
       s_ *= 0x15a4e35; ++s_;
       return ((s_>>16)&0x7fff) % n;
   }
   static struct Ltbl {
       S2B    n;                     //替換字串的單詞數     
       char*  s;                     //替換字串
   } ltbl[26], term[36];             //字元替換表, 與單詞替換表
   static S2B  termPos[26];          //紀錄字元所對應到的第一個
                                     //單詞的開頭位置
public:
   static void translate (char*);    //進行字串替換
   Leet();                           //初始化函式
};

long int Leet::s_=0;
S2B Leet::termPos[26];

Leet::Ltbl Leet::ltbl[26] =          //建立替換字元表
{
   4,"A a 4 @ ",  4,"B b 6 8 ",  4,"C c < K ",  
   4,"D d |> |) ",  3,"E e 3 ",  2,"F f ",  
   3,"G g 9 ",   3,"H h # ",   5,"I i 1 y | ",  
   2,"J j ",   3,"K k |< ",   4,"L l 1 |_ ",  3,"M m |\\/| ",  
   3,"N n h ", 3,"O o 0 ",  2,"P p ",  2,"Q q ",  
   2,"R r ",  5,"S s 5 z $ ",  4,"T t 7 + ",  5,"U u |_| O o ",  
   5,"V v |/ \\/ / ",  4,"W w \\/\\/ // ",  
   3,"X x >< ",  3,"Y y j ",  3,"Z z 2 "
};                                   //建立單詞替換表
Leet::Ltbl Leet::term[36] = 
{
   1, "at @ ",
   2, "cool kewl kool ",
   1, "dude dOOd ",
   1, "dudes dOOdz ",
   4, "drugs drugz drugz droogs droogz ",
   4, "ellet 31337 1337 leet elite ",
   4, "elite 31337 1337 leet elite ",
   2, "god root sysop ",
   2, "hacker h4X0r haxor ",
   2, "have G0tz gots ",
   1, "hello 43770 ",
   8, "i eye 3y3 ey3 3ye i | 1 y ",
   3, "information info 411 four-eleven ",
   2, "info 411 four-eleven ",
   1, "let 137 ",
   1, "love luv ",
   1, "microsoft M$ ",
   6, "of u|/ |_|V U/ uv |_||/ ",
   1, "peasant pissant ",
   3, "please pleez pleeze pleze ",
   1, "phone fone ",
   2, "porn pr0n pron ",
   1, "porno pr0n0 ",
   3, "poser pozer poseur pozeur ",
   2, "pot pott p0t ",
   1, "root god ",
   1, "see c ",
   3, "the Da D4 4 ",
   1, "to 2 ",
   1, "too 2 ",
   5, "you u U j0O Joo |_| ",
   3, "your j0r jo joor ",
   0, "{ "
};

Leet::Leet()     //初始化函式
{
   if (!s_) {
      s_ = time(0);
      for (int j=0, i=0; i<26; i++) {         //紀錄各字首在 term[] 
         while (*term[j].s < i+'a') j++;      //中的起始位置
         if (*term[j].s^ i+'a') {
             termPos[i] = -1; 
             continue;
         }
         termPos[i] = j; 
      }
   }
}
void Leet::translate (char* s)
{  
   int  n, i,j;  Ltbl* p;  
   bool bInWord = 0;                          //當字串指標 ps 指向字串 
   char *ps2,*ps=s;                           //開頭時,bInWord = false

   do if (*ps>='A' && *ps<='Z')               //先將字串轉成小寫
         *ps += ('a'-'A'); 
   while (*ps++);

   do {
      n = *s; 
      if (n>='a' && n<='z')  n-='a';          //將小寫轉成 0~25, 
      else {                                  //非字母者直接印出
          if(n=='`') cout<<'\\';  
          cout<<*s; bInWord=0;  
          continue;
      }   
          //單詞判讀:

      if (termPos[n]==-1 || bInWord) 
          goto AC;                            //"alpha chg" 之意

      p = term + termPos[n];
      for (;*p->s == *s; p++)                 //比對相同字首的單詞
      {
         ps = p->s;  ps2 = s;                 //使用字串指標加快運算速度
         while (*ps^' ' && *ps++ == *ps2++);  //持續比對至遇到空白
         if (*ps == *ps2)  break;             //若遇到相符的樣式便結束比對
      }
      if (*p->s^*s ||_(2))  goto AC;          //若無相關單詞, 便直接做字元轉換
      
      n = _(p->n) + 1;
      for (j=i=0; i<n; i++)  
          while (p->s[j++]^' ');
      
      while (p->s[j]^' ')                     //持續輸出字元,
          cout << p->s[j++];                  //直到遇到空白
      s = ps2 - 1;  
      bInWord = 0;  
      continue;                               //單詞判讀成功

          //字元判讀:
AC:   
      p = ltbl + n;
      n = _(p->n);
      for (j=i=0; i<n; i++)  
          while (p->s[j++]^' ');

      while (p->s[j]^' ')                     //持續輸出字元,
          cout << p->s[j++];                  //直到遇到空白
      bInWord = true;
   }
   while(*s++);
}

void main()
{
   Leet leet;                                 //建立物件
   char buf[1024]; 
   gets (buf);                                //讀取字串
   leet.translate (buf);                      //進行轉換
}

點陣字

 
以前的 DOS,或仿 DOS 環境,可以在 BIOS 的 F000:FA6E 取得
ASCII bitmap,在 WinXP上可以 LoadLibrary("ntdll.dll"),
用裡頭的 ZwOpenSection 與 ZwMapViewOfSection 取得此
section 的映射,但此法在 Vista 下不能用。

DOS 倚天中文下則由 B800:0000 開始取 (Big5, color) pair,
再對到 16 or 24 號字形檔 (.15 or .24x) 取出 bitmap。
Windows 上有許多 true type font,這些向量字不存在 bitmap,
只能用 GetGlyphOutline 或 TextOut 去轉出點陣圖。

現今由於字型檔繁多,較便捷的做法是用 Win32 API 指定字型檔與字樣,
將字畫到 canvas 上,再把座標數出來,譬如:

#include <windows.h>
#include <stdio.h>

//輸出文字 s, 字體=face, 字形大小=size

void show_text (HDC hdc, wchar_t* s, int size=16, wchar_t* face= L"細明體")
{
    int  x,y, len = wcslen(s);  
    HFONT   font    = CreateFont (size,0,0,0,400,0,0,0,0,0,0,0,0,face);
    HGDIOBJ oldFont = SelectObject (hdc, font);
    SetBkColor (hdc,RGB(255,255,255));
    SetTextColor (hdc, 0);                 //黑色
    TextOut (hdc, 0,0, s, len);

    for (y=0; y<size; y++, puts(""))
        for (x=0; x<len*size; x++)
            printf (GetPixel (hdc,x,y)? "  ":"█");
    SelectObject (hdc, oldFont);     
    DeleteObject (font);   
}

int main ()
{
    SetConsoleTitle (L"Conso");
    HDC hdc = GetDC (FindWindow (0, L"Conso"));

    show_text (hdc, L"選擇");

    DeleteDC (hdc);
    return system ("pause");
}
輸出:
█      ████  ████        ██
      ██  █    █  █    █        █      █████████
            ████  ████        █      █    █  █    █
  █        █        █          █████  █████████
    ██    █    █  █    █        █              █
              ███    ███        █        ███████
                                      █              █
      █          █    █            █  █  █████████
  ████    ████████        ██        █      █
      █          █    █        ███            █  █
      █    ██████████  █  █        ███████
      █          █    █            █              █
      ██    ██        ██        █      █████████
  ██    ██                    ███              █
  █          █████████    █                █



底下是另一種 ttf 轉點陣的寫法,需用 Unicode mode 編譯:

//將文字 ch 的點陣圖存入 buf 中, 點陣圖大小記錄於 bytes 中傳回
//字體=face, 字形大小=size, [此函式在 Unicode 模式下測試正常]

int text_bitmap (HDC hdc, UINT ch, char* buf, GLYPHMETRICS& gm,
                int size=16, wchar_t* face= L"細明體")
{
    MAT2    mat     = {{0,1},{0,0},{0,0},{0,1}};    //轉置矩陣
    HFONT   font    = CreateFont (size,0,0,0,400,0,0,0,0,0,0,0,0,face);
    HGDIOBJ oldFont = SelectObject (hdc, font);
    int bytes = GetGlyphOutline (hdc, ch, 1, &gm, 0, 0, &mat);
    if (bytes != GDI_ERROR)
        GetGlyphOutline (hdc, ch, 1, &gm, bytes, buf, &mat);
    SelectObject (hdc, oldFont);     
    DeleteObject (font);   
    return bytes;
}

int main ()
{
    SetConsoleTitle (L"Conso");
    HDC hdc = GetDC (FindWindow (0, L"Conso"));

    GLYPHMETRICS gm;
    char a[512];
    int sz = text_bitmap (hdc, L'選', a, gm);
    int nx = sz/gm.gmBlackBoxY;     //每行占幾Byte, gmBlackBoxX=位元寬度
                                    //亦即 ((gm.gmBlackBoxX+31)>>5)<<2   
    for (int x,j,i=0; i<sz; puts(""))
        for (x=0; x<nx; x++, i++)
            for (j=1<<8; j; j>>=1)
                printf (a[i]&j? "█":"  ");
   
    DeleteDC (hdc);
    return system ("pause");
}
輸出:
█      █████  ████
      ██  █    ██  █    █
            █████  ████
██        █          █
    ██    █    ██  █    █
              ████    ███

      █          ██    █
█████    █████████
      █          ██    █
      █    ███████████
      █          ██    █
      ██    ██          ██
███    ██
██          ██████████

字串處理


//判斷字串是否相等
    bool str_eq (register const char* a, 
                 register const char* b)
    {
        while (*a == *b++) 
            if (!*a++) return true;
        return !(*a-b[-1]);
    }

洗版程式


#include <windows.h>
#include <stdio.h>

int main ()
{
    wchar_t text[] = L"讚";                  //指定文字
    wchar_t face[] = L"細明體";              //指定字體
    int  size = 32;                         //指定字形大小
    int  x,y, len = (sizeof text/sizeof*text)-1;  

    SetConsoleTitle (L"ASCII Art");
    HDC     hdc     = GetDC (FindWindow (0, L"ASCII Art")); 
    HFONT   font    = CreateFont (size,0,0,0,FW_BOLD,0,0,0,0,0,0,0,0,face);
    HGDIOBJ oldFont = SelectObject (hdc, font); 

    SetBkColor (hdc, RGB (255,255,255));
    SetTextColor (hdc, 0);                  //黑色
    TextOut (hdc, 0,0, text, len);

    FILE* f = fopen ("text.txt","wt");      //開檔
    for (y=0; y<size; y++, fputc('\n',f))
        for (x=0; x<len*size; x++)
            fprintf (f, GetPixel (hdc,x,y)? "□":"■");
    fclose (f);

    SelectObject (hdc, oldFont);     
    DeleteObject (font);   
    DeleteDC (hdc);
}
輸出結果:
□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□
□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□
□□□□□□□□■□□□□□□■■■□□□□□□□■■□□□□□□
□□■■■■■■■■□□■■■■■□□□□□■■■■□□□□□□□
□□□□□□□□□□□□■□□■■□□■■■□□□■□□□■□□□
□□□□□□□□□□□□■■■■■■■■■■■■■■■■■■■□□
□□□□□□□□□□□■□□□■■□□□□□□□□■□□□□□□□
□□□□□□□□■■□□□□□■■□□■■□□□□■□□□■□□□
□□■■■■■■■■■■■■■■■■■■■■■■■■■■■■■□□
□□□□□□□□□□□□□□■□□■□□□□□■□□■□□□□□□
□□□□□□□□□□□□□■□□□■□□□□□■□□■□□□□□□
□□□□□□□□■■□□□■□□□■■■■■■□□□■□□□■□□
□□□■■■■■■■■■■■■■■■□□□■■□□□■■■■■■□
□□□□□□□□□□□□■□□□□□□□■□□□□□■■■■■□□
□□□□□□□□□□■■□□■■■■■■■■■■■■■■■□□□□
□□□□□□□□■■□□□□■■□□□□□□□□□□□■■□□□□
□□■■■■■■■■□□□□■■□□□□□□□□□□□■□□□□□
□□□□□□□□□□□□□□■■■■■■■■■■■■■■□□□□□
□□□□□□□□□□□□□□■■□□□□□□□□□□□■□□□□□
□□□□□□□□□□□□□□■■□□□□□□□□□□□■□□□□□
□□□■□□□□□■□□□□■■□□□□□□□□□□□■□□□□□
□□□■■■■■■■■□□□■■■■■■■■■■■■■■□□□□□
□□□■□□□□■■□□□□■■□□□□□□□□□□□■□□□□□
□□□■□□□□■■□□□□■■□□□□□□□□□□□■□□□□□
□□□■□□□□■■□□□□■■■■■■■■■■■■■■□□□□□
□□□■□□□□■■□□□□■■□□□□□□□□□□□■□□□□□
□□□■□□□□■■□□□□■□□□■□□□□■□□□□□□□□□
□□□■□□□□■■□□□□□□□■■■□□□□■■■□□□□□□
□□□■■■■■■■□□□□□■■□□□□□□□□□■■■□□□□
□□□■□□□□■■□□□■■□□□□□□□□□□□□□■■■□□
□□□■□□□□□□□■■□□□□□□□□□□□□□□□□□■□□
□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

二元樹

 
用 C 語言的 struct 建立二元樹,一般作法是用兩個
link list node 不斷去連結子樹。 用 array 建也是可行的,
特別是超大型、且要求高速存取的二元樹,
一般會用 hash 來分配節點。

底下是簡單範例,使用 C 建立一個 binary tree 形式的
container,並附上相關操作。

//--------------- BTree definition --------------------

typedef struct Node
{
    void *data;                     //資料項
    Node *L, *R;                    //指向左右子樹
} 
Node;
                                    //建樹            
void add (Node** p, void* data, 
          int (*comp)(void*,void*), int size)    
{
    void* obj;

    if (!*p) {
        obj = malloc (size);        //建立存放物件的空間
        memcpy (obj, data, size);
        *p = (Node*) malloc (sizeof(Node));
        (*p)->data = obj;
        (*p)->L = (*p)->R = 0;
    }
    else if (comp((*p)->data, data)) 
        add (&(*p)->L, data, comp, size);    //建左子樹  
    else 
        add (&(*p)->R, data, comp, size);    //建右子樹
}

void release (Node* p)              //砍樹
{
    if (!p) return;
    release (p->L);
    release (p->R);
    free (p->data);
    free (p); p = 0;
}


typedef enum {PRE, IN, POST} Order;    //指定節點拜訪順序
void show (Node* p, Order o, void (*print)(void*))  //秀樹
{
    if (!p) return;
    if (PRE == o) print (p->data);  show (p->L, o, print);
    if (IN  == o) print (p->data);  show (p->R, o, print);
    if (POST== o) print (p->data);    
}


//---------------------- Instance ------------------------

typedef struct { char* name; int IQ; } Grade;

void print_int(void* i)          { printf(" %d", *(int*)i);     }
int  comp_int (void* a, void* b) { return *(int*)a > *(int*)b;  }
void print_ch (void* i)          { printf("%c", *(char*)i);     }
int  comp_ch  (void* a, void* b) { return *(char*)a > *(char*)b;}
void print_iq (void* i)          { printf(" %s", ((Grade*)i)->name); }
int  comp_iq  (void* a, void* b) { return ((Grade*)a)->IQ > ((Grade*)b)->IQ;}

int main (void)   
{   
    int   i, j;
    char  exp[] = "hello word";
    Grade grade[] = 
    {
        "羅開",  120,
        "木蘭花",130,
        "高達",  113,
        "白素",  145,
        "衛斯理",115, 
    };
    Node* root = 0;
    srand (time (0));

    //TEST1
    for (i=0; i<10; i++) {        
        j = rand()%100;
        add (&root, &j, comp_int, sizeof(int));        
    }
    show (root, IN, print_int);
    release (root);
    puts("\n");
    root=0;

    //TEST2
    for (i=0; i<sizeof exp; i++)         
        add (&root, exp+i, comp_ch, sizeof(char));            
    show (root, IN, print_ch);
    release (root);
    puts("\n");
    root=0;

    //TEST3
    for (i=0; i<5; i++)         
        add (&root, grade+i, comp_iq, sizeof(Grade));            
    show (root, IN, print_iq);
    release (root);

    getch();
    return 0;
}

用 Haskell 寫,流程架構更為清晰:
data Tree  a = Leaf | Node(a, Tree a, Tree a)
add n Nil = Node n Nil Nil
add n p @ (Node v L R)
        | n < v = Node x (add n L) R
        | n > v = Node x L (add n R)
        | otherwise = p
preodr  Leaf=[] preodr (Node x,L,R) = [x] ++ preodr L ++ preodr R
postodr Leaf=[] postodr(Node x,L,R) = postodr L ++ postodr R ++ [x]
inodr   Leaf=[] inodr  (Node x,L,R) = inodr L ++ [x] ++ inodr R 

邊緣偵測


用平面方程去逼近 3x3 影像區塊時,可假設

      f(x,y) = ax + by + c

當中的 (a,b) 表示此區塊的 gradient (可摹想成傾斜向量)
代入 x,y = [-1,0,1] 可得出此區域的代數描述:

     ┌ -a-b+c  -a+c  -a+b+c ┐
     │   -b+c     c     b+c │
     └  a-b+c   a+c   a+b+c ┘

想偵測區塊中一條水平的線,可使用如下的 mask:

     ┌  0   0   0 ┐     ┌  1   1   1 ┐
     │  1   1   1 │ 或  │  0   0   0 │
     └ -1  -1  -1 ┘     └ -1  -1  -1 ┘

後者較佳,因為直行數值為單調增(減),有助於設計上的最佳化。
再將 mask 改成加權形式,用以增強邊緣點,寫成:

     ┌  β  α  β ┐     ┌  β  0  -β ┐
     │   0   0  0  │ 與  │  α  0  -α │
     └ -β -α -β ┘     └  β  0  -β ┘

將 mask 和區域的代數描述 做 convolution,分別得到一階導數

      2b(α+2β)   與   2a(α+2β)

把他們分別叫做 Gx, Gy,由於此區域之 gradient 量值為

      √(Gx*Gx + Gy*Gy) = 2(α+2β) * √(a*a+b*b)

當 2(α+2β)=1 時,gradient 才符合標準定義 √(a*a+b*b)
於是求解兩根,得 (α,β) = (1/4, 1/8) = ....
將兩根代回 mask 並乘上 8 轉成整數,便得出 Sobel kernel:
  
     ┌  1   2   1 ┐     ┌  1   0  -1 ┐
     │  0   0   0 │ 與  │  2   0  -2 │
     └ -1  -2  -1 ┘     └  1   0  -1 ┘
這程式分別輸出 horizontal 與 vertical mask 運算的結果。

一般對影像邊緣有 zero padding 與 wrapping 與 omit 3 種料理法,
此處採用省略法。無論用的是何種方法,實際上只能處理中央的
(W-2)*(H-2) 區塊。

int sobelH [3*3] = {-1,-2,-1, 0,0,0, 1,2,1};   //平的
int sobelV [3*3] = {-1,0,1, -2,0,2, -1,0,1};   //直的

template <typename T>      
void edge (T* in, T* out, int w, int h, int* m)    //m = kernel
{
    int c;                  //c = color
    out += (w+1);
    in  += (w+1);
    T* end = out+ (w-2)*h-2;            

    while (out < end) {
        c  = m[0]*in[-w-1]; c += m[1]*in[-w]; c += m[2]*in[-w+1];
        c += m[3]*in[  -1]; c += m[4]*in[ 0]; c += m[5]*in[   1];
        c += m[6]*in[ w-1]; c += m[7]*in[ w]; c += m[8]*in[ w+1];
        if (c < 0)   c = -c; //c/=8;
        if (c > 255) c = 255;
        *out++ = c;
        in++;
    }
}

排序

 
Quick Sort:
template <class T> struct Qsort
{
    T *a, t;
    void swap (int i, int j) {t=a[i]; a[i]=a[j]; a[j]=t;}
    void operator = (T* v)   {a=v;}

    void sort (int L, int R)        //M=midden, L=left, R=right
    {
        if (L >= R) return;               
        int i, M=L;
        swap (L, (L+R)/2)                        
        for (i=L+1; i<=R; ++i)
            if (a[i] < a[L]) 
                swap (++M, i);  
        swap (L, M);        
        sort (L, M-1); 
        sort (M+1, R);
    }
};

int main ()
{
    int i, a[] = {26, 8, 42, 3, 81, 14, 60, 16, 50, 18};
    int n = sizeof a/ sizeof*a - 1;
    Qsort<int> Q; 
    Q = a;
    Q.sort (0, n);
    for (i=0; i<=n; i++) 
        cout <<" " << a[i];
}

巨集

取十進位數的每位數字:

#define DEC(x,n) ((x/(int)1E##n)%10)

int a = 1234;
printf ("%i, %i, %i, %i\n", 
    DEC(a,0), DEC(a,1), DEC(a,2), DEC(a,3));

Fix Point Number

 
Just for reference.
it's non-thread-safe and low-precision design.

struct Fixed
{
    static Fixed m;
    static const int M = 1<<sizeof(int)*4;
    int n;
    Fixed (float i) {n = int(i*M);}
    Fixed operator+ (Fixed f) {m.n = n+f.n; return m;}
    Fixed operator- (Fixed f) {m.n = n-f.n; return m;}
    Fixed operator* (Fixed f) {m.n = int(double(n)*f.n/M); return m;}
    Fixed operator/ (Fixed f) {m.n = int(double(n)*M/f.n); return m;}
    operator float() const {return float(n)/M;}
};

Fixed Fixed::m = 0;

int main ()
{
    Fixed a = 3.1415;
    Fixed b = 271.8281;
    #define _ <<endl<<
    cout _ a+b _ a-b _ a*b _ a/b;
}

萬年曆


int main ()
{
    char* month[] = {
        "January", "Feburary", "March", "Appril", "May", "June",
        "July", "August", "September","Octorbor","November","December"
    };
    int i,p,y, m[] = {1,-2,1,0,1,0,1,1,0,1,0,1};

    cout << "Enter year: "; 
    cin  >> y;
    
    i = y - 1; 
    p = (y + i/4 - i/100 + i/400) % 7;      //算當年1月1日的位置
    
    if (y%4==0 && y%100 || y%400==0) 
        m[1] = -1;

    for (y=0; y<12; y++) 
    {
        cout << "\n------- "<<month[y]<<" -------" 
             << "\n Su Mo Tu We Th Fr Sa\n";

        for (i=p; i--;) cout <<"   ";
        for (i=1; i<=m[y]+30; i++) 
            printf (" %2d%s", i, (p+i)%7? "":"\n");  

        p = (p + m[y] + 30) % 7;
    }
}

數獨


//------------------單行數獨------------------

const int N = 9;
int M[N] = {0,1,0,3,0,8,0,2,5};
int nHole, hole[N*N];

bool bPack (int n)                      //是否可將 n 填入 M 裡
{
    for (int i=0; i<N; i++)             //若 M 中已存在 n
        if (n == M[i]) return false;    //則返回 false
    return true;
}

void fillHole (int pos)                 //將 M 中的空位填滿
{
    int i, x;
    if (pos == nHole) {                 //若空位皆已填滿
        for (i=0; i<N; i++)
            cout << M[i];               //便印出解答
        puts(""); return;               //然後返回
    }
    for (i=1; i<=N; i++) {              //嘗試在 M[x] 處填入 1~N
        x = hole[pos];                  //取得空洞位置
        if (bPack (i)) {                //若可用 i 填起來
            M[x] = i;                   //就令 M[x] = i
            fillHole (pos+1);           //繼續填下一個洞   
            M[x] = 0;                   //將 M[x] 還原, 待以用
        }                               //其他值去嘗試填入
    }
}

int main()
{
    for (int i=0; i<N; i++)
        if (0==M[i])                    //將 M 中 0 的位置
            hole [nHole++] = i;         //記錄在 hole 裡
    fillHole (0);
}

多行的就像這樣....
同理,可擴展至 N*N*N*....N 的解法。

//------------------多行數獨------------------

const int N = 9;

int nHole = 0;
int hole [N*N];

int M[N][N] =
    {0,0,4,0,0,8,0,2,5,
     2,0,0,0,0,0,9,0,0,
     0,0,6,0,0,5,0,0,0,
     5,7,0,0,6,0,0,0,0,
     1,0,0,0,4,0,0,0,8,
     0,0,0,0,2,0,0,3,7,
     0,0,0,3,0,0,8,0,0,
     0,0,7,0,0,0,0,0,1,
     6,2,0,9,0,0,4,0,0};

bool bPack (int x, int y, int n)            //是否可將 n 填入 M[y][x] 裡
{
    for (int i=0; i<N; i++)                 //若 M[0~N-1][x]
        if (n == M[i][x] || n == M[y][i])   //或 M[y][0~N-1] 中已存在 n
            return false;                   //則返回 false
    return true;
}

void fillHole (int pos)                     //將 M 中的空位填滿
{
    int i, x, y;
    if (pos == nHole) {                     //若空位皆已填滿
        for (i=0; i<N*N; i++) {             //便印出解答   
            if (0 == i%N) puts("");         //每印 N 個就換行
            cout << M[0][i];               
        }
        puts(""); getch(); return;          //然後返回
    }
    for (i=1; i<=N; i++) {                  //嘗試在 M[y][x] 處填入 1~N
        y = (x=hole[pos]) / N;              //取得空洞位置 y 座標
        x %= N;                             //取得空洞位置 x 座標
        if (bPack (x,y,i)) {                //若 M[y][x] 可用 i 填起來
            M[y][x] = i;                    //就令 M[y][x] = i
            fillHole (pos+1);               //繼續填下一個洞   
            M[y][x] = 0;                    //將 M[y][x] 還原,
        }                                   //待以用其他值去嘗試填入
    }
}
int main ()
{
    for (int i=0; i<N*N; i++)
        if (0 == M[0][i])                   //將 M 中 0 的位置
            hole [nHole++] = i;             //記錄在 hole 裡
    fillHole (0);
}

外插法


#include <math.h>
   
typedef double S8B;

//輸入: X, Y, n(元素數目), x, 輸出: y, dy(精確度)

void extrapolate (S8B X[], S8B Y[], int n, S8B x, S8B& y, S8B& dy)
{
    S8B  t, d; 
    S8B  dx = fabs (x - X[0]);
    S8B* C  = new S8B[n];
    S8B* D  = new S8B[n];
    int  i, m, ns = 0; 
    dy = y = 0;
   
    for (i=0; i < n; i++)
    {
        d = fabs (x - X[i]);
        if (d == 0) {y = Y[i]; dy=0; return;}
        else if (d < dx) {ns = i; dx = d;}
        C[i] = Y[i];
        D[i] = Y[i] + 1e-25;   //防止下面發生 0/0
    }
    y = Y [ns--];

    for (m=1; m<n; m++) 
    {
        for (i=0; i<n-m; i++)
        {
            t = (X[i]-x) * D[i] / (X[i+m]-x);
            d = t - C[i+1];
            if (d == 0) cout <<"x 處存在極點";
            d = (C[i+1] - D[i]) / d;
            C[i] = d*t;
            D[i] = C[i+1]*d;
        }
        y += (dy = ns+ns+2< n-m? C[ns+1]: D[ns--]);        
    }
    delete[] C;
    delete[] D;
}

int main()
{
    S8B X[] = {1920, 1930, 1940, 1950, 
               1960, 1970, 1980, 1990};
    S8B Y[] = {106.46, 123.08, 123.12, 152.27, 
               180.67, 205.05, 227.23, 249.46};
    S8B y, dy;
    extrapolate (X, Y, 8, 2000, y, dy);
    printf ("y = %lf ± %lf", y, dy);
}

公因公倍數


//-----------------------------------
//     Greatest Common Divisor
//-----------------------------------

//遞歸版

int gcd (int a, int b)  
{  
    return b? gcd (b, a%b): a; 
}

//慢速版,有'減'零風險

int gcd (int a,int b)
{ 
    while (a^b) a>b? a-=b: b-=a;
    return a;
} 

//有'除'零風險

int gcd (int a, int b)
{
    while ((a%=b) && (b%=a));
    return a + b;
}

//遞歸 Stein 算法

int gcd (int a,int b)
{
    static int A, B;
    if (a == 0) return b;
    if (b == 0) return a;
    A = a % 2;
    B = b % 2;
    if (!A && !B) return gcd (a/2, b/2) *2;
    if (A == 0)   return gcd (a/2, b  );
    if (B == 0)   return gcd (a  , b/2); 
    return gcd (abs(a-b), min(a,b));
}

//用位元算

typedef unsigned int U4B;

U4B gcd (U4B a, U4B b)
{ 
    if (!a || !b)     return a|b; 
    if (~a&1 && ~b&1) return gcd (a>>1,b>>1)<<1; 
    if (~a&1 &&  b&1) return gcd (a>>1,b   ); 
    if ( a&1 && ~b&1) return gcd (a   ,b>>1); 
    if (a > b)        return gcd (a-b ,b);  
                      return gcd (b-a ,a); 
}

//非遞歸 Stein 很多地方有快速版,跳略。

//-----------------------------------
//      Least Common Multiple
//-----------------------------------

//套定義

int lcm (int a, int b)
{
    return (a*b) / gcd (a,b);
}

//反向操作

int lcm (int a, int b)
{
    int A = a, B = b;
    while (a^b) 
        a>b ? (a-=b, A+=B): (b-=a, B+=A);
    return (A+B) / 2;
}

//縮成短碼

int lcm (int a, int b)
{
    int c = a*b;
    while (b^=a^=b^=a%=b);
    return c/a;
}

//寫成模版

template <int a, int b> struct Gcd {
    enum {v = Gcd<b,a%b>::v};
};
template <int a> struct Gcd <a,0> {
    enum {v = a};
};
template <> struct Gcd <0,0> {
    enum {v = ~0};
};
template <int a, int b> struct Lcm {
    enum {v = a*b/ Gcd<a,b>::v};
};

猜數字

 
用 VC++ 8.0 以上編譯:

#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <stdio.h>
#include <conio.h>
using namespace std;

int random (int low, int high)
{
   return rand() % (high - low) + low;
}

#define#define#define 吧       ;}
#define 若       ;if(
#define 則       ){
#define 便       ){
#define 且       &&
#define 或       ||
#define 至       ,
#define 當       ;while(   
#define 若是     ;if(
#define 而若     ;}else if(
#define 否則     ;}else
#define 否則便   ;}else{
#define 設有
#define 整數     int
#define 小數     float
#define 讀入     ;cin >>
#define 印出     ;cout <<
#define 介於     random (
#define 主程式   void main()
#define 等待按鍵 ;getch();
#define 進入迴圈 ;while(1)
#define 跳離迴圈 ;break;
#define 間的亂數 );
#define 啟動亂數 ;srand(time(0));


主程式 //猜數字            
{
    設有 整數 n,i

    啟動亂數
    令 n = 介於 1 至 100 間的亂數

    進入迴圈
    {
        印出 "請猜一個介於 0~100 間的整數: "  
        讀入 i
        若是 i>n 便 印出 "太大了!"
        而若 i<n 便 印出 "太小了!"
        否則便 印出 "恭喜您猜中了!" 並 跳離迴圈 吧
    }
    等待按鍵
}

2009年10月30日 星期五

猜拳

 
笨笨的AI:
int main (/* daviddr 081226 */)
{
    int you, com, i,j=0, *k; t[9]={0},p[3]={0};
    char* h = "剪刀\0石頭\0布";
    char* r = "\n平手\0    \n電腦贏了\0\n妳贏了";      
    for (;;p[i]++, t[j*3+you]++, j = you) {
        cout <<"請輸入 (1=剪刀 2=石頭 3=布): ";
        cin  >> you; you--;
        if (you<0 || you>2) break;
        k   = t + j*3;
        com = *k>k[1] && *k>k[2]?1: k[1]<k[2]?0:2;
        cout <<"\nYou: "<< h +you*5;
        cout <<"\nCom: "<< h +com*5;
        i = (3+com-you) % 3;
        puts (r + 10*i);
    }
}

也可將藏鬮視為 non-cooperative 的 zero-sum game,
由於沒有純粹的 Nash equilibrium,故採混合策略以同等機率出
scissors, rock, 或 paper 總獲益較大。

技巧方面:雖然佳士得採用「先出剪刀」策略,
贏得了橋山高吉名畫拍賣會主持權,但那是「一次」且偏理性的賽局。
多次情況下,可嘗試假設以 7+-2 局作為人腦 Memory cache 數,
在此有限記憶下,自行構思 game matrix 進行動態策略機率估算。

開根號

 
算平方根:
inline float sqrt (register float f)
{
    _asm {
        fld f
        fsqrt
        fstp f
    }
    return f;
}

算任意方根:
用 Newton-Raphson 求 root:
將 y = x 的 n 次方
化成 f(r) = r^n - y , r = 初始預測值
令逼近根 r' = r+e,取 Taylor Expansion:

        0 = f (r+e) = f (r) + e*f'(r) + e*e*f"(r)/2 + ...
        0 = f'(r+e) = f'(r) + e*f"(r) + ...

用前兩項來預測:

        f(r) + e*f'(r) = 0
        e = -f(r)/f'(r)

得出新的根
     
        r' = r - f(r)/f'(r)  
寫成 code 便是:
double root (double m, double n)
{      
    for (double x,d,r=m, e=1; e>5e-6; m-=e=(d*m-r)/(n*d))      
        for (d=m, x=1; x<n-1; ++x) d*=m;
    return m;
}

int main (/* daviddr 081225 */)
{
     float x, n;
     scanf ("%f %f", &x, &n);         
     printf ("%f\n", root (x,n));
}

唯讀字串


char *p = "hello world!"; 
    p[0] = 'H'; 
此段程式首先將 p 指向一個唯讀字串 (const char [13]) 的起始位址,
此字串在 VC++ Debug Mode 下,位於記憶體的唯讀區段中,如下所示:
(在 Release Mode 下,某些版本會放在可讀寫的 .DATA 中)
.686P
        .XMM
        .model  flat

CONST   SEGMENT
$SG18132 DB 'hello world!', 00H     ;<-----位於此處
CONST   ENDS

_TEXT   SEGMENT
_main   PROC
        push    ebp
        mov ebp, esp
        push    ecx
        mov DWORD PTR _p$[ebp], OFFSET $SG18132
        mov eax, DWORD PTR _p$[ebp]
        mov BYTE PTR [eax], 72          ;'H'
        xor eax, eax
        mov esp, ebp
        pop ebp
        ret 0
_main   ENDP
_TEXT   ENDS
CONST SEGMENT 對應到的 Page Table Entry,其 R/W 旗標設為 0,
使索引到的內容可讀不可寫,一旦指令變更此段記憶體的內容,
會發生存取違規。

若是用 g++ 編,則會置於唯讀 .rdata 區段
.section .rdata,"dr"
LC0:
    .ascii "hello world!\0"
    .text
    .align 2
.globl _main
    .def    _main;  .scl 2; .type 32;   .endef
_main:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $8, %esp            #播出一塊空間放 p
    movl    $LC0, -4(%ebp)      #p = "hello world!"
    movl    -4(%ebp), %eax      #eax = p
    movb    $72, (%eax)         #p[0] = 'H'
    movl    $0, %eax
    leave
    ret


改成 char p[] = "hello world!"; 
或 char p[] = {"hello world!"}; 後,
程式分配 16Bytes 的堆疊空間給 p[],
並將 "hello world!" 由常數區複印一份到此空間中。
此堆疊區段可讀、可寫、可執行,故之後 p[0]='H' 時,
便不會因寫入常數區段而發生存取違規。 

_TEXT   SEGMENT
        _p$ = -16                        ; size = 13, 對齊 4k 邊界後為 16
_main   PROC
        push    ebp
        mov ebp, esp
        sub esp, 16                      ;挪出可容納 13 Byte 的堆疊空間 
        mov eax, DWORD PTR $SG18132      ;將 eax 指向 $SG18132 開始拷貝字串       
        mov DWORD PTR _p$[ebp], eax      ;拷貝hell
        mov ecx, DWORD PTR $SG18132+4
        mov DWORD PTR _p$[ebp+4], ecx    ;拷貝o wo
        mov edx, DWORD PTR $SG18132+8
        mov DWORD PTR _p$[ebp+8], edx    ;拷貝rld!
        mov al, BYTE PTR $SG18132+12
        mov BYTE PTR _p$[ebp+12], al     ;拷貝\0
        mov BYTE PTR _p$[ebp], 72        ;令 p[0] = 'H'
        xor eax, eax
        mov esp, ebp
        pop ebp
        ret 0
_main   ENDP
_TEXT   ENDS

g++ 下,亦生成類似的拷貝動作,只是拷貝方向不同:
_main:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $40, %esp
    movl    LC0, %eax
    movl    %eax, -24(%ebp)
    movl    LC0+4, %eax
    movl    %eax, -20(%ebp)
    movl    LC0+8, %eax
    movl    %eax, -16(%ebp)
    movzbl  LC0+12, %eax
    movb    %al, -12(%ebp)
    movb    $72, -24(%ebp)
    movl    $0, %eax
    leave
    ret

欲在 Intel 保護模式下存取唯讀區段,可建立一個 segment descriptor,
將第 9 bit 置為 1,再指向該區段,進行分頁存取。

Linux 下可使用 mprotect
#include <sys/mman.h>
#include <limits.h>
.....
if (-1 != mprotect (p, strlen(p), PROT_WRITE)) 
    p[0] = 'H';
Win32 下可使用 VirtualProtect
#include <windows.h>
.....
DWORD oldFlag;
if (VirtualProtect (p, strlen(p), PAGE_READWRITE, &oldFlag))
    p[0] = 'H';

再來比較 "\0" 與 '\0':

\x 是指將 x 映射成 ASCII 或其他指定碼表中索引為 x 的字元。
'\0' 一般被編譯成 .asm 中的常數定字,成為組語指令的「一部份」。

"\0" 則佔有 2 個字元碼寬,位於 Stack 常數保護區中,
其 asm code 視被 assign 的對象以及編譯器類型而有所不同,
Visual Studio 2008 實作方法為:

char b;
    char ch = '0';       //mov  byte ptr [ch],30h 

    char a[] = "\0";     //mov  ax,word ptr ["\0" (428978h)] 
                         //mov  word ptr [a], ax 

    char *p = "\0";      //mov  dword ptr [p], offset "\0" (428978h) 
    char *c;

    c = a;               //lea  eax,[a] 
                         //mov  dword ptr [c],eax 

    c = p;               //mov  eax,dword ptr [p] 
                         //mov  dword ptr [c],eax 

    b = ch;              //mov  al,byte ptr [ch] 
                         //mov  byte ptr ,al 

'\0' 成為定字 0x30,可直接編成機器碼:C6 45 EF 30
此處,array 的配置較 pointer 繁瑣,多了 3 Byte:
array 機器碼:66 A1 78 89 42 00 66 89 45 E0 pointer 機器碼:C7 45 D4 78 89 42 00
但使用上能以較快的微指令來實作 (lea 一般占 1-cycle,
可勝出大部分 mov 家族) 來實作,故速度較快。

魔方陣

 
N 階奇數魔方陣:
void magic (int n)
{   
    int m [9*9] = {0};
    int i=0, o=n-1, r=0, c=n/2;

    while (i < n*n) {
        m [r*n+c] = ++i; 
        i%n? (r?--r:r=o), c-o?++c: c=0: ++r;
    }
    while (i--) 
        printf ("%3d%c", m[i], i%n?' ':'\n');  
    puts ("");                              
}

int main (/* daviddr 081224 */)
{    
    return magic(5), getch();
}

針對(2k+1)*(2k+1)方陣,傳統製作方法是: 1. 以 (k,0) 做為起點。 ┌─┬─┬─┐ │ │1│ │ ├─┼─┼─┤ │ │ │ │ ├─┼─┼─┤ │ │ │ │ └─┴─┴─┘ 2. 朝右上方移動 (令x++,y--),遇到邊緣則繞捲。 ┌─┬─┬─┐ │ │1│ │ ├─┼─┼─┤ │ │ │ │ ├─┼─┼─┤ │ │ │2│ (2由上往下繞捲到此處) └─┴─┴─┘ ┌─┬─┬─┐ │ │1│ │ ├─┼─┼─┤ │3│ │ │ (3由右往左繞捲到此處) ├─┼─┼─┤ │ │ │2│ └─┴─┴─┘ 3. 當(x,y)處的右上方已有數字時,便往下放在(x,y+1) 放置時遇到邊緣則繞捲。 ┌─┬─┬─┐ │ │1│ │ ├─┼─┼─┤ │3│ │ │ ├─┼─┼─┤ │4│ │2│ └─┴─┴─┘ 4. 重複此法填到最後一個數字。

簡易電子琴

 
按 zxcvbnmasdfghjqwertyu 發音,
按 0~7 變更樂器,樂器種類可在 prog[] 裡自行變更。
樂器編號有點忘了,印象中是 0~127,可自行改變。
有些樂器如法國號等,聲音很吵,拉的很長,這部分程式未做處理;
pitchs[] = {0,2,4,5,7,9,11} 用來跳過 {1,3,6,8,10}
等 5 筆黑鍵音,因為鍵盤的編排很難將黑鍵安插進來。
#pragma comment(lib, "winmm.lib")
#include <conio.h>  
#include <stdio.h>  
#include <windows.h>
#include <mmsystem.h>

#define DO(s) if (MMSYSERR_NOERROR != s) {\
            printf ("Error in %s: %d",__FILE__,__LINE__);\
            getch(); exit(1);\
        }

HMIDIOUT midi;   

void play (int state, int d1=0, int d2=0)
{
    UCHAR data[4] = {state, d1, d2, 0};
    DO (midiOutShortMsg (midi, *(DWORD*)data));            
}

UCHAR get_pitch (char ch)
{
    static char *p, key[] = "zxcvbnmasdfghjqwertyu";
    static UCHAR pitchs[] = {0,2,4,5,7,9,11};
    for (p=key; *p && ch^*p; ++p);
    return (60-12) + 12*((p-key)/7) + pitchs [(p-key)%7];
}
int main (/* daviddr 081223 */)
{
    int  ch, prog[] = {0,13,24,15,7,73,46,53}; //樂器編號
    DO (midiOutOpen (&midi, 0,0,0, CALLBACK_NULL));
    while (VK_ESCAPE != (ch = getch()))         
        if ('0'<=ch && ch<='7') 
            play (0xC0, prog[ch-'0']);
        else {
            play (0x80); 
            play (0x90, get_pitch(ch), 100);
        }         
    midiOutReset (midi);
    midiOutClose (midi);
    return 0;
}

影片播放器


#pragma comment (lib, "comctl32.lib") 
#pragma comment (lib, "dxguid.lib")
#pragma comment (lib, "strmiids.lib")
#ifndef UNICODE
#define UNICODE
#endif
#define daviddr 090430
#include <windows.h>
#include <commctrl.h>
#include <dshow.h>

#include <cstdio>
extern"C" WINBASEAPI HWND WINAPI GetConsoleWindow();
#define MsgBox(s) MessageBox (0,s,0,MB_OK)

WCHAR e_str[256];
void cdecl MsgBox_ (wchar_t* fmt, ...)
   {swprintf_s (e_str, 256, fmt, (char*)(&fmt+1)); MsgBox(e_str);}

namespace FileDlg
{
    WCHAR title[256] = L"*.*";
    WCHAR filter[256] = 
        L"AVI File (*.avi)\0*.avi\0"   
        L"MPEG File (*.mpg)\0*.mpg\0"   
        L"Mp3 File (*.mp3)\0*.mp3\0"   
        L"Wave File (*.wav)\0*.wav\0"   
        L"All Files (*.*)\0*.*\0\0";
    WCHAR file_name[512], init_dir[512], exe_path[512]={0}, *fname;
    OPENFILENAME ofn = {
            sizeof(OPENFILENAME), 0, 0, (LPCWSTR)filter,0,0,1, title, 
            512, file_name, 512, init_dir, 0, 6, 0,1, L"", 0,0,0
    };
    LPWSTR open (HWND hwnd)
    {
        ofn.hwndOwner    = hwnd;
        ofn.lpstrTitle   = L"開檔"; 
        ofn.lpstrFilter  = filter;
        ofn.Flags        = 6; 
        ofn.lpstrFile[0] = 0;               //若開檔後仍為0表示按了[Cancel]

        if (!GetOpenFileName (&ofn)) { 
            if(*ofn.lpstrFile) 
                MsgBox_ (L"Fail to open: %d", CommDlgExtendedError()); 
            return 0;
        }
        return fname = ofn.lpstrFile;       //取個短名字        
    }
}


#define DO(b) if (FAILED(b)) \
              {MsgBox_(L"fail in %s line %d",__FILE__,__LINE__);}


struct Player
{
    bool bPlaying; 
    long evCode;
    LONGLONG pos, duration;           
    IMediaEvent*   pEvent;
    IGraphBuilder* pGraph;
    IMediaControl* pCtrl;
    IVideoWindow*  pVideo;
    IMediaSeeking* pSeek;

    void init()
    {
        bPlaying = false;
        DO (CoCreateInstance (CLSID_FilterGraph, 0, CLSCTX_INPROC, 
                        IID_IGraphBuilder, (void**) &pGraph));
        DO (pGraph->QueryInterface (IID_IMediaControl, (void**) &pCtrl));
        DO (pGraph->QueryInterface (IID_IVideoWindow,  (void**) &pVideo));
        DO (pGraph->QueryInterface (IID_IMediaEvent,   (void**) &pEvent));
        DO (pGraph->QueryInterface (IID_IMediaSeeking, (void**) &pSeek));
    }
    void free()
    {
        if (bPlaying) {
            setTimeInfo (0);
            pCtrl->Stop();
        }
        pVideo->put_Visible (OAFALSE);
        pVideo->put_Owner (0);
        pSeek->Release();
        pCtrl->Release();
        pGraph->Release();        
    }
    void run (WCHAR* path, HWND hwnd)
    {
        bPlaying = true;
        DO (pGraph->RenderFile (path, 0));
        DO (pVideo->put_Owner ((OAHWND)hwnd));
        resize (hwnd);
        DO (pCtrl->Run());
    }
    void resize (HWND hwnd)
    {
        if (!bPlaying) return;
        RECT rc; GetClientRect (hwnd, &rc);
        DO (pVideo->put_WindowStyle (WS_CHILD| WS_CLIPSIBLINGS));
        DO (pVideo->SetWindowPosition (0, 0, rc.right, rc.bottom-20));
    }
    void getTimeInfo()
    {
        pSeek->GetCurrentPosition (&pos);
        pSeek->GetDuration (&duration);   
    }
    void setTimeInfo (double pos_)
    {
        LONGLONG duration = 1;
        pSeek->GetDuration (&duration);
        duration *= pos_;
        pSeek->SetPositions (&duration,
            AM_SEEKING_AbsolutePositioning,
            NULL, AM_SEEKING_NoPositioning);
    }
    void pause (bool b) {b?pCtrl->Pause():pCtrl->Run();}
};

//-------------------------- 主程式 -------------------------------

HINSTANCE  e_hInst;

LRESULT CALLBACK WndProc (HWND hwnd, UINT msg, WPARAM wParam, LPARAM lParam)
{
    static enum {ID_TIMER, ID_OPEN, ID_PAUSE, ID_SLIDER};
    static bool bPause;
    static int w,h;
    static Player player;
    static HMENU  hMenu;  
    static HWND   hSlider;             //scroll handle
    
    switch (msg)
    {
      case WM_CREATE:
           hMenu = (HMENU) CreateMenu();
           AppendMenu (hMenu, MF_STRING, ID_OPEN,  L"開檔");
           AppendMenu (hMenu, MF_STRING, ID_PAUSE, L"暫停");
           SetMenu (hwnd, hMenu);
           hSlider = CreateWindow (TRACKBAR_CLASS, L"",
                     WS_CHILD| WS_VISIBLE| TBS_AUTOTICKS, 216,4,256,16,
                     hwnd, (HMENU)ID_SLIDER, e_hInst, 0);
           SendMessage (hSlider, TBM_SETRANGE, TRUE, MAKELONG(1,1000));
           SendMessage (hSlider, TBM_SETPOS, TRUE, 1);
           return 0;

      case WM_CLOSE:           
           if (player.bPlaying) {
               player.free();
               KillTimer (hwnd, ID_TIMER);                   
           }
           PostQuitMessage(0);
           return 0;  

      case WM_SIZE:
           player.resize (hwnd);
           w = LOWORD (lParam);
           h = HIWORD (lParam);
           MoveWindow (hSlider, 2, h-20, w-4, 20, TRUE);     
           return 0;

      case WM_KEYDOWN:
           switch (wParam) {
             case VK_ESCAPE: SendMessage (hwnd, WM_CLOSE, 0, 0); break;
             case VK_RETURN: player.pause (bPause = !bPause); break;
           }
           return 0;

      case WM_HSCROLL:
           player.setTimeInfo (
               double(SendMessage (hSlider, TBM_GETPOS, 0, 0))/1000);
           return 0;

      case WM_TIMER:
           player.getTimeInfo();
           SendMessage (hSlider, TBM_SETPOS, TRUE,
               player.pos * 1000 / player.duration);
           return 0;

      case WM_COMMAND:
           if (ID_OPEN == LOWORD(wParam)) {           
               if (FileDlg::open (hwnd)) {               //若開檔成功
                   if (player.bPlaying) {                //關閉計時器
                       player.free();
                       KillTimer (hwnd, ID_TIMER);
                   }
                   bPause = false;
                   swprintf_s (e_str, L"%s", FileDlg::fname);
                   SetWindowText (hwnd, e_str);   
                   player.init();           
                   player.run (FileDlg::fname, hwnd);
                   SetTimer (hwnd, ID_TIMER, 20, 0);     //啟動計時器
               }    
           }else if (ID_PAUSE == LOWORD(wParam))           
               player.pause (bPause = !bPause);
           return 0;
          
      default: return  DefWindowProc (hwnd, msg, wParam, lParam);
    }
    return 0;          
}

int WINAPI WinMain (HINSTANCE hInst, HINSTANCE, PSTR, int nShow)
{
    CoInitialize (0);            
    WNDCLASSEX wc = {0x30,3,WndProc,0,0,hInst,0,0,(HBRUSH)1,0,L"DS",0};
    if (!RegisterClassEx(&wc)) return 0;  
    HWND hwnd = CreateWindow (L"DS",L"Player",
        13565952,100,50,560,500,0,0,hInst,0);
    if (!hwnd) return 0;  
    e_hInst = hInst;
    MSG msg; ShowWindow (hwnd, nShow);
    while (GetMessage (&msg, 0,0,0)) {
        TranslateMessage (&msg);
        DispatchMessage (&msg);
    }
    CoUninitialize();
    return msg.wParam;
}

OOXX

 
無 AI 版本,在框框內按滑鼠左鍵落子。
#include <windows.h>
#include <stdio.h>
extern "C" WINBASEAPI HWND WINAPI GetConsoleWindow();

int main (/* 090701 */)
{
    short pos, x, y, ch = 0, rnd = 0, c[11] = {0}; 
    short win[] = {7,56,73,84,146,273,292,448,0}, *w;
    char  map[] = "□ □ □\n□ □ □\n□ □ □";
    COORD coor  = {0,0};        
    POINT p; puts (map); 
   
    while (rnd < 9) {
        GetCursorPos (&p);
        ScreenToClient (GetConsoleWindow(), &p);
        pos = (x=p.x-2)/21 + ((y=p.y-2)/15)*3;
        if (x<0 || x>60 || y<0 || y>42 || c[pos] ||
            GetAsyncKeyState (1)>=0) continue;
        SetConsoleCursorPosition 
            (GetStdHandle (STD_OUTPUT_HANDLE), coor);
        map[pos*3]   = "○╳"[ch*2  ];
        map[pos*3+1] = "○╳"[ch*2+1];
        puts (map);
        c[ch+9] |= (c[pos] = 1) << pos;
        for (w=win; *w; *w==(c[ch+9]&*w)? rnd=99, w=win+8: w++);                
        if (rnd != 99) ch = !ch, rnd++;
    }
    system ("pause"+ !printf (9==rnd? "\n平手":"\n%c 獲勝", "OX"[ch]));
}

彈跳球



#undef  UNICODE
#undef _UNICODE
#pragma comment (lib, "msimg32.lib")
#define daviddr_2009_7_1

#include <windows.h>
#include <cmath>
#include <time.h>
#define ID_TIMER 1

const int cW = 640, cH = 480;           //記錄視窗真實邊界

int bW = cW - 2*GetSystemMetrics (SM_CXSIZEFRAME); 
int bH = cH - 2*GetSystemMetrics (SM_CYSIZEFRAME)-
                GetSystemMetrics (SM_CYCAPTION);                  
HDC hdcMem;

struct Ball
{
    COLORREF c;
    float x, y, vx, vy, r;

    float vlen() {
        return sqrt (vx*vx + vy*vy);
    }
    void draw() {
        SetDCBrushColor (hdcMem, c);
        Ellipse (hdcMem, x-r, y-r, x+r, y+r);
    }
    void move() {                    
        x += vx;  y += vy;
        if (x<=r)   x=r+1,  vx=-vx; 
        if (x>bW-r) x=bW-r, vx=-vx;
        if (y<=r)   y=r+1,  vy=-vy;  
        if (y>bH-r) y=bH-r, vy=-vy;            
    }
}; 

void collide_test (Ball& a, Ball& b)
{
    if (&a == &b) return;                   //不可能和自身碰撞
    float dot, 
          dx = b.x-a.x, 
          dy = b.y-a.y,
          r  = a.r + b.r, 
          d  = dx*dx + dy*dy;

    if (d < r*r && (d = sqrt (d)) &&         
        0 < (dx*a.vx + dy*a.vy)/(a.vlen()*d)){
        dx /= d; 
        dy /= d;      
        dot = b.vx*dx - a.vx*dx + b.vy*dy - a.vy*dy;
        dx *= dot; 
        dy *= dot;
        a.vx += dx; a.vy += dy;  
        b.vx -= dx; b.vy -= dy;        
    }
}


LRESULT CALLBACK WndProc (HWND hwnd, UINT msg, WPARAM wParam, LPARAM lParam)
{
    static PAINTSTRUCT ps;
    static HBITMAP     hBmp;
    static HDC         hdc;
    static int i, j;
    static const int DELAY = 16;
    static const int nBall = 22;
    static Ball ball[nBall];
    static GRADIENT_RECT grect = {0,1};
    #define RC (rand()%256)<<8 
    static TRIVERTEX vtx[2] = {{0,0,RC,RC,RC,0},{bW,bH,RC,RC,RC,0}};
    
    switch (msg) 
    {
       case WM_CREATE:    
            hdc    = GetDC (hwnd);
            hdcMem = CreateCompatibleDC (hdc);
            hBmp   = CreateCompatibleBitmap (hdc, cW, cH);
            ReleaseDC (hwnd, hdc);
            SelectObject (hdcMem, hBmp);
            DeleteObject (hBmp);
            SelectObject (hdcMem, GetStockObject(DC_BRUSH));
            SetTimer (hwnd, ID_TIMER, DELAY, 0);
            for (i=0; i<nBall; ++i) {
                ball[i].c  = RGB(rand()%256,rand()%256,rand()%256);
                ball[i].x  = rand()%cW;
                ball[i].y  = rand()%cH;
                ball[i].r  = 10+rand()%36;
                ball[i].vx = float (4+rand()%8);
                ball[i].vy = float (4+rand()%8);                
            }
            return 0;
            
       case WM_DESTROY:
            KillTimer (hwnd, ID_TIMER);
            DeleteDC (hdcMem);
            PostQuitMessage (0);
            return 0; 
            
       case WM_PAINT:
            hdc = BeginPaint (hwnd, &ps);
            GradientFill (hdcMem, vtx, 2, &grect, 1, 1);
            for (i=0; i<nBall; ++i) ball[i].draw();
            BitBlt (hdc, 0,0, cW, cH, hdcMem, 0,0, SRCCOPY);
            EndPaint (hwnd, &ps);
            return 0; 
    
       case WM_TIMER:       
            for (i=0; i<nBall; ++i) {
                ball[i].move(); 
                for (j=0; j<nBall; ++j)
                    collide_test (ball[i], ball[j]);
            }
            InvalidateRect (hwnd, 0, false);
            return 0;
    }
    return DefWindowProc (hwnd, msg, wParam, lParam);    
}

int WINAPI WinMain (HINSTANCE hInst, HINSTANCE, PSTR, int nShow)
{
    srand ((UINT)time(0));            
    WNDCLASSEX wc = {0x30,3,WndProc,0,0,hInst,0,0,(HBRUSH)1,0,"T",0};
    if (!RegisterClassEx(&wc)) return 0; 
    HWND hwnd = CreateWindow ("T"," ",13565952,100,50,cW,cH,0,0,hInst,0);
    if (!hwnd) return 0;  
    MSG msg;  
    ShowWindow (hwnd, nShow);
    while (GetMessage (&msg, 0,0,0)) {
        TranslateMessage (&msg);
        DispatchMessage (&msg);
    }
    return msg.wParam;
}