Finden Nähe n aus Summe von n Zahlen

Question

ich für nächsten Wert von n zu lösen versuchen, wenn mir eine Summe von ersten n Zahlen gegeben werde. Bedeutung, wenn ich summe als 60 habe, meine n sollte 10 als die Summe der ersten 10 Zahlen ist 55, wenn ich 11 die Summe wäre 66, die Überschreitung meiner erforderlichen Summe.

int num=1, mysum = 0; 
int givensum=60; 
while (mysum < givensum) { 
    mysum += num; 
    num++; 
} 
cout<<num-1; 
return 0; 

Die andere Art, wie ich denke, kann dies zu lösen, ist durch für quadratische Gleichung zu lösen
n(n+1)/2 = givensum und n von ihm erhalten. Gibt es eine andere Möglichkeit, dieses Problem zu lösen?

Answer 1

Ich glaube nicht, dass es einen besseren Weg als die Lösung der quadratic equation gibt. Es ist ziemlich einfach,

n*(n+1)/2 = sum 
n^2 + n - sum*2 = 0 
assumin ax^2 + bx + c = 0 
a = 1, b = 1, c = -2*sum 

da wir Antwort nicht die negativen brauchen:

n = (-b + sqrt(b^2 - 4ac))/2a 

Dies ist die Umsetzung:

#include <iostream> 
#include <cmath> 
using namespace std; 


int main() 
{ 
    int sum = 60; 
    int a = 1; 
    int b = 1; 
    int c = -sum*2; 

    double delta = b*b - 4*a*c; 
    if (delta >= 0){ 
     double x1 = -b + sqrt(delta); 
     //double x2 = -b - sqrt(delta); // we don't need the negative answer 
     x1 /= 2*a; 
     //x2 /= 2*a; 
     cout << x1 << endl; 
    } 
    else { 
     cout << "no result"; 
    } 
} 

das Ergebnis ist eine Gleitkommazahl, wenn Sie möchten, dass die Summe der n Elemente kleiner oder gleich der Eingabesumme ist, die Sie mit der Funktion floor abrunden sollten.

---

Betrachten wir die Funktion f(n) = n*(n+1)/2 die die Summe der ersten n ganzen Zahlen ergibt. Diese Funktion wird streng genommen. So können Sie binäre Suche verwenden n zu finden, wenn der Wert für f(n) Ihnen gegeben:

#include <iostream> 
#include <cmath> 
using namespace std; 


int main() 
{ 
    int sum = 61; 
    int low = 1, high = sum, mid; 
    while (low < high){ 
     mid = ceil ((low+high)/2.0); 
     int s = mid*(mid+1)/2; 
     if (s > sum){ 
      high = mid-1; 
     } else if (s < sum) { 
      low = mid; 
     } else { 
      low = mid; 
      break; 
     } 
    } 
    cout << low << endl; 
} 

Answer 2

Nachdem der Code aus while ausbricht, wird mysum die nächste Summe, die größer ist als Ihre . Für das von Ihnen angegebene Beispiel wird die while-Schleife ausgeführt, da 55 is less than 60, und die mysum wird 66 und num wird 12 in der letzten Ausführung der Schleife kurz bevor es stoppt. Nach diesem Schritt, weil 66 is not less than 60, wird die while nicht erneut ausgeführt. Daher sollten Sie die mysum von verringern.

cout<<num-2; 

Answer 3

So wollen wir eine ganze Zahl finden n so dass (n+1)*n/2 <= y < (n+2)*(n+1)/2

die quadratische Gleichung lösen f(x)=y, wo f(x)=(x+1)*x/2 kann mit Fließkomma-Arithmetik durchgeführt werden, wobei dann n als ganzzahliger Teil von x genommen wird.

aber wir haben nicht wirklich Gleitkomma brauchen, weil wir nur den ganzzahligen Teil des Ergebnisses wollen, können wir es auch tun, mit einem Newton-Raphson Iteration https://en.wikipedia.org/wiki/Newton%27s_method

Die Ableitung von f(x)f'(x)=(x+(1/2)) ist.Nicht eine gute ganze Zahl, aber wir können alle mit 2 multiplizieren, und schreiben Sie die Schleife wie folgt aus: (dies ist Smalltalk, aber das ist nicht wirklich wichtig):

Integer>>invSumFloor 
    "Return the integer n such that (1 to: n) sum <= self < (1 to: n+1) sum" 

    | guess delta y2 | 
    y2 := self * 2. 
    guess := 1 bitShift: y2 highBit + 1 // 2. 
    [ 
     delta := ((guess + 1) * guess - y2) // (guess * 2 + 1). 
     delta = 0 ] 
      whileFalse: [ guess := guess - delta ]. 
    ^guess - 1 

So wir so iterieren:

x(n+1) = x(n) - (2*f(x(n))-2*y)/(2*f'(x(n))) 

Aber anstatt eine genaue Division zu nehmen, verwenden wir //, was der Quotient auf die nächste ganze Zahl abgerundet ist.

Normalerweise sollten wir testen, ob die Schätzung in der Endphase überschätzt wird oder nicht.

Aber hier, wir arrangieren, dass die anfängliche Schätzung eine Überschätzung des Ergebnisses sein wird, aber nicht zu sehr überschätzt, so dass die Rate immer überschätzt bleibt. So können wir in der Endphase einfach 1 subtrahieren. Die obige Implementierung verwendet eine grobe Schätzung der ersten Bitposition als anfänglichen Wert x.

Wir können dann überprüfen Sie die Implementierung auf den ersten zehntausend natürliche Zahlen mit:

(1 to: 10000) allSatisfy: [:y | 
    | n sum | 
    n := y invSumFloor. 
    sum := (1 to: n) sum. 
    (sum <= y and: [y < (sum + n + 1)])]. 

die true Antworten

Was mit Smalltalk schön ist, dass man dann Dinge wie diese versuchen:

80 factorial invSumFloor. 

Und erhalten Sie etwas wie:

378337037695924775539900121166451777161332730835021256527654 

Sie sehen hier, dass Newton Raphson schnell konvergiert (7 Iterationen im obigen Beispiel). Dies unterscheidet sich sehr von der ursprünglichen naiven Iteration.