passiontcfsh 10 發表於 June 15, 2011 檢舉 Share 發表於 June 15, 2011 請大家有空幫幫忙想一下兩題問題最好在一個小時內解決一、某國家一共發行了1元、3元、4元三種不同面額的鈔票。 現在我們手上有n元, 請問(a)要如何把n元兌換成1元、3元、4元這些鈔票,使得所用鈔票的量為最少。 (b)兌換後的鈔票各為幾張輸入: n (0 < n < 1000 ); 輸出: (a)最少的張數。(b) 1元、3元、4元三種不同面額鈔票的張數(假設有三種不同面額的鈔票 1元、3元、4元,若要兌換10元的鈔票,最少鈔票的量為 ? 張。一般若用10/4=2,再用餘數去2/1=2 ,則會用4張; 可是若3元2張,再1張4元就可以了,只要3張) 輸入範例: 10 39 輸出範例: (a)3 (b)0 2 1(a)10 (b)0 1 9二、請設計一程式,可以找出所有符合下列特性的運算式AB=C,(1) 其中A,B, C均為整數;且A是兩位數,B是三位數,C為五位數,(2)所有A、B、和C的組成十進位數字(合起來共有十個十進位數字)全部皆相異。例如,27594=16038和78345=26910等皆符合以上特性。本題沒有輸入,請直接顯示出所有符合特性的運算式,並計算共有幾種不同的運算式。輸入:(無)輸出:列出所有符合特性的運算式,並計算共有幾種不同的運算式。參考答案27 X 594 = 1603836 X 495 = 1782039 X 402 = 1567845 X 396 = 1782046 X 715 = 3289052 X 367 = 1908454 X 297 = 1603863 X 927 = 5840178 X 345 = 26910共9種運算式 鏈接文章 分享到其他網站
su_horng 10 發表於 June 15, 2011 檢舉 Share 發表於 June 15, 2011 一、範圍這麼小,隨便枚舉兩種錢幣的用量就好二、範圍很小枚舉就好 鏈接文章 分享到其他網站
willyliu 10 發表於 June 16, 2011 檢舉 Share 發表於 June 16, 2011 (已編輯) (1)假設n元需要a個一元, b個三元, c個四元, 我們以(a, b, c)表示一組解.可以得知: (i)存在一組最佳解, 使a=0或b=0, 否則可以得到(a-1, b-1, c+1), 所需鈔票更少.(ii) 存在一組最佳解, 使a<3, 否則可以得到(a-3, b+1, c).(iii) 存在一組最佳解, 使b<3, 否則可以得到(a+1, b-3, c+2).由此, 只需知道(a, b)=(0, 1), (0, 2), (1, 0), (2, 0)可不可行, 哪個比較好就行了.因此我們可以將n擴大到2^10,000,000 此內容已被編輯, June 16, 2011 ,由 willyliu 鏈接文章 分享到其他網站
Recommended Posts