// count_change.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

/*-------------------------------------------------------------
實例：要想得到一個迭代的斐波那契算法需要一點點智慧。
給了半美元、四分之一美元、10美分、5美分、1美分的硬幣，將1美元換成零錢，一共有多少中不同的方式？
更一般的問題時，給定了任意數(shù)量的現(xiàn)金，我們能寫出一個程序，計算出所有換零錢方式的種數(shù)嗎？
采用遞歸過程，這一過程有一種很簡單的解法。假定我們所考慮的可用硬幣類型種類排了某種順序，于是就有下面的關系：
將總數(shù)為a的現(xiàn)金換成n中硬幣的不同方式的數(shù)目等于
1.將現(xiàn)金數(shù)a換成除第一種硬幣之外的所有其它硬幣的不同方式數(shù)目，加上
2.將現(xiàn)金數(shù)a-d換成所有種類的硬幣的不同方式數(shù)目，其中的d是第一種硬幣的幣值。
---------------------------------------------------------------*/
int first_denomination(int kinds_of_coins)
{
?if (1 == kinds_of_coins)
?{
??return 1;
?}
?else if(2 == kinds_of_coins)
?{
??return 5;
?}
?else if(3 == kinds_of_coins)
?{
??return 10;
?}
?else if(4 == kinds_of_coins)
?{
??return 25;
?}
?else if(5 == kinds_of_coins)
?{
??return 50;
?}
}

int cc(int amount, int kinds_of_coins)
{
?if (0 == amount)
?{
??return 1;
?}
?else if ((amount < 0) || (0 == kinds_of_coins))
?{
??return 0;
?}
?else
?{
??return ( ( cc(amount, kinds_of_coins-1) )+
???? ( cc(amount-first_denomination(kinds_of_coins), kinds_of_coins))
???? );
?}
}

int _tmain(int argc, _TCHAR* argv[])
{
?int n = cc(100, 5);
?return 0;
}

?

總結(jié)

以上是生活随笔為你收集整理的斐波那契算法举例(iterative Fibonacci algorithm)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。