[程式]Coin Change Dynamic

因為明天要考試的關係，在念書的時候找到一個小練習來做

所謂的Dynamic(動態)就是不用Recursive(遞迴)的方式完成指定的工作

這次的程式是換錢換最少數目硬幣，語言是用C++
#include
#include
using namespace std;
int Coin(int n)//宣告函數開始
{
    int rest=0,change50=0,change20=0,change10=0,change5=0;//宣告餘額、換50、換20、換10、換5
    if(n==0) return 0;//如果是零元，回傳0
    if(n==1||n==5||n==10||n==20||n==50){return 1;}//如果是剛好單枚硬幣能夠換完，回傳1
    rest=n%50;//先把金額換50
    if(rest==0)//如果沒有餘額
    {
        change50=n/50;//計算換了幾個50
        return change50;//回傳換好的數目
    }
    else//換完50還有剩的話(總金額被50除有餘數的狀況)
    {
        change50=n/50;
        rest=(n-50*change50)%20;//把剩下的金額拿續換20
        if(rest==0)//剛好可以換完的話
        {
            change20=(n-50*change50)/20;//統計20元數量
            return change50+change20;//回傳50元數量+20元數量....以下略
        }
        else
        {
            change20=(n-50*change50)/20;
            rest=(n-50*change50-20*change20)%10;
            if(rest==0)
            {
                change10=(n-50*change50-20*change20)/10;
                return change50+change20+change10;
            }
            else
            {
                change10=(n-50*change50-20*change20)/10;
                rest=(n-50*change50-20*change20-10*change10)%5;
                if(rest==0)
                {
                    change5=(n-50*change50-20*change20-10*change10)/5;
                    return change50+change20+change10+change5;
                }
                else
                {
                    change5=(n-50*change50-20*change20-10*change10-5*change5)/5;
                    rest=(n-50*change50-20*change20-10*change10-5*change5);
                    return change50+change20+change10+change5+rest;
                }
            }
        }
    }
       
   
}

int tmain()
{
    int n;
    cout<<"請輸入欲兌換之金額:\n";
    cin>>n;
    cout<<"\n換完的硬幣數:"<
  
    return 0;
}

沒有縮減過，雖很長但是理念很簡單..

然後換錢問題，要如何換出最少的硬幣數目?

首先，錢拿到之後先從大面額開始換

有剩下的金額的話才繼續往下，用比較小的面額來換

Ex.
85 -> 50+35 -> 50+20+15 -> 50+20+10+5

所以是四枚


希望明天考試順利...