- 有三位學姐放假的時候結伴去 Venice 逛市集。
她們想要買著名的
Murano
Stones 當作紀念品帶回家。
市集上販賣紀念品的攤販很多，所以她們可以一家一家詢問比價。
可是由於遊客實在太多（Venice
每年約有三千萬名觀光客造訪；Taiwan每年約731萬造訪；Malaysia每年約2500萬。
如果你考慮一下這幾個地方的面積，你就會發現這數字實在驚人），
當天市集上只開放單向通行。
所以問完一家的價格後，如果當下決定不買，要再去問別家，之後是無法回頭再到這家購買的（所謂「好馬不吃回頭草」也）。
-
她們都想用最低的價格買到紀念品，但由於她們對於當地的市場行情沒有任何概念，所以她們就根據在資工系所學到的演算法
(algorithm) 知識，各自設計了一套詢價及採購的策略。
- Hestia 學姐最學術派，尤其她最近讀了暨大圖書館的一本書
The
Mathematics of Love，書中提到，連真命天子 (soulmate)
的尋找都有演算法，她相信類似的策略可以幫助她在此地以最低價購得紀念品。
她打算在市集（一條長長的街）的前三分之一先收集資訊，看問到的最低價格是多少。過了三分之一以後，如果遇到任何一家攤販的售價，小於等於之前問到的最低價格，她就出手買下。
- Christina 學姐書讀得最多，所以腦袋裡剩下的工作記憶體 (
working memory)
也少。她沒有耐性問那麼多家，所以只打算先問三家就好（古人所謂「貨比三家不吃虧」呀），然後遇到小於等於那三家中最低價的，就成交。
- Trista
學姐最務實，她擔心如果堅持要比前面的價格低才成交，萬一後面的售價越來越貴，她豈不是要空手而回？
所以她打算先看完前二分之一，接下來只要小於等於第二低價她就買。但如果走完四分之三還沒遇到，就改為只要小於等於至目前為止的第四低價就成交。要是走了八分之七還沒有，就再放寬為小於等於到目前為止的第八低價就成交。
-
試撰寫一個程式，模擬上述三種策略，以供我們比較其優劣，作為之後學弟妹們逛街的參考。
- 讓我們用上學期學到的
Structure
Chart 來協助設計這個程式。
- 首先你需要一個 CPP2x.cpp 檔，裡面包含有 main()
函式。它會在程式執行時由命令列接收四個參數 (見 P.202 Arguments to main):
最高價、最低價、攤位數、模擬次數。
- 模擬次數預設為 1000 次。
- 攤位數預設為 480。
- 最低價預設為 1 元。（不過通常不會是 1
元，不然演算法就簡單了，只要遇到售價 1 元的就可立即決定成交。）
-
最高價無預設值，若使用者未提供，則印出錯誤訊息，並提示使用者四個參數各自代表什麼。
- main() 函式會呼叫一個 printIntro() 函式，說明本程式之目的。
- 其次 main() 會呼叫 simNshopping() 函式，用 pass-by-value
傳進去最高價 (max)，最低價 (min)，攤位數 (nBooth)，模擬次數
(nIteration)。傳出來的參數有兩個：成交次數 (nDeal)、以最低價成交次數
(nOptimal)。我們應可確定 nIteration >= nDeal >= nOptimal.
由於C語言中函式只能回傳一個值，不像 Python 可以 return
多個數值，因此簡單起見，這兩個參數以 pass-by-reference 的方式傳遞。
- simNshopping() 中用一個 for 迴圈，執行 nIteration 次，
每次呼叫 simOneShopping() 函式。
simOneShopping() 模擬單趟逛街行程中的採購情形，以 pass-by-value
方式傳入的參數為
最高價 (max)，最低價 (min)，攤位數 (nBooth)；
以 pass-by-reference 傳出的參數為 成交的價格 (boughtPrice) 以及
此行所問到的最低價 (lowestPrice)。boughtPrice 傳入的初始為0，若傳出值亦為零，則代表未成交。
- simOneShopping() 中，以 for 迴圈執行 nBooth
次，每次產生一個大於等於 min 則小於等於 max 的整數，作為該攤位的定價
(boothPrice)。
- simOneShopping()
中以陣列儲存目前市集上詢到的所有價格。為簡單起見，我們在這裡用一個固定大小
(4800) 的整數陣列儲存。
（在第十章的 STL 中，我們會再學到用其他資料結構，像 vector 或 list
來做更有效的處理。）
這個陣列中我們把所有問到的價格由小排到大，所以 prices[0]
就是目前問到的最低價。
- 為了讓陣列排序，每次亂數產生 boothPrice 後，會呼叫 insert(int
prices[], int currentBooth, boothPrice) 函式，把 boothPrice
插入到陣列中對應的位置。
你可以參考 Insertion Sort
的做法。
currentBooth 代表目前已行進到哪個攤位。
- 若 boothPrice 低於 lowestPrice (初始值為 max), 則更新
lowestPrice 的內容為 boothPrice。
- 若 boughtPrice 為零，則呼叫 wantToBuy() 函式判定是否成交。
若成交則令 boughtPrice 值為
boothPrice。
(若 boughtPrice
大於零，代表剛才已經買了，接下來就算看到更便宜的，也無法再買了。)
- 每位學姐的 wantToBuy() 規則會不一樣，所以你應該準備 hestia.app,
christina.cpp, trista.cpp 三個檔案。每個檔案中都各自是一個 wantToBuy()
式的定義。
編譯時你 CC CPP2x.cpp hestia.cpp -o hestia.exe, 再執行 hestia.exe，就是
Hestia 學姐的演算法。
CC CPP2x.cpp christina.cpp -o christina.exe, 就是
Christina 學姐的演算法。
CC CPP2x.cpp trista.cpp -o trista.exe, 就是
Trista 學姐的演算法。
- 三位學姐的 wantToBuy(), 其 function header 都相同，是
bool wantToBuy(int boothPrice, int currentBooth, int prices[], int
nBooth)。
- Hestia 學姐的 wantToBuy(), function body 內容大致為
if (currentBooth >= nBooth / 3 && boothPrice <= prices[0])
return true;
else
return false;
- Christina 學姐的 wantToBuy() 則為
if (currentBooth >= 3 && boothPrice <= prices[0])
return true;
else
return false;
- Trista學姐的wantToBuy()則為
if (currentBooth > nBooth * 7 / 8)
if (boothPrice <= prices[7])
return true;
else
return false;
else if (currentBooth > nBooth * 3 / 4)
if (boothPrice <= prices[3])
return true;
else
return false;
else
if (boothPrice <= prices[1])
return true;
else
return false;
- simNshopping() 依據 simOneShopping 所傳回的 lowestPrice 和
boughtPrice, 更新 nDeal 及 nOptimal。
若 boughtPrice 大於 0，則 nDeal 加一。
若 boughtPrice 等於 lowestPrice, 則 nOptimal 亦加一。
- simNshopping() 執行完後，main() 呼叫 printSummary(),
傳入 nIteration, nDeal, nOptimal。
函式會印出在 nInteration 次擬模中，
有 nOptimal/nIteration 比例以「最低價格」成交，
(nDeal - nOptimal)/nIteration 比例有買到但非最低，
(nIteration - nDeal)/nIteration 比例為空手而回。
