這是 24 game 的 app ，可以玩玩看~
https://play.google.com/store/apps/details?id=com.thunyasit.game24&hl=zh_TW
這是 24 game 桌遊版的網站~
https://www.24game.com/
以下要開始破壞遊戲體驗啦XD
一、24 Game 簡介
24點遊戲是一種使用撲克牌來進行的益智類遊戲，遊戲內容是：從一副撲克牌中抽去大小王剩下52張，任意抽取4張牌，把牌面上的數（A代表1）運用加、減、乘、除和括號進行運算得出24。每張牌都必須使用一次，但不能重複使用。
有些組合有不同種算法，例如2，4，6，Q四張牌可用 2 + 4 + 6 + 12 = 24 或 4 × 6 ÷ 2 + 12 = 24 或 12 ÷ 4 × (6 + 2) = 24等來求解。也有些組合算不出24，如1、1、1、1 和 6、7、8、8等組合。
二、Expression Tree and postfix notation
因為要用 expression tree 列出各種情況，所以在此先介紹一下 expression tree ，順便介紹 postfix notation，雖然24 game沒用到XD
一個運算式很自然地可以畫成一棵樹, 叫做 expression tree 運算式樹。
每個運算子在離開開節點時才寫出來的運算式，叫做 postfix notation。
postfix notation 具有以下性質：
- 不需要小括弧。
- 程式求運算式值容易處理。(使用一個 stack)
- 遇到運算元就 push
- 遇到一個 n 元運算子就做 n 次 pop 並計算
- 將計算結果 push 回去
下面是一個程式的範例：
postfix.cpp
/* * C++ Program to Construct an Expression Tree for a Given Prefix Expression */ #include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> using namespace std; class TreeNode { public: char data; TreeNode *left, *right; TreeNode(char data) { this->data = data; this->left = NULL; this->right = NULL; } }; class StackNode { public: TreeNode *treeNode; StackNode *next; StackNode(TreeNode *treeNode) { this->treeNode = treeNode; next = NULL; } }; class ExpressionTree { private: StackNode *top; public: ExpressionTree() { top = NULL; } void clear() { top = NULL; } void push(TreeNode *ptr) { if (top == NULL) top = new StackNode(ptr); else { StackNode *nptr = new StackNode(ptr); nptr->next = top; top = nptr; } } TreeNode *pop() { if (top == NULL) { cout<<"Underflow"<<endl; TreeNode *ptr = NULL; return ptr; } else { TreeNode *ptr = top->treeNode; top = top->next; return ptr; } } TreeNode *peek() { return top->treeNode; } void insert(char val) { if (isDigit(val)) { TreeNode *nptr = new TreeNode(val); push(nptr); } else if (isOperator(val)) { TreeNode *nptr = new TreeNode(val); nptr->left = pop(); nptr->right = pop(); push(nptr); } else { cout<<"Invalid Expression"<<endl; return; } } bool isDigit(char ch) { return ch >= '0' && ch <= '9'; } bool isOperator(char ch) { return ch == '+' || ch == '-' || ch == '*' || ch == '/'; } int toDigit(char ch) { return ch - '0'; } void buildTree(string eqn) { for (int i = eqn.length() - 1; i >= 0; i--) insert(eqn[i]); } double evaluate() { return evaluate(peek()); } double evaluate(TreeNode *ptr) { if (ptr->left == NULL && ptr->right == NULL) return toDigit(ptr->data); else { double result = 0.0; double left = evaluate(ptr->left); double right = evaluate(ptr->right); char op = ptr->data; switch (op) { case '+': result = left + right; break; case '-': result = left - right; break; case '*': result = left * right; break; case '/': result = left / right; break; default: result = left + right; break; } return result; } } void postfix() { postOrder(peek()); } void postOrder(TreeNode *ptr) { if (ptr != NULL) { postOrder(ptr->left); postOrder(ptr->right); cout<<ptr->data; } } void infix() { inOrder(peek()); } void inOrder(TreeNode *ptr) { if (ptr != NULL) { inOrder(ptr->left); cout<<ptr->data; inOrder(ptr->right); } } void prefix() { preOrder(peek()); } void preOrder(TreeNode *ptr) { if (ptr != NULL) { cout<<ptr->data; preOrder(ptr->left); preOrder(ptr->right); } } }; int main() { string s; cout<<"Expression Tree Test"<<endl; ExpressionTree et; cout<<"\nEnter equation in Prefix form: "; cin>>s; et.buildTree(s); cout<<"\nPrefix : "; et.prefix(); cout<<"\n\nInfix : "; et.infix(); cout<<"\n\nPostfix : "; et.postfix(); cout<<"\n\nEvaluated Result : "<<et.evaluate(); return 0; }
input
+-+7*/935/82*/625
output
Expression Tree Test
Enter equation in Prefix form: +-+7*/935/82*/625
Prefix : +-+7*/935/82*/625
Infix : 7+9/3*5-8/2+6/2*5
Postfix : 793/5*+82/-62/5*+
Evaluated Result : 33
三、卡塔蘭數
給定了數字和可能的算子，我們很容易有疑問：「要列出幾種可能呢？」，卡塔蘭數給了我們一些啟發，可以知道有三個算子時的排列數目。當然還有「加乘」數字顛倒情況相同，「減除」數字顛倒情況不同等細部情況。因此，最後我們會用button-up遞迴列舉的方式去解這個問題。
卡塔蘭數的一般項公式為：
$C_n = \frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{(n+1)!n!}$
- n個資料執行stack permutation，其合法的排列組合個數為多少?
- Cn表示長度2n的dyck word的個數。Dyck word是一個有n個X和n個Y組成的字串，且所有的前綴字串皆滿足X的個數大於等於Y的個數。以下為長度為6的dyck words:
- XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
- 將上例的X換成左括號，Y換成右括號，Cn表示所有包含n組括號的合法運算式的個數：
- ((())) ()(()) ()()() (())() (()())
- Cn表示有n個節點組成不同構二元樹的方案數。下圖中，n等於3，圓形表示節點，月牙形表示什麼都沒有。
證明
令1表示進stack，0表示出stack，則可轉化為求一個2n位 (含n個1、n個0) 的二進位數，滿足從左往右掃到任意一位時，經過的0數不多於1數。顯然含n個1、n個0的2n位二進位數共有${2n \choose n}$ 個，下面考慮不滿足要求的數目。
考慮一個含n個1、n個0的2n位二進位數，掃描到第2m+1位上時有m+1個0和m個1（容易證明一定存在這樣的情況），則後面的0-1排列中必有n-m個1和n-m-1個0。將2m+2及其以後的部分0變成1、1變成0，則對應一個n+1個0和n-1個1的二進位數。反之亦然（相似的思路證明兩者一一對應）。
從而
$C_n = {2n \choose n} - {2n \choose n + 1} = \frac{1}{n+1}{2n \choose n}$。
證畢。
[用心去感覺] 不越過對角線的單調路徑的個數
我覺得最好理解上面證明的方法是下面這個例子，是完全對應的：
Cn表示所有在n × n格點中不越過對角線的單調路徑的個數。一個單調路徑從格點左下角出發，在格點右上角結束，每一步均為向上或向右。計算這種路徑的個數等價於計算Dyck word的個數：X代表「向右」，Y代表「向上」。
下圖為n = 4的情況：
四、程式碼：24 game 解答
這份網路上的程式碼真的很精銳！各種指標、遞迴，struct也包得很漂亮，值得細細地觀賞，主要採用button-up遞迴列舉的方式列出所有的樹，每生出一棵樹就去檢驗有沒有等於24，有的話就傳給印出的函式打印答案。
#include <stdio.h> #include <stdlib.h> #include <time.h> #define n_cards 4 #define solve_goal 24 #define max_digit 13 typedef struct { int num, denom; } frac_t, *frac; typedef enum { C_NUM = 0, C_ADD, C_SUB, C_MUL, C_DIV } op_type; typedef struct expr_t *expr; typedef struct expr_t { op_type op; expr left, right; int value; } expr_t; void show_expr(expr e, op_type prec, int is_right) { const char * op; switch(e->op) { case C_NUM: printf("%d", e->value); return; case C_ADD: op = " + "; break; case C_SUB: op = " - "; break; case C_MUL: op = " x "; break; case C_DIV: op = " / "; break; } if ((e->op == prec && is_right) || e->op < prec) printf("("); show_expr(e->left, e->op, 0); printf("%s", op); show_expr(e->right, e->op, 1); if ((e->op == prec && is_right) || e->op < prec) printf(")"); } void eval_expr(expr e, frac f) { frac_t left, right; if (e->op == C_NUM) { f->num = e->value; f->denom = 1; return; } eval_expr(e->left, &left); eval_expr(e->right, &right); switch (e->op) { case C_ADD: f->num = left.num * right.denom + left.denom * right.num; f->denom = left.denom * right.denom; return; case C_SUB: f->num = left.num * right.denom - left.denom * right.num; f->denom = left.denom * right.denom; return; case C_MUL: f->num = left.num * right.num; f->denom = left.denom * right.denom; return; case C_DIV: f->num = left.num * right.denom; f->denom = left.denom * right.num; return; default: fprintf(stderr, "Unknown op: %d\n", e->op); return; } } int solve(expr ex_in[], int len) { int i, j; expr_t node; expr ex[n_cards]; frac_t final; if (len == 1) { eval_expr(ex_in[0], &final); if (final.num == final.denom * solve_goal && final.denom) { show_expr(ex_in[0], C_NUM, 0); return 1; } return 0; } for (i = 0; i < len - 1; i++) { for (j = i + 1; j < len; j++) ex[j - 1] = ex_in[j]; ex[i] = &node; for (j = i + 1; j < len; j++) { node.left = ex_in[i]; node.right = ex_in[j]; node.op = C_ADD; if (solve(ex, len - 1)) return 1; node.op = C_SUB; if (solve(ex, len - 1)) return 1; node.op = C_MUL; if (solve(ex, len - 1)) return 1; node.op = C_DIV; if (solve(ex, len - 1)) return 1; node.left = ex_in[j]; node.right = ex_in[i]; node.op = C_SUB; if (solve(ex, len - 1)) return 1; node.op = C_DIV; if (solve(ex, len - 1)) return 1; ex[j] = ex_in[j]; } ex[i] = ex_in[i]; } return 0; } int solve24(int n[]) { int i; expr_t ex[n_cards]; expr e[n_cards]; for (i = 0; i < n_cards; i++) { e[i] = ex + i; ex[i].op = C_NUM; ex[i].left = ex[i].right = 0; ex[i].value = n[i]; } return solve(e, n_cards); } int main() { int i, j, n[] = { 3, 3, 8, 8, 9 }; srand(time(0)); for (j = 0; j < 10; j++) { for (i = 0; i < n_cards; i++) { n[i] = 1 + (double) rand() * max_digit / RAND_MAX; printf(" %d", n[i]); } printf(": "); printf(solve24(n) ? "\n" : "No solution\n"); } return 0; }
有趣的是 10 個 1~99 的數字湊 24 答案竟然幾乎瞬間給出，這個效率也太好了XD
References
wiki - 24 點
https://zh.wikipedia.org/wiki/24%E7%82%B9
運算式 - 運算式/運算子/運算元/優先順序
http://user.frdm.info/ckhung/b/pr/expression.php
wiki - 卡塔蘭數
https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0
Problem Solving with Algorithms and Data Structures
http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html
rosettacode 24 - game/Solve
http://rosettacode.org/wiki/24_game/Solve#C.2B.2B
發表文章
