Eine Dreieckszahl ist die Summe der n natürlichen Zahlen von 1 bis n. Was ist die schnellste Methode, um herauszufinden, ob eine gegebene positive ganze Zahl eine dreieckige ist?
Hier ist ein Schnitt der ersten 1200. bis 1300. Dreieckszahlen, hier können Sie leicht ein Bitmuster sehen (falls nicht, versuchen Sie es zu verkleinern):
%Vor%Können Sie beispielsweise auch eine gedrehte Normalverteilungskurve sehen, die durch Nullen zwischen 807085 und 831405 dargestellt wird? Dieses Muster wiederholt sich regelmäßig. - & gt;
Wenn n die m th Dreieckszahl ist, dann n = m*(m+1)/2 . Lösung für m mit der quadratischen Formel:
So n ist dreieckig, wenn und nur wenn 8n+1 ein perfektes Quadrat ist. Um schnell zu bestimmen, ob eine Zahl ein perfektes Quadrat ist, siehe diese Frage: Schnellste Methode, um zu bestimmen, ob die Wurzel einer ganzen Zahl eine Ganzzahl ist .
Beachten Sie, dass, wenn 8n + 1 ein perfektes Quadrat ist, der Zähler in der obigen Formel immer gerade ist, so dass nicht überprüft werden muss, ob er durch 2 teilbar ist.
Eine ganze Zahl x ist genau dann dreieckig, wenn 8x + 1 ein Quadrat ist.
Hausaufgaben?
Summe der Zahlen von 1 bis N
1 + 2 + 3 + 4 + ... n-1 + n
Wenn Sie das erste plus das letzte hinzufügen, dann das zweite plus das zweite von dem letzten, dann ...
= (1 + n) + (2 + n-1) + (3 + n-2) + (4 + n-3) + ... (n / 2 + n / 2 + 1)
= (n = 1) + (n + 1) + (n + 1) + ... (n + 1); .... n / 2 mal
= n (n + 1) / 2
Damit sollten Sie beginnen ...
Die angenommenen Antworten führen Sie zu einem weiteren Schritt, um zu überprüfen, ob die Zahl ein perfektes Quadrat ist. Warum folgst du nicht einfach? Es erfordert die gleiche Anstrengung, ein perfektes Quadrat zu finden.
%Vor%Tags und Links algorithm java c math bit-manipulation