序三 A* Wi-Fi RLE RSA - v -
前言 NPC Horner s rule DOS PCX RLE RSA - - vii -
演算法的樂趣 0-1 60 23 1 32 O(n) O(n 2 ) O(n) O(n) MP3 - viii -
前言 http://books.gotop.com.tw/download/acl045600 http://blog.csdn.net/orbit/ - ix -
第 8 章愛因斯坦的思考題 2 15 1. 2. 3. 4. 5. 6. Pall Mall 7. Dunhill 8. 9.
演算法的樂趣 10. Blends 11. Dunhill 12. BlueMaster 13. Prince 14. 15. Blends 15 8-1 表 8-1 愛因斯坦思考題推理結果 房子顏色 國 籍 飲 料 寵 物 煙 黃色 挪威 水 貓 Dunhill 藍色 丹麥 茶 馬 Blends 紅色 英國 牛奶 鳥 PallMall 綠色 德國 咖啡 魚 Prince 白色 瑞士 啤酒 狗 BlueMaster - 122 -
第 8 章愛因斯坦的思考題... 8.2.1 基本模型定義 5 5 5 5 5 25 25 5 + 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 0 4 25 8-1 25 group group - 123 -
演算法的樂趣 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) 8.2.2 線索模型定義 15-124 -
第 8 章愛因斯坦的思考題 if else if else 15... 1 2 3 5 6 7 12 13 Dunhill Blends... 10 11 14 15... 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 1 2 3 5 6 7 12 13 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 } }; - 125 -
演算法的樂趣 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 10 11 14 15 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 4 4-126 -
第 8 章愛因斯坦的思考題 8.3.1 窮舉所有的組合結果 group 8.2.2 4 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() - 127 -
演算法的樂趣 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); /* */ } 5 8-1 5 5 = 120 4 4 = 24 24 5 = 120 9 4 = 24 24 24 = 576 576 5 = 120 8 4 = 24 576 24 = 13824 13824 5 = 120 13824 20 = 1658880 1658880 5 = 120 1658880 120 = 199065600 2-128 -
第 8 章愛因斯坦的思考題 8.3.2 利用線索判定結果的正確性 8.2.2 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 綁定關係線索檢查的流程圖 - 129 -
演算法的樂趣 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 組 相鄰關係線索檢查流程圖 - 130 -
第 8 章愛因斯坦的思考題 8-1 8-2 binds relations if else 2 8.1 [1] Levitin A... 2007 [2] Cormen T H, et al. Introduction to Algorithms (Second Edition). The MIT Press, 2001 [3] Kleigberg J, Tardos E. Algorithm Design. Addison-Wesley, 2005-131 -