求a的n次方

曾经终败给现在 2021-11-08 22:12 351阅读 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 条评论，351人围观）

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

相关阅读

相关 C语言------求n的k次方

求n的k次方代码部分 include<stdio.h> double mypow(int n, int k) {

痛定思痛。/ 2023年10月09日 13:24/ 0 赞/ 43 阅读

相关 c++求a的b次方/次幂

![watermark,type\_d3F5LXplbmhlaQ,shadow\_50,text\_Q1NETiBA6LaFMzM4,size\_20,color\_FFFFF

r囧r小猫/ 2023年09月30日 10:43/ 0 赞/ 19 阅读

相关 leecode 求 x 的 n 次方

通用做法 n 次循环让 n 个 x 相乘快速幂思想举个例子，例如我们要求 2^8 1. 通过 2 \ 2 = 4 得到 2^2 2. 利用刚才的结果，让

小咪咪/ 2023年06月18日 10:52/ 0 赞/ 21 阅读

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

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

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

相关求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 赞/ 197 阅读

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

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

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

相关快速幂求x的n次方

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

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

相关求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 赞/ 224 阅读

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

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

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

相关求a的n次方

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

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