LeetCode：Compute Digit （计算PI后面的100位小数点）

迷南。 2022-05-14 07:37 114阅读 0赞

首先，这个题目是以前读书时候竞赛上出现的一道题目，当时没有做出来，我只是知道思路，因为数太大没计算出现；最近刚好复习BigInteger和BigDecimal 的知识，而不能用double，就想到了这个题目；

--------------------

要求解PI首先要知道他的求解公式：

**arctan(x)  =  x − x3/3 + x5/5 − x7/7 + x9/9 − x11/11 + . . .**

<table> 
 <tbody> 
  <tr> 
   <td><strong>π&nbsp;&nbsp;=</strong></td> 
   <td><strong>&nbsp;&nbsp;12·arctan(1/4)</strong></td> 
   <td><strong>+</strong></td> 
   <td><strong>&nbsp;&nbsp;&nbsp;&nbsp;4·arctan(1/20)</strong></td> 
   <td><strong>+</strong></td> 
   <td colspan="3"><strong>&nbsp;&nbsp;&nbsp;&nbsp;4·arctan(1/1985)</strong></td> 
  </tr> 
 </tbody> 
</table>

就可以根据给出的公式来进行求解：

package gc;
    
    import java.math.BigDecimal;
    import java.math.BigInteger;
    
    import org.junit.Test;
    
    /**
    *类描述:根据泰勒公式计算PI小数点后面的100位数            计算时间太长，但是自我感觉程序没有问题
    *arctan(x) = x − x3/3 + x5/5 − x7/7 + x9/9 − x11/11 + . . .
    *
    *π  =12·arctan(1/4)	+4·arctan(1/20)	+4·arctan(1/1985)
    *根据此公式计算PI的值
    *
    *@author: 张宇
    *@version 1.0
     */
    public class ComputePI3 {
    	@Test
        public void fun(){
        	BigDecimal integerNumber1=new BigDecimal(12);
        	BigDecimal integerNumber2=new BigDecimal(4);
        	BigDecimal integerNumber3=new BigDecimal(4);
        	
        	BigDecimal decimalNumber1=BigDecimal.ONE.divide(new BigDecimal(4),102,BigDecimal.ROUND_HALF_EVEN);
        	BigDecimal decimalNumber2=BigDecimal.ONE.divide(new BigDecimal(20),102,BigDecimal.ROUND_HALF_EVEN);
        	BigDecimal decimalNumber3=BigDecimal.ONE.divide(new BigDecimal(1985),102,BigDecimal.ROUND_HALF_EVEN);
        	
        	BigDecimal partPI1=integerNumber1.multiply(arctanCompute(decimalNumber1));
        	BigDecimal partPI2=integerNumber2.multiply(arctanCompute(decimalNumber2));
        	BigDecimal partPI3=integerNumber3.multiply(arctanCompute(decimalNumber3));
        	
        	BigDecimal PI=partPI1.add(partPI2).add(partPI3);
        	System.out.println(PI.toString());
        }
        //arctan(x) = x − x3/3 + x5/5 − x7/7 + x9/9 − x11/11 + . . .
    	private BigDecimal arctanCompute(BigDecimal decimalNumber) {
    		// TODO Auto-generated method stub
    		BigDecimal xx=decimalNumber.multiply(decimalNumber);
    		BigDecimal x=decimalNumber;
    		BigDecimal sum=BigDecimal.ZERO;
    		boolean flag=true;
    		BigDecimal temp;
    		BigDecimal res=BigDecimal.ONE;
    		for(int i=1;;i+=2){
    			temp=BigDecimal.ONE.divide(new BigDecimal(i),102,BigDecimal.ROUND_HALF_EVEN).multiply(res);
    			if(temp.compareTo(BigDecimal.ZERO)==0){
    				break;
    			}
    			
    			if(flag){
    				sum=sum.add(temp);
    				flag=false;
    			}else{
    				sum=sum.subtract(temp);
    				flag=true;
    			}		    
    			res=res.multiply(xx);			
    		}
    		    sum=sum.multiply(x);
    		return sum;
    	}
    }

时间复杂度：O(logn)

空间复杂度：O(1)

--------------------

自认为这个方法没有问题，就是计算时间太长，后面在网上找到了一种效率比较高的方法；

package gc;
    
    import java.math.BigDecimal;
    import java.math.BigInteger;
    import org.junit.Test;
    
    /**
    *类描述:根据泰勒公式计算PI小数点后面的100位数           
    *arctan(x) = x − x3/3 + x5/5 − x7/7 + x9/9 − x11/11 + . . .
    *
    *π  =12·arctan(1/4)	+4·arctan(1/20)	+4·arctan(1/1985)
    *根据此公式计算PI的值
    *
     */
    public class ComputePI4 {
    	@Test
        public void fun(){
        	BigDecimal integerNumber1=new BigDecimal(12);
        	BigDecimal integerNumber2=new BigDecimal(4);
        	BigDecimal integerNumber3=new BigDecimal(4);
        	   	
        	BigDecimal partPI1=integerNumber1.multiply(arctanCompute(4));
        	BigDecimal partPI2=integerNumber2.multiply(arctanCompute(20));
        	BigDecimal partPI3=integerNumber3.multiply(arctanCompute(1985));
        	
        	BigDecimal PI=partPI1.add(partPI2).add(partPI3);
        	System.out.println(PI.toString().substring(2,102));
        }
        //arctan(x) = x − x3/3 + x5/5 − x7/7 + x9/9 − x11/11 + . . .
    	private BigDecimal arctanCompute(int x) {
    		// TODO Auto-generated method stub
    		BigDecimal result = BigDecimal.ZERO;
    		BigDecimal squreXx = new BigDecimal(x * x);
    		BigDecimal decimalX = new BigDecimal(x);
    		BigDecimal temp;
    		BigDecimal res = BigDecimal.ONE.divide(decimalX, 102,BigDecimal.ROUND_HALF_EVEN);
    
    		boolean flag = true;
    		for (int i = 1;; i += 2) {
    			temp = res.divide(new BigDecimal(i), 102, BigDecimal.ROUND_HALF_EVEN);
    			if (temp.compareTo(BigDecimal.ZERO) == 0) {// 根据莱布尼兹级数结果=0时返回
    				break;
    			}			
    			if (flag) {
    				result = result.add(temp);
    				flag=false;
    				
    			} else {
    				result = result.subtract(temp);
    				flag=true;
    			}			
    			res = res.divide(squreXx, 102, BigDecimal.ROUND_HALF_EVEN);
    		}
    		return result;
    	}
    }

时间复杂度:O(logn)

空间复杂度：O(1)

这种方法能很快计算出来PI的后面100位小数：

1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679

--------------------

源码github地址：[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode