042 – Kodierte Dreieckszahlen

 

Die n-te Zahl aus der Reihe der Dreieckszahlen ist definiert als

    \[\Delta_n = \frac {n \cdot \left(n + 1\right)}{2}\]

Die ersten zehn Dreieckszahlen sind also: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Wenn man jeden Buchstaben in einem Wort durch seine Position im Alphabet kodiert und dann alle Buchstaben des Wortes addiert, erhält man einen Wortwert. Der Wortwert von “SKY” ist zum Beispiel 19+11+25=55. Dies ist die zehnte Dreieckszahl. Wenn ein Wort einen Wortwert hat, der einer Dreieckszahl entspricht, nennen wir es Dreieckswort.

Wie viele Dreieckswörter sind in der Datei words.txt vorhanden?

Lösung

Wir kodieren zunächst alle Wörter in der Textdatei. Dann suchen wir den größten Wortwert, um zu ermitteln, wie viele Dreieckszahlen wir berechnen müssen. Dazu stellen wir die Formel um:

    \[\Delta_{\max} = \frac {n \cdot \left(n + 1\right)}{2}\]

    \[\Rightarrow n^2+n-2\Delta_{\max} = 0\]

    \[\Rightarrow n = -1 + \sqrt{\frac{1}{4} + 2\Delta_\max}\]

    \[\Rightarrow n = \frac{1}{2} \left(-2 + \sqrt{1 + 8\Delta_\max}\right)\]

Anschließend vergleichen wir alle Wortwerte mit den Dreieckszahlen und zählen die passenden.

clc
clear all
tic

datei = fopen('words.txt');
inhalt = textscan(datei, '%q', 'delimiter', ',');
werte = char(inhalt{1});
werte = double(werte);
werte = werte - 64;
werte(werte < 0) = 0;
summen = sum(werte,2);
n = ceil(.5 * (-2 + sqrt(1 + 8 * max(summen))));
dreieck = cumsum(1 : n);
ergebnis = sum(ismember(summen, dreieck))

toc

Ergebnis: 162
Rechenzeit: 0.049698 Sekunden