所謂的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
所以是四枚
希望明天考試順利...
沒有留言:
張貼留言