实现阶乘

[编程题]实现阶乘

热度指数：12645 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

请实现函数 pow(x, n).

示例1

输入

6.88023,3

输出

325.69333

算法知识视频讲解

Java

liangshang

快速幂的思路是这样的，比如我们要求 3 ^ 5，其中5的二进制表示为0101，因此3 ^ 5可以分解成 3 ^ (2 ^ 0) * 3 ^ (2 ^ 2) = 3 ^ 1 * 3 ^ 4 = 3 ^ 5

public class Solution {
    public double pow (double x, double n) {
        // write code here
        long num = (long) n;
        if (num < 0) {
            x = 1/ x;
            num = -num;
        }
        double res = 1;
        while (num != 0) {
            if ((num & 1) != 0)
               res *= x;
            x = x * x;
            num = num >> 1;
        }
        return res;
    }
}

发表于 2020-10-18 14:24:29 回复(0)

Java

日常不想上班的码农

import java.util.*;


public class Solution {
    public double pow(double x, double n) {
        boolean bigZero = n > 0;
        int mi = Math.abs((int)n);
        double res = myPowHelper(x, mi);
        if (bigZero) {
            return res;
        }
        return 1 / res;
    }
    // 递归版本
    public double myPowHelper(double x, int n) {
        if (n == 0) {
            return 1;
        }
        double res = 1;
        if ((n & 1) == 0) {
            double temp = myPowHelper(x, n / 2);
            res = temp * temp;
        } else {
            double temp = myPowHelper(x, n / 2);
            res = temp * temp * x;
        }
        return res;
    }
        // 迭代版本
    public double myPowHelperTwo(double x, int n) {
        if(n == 0) {
            return 1;
        }
        double res = 1;
        if((n & 1) == 0) {
            for(int i = 0; i < n / 2; i++) {
                res *= x;
            }
            res *= res;
        } else{
            for(int i = 0; i < n / 2; i++) {
                res *= x;
            }
 
            res = res * res * x;
        }
        return res;
    }
}

编辑于 2020-08-01 19:33:29 回复(0)

Java

Schefferk

 public double pow (double x, double n) {
        // write code here
     double res = power(x, Math.abs((int)n));
     return n > 0 ? res : 1.0/res;
 }
    
public double power(double x, int n){
    if(n == 0){
        return 1;
    }
    if(n % 2.0 == 0){
        return power(x * x, n/2);
    }else {
        return power(x * x, n / 2) * x;
    }
}

首先是不管n的正负，都把它当成是正数处理，如果是负数，最后求倒数

编辑于 2020-06-29 23:48:29 回复(0)

Java

菜鸟在进步

double result = 1;

long N = Math.abs((long) n);
while (N != 0) {
    if ((N & 1) == 1)
        result *= x;
    x *= x;
    N >>= 1;
}
return n > 0 ? result : 1 / result;

编辑于 2019-02-28 16:49:22 回复(0)

Java

Holiday_12138

public class Solution {
    public double pow(double x, int n) {
        if(n < 0)
            return 1/pow(x, -(n + 1)) * (1 / x);
        double res = 1;
        while(n >= 1) {
            if((n & 1) == 1)
                res *= x;
            x *= x;
            n >>= 1;
        }
        return res;
    }
}

发表于 2017-06-19 12:05:16 回复(0)

Java

kuiblog.com

public class Solution{
      public double pow(double x, int n){

          if(n<0){
              return 1/power(x,-n);
          }else if(n>0){
              return power(x,n);
          }else{
            return 1;
        }
      }

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

发表于 2017-05-16 15:31:51 回复(0)

Java

詆調壹點

public class Solution {
    public static double pow(double x, int n) {
		if(n == 0) return 1;
		if(n < 0) return 1 / x * pow(1 / x, - (n + 1));
		if(n % 2 == 0) return pow(x * x, n / 2);
		else return pow(x * x, n / 2) * x;
	}
}

发表于 2017-03-25 22:28:31 回复(5)

Java

城市里的养猫者

public class Solution {
    
    public double pow(double x, int n) {
        
        if(n == 0)
            
            return 1;
        
        if(n<0){
            n = -n;
            x = 
            n = -n;
            x = 1/x;
        }
        
        }
        return (n%2 == 0) ? pow(x*x, n/2) : x*pow(x*x, n/2);
    }
}
    }
}

发表于 2017-03-12 12:49:03 回复(0)