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

要求:

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

思路:

  1. 入队数列的前k项(前k-1项为0,第k项为1)
  2. 队首元素赋值给sum,并出队
  3. 队首元素赋给temp,并出队
  4. sum与temp相加,并将temp入队
  5. 重复步骤3、4一共k-1次
  6. 入队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项中我们也会讨论如何运用递归来求解该问题。

发表评论

电子邮件地址不会被公开。 必填项已用*标注