a的n次方的高效算法

布满荆棘的人生 2022-08-01 03:12 178阅读 0赞

**a^b的高效算法**  
LZ之所以要贴上这个算法，是因为LZ的一个朋友用这个小算法考过LZ，我当时想到了这个算法，思想有了，但是没有实现出来，但是我朋友用递归的方法写的，但是递归的LZ的理解不是很深刻，所以这里用自己理解的非递归的形式写出来。

#include<stdio.h>
    int pow(int a,int b)  //不用栈的方法
    {
        int r=1;
        if(b==0)
            return 1;
        if(b==1)
            return a;
        while(b>1)
        {
            if(b%2!=0)
                r*=a;
            a*=a;
            b/=2;
        }
        return a*r;
    }
    int _pow(int a,int b)  //用栈操作
    { 
        int stack[65],index=0;
        int res=1;
        if(b==0)
            return 1;
        if(b==1)
            return a;
        while(b>0)
        {
            stack[index++]=b%2;
            b/=2;
        }
        for(int i=index-1;i>=0;i--)
        {
            if(stack[i]==0)
                res*=res;
            else{
                res*=res;
                res*=a;
            }
        }
        return res;
    }
    int __pow(int a,int b) //最原始的方法，一般都能想到，但是效率很差，
    {                    
        int res=1;
        if(b==0)
            return 1;
        for(int i=1;i<=b;i++)
            res*=a;
        return res;
    }
    int main()
    {
        int a,b;
        while(scanf_s("%d%d",&a,&b))
        {
          printf("%d\n",__pow(a,b));
          printf("%d\n",_pow(a,b));
          printf("%d\n",pow(a,b));
        }
        return 0;
    }

原理:  
假如 b=13  
那么 b的二进制形式为1101,我们知道:

![这里写图片描述][20150618230430230]

那么:

![这里写图片描述][20150618230530480]

在这里我们可以利用栈这种数据结构来实现将b转为二进制，大概思路就是这样。  
运行截图:

![这里写图片描述][20150618230203513]

大家有不明白的可以看看这个博主写的，我有一部分也是借鉴这个博主的。

> [http://blog.csdn.net/pakko/article/details/6890452][http_blog.csdn.net_pakko_article_details_6890452]

[20150618230430230]: /images/20220731/67155699771f47c782ff21c989da41c5.png
[20150618230530480]: /images/20220731/febfe518bc774f6bb205173a0dafc4da.png
[20150618230203513]: /images/20220731/6aa839d2211e428cba61aec14cf53e6f.png
[http_blog.csdn.net_pakko_article_details_6890452]: http://blog.csdn.net/pakko/article/details/6890452