數字與遊戲On Numbers and Games(PPT-40).ppt

數字與遊戲On Numbers and Games 澎湖科技大學-資訊管理系 高國元 內容大綱 數字的誕生 數字和零的關係 二元樹遊戲 二元樹的加法運算 結論 數字的誕生 很久很久以前，在山上住著一位老農夫和一位放羊的孩子。 … 他們從生活的需求過程中，定義了數字的符號。 … 這些符號成為他們溝通的工具。 數字的誕生【 0 】 我們需要一個符號來代表「沒有」。 數字的誕生【 1 】 從「沒有」到「有」 ，我們需要一個新的符號。 數字的誕生【 2 】 我們需要一個新的符號來代表比 1 還要多的量。 數字的誕生【 3 】 我們需要一個新的符號來代表比 2 還要多的量。 數字的誕生【 n 】 下面這個符號代表多少？ 數字的誕生【 -n 】 有些日子裡，我們不得不欠錢 … 數字的誕生【 1/2 】 有個量比 0 還要多、比 1 還要少。 數字的誕生【 1/4 】 有個量比 0 還要多、比 1/2 還要少。 數字的誕生【 3/4 】 有個量比 1/2 還要多、比 1 還要少。 數字的誕生【 d 】 下面這個符號代表多少？ 數字的誕生【 d 】 下面這個符號代表多少？ 數字的誕生【 -d 】 把每個量d左右反轉，就可以得到-d。 數字的誕生【 觀察 】 數字的誕生有先後順序。 每個數字的符號長的像一顆二元樹。 有些二元樹不是我們所熟知的數字。 數字和零的關係【 ≧0 , ≦0 , ≡0 , || 0】 d ≧ 0, 若且唯若 d 沒有 ≦0 的右子樹。 d ≦ 0, 若且唯若 d 沒有 ≧0 的左子樹。 d ≡ 0, 若且唯若 d ≧0 且 d ≦0 。 d ＞ 0, 若且唯若 d ≧0 且 d !≡0 。 d ＜ 0, 若且唯若 d ≦0 且 d !≡0 。 d || 0, 若且唯若以上三者皆非。 數字和零的關係【 無聊的証明】 0 ≧0 0 ≦0 0 ≡0 數字和零的關係【 無聊的証明】 1 ＞0 2 ＞0 3 ＞0 … 數字和零的關係【 無聊的証明】 -1 ＜ 0 -2 ＜ 0 -3 ＜ 0 … 數字和零的關係【 無聊的証明】 1/2 ＞ 0 1/4 ＞ 0 3/4 ＞ 0 … 數字和零的關係【 無聊的証明】 ??? !≧ 0 ??? !≦ 0 ??? !≡ 0 ??? || 0 二元樹遊戲【 規則一】 有二個對局者，分別為左方及右方。 任意給定一個二元樹。 輪到左方下着手時，左方需由二元樹的根節點移往左子樹。然後遊戲從左子樹開始，繼續由右方着手。 輪到右方下着手時，右方需由二元樹的根節點移往右子樹。然後遊戲從右子樹開始，繼續由左方着手。 無法着手者為敗方。 二元樹遊戲【 範例】 二元樹遊戲【 勝負結果】 每個二元樹 對局的可能結果共有四種類型： 左方獲勝(無論先着或後着) 。 右方獲勝(無論先着或後着) 。 雙方先着者落敗。 雙方先着者獲勝。 二元樹遊戲【 結果推論】 每個二元樹 T 代表一個量，對局結果可由T 與0 的關係推論。 左方獲勝。 T ＞ 0 右方獲勝。 T ＜ 0 雙方先着者落敗。 T ≡ 0 雙方先着者獲勝。 T || 0 二元樹遊戲【典型範例 - Nim】 二元樹遊戲【典型範例 - Domineering 】 二元樹遊戲【典型範例 - Go】 二元樹遊戲【 規則二】 有二個對局者，分別為左方及右方。 任意給定 n 個二元樹。 輪到左方下着手時，左方需選擇一個二元樹由根節點移往左子樹。然後遊戲從左子樹開始，繼續由右方着手。 輪到右方下着手時，右方需選擇一個二元樹由根節點移往右子樹。然後遊戲從右子樹開始，繼續由左方着手。 無法着手者為敗方。 二元樹的加法運算【 符號說明】 若 G 為一個二元樹，則 GL 代表 G 的左子樹集合， GR 代表 G 的右子樹集合， G 可表示為 {GL | GR} 。 二元樹的加法運算【 定義】 若 G, H 為二元樹，則 G + H = {GL + H, G + HL | GR + H, G + HR} 二元樹的等價關係【 定義】 G ≧ H, 若且唯若 G -H ≧ 0 。 G ≦ H, 若且唯若 G -H ≦ 0 。 G ≡ H, 若且唯若 G ≧ H 且 G ≦ H 。 G ＞ H, 若且唯若 G ≧ H 且 G !≡ H 。 G ＜ H, 若且唯若 G ≦ H 且 G !≡ H 。 G || H, 若且唯若以上三者皆非。 二元樹的加法運算【 特性】 G + 0 ≡ G G + -G ≡ 0 G + H ≡ H + G (G + H) + K = G + (H + K) 二元樹的加法運算【 結論】 所有的二元樹所成的集合，搭配加法算， 形成一個完整的代數群結構。 二元樹的加法運算【 0 + 0 = 0】 證