找到兩個數字之間的平方根的數量

我已經寫了這個函數來找出兩個數字（包括）之間的平方根的數量。找到兩個數字之間的平方根的數量

static int FindRoot(int no1, int no2) { 
    int res = 0; 
    for (int x = no1; x <= no2; x++) { 
     for (int y = 1; y <= no2; y++) { 
      if (y * y == x) 
       res++; 
     } 
    } 
    return res; 
}

這將工作正常，但我在考慮它的性能。因爲在這種情況下，inner For loop將從起始位置（1）開始執行，所以如果有人將大量程傳遞給該方法，則需要時間。

所以，我的問題是：

有沒有其他辦法可以具有更好的性能發現呢？

PS-我不能使用Math.sqrt()功能

來源

2016-04-15 Trying

你的功能僅適用於完美的平方根？ –

你可以解決規則和實現[牛頓方法]（https://en.wikipedia.org/wiki/Newton%27s_method#Square_root_of_a_number）來計算平方根......但這可能不是你想要的：P – SamYonnou

我希望如此，它適用於我測試過的少數情況。有什麼問題，然後幫我找出答案。 – Trying

static int FindRoot(int no1, int no2) { 
    int res = 0; 
    int x = 0; 

    // Ignore squares less than no1 
    while(x*x < no1) { 
     x++; 
    } 

    // Count squares up to and including no2 
    while(x*x <= no2) { 
     res++; 
     x++; 
    } 

    return res; 
}

來源

2016-04-15 19:26:38 AJNeufeld

可以與具有單for循環擺脫外環

static int findRoot(int lo, int hi) { 
    int numRoots = 0; 

    for (int x = 0, x2 = 0; x2 <= hi; x++, x2 = x * x) { 
     if (x2 >= lo) { 
      numRoots++; 
     } 
    }  

    return numRoots; 
}

這裏跑不掉您有效地只是做你的內心循環一次，當x2（x平方）在lo和hi之間時遞增numRoots，並且當x2大於hi時（而不是當x是大於hi就像在你的代碼中）。

來源

2016-04-15 19:25:35 SamYonnou

您錯過了將零計爲可能的平方根。從「x = 0，x2 = 0」開始。 – AJNeufeld

@AJNeufeld嗯好點，OP的代碼也是 – SamYonnou

它也可以工作。

static int FindRoot2(int no1, int no2) { 
    int res = 0; 
    int inner=1; 
    for (int x = no1; x <= no2; x++) { 
     for (int y = inner; y <= no2; y++) { 
      if (y * y == x) 
      { 
       inner=y; 
       res++; 
      } 
     } 
    } 
    return res; 
}

在這種情況下，內循環將無法啓動的原因有很多，爲什麼你的當前算法是ineffecient從1

來源

2016-04-15 19:32:36 Trying

這確實做了一些優化，但沒有理由使用除了清晰，直接的O（n）解決方案之外的解決方案。 –

執行，但最大的一個是內部的for循環是沒有必要的。

您正在尋找的算法背後的想法是，從最低的完美平方高於或等於no1開始，然後進入下一個完美平方和下一個完整平方，並跟蹤您有多少人擊中，直到你所在的完美正方形高於no2。

static int FindRoot(int no1, int no2) { 

    int res = 0; 
    int x = 1; 

    // This loop gets x to the first perfect square greater than 
    // or equal to no1 
    while((x * x) < no1) { 
     x++; 
    } 

    // This loop adds 1 to res and increases x 
    // as long as x^2 is less than or equal to no2 
    for(; (x * x) <= no2; x++, res++) { } 

    return res; 
}

來源

2016-04-15 19:34:57

找到兩個數字之間的平方根的數量

回答

相關問題