fibonacci_2.c

本程序是用备忘录法实现计算斐波那契数列

/************************************************
Fibonacci.c  memoized  2008_0507_0004
*************************************************/

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 48   /*定义备忘录表的最大长度*/
#define INF 4294967295

/*fibonacci数列的递归计算*/
unsigned long fibonacci(int p, unsigned long array[])
{
	if (array[p]<INF)
	{
		return array[p];
	}

    if (p==1 || p==2)
	{
		array[p]=1;
	}
	else
	{
		array[p]=fibonacci(p-1, array)+fibonacci(p-2, array);
	}

    printf("%d -> %u\n", p, array[p]);  //输出递归产生的中间值(可去掉)

	return array[p];
}

/*初始化备忘录表，并查找元素*/
unsigned long memzfbnc(int p, unsigned long array[])
{
    int n;
	int i;

	n=MAXSIZE-1;
	
	for (i=0; i<=n; i++)
	{
		array[i]=INF;
	}

	return fibonacci(p, array);
}

void main()
{
	unsigned long fbnc[MAXSIZE];  /*定义备忘录表*/
    int n;      /*要查找fibonacci数列的位置*/
	unsigned long t;

    do
	{
	    printf("Please input the position(1-47): ");
	    scanf("%d", &n);
	}while(n<=0 || n>=48);
	
	printf("***********************\n");
	t=memzfbnc(n, fbnc);
	printf("***********************\n");
	printf("The No.%d element is: %u\n", n, t);

	system("pause");
}