数据结构实验报告-实验二-power（x,n）求幂问题、教材2.19求主元问题的求解

忘是亡心i 2023-06-17 03:58 8阅读 0赞

# **实验二 power（x,n）求幂问题、教材2.19求主元问题的求解** #

##  ##

## 一、实验描述 ##

1.用基于2和3的方式分别写出算法来求power（x,n）。分析两种算法的复杂程度，设计实验来验证想法。

2.基于教材2.19题，设计并实现用分治求数组的主元的算法。如果不用分治，通过比较和计数，求复杂程度。

## 二、实验设计 ##

### 1.power（x,n）求幂问题： ###

若按常规方法计算x的n次方，需要进行n-1次乘法运算，效率低下。现在考虑将power(x,2)的结果保留到中间变量中(以2为底的方法)，则power(x,4)=power(x,2)\*power(x,2),只需两次乘法运算。再将power(x,4)的结果保留，则power(x,8)=power(x,4)\*power(x,4) ……按此思路，用尾递归的方法解题，在int power(x,n)函数中，若n为奇数，则返回power(x,n/2)\*x,若n为偶数，则返回power(x,n/2)，这样每经过一次递归调用，问题规模减半，预计算法时间复杂度为O（log2n）。以3为底的方法同理，按n%3为0,1,2分类，每次递归调用问题规模缩小至1/3，预计算法时间复杂度为O（log3n）。

### 2.教材2.19求主元问题： ###

大小为N的数组A，其主要元素是一个出现次数超过N/2的元素（从而这样的元素最多有一个）。例如，数组3,3,4,2,4,4,2,4,4有一个主要元素4，而数组3,3,4,2,4,4,2,4没有主要元素。如果没有主要元素，那么你的程序应该指出来。下面是求解该问题的一个算法的概要：

首先，找出主要元素的一个候选元（这是难点）。这个候选元是唯一有可能是主要元素的元素。第二步确定是否该候选元实际上就是主要元素，这正好是对数组的顺序搜索。为找出数组A的一个候选元，构造第二个数组B。比较A\[1\]和A\[2\]，如果它们相等，则取其中之一加到数组B中；否则什么也不做。以该方式继续下去直到读完这个数组。然后，递归地寻找B中的候选元；它也是A的候选元。

非分治算法：设置两重循环，将数组内的每一个元素与所有元素比较，若相同，则count++,若count>n/2,则该元素为主元，返回该元素。若循环结束还未满足条件，则返回0，表示没有找到主元。预计算法时间复杂度为O（n2）.

分治算法：采用递归，构造第二个数组B。比较A1和A2，若他们相等，则取其一加入B中，否则什么也不做。以该方式继续下去直到读完整个数组。然后对B数组重复上述操作。预计算法时间复杂度为O（n）。

## 三、实验实现过程 ##

（1）power（x,n）求幂问题：利用递归分别用以2为底和以3为底的方法，计算3的n次幂，输入7组大小分别为10、50、100、500、1000、5000、10000的n；

（2）教材2.19求主元问题：设计三种测试用例判断程序对错；

（3）定义两个时间类型变量start和end，分别用于记录一个函数执行前后的时间，将两个时间相减，便可以得到该函数的运行时间；

（4）对于power（x,n）求幂和与教材2.19求主元问题，记录程序执行1000000次所需的时间。

### 1.power（x,n）求幂问题： ###

（1）定义方法int power(int x,int n) //利用递归方法求解；

（2）将求值函数体循环1000000次，在函数执行前，定义time\_t类型的变量start=clock(); 函数执行后，加上代码：end=clock()；打印（int）(end-start) 记录函数结束时间；

（3）重复5 次实验，得到平均数据；

（4）记录相应7组实验结果并绘制相应Excel图表。

### 2.教材2.19求主元问题： ###

（1）分治法

（2）非分治法

## 四、实验结果 ##

1. power（x,n）求幂问题图表:

1.以2为底：

![format_png][]

2.以3为底：

![format_png 1][]

3.教材2.19求主元问题:

测试用例：

int A\[9\]=\{3,3,4,2,4,4,2,4,4,\};输出：主元：4。

intA\[8\]=\{3,3,4,2,4,4,4,4\};输出：主元：4。

int A\[8\]=\{3,3,4,2,4,4,2,4\};输出：主元：0（即无主元）。

## 五、实验结论 ##

算法时间复杂度分析：

power（x,n）求幂问题得出的n-t曲线近似为对数曲线，以2为底、以3为底的时间复杂度分别为O（log2N）与O（log3N），与预期相符。

教材2.19求主元问题所使用的三种测试用例均得出正确结果，非分治算法时间复杂度为O（N2）,分治算法时间复杂度为O（N）。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL2RvY2ltZy5uY21lbS5jb20vNDAwLzk5M2RkNmRlLnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL2RvY2ltZy5uY21lbS5jb20vNDAwLzk0MmZiODVjLnBuZw?x-oss-process=image/format,png