資訊能力競賽試題求助

[passiontcfsh 10]

請大家有空幫幫忙想一下兩題問題

最好在一個小時內解決

一、某國家一共發行了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

二、請設計一程式，可以找出所有符合下列特性的運算式AB=C，(1) 其中A，B， C均為整數；且A是兩位數，B是三位數，C為五位數，(2)所有A、B、和C的組成十進位數字(合起來共有十個十進位數字)全部皆相異。例如，27594=16038和78345=26910等皆符合以上特性。本題沒有輸入，請直接顯示出所有符合特性的運算式，並計算共有幾種不同的運算式。

輸入：(無)

輸出：列出所有符合特性的運算式，並計算共有幾種不同的運算式。

參考答案

27 X 594 = 16038

36 X 495 = 17820

39 X 402 = 15678

45 X 396 = 17820

46 X 715 = 32890

52 X 367 = 19084

54 X 297 = 16038

63 X 927 = 58401

78 X 345 = 26910

共9種運算式

[su_horng 10]

一、範圍這麼小，隨便枚舉兩種錢幣的用量就好

二、範圍很小枚舉就好

[willyliu 10]

(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