实验二：快速求幂和主元问题的求解_#includelong power(int n){long f;if(n>1)f

实验二：快速求幂和主元问题的求解

一、实验描述

1. 用基于2和3的方式分别写出算法来求power(x, n)，分析两种算法的复杂程度，设计试验来验证；
2. 设计并实现分治求数组的主元的算法，如果不用分治，通过比较和计数，分析其复杂程度。

二、实验设计

1. 若采用常规方法逐次计算x的n次方，需要进行n-1次乘法运算。现考虑以2为底，缓存中间结果，从而避免重复计算。例如power(x,4)=power(x,2)*power(x,2),只需两次乘法运算。再将power(x,4)的结果保留，则power(x,8)=power(x,4)power(x,4)……若采用递归算法，以n=0为基准情形（power(x,0)=1），若n为奇数，则返回power(xx, n/2)x,若n为偶数，则返回power(xx, n/2)，这样每经过一次递归调用，问题规模减半，预计算法时间复杂度为O（log₂n）。同理，若以3为底，以n=0，n=1及n=2为基准情形（power(x,0)=1,power(x,1)=x, power(x,2)=x^2）按n%3为0,1,2分类，每次递归调用问题规模缩小至1/3，预计算法时间复杂度为O（log₃n）。

2. 问题描述：大小为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₁和A₂，如果它们相等，则取其中之一加到数组B中；否则什么也不做。然后比较A₃和A₄，同样地，如果它们相等，则取其中之一加到B中；否则什么也不做。以该方式继续下去直到读完这个数组。然后，递归地寻找B中的候选元；它也是A的候选元。

   分治算法：构造第二个数组B。比较A₁和A₂，如果它们相等，则取其中之一加到数组B中；否则什么也不做。然后比较A₃和A₄，同样地，如果它们相等，则取其中之一加到B中；否则什么也不做。以该方式继续下去直到读完这个数组。然后对B数组重复上述操作。最后对数组A进行遍历，确定该候选元是否为主元。预计算法时间复杂度为O(n)

   非分治算法：采用双重for循环，从A₁开始，将数组内的每一个元素依次与所有元素比较，若相同，则count++。只要count>n/2,则该元素为主元，返回该元素。若循环结束还未满足条件，则返回-1，表示没有找到主元。预计算法时间复杂度为O(n²)

三、实验实现过程

1. 快速求幂
   以2为底：
   1） 定义函数power(x, n), 以n=0为基准情形（power(x, 0)=1）。利用for循环，for语句内按n为奇数或是偶数分别返回power(x*x, n/2)x或power(xx, n/2)，每次循环使n右移一位
   2） 定义clock_t类型变量start_time和end_time，调用clock()函数来记录函数开始和结束的执行时间
   3） 在main函数中将函数体循环1000000次，
   4） 打印(double)(end_time-start_time)
   5） 重复5次实验，取平均值
   6） 记录n依次为50,1000,2000,3000…9000时的实验数据并绘制Excel图表

#include <stdio.h>
#include <stdlib.h>
#include<time.h>

long int power(int x,int n){
    if(n==0){
        return 1;
    }
    if(n%2==0){
        return power(x*x,n/2);
    }
    else return power(x*x,n/2)*x;
}

int main(){
    clock_t start_time,end_time;
    int x=3;
    start_time=clock();
    for(int i = 0;i < 1000000;i++){
         power(x,100);
    }
    end_time=clock();
    printf("%f",(double)(end_time - start_time));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2. 以3为底
   1）定义函数power(x, n)，以n=0，n=1及n=2为基准情形（power(x, 0)=1,power(x, 1)=x, power(x, 2)=x^2）。利用for循环，for语句内按n%3为0、1、2分别返回power(xxx, n/3)、power(xxx, n/3)x, power(xx*x, n/3)xx
   2）定义clock_t类型变量start_time和end_time，调用clock()函数来记录函数开始和结束的执行时间
   3）在main中将函数体循环1000000次
   4）打印(double)(end_time-start_time)
   5）重复5次实验，取平均值
   6）记录n依次为100,500,1000,2000,3000,…8000时的实验数据并绘制图表

#include <stdio.h>
#include <stdlib.h>
#include<time.h>

long int power(int x,int n){
    if(n==0){
        return 1;
    }
    if(n==1){
        return x;
    }
    if(n==2){
        return x*x;
    }
    if(n%3==0){
        return (power(x*x*x,n/3));
    }
    if(n%3==1){
    return power(x*x*x,n/3)*x;
    }
    return power(x*x*x,n/3)*x*x;
}

int main(){
    clock_t start_time,end_time;
    int x=3;
    start_time=clock();
    for(int i = 0;i < 1000000;i++){
         power(x,2000);
    }
    end_time=clock();
    printf("%f",(double)(end_time - start_time));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

3．主元问题
分治算法

1. 定义函数major(int a[], int n)，设定n=0与n=1时为基准情形（n=0时，返回-1；n=1时，返回a[0]）。定义int型变量i,j,k（初值分别为0,0,n/2）与tmp。利用for循环对数组遍历。若a[2i]与a[2i+1]相等，交换a[j]与a[2*i], 并使i与j自增1. 之后递归调用major(a[],j)。如果n为奇数且tmp等于-1，则a[n-1]即为主元，否则，返回tmp
   2）在main函数输入一组数验证算法

#include <stdio.h>
#include <stdlib.h>

int major(int array[], int n) //找出备选主元
{
    int i = 0, j = 0, k = n/2, tmp;
    if(n <= 0)
    {
         return -1;
    }
   if(1 == n)
    {
        return array[0];
    }
    for( ; i < k ; i++)
    {
        if(array[2*i] == array[2*i + 1])
        {
            tmp = array[j];
            array[j++] = array[2*i];
            array[2*i] = tmp;
        }
    }
    tmp = major(array, j);
    if((n % 2 == 1) && (tmp == -1))
    {
        return array[n-1];
    }
    return tmp;
}
int main()
{
    int a[10] = {1,2,1,2,1,2,1,2,1,2}; //遍历数组判断备选元是否为主元
    int majorele = major(a,10);
    int count = 0;
    for(int i = 0; i < 10; i++)
    {
        if(a[i] == majorele)
        {
            count++;
        }
    }
    if(count <= 5){
        printf("无主元\n");
    }
    else
    {
         printf("主元为：%d\n", majorele);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

4. 非分治算法
   1）定义函数major(int a[], int n)，采用双重for循环。定义int型变量i,j（初值为0，i+1）。将a[i]依次与a[j]比较，若相同，则count++。执行一次内层循环j++，执行一次外层循环i++。只要count>n/2,则该元素为主元，返回该元素。若循环结束还未满足条件，则返回-1
   2）在main函数输入一组数验证算法

四、实验结果

1. 以2为底求幂图表
   
   (横轴为N）
   
   （横轴为lnN）
   
2. 以3为底求幂图表
   
   （横轴为N）
   
   （横轴为lnN）
   
3. 主元问题测试用例及结果
   array[10]={1,1,1,1,1,1,7,8,9,10} 返回值：1
   array[10]={1,1,1,1,1,2,2,2,2,2} 返回值：-1（无主元）
   array[9]={1,1,1,1,1,2,2,2,1} 返回值： 1
   array[9]={1,1,3,1,2,2,2,1,3} 返回值： -1（无主元）

五、实验结论

1. 求幂问题拟合得到的的n-t曲线近似为对数曲线，lnN - t曲线近似为直线。以2为底、以3为底的时间复杂度分别为O（log₂N）与O（log₃N），与预期相符；
2. 验证主元问题所使用的四个测试用例均得n出正确结果，分治算法时间复杂度为O（N），非分治算法时间复杂度为O（N²）（非分治算法采用了嵌套的双层for循环）

附：主元问题迭代代码（时间复杂度为O（n))

#include <stdio.h>
#include <stdlib.h>

int major(int *array, int n) //找出被选元
{
    int tmp = -1, count = 0;
    for(int i = 0; i < n; i++)
    {
        if(array[i] == tmp)
        {
            count++;
        }
        else if (count == 0)
        {
            tmp = array[i];
            count++;
        }
        else
            count--;
    }
    if(count == 0)
        return -1;
    return tmp;
}

int main()
{
    int a[11] = {1,2,1,2,1,2,1,2,1,1};
    int majorele = major(a,10);
    int count = 0;
    if(majorele == -1)
    {
        printf("无主元");
    }
    else //遍历数组判断被选元是否为主元
    {
         for(int i = 0; i < 10; i++)
         {
            if(a[i] == majorele)
            {
                count++;
            }
        }
        if(count <= 5){
            printf("无主元\n");
        }
        else
        {
            printf("主元为：%d\n", majorele);
        }
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54