2016年4月6日 星期三

訓練數學感 94/演算法訓練 12 ─ 撿拾硬幣

http://4rdp.blogspot.com/2016/04/94-12.html

圖片引用 芭蕉葉上聽雨聲部落格
看到網友 Pizg 貼文:如何撿拾最多的硬幣,覺得這是一個非常不錯的演算法訓練的題目,因而收錄。

有一個矩形區域,格線中放有硬幣(圖中紅色的點)。
機器人開始是在區域的左下角落,他的任務是在穿越到右上角落的過程中盡可能撿起最多的硬幣。
然而,在每一個步驟中,限制機器人不能退後,只能往右或往上移動。
圖中藍線表示的最佳路徑,也就是機器人可以拾取最大數目的硬幣。

請試寫一程式求解某已知圖案之最佳路徑。


對計算格子有幾種走法有興趣的朋友,可以參考訓練數學感 52 ─ 最短路徑有幾種?一文。另外,覺得這題不太一樣的地方是在格子上放了許多已知位置的硬幣,我們只能走一次取得最多硬幣,好像機器人電量有限,每次只能走有限里程,要盡量一趟取得最多硬幣。

基本題,請計算 6 x 10 格有幾種走法?

加分題,現在每個格子都放一枚硬幣,從左下角往右上角只能往右往上走,然後機器人更換充飽後的電池,再從右上角往左下角走但只能往左及往下撿拾硬幣,請問來回要走幾趟才能把所有硬幣都撿完。

未來希望成為程式設計高手的人,應該試著寫程式看看。

沒有留言:

張貼留言