Finden Sie die Anzahl der Quadratwurzeln zwischen zwei Zahlen

Question

Ich habe diese Funktion geschrieben, um die Anzahl der Quadratwurzeln zwischen zwei Zahlen (inklusive) zu finden.

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; 
} 

Das wird gut funktionieren, aber ich habe über seine Leistung nachgedacht. Da in diesem Fall die inner For loop von Startposition (1) ausgeführt wird, so wird es Zeit brauchen, wenn jemand einen großen Nummernkreis an die Methode übergibt.

Also, meine Frage ist:

Gibt es eine andere Art, wie ich dies mit einer besseren Leistung finden kann?

PS- ich nicht Math.sqrt() Funktion

Answer 1

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; 
} 

Answer 2

verwenden können, können Sie weg eine einzige for-Schleife mit, die durch

der äußeren Schleife Loswerden

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; 
} 

hier Sie effektiv tun nur Ihre innere Schleife einmal, numRoots inkrementieren, wenn x2 (x-squared) zwischen lo und hi ist, und die Schleife zu beenden, wenn x2 größer ist als hi (statt, wenn x ist größer als hi wie in Ihrem Code).

Answer 3

Es wird auch funktionieren.

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; 
} 

In diesem Fall wird die innere Schleife nicht von 1.

Answer 4

Ausführung startet Es gibt viele Gründe, warum Ihr aktuellen Algorithmus effizient ist, aber die größte ist, dass die innere for-Schleife ist nicht erforderlich.

Die Idee hinter dem Algorithmus, den Sie suchen, ist am niedrigsten perfekten Quadrat höher als oder gleich no1 zu beginnen, dann zum nächsten perfekten Quadrat und zum nächsten und nächsten zu gehen und zu verfolgen, wie viele Sie hit, bis das perfekte Quadrat, auf dem du spielst, höher ist als 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; 
}