C++循环队列实现k阶斐波那契数列的计算

循环队列是一种非常适合实现队列的数据结构，对于斐波那契数列，我们可以使用循环队列来实现。

首先，我们需要定义一个循环队列的结构体，包含队列的头部、尾部、队列的最大长度和队列中元素的个数：

#define MAXSIZE 100
typedef struct {
    int *base;  // 队列元素的基地址
    int front;  // 队列头指针
    int rear;   // 队列尾指针
    int maxSize;    // 队列最大长度
    int count;  // 队列中元素的个数
} SqQueue;

然后，我们可以使用循环队列来实现k阶斐波那契数列的计算。k阶斐波那契数列的递推公式为：

F(n) = F(n-1) + F(n-2) + ... + F(n-k)

我们可以使用一个长度为k的循环队列来存储最近的k个斐波那契数，每次计算新的斐波那契数时，将队列中的k个数相加即可。

以下是完整的代码实现：

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

#define MAXSIZE 100

typedef struct {
    int *base;  // 队列元素的基地址
    int front;  // 队列头指针
    int rear;   // 队列尾指针
    int maxSize;    // 队列最大长度
    int count;  // 队列中元素的个数
} SqQueue;

// 初始化队列
void InitQueue(SqQueue *Q, int k) {
    Q->base = (int *)malloc(sizeof(int) * k);
    Q->front = Q->rear = 0;
    Q->maxSize = k;
    Q->count = 0;
}

// 判断队列是否为空
int IsEmpty(SqQueue Q) {
    return Q.count == 0;
}

// 判断队列是否已满
int IsFull(SqQueue Q) {
    return Q.count == Q.maxSize;
}

// 入队
void EnQueue(SqQueue *Q, int x) {
    if (IsFull(*Q)) {
        printf("队列已满，无法插入元素！\n");
        return;
    }
    Q->base[Q->rear] = x;
    Q->rear = (Q->rear + 1) % Q->maxSize;
    Q->count++;
}

// 出队
int DeQueue(SqQueue *Q) {
    if (IsEmpty(*Q)) {
        printf("队列为空，无法删除元素！\n");
        return -1;
    }
    int x = Q->base[Q->front];
    Q->front = (Q->front + 1) % Q->maxSize;
    Q->count--;
    return x;
}

// 计算k阶斐波那契数列的第n项
int KFibonacci(int n, int k) {
    SqQueue Q;
    InitQueue(&Q, k);
    int i, sum = 0;
    for (i = 0; i < n; i++) {
        if (i < k) {
            EnQueue(&Q, 1);
            sum++;
        } else {
            int x = DeQueue(&Q);
            EnQueue(&Q, sum);
            sum = sum + sum - x;
        }
    }
    return sum;
}

int main() {
    int n, k;
    printf("请输入n和k：");
    scanf("%d %d", &n, &k);
    int result = KFibonacci(n, k);
    printf("k阶斐波那契数列的第%d项为：%d\n", n, result);
    return 0;
}