K阶斐波那契数列--------西工大NOJ习题.10

原创不易,转载请说明出处!!!

科普：k阶斐波那契数列的0到n-1项需要有初始值。

其中，0到n-2项初始化为0，第n-1项初始化为1.

（我的一篇博文）

我使用的方法是尺取法，这样可以大大地减小时间复杂度。

具体见代码：

#include <stdio.h>

#include <stdlib.h>

typedef int Elem;

typedef struct Queue

{

    Elem *data;

    int head;

    int tail;

    int size;//仅仅是一个功能，程序的判空，判断满并不依赖。

    int MAX_SIZE;//是真正申请的最大值，实际存放MAX_SIZE-1个。

}Queue;

//函数原形声明

Queue *Creat(int max);

int Size(Queue* Q);

Elem GetTail(Queue *Q);

Elem GetHead(Queue *Q);

int Pop(Queue *Q);

int Push(Queue *Q, Elem e);

int Full(Queue* Q);

int Empty(Queue *Q);

int Destroy(Queue* Q);

Queue *Creat(int max)

{

    if(max <= 0)

        return NULL;

    Elem *D = (Elem*)calloc(max + 1, sizeof(Elem));

    if(!D)

        return NULL;

    Queue *Q = (Queue*)malloc(sizeof(Queue));

    if(!Q)

    {

        free(D);

        return NULL;

    }

    Q->MAX_SIZE = max + 1;

    Q->data = D;

    Q->head = 0;

    Q->tail = 0;

    Q->size = 0;

    return Q;

}

int Destroy(Queue* Q)

{

    if(!Q)

        return 0;

    free(Q->data);

    free(Q);

    return 1;

}

int Empty(Queue *Q)

{

    if(Q->head == Q->tail)

        return 1;

    else

        return 0;

}

int Full(Queue* Q)

{

    if((Q->tail+1)%Q->MAX_SIZE == Q->head)

        return 1;

    else

        return 0;

}

int Push(Queue *Q, Elem e)

{

    if(Full(Q))

       return 0;

    Q->data[Q->tail] = e;

    Q->tail = (Q->tail + 1)%Q->MAX_SIZE;

    Q->size += 1;

    return 1;

}

int Pop(Queue *Q)

{

    if(Empty(Q))

        return 0;

    Q->head = (Q->head + 1) % Q->MAX_SIZE;

    Q->size -= 1;

    return 1;

}

Elem GetHead(Queue *Q)

{

    if(Empty(Q))

    {

        *(int *)NULL;//专门让程序crash

    }

    return Q->data[Q->head];

}

Elem GetTail(Queue *Q)

{

    if(Empty(Q))

    {

        *(int *)NULL;//专门让程序crash

    }

    int t;

    t = Q->tail;

    t -= 1;

    if(t >= 0)

        return Q->data[t];

    else

    {

        return Q->data[Q->MAX_SIZE-1];

    }

}

int Size(Queue* Q)

{

    return Q->size;

}

int main()

{

    int max, n;

    scanf("%d%d",&max, &n);

    int sum = 0;//使用尺取法

    Queue* Q = Creat(n);//指定大小为n.

    for(int i = 1; i <= n; i++)//先在队列中塞下前n项

    {

        if(i < n)

            Push(Q,0);

        else

            Push(Q,1);

    }

    sum = 1;//初始化n项的和

    while(sum<=max)//当要增加的小于等于最大值时,继续算.

    {

        int tmp = sum;//前一时刻的sum和

        sum -= GetHead(Q);

        Pop(Q);

        sum += tmp;//更新sum,为下一次做准备

        Push(Q,tmp);

    }

    for(int i = 1; i <= n; i++)//依次输出

    {

        printf("%d ",GetHead(Q));

        Pop(Q);

    }

    Destroy(Q);//销毁循环队列.

    return 0;

}

巴特西

K阶斐波那契数列--------西工大NOJ习题.10

K阶斐波那契数列--------西工大NOJ习题.10

最新文章

热门文章