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 便 印出 "太小了!"
        否則便 印出 "恭喜您猜中了！" 並 跳離迴圈 吧
    }
    等待按鍵
}

猜拳

　
笨笨的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 進行動態策略機率估算。