数据结构实验报告-实验一-求整数和、切pizza和Hanoi塔等问题的求解

我不是女神ヾ 2023-06-17 03:57 17阅读 0赞

# **实验一 求整数和、切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.求整数和问题图表 ###

<table> 
 <tbody> 
 <tr> 
 <td> 整数值 </td> 
 <td> 100 </td> 
 <td> 200 </td> 
 <td> 300 </td> 
 <td> 400 </td> 
 <td> 500 </td> 
 <td> 600 </td> 
 <td> 700 </td> 
 <td> 800 </td> 
 <td> 900 </td> 
 </tr> 
 <tr> 
 <td> 时间平均值 </td> 
 <td> 0.343 </td> 
 <td> 0.648 </td> 
 <td> 0.967 </td> 
 <td> 1.327 </td> 
 <td> 1.625 </td> 
 <td> 1.949 </td> 
 <td> 2.297 </td> 
 <td> 2.616 </td> 
 <td> 2.951 </td> 
 </tr> 
 </tbody> 
</table>

![format_png][]

### 2.切pizza问题图表 ###

<table> 
 <tbody> 
 <tr> 
 <td> 切的次数 </td> 
 <td> 100 </td> 
 <td> 200 </td> 
 <td> 300 </td> 
 <td> 400 </td> 
 <td> 500 </td> 
 <td> 600 </td> 
 <td> 700 </td> 
 <td> 800 </td> 
 <td> 900 </td> 
 </tr> 
 <tr> 
 <td> 时间平均值 </td> 
 <td> 0.319 </td> 
 <td> 0.629 </td> 
 <td> 0.934 </td> 
 <td> 1.235 </td> 
 <td> 1.539 </td> 
 <td> 1.841 </td> 
 <td> 2.155 </td> 
 <td> 2.44 </td> 
 <td> 2.753 </td> 
 </tr> 
 </tbody> 
</table>

![format_png 1][]

### 3.Hanoi塔问题图表 ###

![format_png 2][]

![format_png 3][]

## 五，实验结论 ##

### 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迅速增大，递归占用内存也迅速增加）。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL2RvY2ltZy5uY21lbS5jb20vNDAwL2EwMDk3MzBlLnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL2RvY2ltZy5uY21lbS5jb20vNDAwLzc2YzMxZjYxLnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cDovL2RvY2ltZy5uY21lbS5jb20vNDAwL2M5MjJjMzNhLnBuZw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cDovL2RvY2ltZy5uY21lbS5jb20vNDAwLzc0ZDQwM2JmLnBuZw?x-oss-process=image/format,png