数据结构实验报告-实验一-求整数和、切pizza和Hanoi塔等问题的求解
实验一 求整数和、切pizza和Hanoi塔等问题的求解
一，实验描述
用C语言编程实现求整数和，切pizza以及Hanoi塔等问题的求解，在程序中加入clock ()来计算求解时间，使用不同的输入值得到对应的时间值。分析算法的时间复杂度并与测量结果进行比较，如果存在差异，解释原因。
二，实验设计
1.求整数和问题：利用递归来计算n项和的值，输入9组大小分别100,200,300,400,500,600，700,800，900的n；
2.切pizza问题：利用迭代的方式来计算切n刀后的pizza块数，输入10组大小为100至900的n；
3.Hanoi塔问题：利用递归来求解Hanoi问题，输入大小为8至16的n；
4.定义两个时间类型变量start和end，分别用于记录一个函数执行前后的时间，将两个时间相减并除以CLOCKS_PER_SEC，便可以得到该函数的运行时间；
5.对于求整数和与切pizza问题，记录程序执行1000000次所需的时间；对于Hanoi塔问题，记录得到时间的2的对数值；分别用合适的Excel图表对它们进行描述。
三，实验实现过程
1.整数求和问题：
（1）定义int型变量input并通过scanf()函数对变量n赋值，把n作为求和函数的参数；
（2）定义clock_t类型的变量start并调用clock（）函数来记录函数开始执行时间；
（3）定义方法func(int n) //利用递归方法求解；
（4）定义clock_t类型的变量end并调用clock（）函数来记录函数结束时间。
（5）将求值函数体循环1000000次，在函数执行前，加上代码： start=clock(); 函数执行后，加上代码：end=clock()；
（6）打印(double)(end-start)/CLOCKS_PER_SEC；
（7）重复5 次实验，得到平均数据；
（8）记录相应9组实验结果并绘制相应Excel图表。
2.切pizza问题：
（1）定义int型变量input并通过scanf()函数对变量n赋值，把n作为计算块数函数的参数；
（2）定义clock_t类型的变量start并调用clock（）函数来记录函数开始执行时间；
（3）定义方法qie(int n) //利用循环来求和；
（4）定义clock_t类型的变量end并调用clock（）函数来记录函数结束执行时间；
（5）将求值函数体循环1000000次，在函数执行前，加上代码： start=clock(); 函数执行后，加上代码：end=clock()；
（6）打印(double)(start-end)/ CLOCKS_PER_SEC；
（7）重复5 次实验，得到平均数据；
（8）记录相应9组实验结果并绘制相应Excel图表。
3.Hanoi塔问题：
（1）定义int型变量input并通过scanf()操作得到值作为求pizza块数的函数的参数；
（2）定义clock_t类型的变量start并调用clock（）函数来记录开始时间；
（3）定义方法HanoiTower(int n,char source,char temp,char target)//利用递归来求解问题；
（4）定义clock_t类型的变量end并调用clock（）函数来记录函数结束执行时间；
（5）打印（double）(end-start)/CLOCKS_PER_SEC；
（6）重复5 次实验，得到平均数据；
（7）记录相应9组数据并求2的对数，绘制出相应Excel图表。
四，实验结果
1.求整数和问题图表
|
整数值 |
100 |
200 |
300 |
400 |
500 |
600 |
700 |
800 |
900 |
|
时间平均值 |
0.343 |
0.648 |
0.967 |
1.327 |
1.625 |
1.949 |
2.297 |
2.616 |
2.951 |
2.切pizza问题图表
|
切的次数 |
100 |
200 |
300 |
400 |
500 |
600 |
700 |
800 |
900 |
|
时间平均值 |
0.319 |
0.629 |
0.934 |
1.235 |
1.539 |
1.841 |
2.155 |
2.44 |
2.753 |
3.Hanoi塔问题图表
|
n |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
|
时间 |
0.009 |
0.018 |
0.037 |
0.078 |
0.153 |
0.206 |
0.303 |
1.222 |
2.448 |
|
T的2的对数 |
-6.79 |
-5.79 |
-4.76 |
-3.68 |
-2.71 |
-2.28 |
-1.72 |
0.289 |
1.292 |
五，实验结论
1，算法时间复杂度分析
对于用递归方法求n项整数和与用迭代方法求切pizza所得的块数，它们的时间复杂度T(N)都等于O(N)；Hanoi塔问题使用递归方法，有T(N)=2T(N-1)+1， T(1)=1消去系数和常量得T(N)=O(2^N)；
2，与测量结果进行比对
求整数和问题与切pizza问题最后得到的结果曲线均为一条直线，n与时间t成线性关系，与算法时间复杂度分析所得的T(N)=O(N)吻合；Hanoi塔问题最后得到的结果曲线大致呈现出线性增长，与前面的分析吻合，曲线存在波动可能与CPU的内存分配与运行速度有关（n增大，2^n迅速增大，递归占用内存也迅速增加）。