course_data_structures/Data Structure Class 5/hw6/readme.txt

数据结构 作业6

目标：本次作业练习递归问题的求解和队列的应用。


开始：

（1）解压hw6.rar，得到hw6文件夹。在hw6文件夹中，
    Queue.h包含队列的虚基类；
    Recursive.h包含正整数输出PrintOut（）递归函数；
    K_Fib.h包含K阶斐波那契序列输出K_Fib（）函数；
    SeqQueue.h包含顺序循环队列数据结构SeqQueue类，
    测试文件Test.cpp的main（）函数包括测试正整数输出递归函数的代码和测试K阶斐波那契序列计算器的代码。

（2）建立一个空项目，添加Queue.h、Recursive.h、K_Fib.h、SeqQueue.h头文件以及Test.cpp源文件。

（3）你的第一个任务：

    在Recursive.h文件中PrintDigit()函数实现将单个数字(0-9)输出。设n是一个正整数（其位数不确定），请编写PrintOut()通过调用PrintDigit()函数实现输出正整数n，要求PrintOut（）函数用递归函数实现。

（4）你的第二个任务:

    在K_Fib.h文件中K_Fib()函数实现计算并输出K阶斐波那契序列（f0,f1,…,fn），其中该序列最大项fn小于或等于max，而第n+1项大于max。算法要求仅采用空间容量为K的数组实现，请编写代码实现该函数功能。

    提示：由于要求仅采用空间容量为K的数组实现，因此在输出K阶斐波那契序列过程中，需要删除或插入表中的元素。由于插入在表的一端进行，删除在表的另一端进行，因此采用顺序循环队列实现。在算法执行结束时，留在循环队列中的元素应是所求K阶斐波那契序列中的最后K项f(n-k+1),…,fn。