演算法 -- 電腦如何計算平方根呢?
演算法演算法簡介複雜度理論系統搜尋法逼近法隨機搜尋法隨機統計法最佳化分配濃縮法遞迴法分割擊破法動態規劃法事前計算法轉換領域法轉換問題法訊息相關網站參考文獻最新修改簡體版English |
會寫程式的人都知道要如何讓電腦計算二次方 ($x^2$)、三次方($x^3$)等函數，然而、要計算平方根這類的函數，可就沒那麼容易了，這類函數必須採用一種稱為逼近的方式來計算，本文中我們將以開根號這個問題為例，說明電腦如何逼近一個問題的解答。 簡介電腦計算平方根，必需要採用逼近的方法，所謂逼近的方法，就是用猜測、計算、再猜測、再計算…的方式，其中、每次的猜測都會根據前幾次猜測的結果，會猜的越來越準。 以開根號這個問題為例，假設我們想計算 5 這個數字的平方根，首先我們要先訂出一個範圍，我們知道 $1^2 = 1$，$5^2=25$，因此、我們可以用這兩個數值作為起始的邊界值，然後開始利用二分搜尋法，不斷逼近其結果，其過程圖示如下。  上述過程中、我們先計算 (1+5)/2 = 3 的平方，發現 3<sup>2</sup> = 9, 比 5 還大，於是知道5 的平方根必然在 1-3 之間，於是在計算 (1+3)/2 = 2 的平方，發現 $2^2 = 4$，比 5 還小，於是知道 5 的平方根必然在 2-3 之間，如此不斷縮小範圍的結果，就會得到一個愈來愈準的區間，當誤差小的一定程度 (例如： 0.00000000001) ，我們就可以說找到正確結果了。 ==實作== class Sqrt { public static void main(String[] args) throws Exception { System.out.println("sqrt(5)="+sqrt(5)); } public static double sqrt(double x) throws Exception { double small = 0.0000001; double low, high; if (x < 0) throw new Error(); if (x < 1) { low = 0; high = 1; // 若 0 < x < 1 則其平方根必然介於 0 與 1之間。 } else { low = 1; high = x; // 若 x > 1 , 則其平方根必然介於 1 與 x 之間。 } while (high - low > small) // 不斷逼近，直到範圍夠小為止。 { double mid = (low + high) / 2; if (mid*mid > x) // 解小於 mid , 將上限調為 mid high = mid; else low = mid; // 解大於 mid , 將下限調為 mid } return low; } } 執行結果如下：
結語在本文中，我們示範了如何用逼近法計算平方根，只要活用逼近法，幾乎所有數值問題都可以利用此法解決，包含 3 次方根、4次方根…等等。 |
page revision: 5, last edited: 05 Nov 2010 02:34
Post preview:
Close preview