eine Pyramide gegeben wie:Finden Sie die Pyramidenreihe basierend auf dem Index?
0
1 2
3 4 5
6 7 8 9
...
und der Index der Pyramide i gegeben, wo i die i te Zahl der Pyramide darstellt, ist es eine Möglichkeit, den Index der Zeile des i ten Element, das zu finden gehört? (ZB wenn i = 6,7,8,9, ist es in der dritten Reihe, von Startreihe 0)
Es gibt eine Verbindung zwischen den Zeilennummern und den Dreieckszahlen. Die nth triangular number, bezeichnet mit T n, ist gegeben durch T n = n (n-1)/2. Die ersten paar Dreieckszahlen sind 0, 1, 3, 6, 10, 15, usw., und wenn Sie bemerken, sind die Starts jeder Reihe durch die n-te Dreieckszahl gegeben (die Tatsache, dass sie aus diesem Dreieck kommen) woher dieser Name kommt.)
Also wirklich, das Ziel hier ist, die größte n so zu bestimmen, dass T n i. Ohne jede kluge Mathe zu tun, könnten Sie dies in der Zeit O (√ n) von nur Rechen T , T , T usw. lösen, bis Sie etwas, das größer ist als ich finden. Noch besser ist, Sie könnten binäre Suche für sie in der Zeit O (log n) von T Berechnung , T , T , T usw., bis Sie überschreiten, dann binäre Suche auf den Bereich du fandest.
Alternativ könnten wir versuchen, dies direkt zu lösen. Angenommen, wir die Wahl von n, so dass
n (n + 1)/2 = i
erweitern, erhalten wir
n /2 + finden wollen n/2 = i.
Gleichwertig
n /2 + n/2 - i = 0,
oder, noch einfacher:
n + n - 2i = 0.
Nun verwenden wir die quadratische Formel:
n = (-1 ± √ (1 + 8i))/2
Die negative Wurzel wir ignorieren können, so dass der Wert n wir wollen, ist
n = (-1 + √ (1 + 8i))/2.
Diese Zahl wird nicht notwendigerweise eine ganze Zahl sein, so dass die Zeile, die Sie wollen zu finden, die wir abrunden gerade:
row = & lfloor; (- 1 + √ (1 + 8i))/2 & rfloor ;.
In Code:
int row = int((-1 + sqrt(1 + 8 * i))/2);
Lassen Sie uns bestätigen, dass dies funktioniert es durch die Prüfung ein bisschen aus. Wohin gehen 9? Nun, wir haben
(-1 + √ (1 + 72))/2 = (-1 + √ 73)/2 = 3,77
Abrunden, sehen wir, es geht in der Reihe 3 - was ist richtig!
Einen anderen versuchen, wo geht 55? Nun,
(-1 + √ (1 + 440))/2 = (√ 441 - 1)/2 = 10
So sollte es gehen in Zeile 10. Die zehnte Dreieckszahl ist T = 55, also in der Tat beginnt 55 von dieser Reihe. Sieht so aus, als ob es funktioniert!
Ich denke i te Element n ten Reihe gehört, wo n ist die Anzahl der n(n+1)/2 <= i < (n+1)(n+2)/2
Zum Beispiel, wenn i = 6, dann n = 3 weil n(n+1)/2 <= 6 und wenn i = 8, dann n = 3 weil n(n+1)/2 <= 8
ich row = Math.floor (√ (2i + 0,25) - 0,5), wo ich Ihre Nummer
im Wesentlichen der gleiche wie der Kerl oben, aber ich reduziert n + n (n + 0,5) - 0,25