斐波那契算法举例(iterative Fibonacci algorithm)

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

#include "stdafx.h"

/*-------------------------------------------------------------
实例：要想得到一个迭代的斐波那契算法需要一点点智慧。
给了半美元、四分之一美元、10美分、5美分、1美分的硬币，将1美元换成零钱，一共有多少中不同的方式？
更一般的问题时，给定了任意数量的现金，我们能写出一个程序，计算出所有换零钱方式的种数吗？
采用递归过程，这一过程有一种很简单的解法。假定我们所考虑的可用硬币类型种类排了某种顺序，于是就有下面的关系：
将总数为a的现金换成n中硬币的不同方式的数目等于
1.将现金数a换成除第一种硬币之外的所有其它硬币的不同方式数目，加上
2.将现金数a-d换成所有种类的硬币的不同方式数目，其中的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;
}

 

总结

以上是生活随笔为你收集整理的斐波那契算法举例(iterative Fibonacci algorithm)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。