求立方根演算法--個人對立方根演算法的窮舉和優化

在hpe實訓中心學習,遇到了求立方根的題目,在此做一下演算法筆記,

分析過程:

數n的立方根就是n=i*i**i;所以我們會優先想到一下方法.

    static double g32(double n){ //簡易版
        double i = 0, k = 0.0005f;
        if (n < 0) {    //輸入負數判斷
            k /= -1;
        }
        do{
            i+=k;
        }while(abs(i*i*i)<abs(n)); //abs為自己寫的求絕對值方法
        return i;
    }

可以看出此方法的求解精度為0.001;且當輸入數據過大時效率堪憂,所以就有了以下優化

    static double g33(double n){    //優化2
        double i = 0, k = 5f;
        if (n < 0) {
            k /= -1;
        }for (int t = 0; t < 15; t++) {//精度到小數點後15位
            do {
                i += k;　　//開始時每次加5快速逼近正確值
            } while (abs(i * i * i) < abs(n));　　//當i^3>=n時退出
            i-=k;k /= 9.2;　　//i還原到退出前的值,k縮小,進入下一次逼近
        }　
        return i;
    }

此方法可以快速求得立方根,輸入數值n不太大時使用,當n太大在逼近過程中i^3與(i+k)^3差距太大,迴圈次數劇增,進入死迴圈狀態.在我電腦上當n=9999999999 (10個9)時就會進入死迴圈

所以想到一種解決方法,設置一迴圈次數計數器w,使k值隨迴圈次數增加而增加,在一定程度上解決死迴圈問題.下麵是代碼

    static double g34(double n){    //最終優化
        double i = 0, k = 5f;
        if (n < 0) {
            k /= -1;
        }
        int w=0;
        for (int t = 0; t < 15; t++) {
            do {
                i += k;
                k=k+w*k/50000;
                w++;　　//迴圈計數器
            } while (abs(i * i * i) < abs(n));
            i-=k;k /= 9.5;
        }
        System.out.println(w);
        return i;
    }

更改後n等於20個9也不會死迴圈.

最後附上所有程式代碼.

package com.gfuzan.test;

import java.util.Scanner;

public class Test {

    /**
     * 開發: GFuZan
     * 時間: 2017.08.08
     * 功能: 立方根
     */
    public static void main(String[] args) {
        System.out.print("請輸入一個數: ");
        Scanner sc = new Scanner(System.in);
        double n = sc.nextDouble();
        sc.close();
        System.out.println("Math:    \t"+ Math.pow(n, 1.0/3));
        System.out.println("My簡易版:  \t"+g32(n)); 
        System.out.println("My優化2:  \t"+g33(n)); 
        System.out.println("My最終優化:\t"+g34(n)); 
        
    }
    
    static double g32(double n){ //簡易版
        double i = 0, k = 0.0005f;
        if (n < 0) {
            k /= -1;
        }
        do{
            i+=k;
        }while(abs(i*i*i)<abs(n));
        return i;
    }
    static double g34(double n){    //最終優化
        double i = 0, k = 5f;
        if (n < 0) {
            k /= -1;
        }
        int w=0;
        for (int t = 0; t < 15; t++) {
            do {
                i += k;
                k=k+w*k/50000;
                w++;
            } while (abs(i * i * i) < abs(n));
            i-=k;k /= 9.5;
        }
        return i;
    }
    static double g33(double n){    //優化2
        double i = 0, k = 5f;
        if (n < 0) {
            k /= -1;
        }
        for (int t = 0; t < 15; t++) {
            do {
                i += k;
            } while (abs(i * i * i) < abs(n));
            i-=k;k /= 9.2;
        }
        return i;
    }
    static double abs(double f) {
        if (f < 0) {
            return 0 - f;
        }
        return f;
    }
}

運行結果