Microsoft Word - ACL chapter00a-1ed .doc

Size: px

Start display at page:

Download "Microsoft Word - ACL chapter00a-1ed .doc"

矶氏妆寿
5 years ago
Views:

1 序三 A* Wi-Fi RLE RSA - v -

2 前言 NPC Horner s rule DOS PCX RLE RSA - - vii -

3 演算法的樂趣 O(n) O(n 2 ) O(n) O(n) MP3 - viii -

4 前言 ix -

5 第 8 章愛因斯坦的思考題 Pall Mall 7. Dunhill 8. 9.

6 演算法的樂趣 10. Blends 11. Dunhill 12. BlueMaster 13. Prince Blends 表 8-1 愛因斯坦思考題推理結果房子顏色國籍飲料寵物煙黃色挪威水貓 Dunhill 藍色丹麥茶馬 Blends 紅色英國牛奶鳥 PallMall 綠色德國咖啡魚 Prince 白色瑞士啤酒狗 BlueMaster

7 第 8 章愛因斯坦的思考題基本模型定義 typedef struct tagitem ITEM_TYPE type; int value; }ITEM; ITEM_TYPE value type value 0 4 type 0 4 type value 0 4 type value group group

8 演算法的樂趣 typedef struct taggroup ITEM items[groups_items]; }GROUP; items items type items items[i].type== type_house GROUP GROUP GROUP typedef struct taggroup int itemvalue[groups_items]; }GROUP; ITEM_TYPE typedef enum tagitemtype type_house = 0, type_nation = 1, type_drink = 2, type_pet = 3, type_cigaret = 4 }ITEM_TYPE; GROUP if(group.itemvalue[type_house] == COLOR_BLUE) 線索模型定義

9 第 8 章愛因斯坦的思考題 if else if else Dunhill Blends typedef struct tagbind ITEM_TYPE first_type; int first_val; ITEM_TYPE second_type; int second_val; }BIND; first_type first_val second_type second_val 6 first_type type_house first_val COLOR_GREEN COLOR_GREEN second_type type_drink second_val DRINK_COFFEE DRINK_COFFEE binds const BIND binds[] = type_house, COLOR_RED, type_nation, NATION_ENGLAND }, type_nation, NATION_SWEDEND, type_pet, PET_DOG }, type_nation, NATION_DANMARK, type_drink, DRINK_TEA }, type_house, COLOR_GREEN, type_drink, DRINK_COFFEE }, type_cigaret, CIGARET_PALLMALL, type_pet, PET_BIRD }, type_house, COLOR_YELLOW, type_cigaret, CIGARET_DUNHILL }, type_cigaret, CIGARET_BLUEMASTER, type_drink, DRINK_BEER }, type_nation, NATION_GERMANY, type_cigaret, CIGARET_PRINCE } };

10 演算法的樂趣 typedef struct tagrelation ITEM_TYPE type; int val; ITEM_TYPE relation_type; int relation_val; }RELATION; type val relation_type relation_val 10 Blends type type_cigaret val CIGARET_BLENDS CIGARET_BLENDS relation_type type_pet relation_val PET_CAT PET_CAT relations const RELATION relations[] = type_cigaret, CIGARET_BLENDS, type_pet, PET_CAT }, type_pet, PET_HORSE, type_cigaret, CIGARET_DUNHILL }, type_nation, NATION_NORWAY, type_house, COLOR_BLUE }, type_cigaret, CIGARET_BLENDS, type_drink, DRINK_WATER } }; 8 groups[2].itemvalue[type_drink] DRINK_MILK

11 第 8 章愛因斯坦的思考題窮舉所有的組合結果 group void EnumHouseColors(GROUP *groups, int groupidx) if(groupidx == GROUPS_COUNT) /* */ ArrangeHouseNations(groups); return; } for(int i = COLOR_BLUE; i <= COLOR_YELLOW; i++) if(!isgroupitemvalueused(groups, groupidx, type_house, i)) groups[groupidx].itemvalue[type_house] = i; if(i == COLOR_GREEN) // (4) groups[++groupidx].itemvalue[type_house] = COLOR_WHITE; } } } } EnumHouseColors(groups, groupidx + 1); if(i == COLOR_GREEN) groupidx--; } ArrangeHouseNations()

12 演算法的樂趣 COLOR_BLUE COLOR_YELLOW COLOR_WHITE COLOR_WHITE COLOR_GREEN 9 ArrangeHouseNations() ArrangeHouseNations() void ArrangeHouseNations(GROUP *groups) /* (9) */ groups[0].itemvalue[type_nation] = NATION_NORWAY; EnumHouseNations(groups, 1); /* */ } = = = = = = = = = = = =

13 第 8 章愛因斯坦的思考題利用線索判定結果的正確性 GROUP BIND first_type first_val group group second_type second_val group second_type second_val BIND BIND binds BIND 8-1 i=0 group=findgroupidxbyitem(binds[i],first_type, binds[i],first_val); value=getgroupitemvalue(group, binds[i],second_type) binds[i],second_type == value? 否 i=i+1 是設定檢查失敗標記否是否處理完所有 binds 線索? 是設定檢查成功標記結束圖 8-1 綁定關係線索檢查的流程圖

14 演算法的樂趣 RELATION type val group group relation_type relation_val RELATION RELATION RELATION RELATION relations RELATION 8-2 i=0 group = FindGroupIdxByItem(relations[i],type, relations[i],val); result = CheckGroupRelation(relations[i],relation_type, relations[i],relation_val); result == true? 否 i=i+1 是設定檢查失敗標記否是否處理完所有 relations 線索? 是設定檢查成功標記結束圖 8-2 組相鄰關係線索檢查流程圖

15 第 8 章愛因斯坦的思考題 binds relations if else [1] Levitin A [2] Cormen T H, et al. Introduction to Algorithms (Second Edition). The MIT Press, 2001 [3] Kleigberg J, Tardos E. Algorithm Design. Addison-Wesley,

vi 黃帝內經即學即用別做反自然的事 053 成年人應該斷奶 055 吃肉吃素因人而異 057 要分清飢和餓 058 生活現代化與本能退化 061 調神就是調節奏 063 想冬泳, 先問問自己

vi 黃帝內經即學即用別做反自然的事 053 成年人應該斷奶 055 吃肉吃素因人而異 057 要分清飢和餓 058 生活現代化與本能退化 061 調神就是調節奏 063 想冬泳, 先問問自己目錄 001 第一講道法自然養生首先要找對方向 003 健身不同於健體 006 隨順自然的節拍 008 調和的重要 013 吃飯的講究 017 飲水的學問 021 喝適合自己的茶 025 起居作息要規律 029 形與神俱靠甚麼 031 還原現場 033 039 第二講背道