求a的n次方

曾经终败给现在 2021-11-08 22:12 305阅读 0赞

此题面试时常有：

解答方法有以下三种：

1。 直接迭代求解，这个很简单，复杂度O(n)。

1。 分治法。复杂度 logn

此方法有点凹，原理是：a的n次方可以分别对应两种情况:

1。 n为偶数  那么 an= (a\*a)n/2

2。n为奇数 那么  an=  a\*an-1

代码如下：

int  power( int  a , int  n)  
\{  
      if (n  ==   0 )  
           return   1 ;  
      if (n & 1 )  
           return  a \* power(a,n \- 1 );  
      else   
           return  power(a \* a,n >> 1 );  
\}

3.此方法复杂度为 n的二进制表示中最高位1的index

原理为：事先建立a的 2m m为(0,x);的表。指导找到一个最小的x使得 n<2X然后 利用a中二进制位的位置和个数信息得到最终结果

\#define  MAX 32   
 int  my\_pow( int  a, int  n)  
\{  
     if  (a  ==   1   )  
    \{  
         return   1 ;  
    \}  
     if  (n  == 0 )  
    \{  
         if  (a  ==   0 )  
             return   \- 1 ;  
         return   1  ;  
    \}  
    unsigned  int  table\[MAX\];  
    table\[ 0 \]  =  a;   
     for  ( int  i  =   1 ;i < MAX  &&  i < n;i \++ )  
    \{  
        table\[i\]  =  table\[i \- 1 \] \* table\[i \- 1 \];  
    \}  
    i  =   0 ;  
     int  m  =   1 ;  
     while  ( n >> i)  
    \{  
         if ( 1 & n >> i)  
            m  =  m  \* table\[i\];  
        i \++ ;  
    \}  
     return  m;  
\}

转载于:https://www.cnblogs.com/davidluo/articles/1799680.html

发表评论取消回复

表情：

评论列表（有 0 条评论，305人围观）

还没有评论，来说两句吧...

相关阅读

相关 python实现pow函数（求n次幂，求n次方）

实现 pow(x, n)，即计算 x 的 n 次幂函数。其中n为整数。解法1：暴力法不是常规意义上的暴力，过程中通过动态调整底数的大小来加快求解。代码如下：

冷不防/ 2022年10月08日 02:28/ 0 赞/ 158 阅读

相关求a的b次方、a的b次方对m取模

[求a的b次方、a的b次方对m取模][a_b_a_b_m] 快速计算乘方的算法，求a的b次方 > 如计算2^13，则传统做

约定不等于承诺〃/ 2022年08月25日 05:28/ 0 赞/ 157 阅读

相关【算法】求n的m次方（快速幂取模）

题目求n的m次方，n，m均为自然数。解析看似简单的题目，但是要想写的高效还不是那么容易想出来。实现 unsigned int power(

以你之姓@/ 2022年08月09日 06:45/ 0 赞/ 205 阅读

相关 a的n次方的高效算法

a^b的高效算法 LZ之所以要贴上这个算法，是因为LZ的一个朋友用这个小算法考过LZ，我当时想到了这个算法，思想有了，但是没有实现出来，但是我朋友用递归的方法写的，但是递归

布满荆棘的人生/ 2022年08月01日 03:12/ 0 赞/ 140 阅读

相关快速幂求x的n次方

问题 O(logn)的时间复杂度求x的n次方，x为自然数，n为整数？举例解析如果 power=5 为奇数，result保存当前的多余的一个4，并在返回结果时一

缺乏、安全感/ 2022年07月16日 09:55/ 0 赞/ 213 阅读

相关求a的b次方根

求 a√b ,可以写成 a√−−−√b/2 , a√−−−√−−−−−√b/4, … 因此，b/2k \{k = 1, 2, 3,…\} 无限趋近与1时，a√2k即为结果

叁歲伎倆/ 2022年07月15日 13:28/ 0 赞/ 169 阅读

相关求二次方

题目描述为数组 arr 中的每个元素求二次方。不要直接修改数组 arr，结果返回新的数组示例1 输入 [1, 2, 3, 4] 输出

秒速五厘米/ 2022年06月05日 09:21/ 0 赞/ 186 阅读

相关计算2的n次方

计算2的N次方时间限制: 1000ms内存限制: 65536kB 描述任意给定一个正整数N(N<=100)，计算2的N次方的值。输入输入只

淩亂°似流年/ 2022年05月23日 04:09/ 0 赞/ 172 阅读

相关求M的N次方的后三位

1 include <cstdlib> 2 include <iostream> 3 using namespace std; 4 int

约定不等于承诺〃/ 2021年12月20日 09:04/ 0 赞/ 235 阅读

相关求a的n次方

此题面试时常有：解答方法有以下三种： 1。直接迭代求解，这个很简单，复杂度O(n)。 1。分治法。复杂度 logn 此方法有点凹，原理是：a的n次方可以分别对应两

曾经终败给现在/ 2021年11月08日 22:12/ 0 赞/ 306 阅读