求斐波那契数列的编程实现

数据结构 经典算法与题目

递归法

二阶

int fib(int a)
{
    if (a == 0)
        return 0;
    else if (a == 1)
        return 1;
    else
        return fib(a - 1) + fib(a - 2);
}

java

//二阶斐波那契数列
    public static int fib(int a)
    {
        if ( a== 0)
            return 0;
        else if (a == 1)
            return 1;
        else
            return fib(a-1) + fib(a-2);
    }

python

# 二阶斐波那契数列
def fib (a):
    if a == 0:
        return 0
    elif a == 1:
        return 1
    else:
        return (fib(a-1) + fib(a-2))

k阶

java

//k阶斐波那数列
    public static int fib_k(int a,int k)
    {
        int re = 0;
        if (a < k-1)
            return 0;
        else if (a == k-1)
            return 1;
        else
        {
            for (int i=1;i<=k;i++)
                re+=fib_k(a-i,k);
            return re;
        }
    }

python

# k阶斐波那契数列
def fib_k (a,k):
    re = 0
    if a < k-1:
        return 0
    elif a == k-1:
        return 1
    else:
        for i in range(1,k+1):
            re+=fib_k(a-i,k)
        #print(re)
        return re

数组法

二阶

先从简单的开始

Status Fibonacci_0(int k, int m, int &f)
{
    int x = 0;
    f = x;
    if (k < 2 || m < 0)
        return  ERROR;
    if (m < k - 1)
    {
        f = 0;
        return OK;
    }
    if (m == k || m == k - 1)
    {
        f = 1;
        return OK;
    }
    else
    {
        int* l;
        l = (int*)malloc(k * sizeof(int));
        l[0] = 0;
        l[1] = 1;
        for (int i = k; i < m; i++)
        {
            int v = l[0] + l[1];
            l[0] = v;
            int tmp = l[0];
            l[0] = l[1];
            l[1] = tmp;
            f = l[0] + l[1];
        }
    }
    return OK;
}

这里的函数参数k是阶数，须为2

k阶

Status Fibonacci(int k, int m, int &f)
/* 求k阶斐波那契序列的第m项的值f */
{
    int i,j;
    if (k < 2 || m < 0)
        return  ERROR;
    if (m < k - 1)
    {
        f = 0;
        return OK;
    }
    if (m == k || m == k - 1)
    {
        f = 1;
        return OK;
    }
    else
    {
        int* l;
        l = (int*)malloc(k * sizeof(int));
        for (i = 0; i < k - 1; i++)
            l[i] = 0;
        l[k - 1] = 1;
        for (i = k; i < m; i++)
        {
            for (j = k - 1; j > 0; j--)
            {
                int tmp = l[j];
                l[j] = l[j - 1];
                l[j - 1] = tmp;
            }
            int v = 0;
            for (j = 0; j < k; j++)
                v += l[j];
            l[k - 1] = v;
            f = 0;
            for (j = 0; j < k; j++)
                f += l[j];
        }
    }
    return OK;
}

循环队列法

循环队列的定义

#define ElemType int
typedef struct {
    ElemType *base; // 存储空间的基址
    int front;      // 队头位标
    int rear;       // 队尾位标，指示队尾元素的下一位置
    int maxSize;    // 最大长度
} SqQueue;

c语言

long Fib(int k, int n)
/* 求k阶斐波那契序列的第n项fn
要求：必须使用循环队列
*/
{
    long sum = 0;
    int i, j,m;
    SqQueue a;
    a.maxSize = k+1;    
    //注意循环队列由于判空判满的问题所以有一个元素空间没有用
    a.base = (ElemType*)malloc(a.maxSize * sizeof(ElemType));
    a.front = 0;
    a.rear = 0;
    if (n < k - 1)
    {
        sum = 0;
        return sum;
    }
    else if (n == k-1)
    {
        sum = 1;
        return sum;
    }
    //初始化该队列对应的斐波那契数列
    do
    {
        a.base[a.rear] = 0;
        a.rear = (a.rear + 1) % a.maxSize;
    } while ((a.rear + 1) % a.maxSize != a.front);
    a.base[a.rear-1] = 1;
    m = a.front;
    for (i = k; i < n; i++)
    {
        long v = 0;
        j = a.front;
        do
        {
            v += a.base[j];
            j = (j + 1) % a.maxSize;
        } while ((j + 1) % a.maxSize != a.front);
        a.base[a.rear] = v;
        if ((a.rear + 1) % a.maxSize == a.front)
        {
            a.rear = a.front;
        }
        else
            a.rear = (a.rear + 1) % a.maxSize;
        a.front = (a.front + 1) % a.maxSize;
    }
    sum = 0;
    j = a.front;
    do
    {
        sum += a.base[j];
        j = (j + 1) % a.maxSize;
    } while ((j + 1) % a.maxSize != a.front);
    return sum;
}