c 语言 朴素算法与分治算法计算X^n

朴素算法：不详细讲了，就是先算x乘x，算完结果在乘x，直到n个x相乘

分治算法（看图比较方便）

如图：算法先将X^n分开，分到不能再分为止（分的时候是调用自身函数），程序运行时也是如此，当不能再分时开始和从下往上和，例如3^6，先算sum=3*3*3，再算sum=sum*sum（即sum=3^3*3^3）

朴素算法与分治算法计算X^n的算法比较

#include<stdio.h>

#include<stdlib.h>//strand，rand函数头文件

#include<time.h>//clock函数头文件

doubleputong(int x,int n)//普通方法计算X^n

{

    double time;//运行时间

    clock_t beg,end;//起始时间，结束时间

    beg=clock();                //普通方法起始时间

    long long he=1;//存储结果

    int i;

    for(i=1;i<=n;i++) //循环计算结果

    {

        he=he*x;

    }  

    end=clock();//普通方法结束时间

    time=(double)(end-beg) / CLOCKS_PER_SEC; //普通方法运行时间

    printf("%lld\n",he);

    return time;

}

longlong erfen(int x, int n)//二分（分治）计算X^n

{      

    long long he;//存储结果

    if(n==1)

        return (long long)x;//结束自身循环或n为1

    else if(n > 1)

    {

        long long s;

        int m=n/2;//分段

        s=erfen(x,m);//调用本身函数（递归）

        if(n%2==0)//n为偶次

        {

            he=s*s;//进行分段计算

            return he;

        }

        else

        {

            he=s*s*x;//进行分段计算

            return he;//n为奇次

        }

    }

}

intmain()

{

    int x,n;

    double time;//运行时间

    printf("输入X的值：");

    scanf("%d",&x);

    printf("输入n的值：");

    scanf("%d",&n);

    clock_t beg,end;//起始时间和结束时间

    printf("普通算法运行时间为%f\n",putong(x,n));

    beg=clock();//二分（分治）起始时间

    long long sum=erfen(x,n);

    end=clock();//二分（分治）结束时间

    time=(double)(end- beg) / CLOCKS_PER_SEC;// //二分（分治）运行时间

    printf("二分算法运行时间为%f\n",time);

    return 0;

}