队列的基本应用：计算k阶斐波那契数列的第n项

要求：

k阶斐波那契数列的定义为：数列第1项到第k-1项为0，第k项为1，之后从第(k+1)项开始每一项为前k项之和。使用循环队列计算斐波那契数列的第n项。

思路：

入队数列的前k项（前k-1项为0，第k项为1）
队首元素赋值给sum，并出队
队首元素赋给temp，并出队
sum与temp相加，并将temp入队
重复步骤3、4一共k-1次
入队sum，此时队列中为k阶斐波那契数列的第2、3、……、(k+1)项，且sum存放第(k+1)项的值。

本质上说，1-6将第1至k项的“和”求出，将队列首项出队后将“和”的值入队（即求出了第k+1项），并且为求第k+2项做了准备。这样，我们若要求第n项的值，只要循环n-1次1-6步即可。（PS：循环n-1次是因为，若n=k，不需要循环，直接将1输出即可）

#include <bits/stdc++.h>
using namespace std;

class CircularQueue //顺序队列必须为循环队列
{
public:
    CircularQueue(int length) //length代表存放最大元素的个数
    {
        p = new int[length+1]();
        this->len = length+1;
        this->front = this->rear = 0;
        this->cnt = 0;
    }
    bool in(int num);
    bool out();
    bool isFull();
    bool isEmpty();
    int getLength()
    { return this->cnt; } //获取队列长度
    int getFront()
    { return *(p+front); }
    void show();
    ~CircularQueue()
    {
        delete [] p;
    }
private:
    int rear; //指向队尾元素的后一个
    int front; //队首
    int len; //数组长度
    int cnt; //队列中有效元素个数
    int * p; //用于模拟队列数组的首地址
};

bool CircularQueue::isEmpty()
{
    if (rear == front)
        return true;
    else
        return false;
}

bool CircularQueue::isFull()
{
    if ((rear+1) % len == front)
        return true;
    else
        return false;
}

bool CircularQueue::in(int num)
{
    if (this->isFull())
    {
        cout<<"循环队列已满，无法入队！"<<endl;
        return false;
    }
    *(p+rear) = num;
    rear = (rear+1) % len; //注意该行不能单纯rear++，否则数组会越界
    cnt++;
    return true;
}

bool CircularQueue::out()
{
    if (this->isEmpty())
    {
        cout<<"循环队列已空，无法出队！"<<endl;
        return false;
    }
    front = (front+1) % len; //注意该行不能单纯front++，否则数组会越界
    cnt--;
    return true;
}

void CircularQueue::show()
{
    if (this->isEmpty())
    {
        cout<<"循环队列已空，无法显示！"<<endl;
        return;
    }
    for (int i = front; i != rear; i = (i+1) % len)
    {
        cout<<*(p+i)<<" ";
    }
    cout<<endl;
}

int main()
{
    int k,n,sum = 0,temp;
    cout<<"请输入斐波那契数列的阶数k："<<endl;
    cin>>k;
    cout<<"请输入n的值："<<endl;
    cin>>n;
    if (n<k)
    {
        cout<<k<<"阶斐波那契数列的第"<<n<<"项为0"<<endl;
        return 0;
    }
    if (n==k)
    {
        cout<<k<<"阶斐波那契数列的第"<<n<<"项为1"<<endl;
        return 0;
    }
    CircularQueue queue(k);
    //将队列前k-1项填充为0，第k项为1
    for (int i = 0; i<k-1; i++)
    {
        queue.in(0);
    }
    queue.in(1);
    //这两层for循环的含义较难理解，可以在纸上推一遍
    //第一层for循环控制求到第几项停止
    for (int i = k; i<n; i++)
    {
        sum = queue.getFront();
        queue.out();
        //第二层for循环将包括自身的前k个数相加并将sum添加到队尾
        for (int j = 1; j<k; j++)
        {
            temp = queue.getFront();//把每一个相加项用temp存起来
            queue.out();
            //每次循环把temp的值入队，使得内层循环结束后留在队列中的元素为所求k阶斐波那契序列中的第i+1项。
            sum += temp;
            queue.in(temp);
        }
        queue.in(sum);
    }
    cout<<k<<"阶斐波那契数列的第"<<n<<"项为"<<sum<<endl;
    return 0;
}

测试结果如下：

解后反思：

我们当然也可以使用递归来解决，在递归：计算k阶斐波那契数列的第n项中我们也会讨论如何运用递归来求解该问题。

发表回复取消回复