二進制搜索平方根[作業]

對於一個賦值，我必須創建一個方法，使用二分查找找到一個整數的平方根，如果它不是一個平方數，它應該返回一個整數s，使得s * s < =數字（對於15，它會返回3）。我到目前爲止的代碼是二進制搜索平方根[作業]

public class BinarySearch { 

    /** 
    * Integer square root Calculates the integer part of the square root of n, 
    * i.e. integer s such that s*s <= n and (s+1)*(s+1) > n 
    * requires n >= 0 
    * 
    * @param n number to find the square root of 
    * @return integer part of its square root 
    */ 
    private static int iSqrt(int n) { 
     int l = 0; 
     int r = n; 
     int m = ((l + r + 1)/2); 

     // loop invariant 
     while (Math.abs(m * m - n) > 0) { 
      if ((m) * (m) > n) { 
       r = m; 
       m = ((l + r + 1)/2); 
      } else { 
       l = m; 
       m = ((l + r + 1)/2); 
      } 
     } 
     return m; 
    } 

    public static void main(String[] args) { 
     //gets stuck 
     System.out.println(iSqrt(15)); 
     //calculates correctly 
     System.out.println(iSqrt(16)); 
    } 
}

而這將返回正方形數字的正確數字，但獲取其他整數的無限循環。我知道問題在於時間條件，但由於數字變得越大，方形數字之間的差距越大，所以我無法弄清楚應該放什麼（所以我不能只是說差距必須低於一個門檻）。如果這個練習有幫助，那麼這個練習是關於不變量的（因此它是以這種方式建立的）。謝謝。

來源

2014-12-07 Tim Hodgkin

想一想：Math.abs(m*m-n) > 0永遠是真的非正方形數字，因爲它永遠不是零，並且.abs不能爲負數。這是你的循環條件，這就是爲什麼循環永遠不會結束。

這是否給你足夠的信息讓你去？

來源

2014-12-07 15:27:03 Dima

您需要更改while (Math.abs(m * m - n) > 0)以允許出現誤差範圍，而不是像現在這樣要求完全等於零。

嘗試while((m+1)*(m+1) <= n || n < m * m)

來源

2014-12-07 15:30:50

-1

肯布魯姆說，你必須有一個錯誤瑪吉，1。我已經測試此代碼，並如預期運行15.您還需要使用浮動的，我覺得這算法是不可能的INT的（雖然我沒有數學證明）

private static int iSqrt(int n){ 
float l = 0; 
float r = n; 
float m = ((l + r)/2); 


while (Math.abs(m*m-n) > 0.1) { 
    if ((m)*(m) > n) { 
     r=m; 
     System.out.println("r becomes: "+r); 


    } else { 
     l = m; 
     System.out.println("l becomes: "+l); 

    } 
    m = ((l + r)/2); 
    System.out.println("m becomes: "+m); 
} 

return (int)m; 

}

來源

2014-12-07 15:49:40

使用只有int的問題是，你需要在算法中的錯誤marge變得越來越大，你想知道的數字的平方根。 – 2014-12-07 16:22:42

#define EPSILON 0.0000001 
double msqrt(double n){ 
    assert(n >= 0); 
    if(n == 0 || n == 1){ 
     return n; 
    } 
    double low = 1, high = n; 
    double mid = (low+high)/2.0; 
    while(abs(mid*mid - n) > EPSILON){ 
     mid = (low+high)/2.0; 
     if(mid*mid < n){ 
      low = mid+1; 
     }else{ 
      high = mid-1; 
     } 
    } 
return mid;}

正如你可以在上面看到，你應該簡單地套用二進制搜索（二分法），你可以最小化的Epsilon得到更準確結果，但需要更多時間跑。我用C++編寫代碼（對不起）

來源

2016-06-30 14:34:10 Bhuwan

二進制搜索平方根[作業]

回答

相關問題