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

秒速五厘米 2022-05-31 10:53 28阅读 0赞

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

##     ##

## 一、实验描述 ##

1.  用基于2和3的方式分别写出算法来求power（x,n）。分析两种算法的复杂程度，设计实验来验证想法。
2.  基于教材（《数据结构与算法分析·c语言描述》）中的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图表。

（5）附代码：

####      a.以2为底： ####

#include <stdio.h>
 #include <time.h>
 
 static int power (int x, int n);
 
 static int count = 0;
 
 //********************************
 static int power (int x, int n)
 { 
 if (0 == n)
 return (1);
 
 count++;
 
 if (n & 1)//n是奇数 
 {
 count++;
 return (power (x*x, n>>1) * x);
 }
 
 return (power (x*x, n>>1));//n是偶数 
 }
 
 main ()
 {
 int n = 10000;
 time_t start,end;
 start=clock();
 for(int i=0;i<1000000;i++){
 	power(3,n);
 } 
 end=clock();
 printf("time:%d",end-start);
 //printf ("after %d multiplications 2^%d is computed as %d\n", count, n, power (1, n));
 }

####      b.以3为底： ####

#include <stdio.h>
 #include <time.h>
 static int count=0;
 int main()
 {
 	int power(int x,int n);
 	int n=9000;
 	time_t start,end;
 	start=clock();
 	for(int i=0;i<1000000;i++){
 		power(3,n);
 	} 
 	end=clock();
 	printf("time:%d",end-start);
 	//printf ("after %d multiplications 3^%d is computed as %d\n", count, n, power (3, n));
 }
 int power(int x,int n)
 {
 	if(0==n)
 		return 1;
 	else if(1==n)
 		return x;
 	else if(2==n)
 		count++;
 		return x*x; 
 else if(0==n%3)
 {
 	count=count+2;
 		return power(x*x*x,n/3);
 	}
 	else if(1==n%3)
 	{
 		count=count+3;
 		return power(x*x*x,n/3)*x;
 	}
 	else if(2==n%3)
 	{
 		count=count+4;
 		return power(x*x*x,n/3)*x*x;
 	}
 }

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

### a.分治法： ###

（1）附代码：

#include <stdio.h>
 #include <time.h>
 int main(){
 	int find(int *array,int n);
 	int A[9]={3,3,4,2,2,2,9,3,4};
 	time_t start,end;
 	start=clock();
 	for(int i=0;i<1000000;i++)
 	 find(A,8);
 	end=clock();
 	printf("time:%d",end-start);
 	printf("主元：%d",find(A,9));
 }
 int find(int *array,int n)
 {
 	int length=0;
 	if(1==n)
 	 return array[0];
 	else if(1!=n)
 	{
 		if(n&1)//array长度为奇数 
 		{
 			int B[n/2+1];
 			int j=0;
 			for(int i=0;i<n-1;i+=2)
 			{
 				if(array[i]==array[i+1])
 				 B[j++]=array[i];
 			}
 			B[j]=array[n-1];
 			return find(B,j+1);
 		}
 		else
 		{
 			int B[n/2];
 			int j=0;
 			for(int i=0;i<n;i+=2)
 			{
 				if(array[i]==array[i+1])
 				{
 					B[j++]=array[i];
 				}
 				return find(B,j+1);
 			}
 		}
 	}
 	else return 0;
 }

#### b.非分治法： ####

（1）附代码：

#include <stdio.h>
 int main(){
 	int find(int *array,int n);
 	int example[8]={3,3,4,2,4,4,2,4};
 	printf("主元：%d",find(example,8));
 }
 int find(int *array,int n)
 {
 	int count=0;
 	for(int i=0;i<n;i++)
 	{
 		count=0; 
 		for(int j=0;j<n;j++)
 		{
 			if(array[j]==array[i])
 			 count++;
 		}
 		if(n&1)//n为奇数 
 		{
 			if(count>n/2+1)
 			 return array[i];
 		}
 		else if(0==n%2)//n为偶数 
 		{
 			if(count>n/2)
 			 return array[i];
 		}
 	}
 	return 0;
 }

## 四、实验结果 ##

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

#### a.以2为底： ####

![70][]

#### b.以3为底： ####

![70 1][]

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

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

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

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

## 五，实验结论 ##

### 算法时间复杂度分析： ###