course_data_structures/Data Structure Class 5/hw6/K_Fib.h

//K_Fib.h
#include <cstring>
void K_Fib(int k, int max)
//计算K阶斐波那契序列中的前 n+1 项，即:
//要求fn <=max 而 fn+1>max，函数运行结束时，
//留在队列中的元素恰为所求 K 阶斐波那契序列中的最后 K 项。
{
    int *arr = new int[k];
    memset(arr, 0, sizeof(int) * k);
    arr[k - 1] = 1;
    int cursum = 1, curpos = k - 1;
    for (;;)
    {
        int nxtpos = (curpos + 1) % k;
        int nxtval = cursum;
        if (nxtval > max) break;
        cursum = cursum - arr[nxtpos] + nxtval;
        arr[nxtpos] = nxtval;
        curpos = nxtpos;
    }
    for (int i = curpos + 1; i < k; i++) printf("%d ", arr[i]);
    for (int i = 0; i < curpos + 1; i++) printf("%d ", arr[i]);
    putchar('\n');
    delete[] arr;
    //在此插入你完成第二个任务的代码
}

//上述算法的时间复杂度要求仅为O(n)。如果采用递归算法,算法的时间复杂度将达到O(k^n). 即使采用暂存中间结果的方法,也将达到O(n^2)。