Funktionale Programmierung mit Haskell/ Beispielprogramme/ Zahlenspielereien
Summe von Ziffern
[Bearbeiten]215 = 32768 und die Summe der Ziffern ist 3 + 2 + 7 + 6 + 8 = 26.
Was ist die Summe der Ziffern der Zahl 21000?[1]
Diese Zahl hat zwar 302 Stellen aber sie ist für Haskell nicht zu groß:
Prelude> 2^1000
1071508607186267320948425049060001810561404811705533607443750388370351051124936122493198378815695858127594672917553146825
1871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946
077062914571196477686542167660429831652624386837205668069376
Als Integer ist sie schlecht zu verarbeiten, aber als String ist es einfacher:
Prelude> let s=show (2^1000)
Prelude> s
"1071508607186267320948425049060001810561404811705533607443750388370351051124936122493198378815695858127594672917553146825
18714528569231404359845775746985748039345677748242309854210746050623711418779541821530464749835819412673987675591655439460
77062914571196477686542167660429831652624386837205668069376"
Nun müssen die einzelnen Ziffern wieder zu Zahlen einer Liste verwandelt werden. Dafür gibt es digitToInt. Danach wird die Summe der einzelnen Ziffern gebildet, schon liegt das Ergebnis vor:
Prelude> let k= map Data.Char.digitToInt s
Prelude> k
[1,0,7,1,5,0,8,6,0,7,1,8,6,2,6,7,3,2,0,9,4,8,4,2,5,0,4,9,0,6,0,0,0,1,8,1,0,5,6,1,4,0,4,8,1,1,7,0,5,5,3,3,6,0,7,4,4,3,7,5,0,
3,8,8,3,7,0,3,5,1,0,5,1,1,2,4,9,3,6,1,2,2,4,9,3,1,9,8,3,7,8,8,1,5,6,9,5,8,5,8,1,2,7,5,9,4,6,7,2,9,1,7,5,5,3,1,4,6,8,2,5,1,
8,7,1,4,5,2,8,5,6,9,2,3,1,4,0,4,3,5,9,8,4,5,7,7,5,7,4,6,9,8,5,7,4,8,0,3,9,3,4,5,6,7,7,7,4,8,2,4,2,3,0,9,8,5,4,2,1,0,7,4,6,
0,5,0,6,2,3,7,1,1,4,1,8,7,7,9,5,4,1,8,2,1,5,3,0,4,6,4,7,4,9,8,3,5,8,1,9,4,1,2,6,7,3,9,8,7,6,7,5,5,9,1,6,5,5,4,3,9,4,6,0,7,
7,0,6,2,9,1,4,5,7,1,1,9,6,4,7,7,6,8,6,5,4,2,1,6,7,6,6,0,4,2,9,8,3,1,6,5,2,6,2,4,3,8,6,8,3,7,2,0,5,6,6,8,0,6,9,3,7,6]
Prelude> sum k
1366
Prelude>
In einem Programm zusammengefasst, sieht der Lösungsweg so aus:
import Data.Char
loesung = sum k
where s = show (2^1000)
k = map digitToInt s
AusgabePrelude> :l ep16.hs
[1 of 1] Compiling Main ( ep16.hs, interpreted )
Ok, modules loaded: Main.
*Main> loesung
1366
Die Lösung kann auch in einer einzigen Zeile dargestellt werden:
Prelude> sum $ map Data.Char.digitToInt $ show $ 2^1000
1366
Primfaktoren
[Bearbeiten]Was ist der größte Primfaktor der Zahl 317584931803?[2]
Palindrome
[Bearbeiten]Was ist das größte Palindrom, das aus dem Produkt von zwei dreistelligen Zahlen gebildet werden kann?[3]
Ein Palindrom ist eine Zahl (genauer: Ein Objekt, dessen Typ von der Standardklasse Show abgeleitet ist), die von vorne und hinten gelesen gleich gelesen werden kann, also so:
Prelude> let is_palindrom x = s==reverse s where s=show x
Prelude> is_palindrom 939
True
Prelude> is_palindrom "lagerregal"
True
Prelude> is_palindrom "lagerregal!"
False
Zur Bildung des Produkts aller dreistelliger Zahlen (und für die ganze restliche Berechnung) eignet sich die List comprehension:
Prelude> let a = [x | y<-[100..999], z<-[100..999], let x=y*z] -- Bildet alle Produkte aller dreistelliger Zahlen
Prelude> let a = [x | y<-[100..999], z<-[y..999], let x=y*z] -- diese Multiplikation reicht auch aus (und verkürzt die Laufzeit)
Prelude> let a = [x | y<-[100..999], z<-[y..999], let x=y*z, is_palindrom x] -- jetzt mit eingebauter Palindrom-Abfrage
Prelude> let a = maximum [x | y<-[100..999], z<-[y..999], let x=y*z, is_palindrom x] -- In der Aufgabe ist nur der größte Wert gefragt
Prelude> a -- jetzt wird der Wert berechnet und ausgegeben.
906609
Prelude> maximum [(x,y,z) | y<-[100..999], z<-[y..999], let x=y*z, is_palindrom x] -- Hier mit Ausgabe der Faktoren
(906609,913,993)
Prelude>
Permutierte Vielfache
[Bearbeiten]Finde die kleinste positive Ganzzahl x, deren Produkte 2x, 3x, 4x, 5x und 6x die gleichen Ziffern (in anderer Reihenfolge) enthalten.[4]
Zuerst wird eine Funktion benötigt, die erkennt, ob zwei Zahlen aus den selben Ziffern bestehen. Dabei hilft eine Funktion aus dem Modul Data.List, die aus zwei Backslashes besteht und erkennt, ob zwei Objekte die gleiche Differenzmenge und die gleiche Länge besitzen. Die Funktion bekommt den Namen has_same_digits:
Prelude> let has_same_digits a b = x Data.List.\\ y == [] && length x == length y where x=(show a); y=(show b)
Prelude> has_same_digits 98765 75689
True
Prelude> has_same_digits "regal" "lager"
True
Prelude> has_same_digits "regal" "lagerregal"
False
Prelude> has_same_digits "regallager" "lager"
False
Prelude>
Als nächstes wird check definiert, diese Funktion liefert True, wenn die benötigten Vielfachen von x die gleichen Ziffern besitzen wie x selbst. Die erste Version ist noch etwas vereinfacht und prüft nur, ob x die gleichen Ziffern besitzt wie 2*x. check wird dann so lange aufgerufen, bis zehn Werte gefunden wurden, die dieser Regel entsprechen. Mit map (*2) it wird diese Liste verdoppelt, um die Richtigkeit der Funktionen zu verifizieren:
Prelude> let check x = (has_same_digits x) (2*x)
Prelude> take 10 $ filter check [1..]
[125874,128574,142587,142857,258714,258741,285714,285741,412587,412857]
Prelude> map (*2) it
[251748,257148,285174,285714,517428,517482,571428,571482,825174,825714]
Prelude>
Nachdem die erste Näherung an die Lösung erfolgreich war, kann jetzt die Prüfung gegen alle geforderten Vielfache angegangen werden. Hier bietet sich der Befehl all:
Prelude> let check x = all (has_same_digits n) [2*x, 3*x, 4*x, 5*x, 6*x] -- diese Liste lässt sich auch mit map erstellen
Prelude> head $ filter check [1..]
142857
Prelude> map (*142857) [2..6] -- Verifizieren des Ergebnisses
[285714,428571,571428,714285,857142]
Prelude>
Das Ergebnis bedeutet, dass die Zahl 142857 und alle deren Vielfache 2*142857, 3*142857, 4*142857, 5*142857 und 6*142857 aus den gleichen Ziffern bestehen. Hier ist die Lösung noch einmal als Zusammenfassung:
Prelude> let has_same_digits a b = x Data.List.\\ y == [] && length x == length y where x=(show a); y=(show b)
Prelude> let check x = all (has_same_digits n) (map (x*) [2..6])
Prelude> head $ filter check [1..]
142857
Prelude>