找零錢

z020909

有哪位大大可以幫忙嗎? 能告訴我原理或是如何做嗎?

試寫出一個模擬換零錢的程式：
只可以接受紙鈔（100,200,500,1000）
可以選擇零錢面額(一元、五元、十元、五十元）以及個數
剩下的金額以最少的零錢數找出（假設要以100元戶10個一元，結果會出來10個一元與9個十元)

剩下以最少零錢數找出...
那應該會找出 一個五十元 跟 四個十元吧???
是我會錯意了嗎??

safestation

假設要以100元戶10個一元，結果會出來10個一元與9個十元

這應該不太對= =
100  = (1*10) + (50*1) + (10*4)
只要14個就夠了
輸入格式：
[總額] [面額] [個數]
輸入範例：
100 1 10
輸出範例：
1: 10
5: 0
10: 4
50: 1
原理寫在註解裡面

1. #include<iostream>
   
2. using namespace std;
   
3. int main(){
   
4.   int n, c[]={1,5,10,50}, p[51], v, vn;
   
5.   for(int i = 0;i < 4;i++)
   
6.    p[c[i]] = i;  //拿來放位置，咖方便
   
7.   while(cin >> n >> v >> vn){
   
8.   int m = 3, cc[4]={0}; //cc[]拿來存結果
   
9.                //m為目前最大值在c[]中的位置
   
10.     n -= v*vn; //先把總額去掉一定要拿找的錢
    
11.     cc[p[v]] += vn;  //p[]派上用場了 XD
    
12.     while(n > 0 && m >= 0){ //當還有剩下時繼續做
    
13.                   //m>=0避免超出範圍 (其實如果輸入都符合規定的話，是不需要的)
    
14.     if(n/c[m] > 0){ //也可以寫成 n >= c[m]  
    
15.       cc[m] += (n / c[m]);
    
16.     n %= c[m];
    
17.     }else
    
18.       m--; //剛開始是最大值的位置，如果 n < c[m]，則往前(即變小)
    
19.   }
    
20.   
    
21.   //輸出
    
22.   for(int i = 0;i < 4;i++){
    
23.       cout << c[i] << ": " << cc[i] << endl;   
    
24.   }
    
25.   cout << endl;
    
26.   }
    
27.   system("pause");
    
28.   return 0;
    
29. }

複製代碼

這個方法一般稱為貪婪法(Greedy)
只要想成每次都取最好的答案就夠了
是一種很簡單的演算法

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

...

瀏覽完整內容，請先 註冊 或 登入會員

@@...高手呢!!!
想不到有這樣的寫法!!!
p[c]= i;....可以問依下這段的用意嗎??

基本上是看不懂這樣的寫法@@  SORRY

[ 本帖最後由 小鬼魚 於 2008-1-12 02:05 AM 編輯 ]

safestation

其實只是個小技巧
從頭到尾只用在
cc[p[v]] += vn;

因為已經先把v*vn減掉了
所以要先把結果加進去

而設p是為了增加效率(其實是懶XD)
cc[p[v]] += vn;
直接取v在c中的位置，不用再search一遍

z020909

大大真是厲害!! 雖然我還是不太懂 但是謝謝你的指導囉^^

其實很多地方我沒學過 但是我會慢慢研究的~

playcoo

原帖由 safestation 於 2008-1-12 02:26 AM 發表
其實只是個小技巧
從頭到尾只用在
cc] += vn;

因為已經先把v*vn減掉了
所以要先把結果加進去

而設p是為了增加效率(其實是懶XD)
cc] += vn;
直接取v在c中的位置，不用再search一遍

Greedy演算法的確可解決部分問題，像這個例子！

...

瀏覽完整內容，請先 註冊 或 登入會員

試寫出一個模擬換零錢的程式：
只可以接受紙鈔（100,200,500,1000）
可以選擇零錢面額(一元、五元、十元、五十元）以及個數
剩下的金額以最少的零錢數找出（假設要以100元戶10個一元，結果會出來10個一元與9個十元)

以下是小弟的想法，再接受紙鈔這個地方應該用IF判斷就可以解決了；
當條件滿足妳上述的(100，200，500，1000)才往下做換幣動作，
...

瀏覽完整內容，請先 註冊 或 登入會員

差不多看懂了一低低....
一個簡單的程式要寫的很好還蠻難的呢!!!