第一次实验实验报告
班级：2009211307 姓名：吕博文 学号：09211297 分工情况：个人一组 完成日期：11月5日
斐波那契数列递归和迭代算法
一、问题描述
分别写出下列函数的递归算法和迭代算法，并求出n=10时的函数值。 Fib(n) = n
当n=0或n=1 Fib(n-2) + Fib(n-1) 当n>=2
二、算法思想
用递归算法求解时，若输入的n的值为0或1，根据问题描述中Fib(n)的递归定义，算法直接返回n作为输出结果。当输入的n的值大于等于2时，根据Fib(n)的递归定义，算法将调用自身计算Fib(n-2)和Fib(n-1)的值，然后返回二者的和。
用迭代算法求解时，先初始化Fib(0)和Fib(1)的值，用两个变量curValue和preValue存储，curValue存储较大的数值，preValue存储较小的数值。若输入的n的值为0或1，算法直接返回n。若输入的n的值大于等于2，循环n-1次，每次循环将curValue和preValue的值相加存入curValue中，并用preValue存储原来curValue的值，为下一次循环做好准备。最终的curValue的值即为Fib(n)的值。
三、设计描述
先提示输入n的值，然后调用递归算法计算Fib(n)，输出，再调用迭代算法计算Fib(n)，输出。
递归算法
int ShowFib_1(int n) {
if (n == 0 || n == 1)//初始条件 return n;
else//不符合初始条件时，用递推关系计算 return ShowFib_1(n-2) + ShowFib_1(n-1); }
迭代算法
int ShowFib_2(int n) { preValue = 0; curValue = 1;//设定第
一、第二项的值作为初始条件
if (n == 0 || n == 1)//第
一、第二项可直接输出结果 return n; else
{
for (i = 2; i
{ temp = curValue; curValue = curValue + preValue; preValue = temp;
} returncurValue;
} }
四、源程序
#include using namespace std;
int ShowFib_1(int n);//定义递归函数 int ShowFib_2(int n);//定义迭代函数
int main() { int n;
cout> n;
//递归算法
cout
//迭代算法
cout
//递归算法
int ShowFib_1(int n) {
if (n == 0 || n == 1)//判定初始条件 return n; else//
return ShowFib_1(n-2) + ShowFib_1(n-1); }
//迭代算法
int ShowFib_2(int n) { intpreValue = 0, curValue = 1;//设定第
一、第二项的值 if (n == 0 || n == 1)// return n; else
{
for (int i = 2; i
{ int temp; temp = curValue; curValue = curValue + preValue; preValue = temp;
} returncurValue;
} }
五、测试结果
N=40时利用递归求算时计算机反应速度较慢
N=10时
六、心得体会
在N=40时，等待递归算法算出结果时间较长，可见递归算法计算斐波那契数列的效率不高。但使用迭代算法则想法，可见虽然迭代算法的思路稍难于递归算法，但时间复杂度与空间复杂度均优于递归算法。故更应推荐迭代算法。
另外，本题难度低，过程中没什么问题，故无太多感想。
第二题
一、问题描述
假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点而不设头指针，试编写相应的队列初始化、入队列、出队列和判断队列状态的算法。
利用上述算法完成下面的各操作，并在每一操作后输出队列状态。
1)下列元素逐一入队：5,7,3,8,55 状态：5个元素
2)3个元素出队
状态：２个元素
3)再２个元素出队
状态：队空
4)再１个元素出队
状态：队空（指示下溢）
二、算法思想
主函数中新建一个队列的对象，然后调用其成员函数进行队列的操作。 将5,7,3,8,55 入队→5,7,3出队→8,55出队→在队列为空时出队 每次操作后均输出当前队列状态。
三、设计描述
cla Queue{
//建立一个队列类 public: Queue(){}
~Queue();
intInit();
//初始化队列 int Insert(int);
//入队 int Delete(int&);
//出队 intQState();
//判断状态 private:
typedefstruct node { int data; struct node *next; }Node; Node *rear; };
四、源程序
#include using namespace std;
cla Queue { public: Queue(){} ~Queue();
intInit();//初始化队列
int Insert(int);//入队
int Delete(int&);//出队
intQState();//判断状态
private: typedefstruct node
{
int data;
struct node *next; }Node; Node *rear; };
int Queue::Init()//初始化 { rear=new Node; if(rear) {
rear->data=-1;
rear->next=rear;
return 1; } return 0; }
int Queue::Insert(intelem)//入队 { Node * newd=new Node;
newd->data=elem; newd->next=rear->next; rear->next=newd; rear=newd; return 1; }
int Queue::Delete(int&elem)//出队 { if(rear==rear->next)
return 0;
Node *p=rear->next->next; elem=p->data; rear->next->next=p->next; if(p==rear) //删最后一个
rear=rear->next; free(p); return 1;
}
int Queue::QState()//判定状态 {
int i=0; Node *q=rear->next;
cout
coutnext->data
q=q->next;
i++; } if(0==i)
cout
else
cout
Queue::~Queue()//删除，如有未释放空间 { int i; if(rear)
} {
} if(rear->next==rear) free(rear); else { while(rear->next!=rear)
Delete(i); free(rear); } //主函数 int main() { Queue DQ; intele; DQ.Init(); DQ.QState();
cout
5,7,3,8,55
cout
if(DQ.Delete(ele))// 出队
cout
if(DQ.Delete(ele))
cout
if(DQ.Delete(ele))
cout
DQ.QState();//当前状态 8,55 cout
system(\"pause\");
if(DQ.Delete(ele))
cout
cout
cout
if(DQ.Delete(ele))
cout
} cout
system(\"pause\");
五、测试结果
六、心得体会
这个程序的实现关键在于类，类对于数据结构可以说是非常重要非常基础也是必不可少的一个杀手锏。在编这道题的过程中，最初的想法是设计一个程序可以实现入队、出队、上溢下溢提示，但考虑到这道题的具体要求，改为了程序自动将题目所要求出入队的元素进行操作，不过不影响核心算法核心思想的实现。
基于信息技术的数学探究课题设计一例——“斐波那契数列”教学课例
