Summe von 4 Quadraten < Haskell < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Aufgabe | Aus der Zahlentheorie ist bekannt, dass sich jede natürliche Zahl als Summe von maximal vier Quadratzahlen
darstellen läßt.
Implementieren Sie eine Haskell-Funktion sq::Int->[Int], so dass sq n für n>0 eine Liste von maximal vier
Zahlen ist, deren Summe ihrer Quadrate gleich n ist. Dabei soll die Liste so klein wie möglich und die Zahlen
in der Liste aufsteigend geordnet sein. |
Ich hab mich mal mit dem Problem auseinander gesetzt und folgene Implemtierung ausgetüfftelt:
sq::Int->[Int]
sq n = li (sq' n)
li::[Int]->[Int]
li [] = []
li (t:r)
| r == [] = [t]
| r /= [] = li r ++ [t]
sq'::Int->[Int]
sq' n
| n == 0 = [0]
| otherwise = f1 n 1
f1::Int->Int->[Int]
f1 n i
| i*i == n =
| i*i < n = f1 n (i+1)
| i*i > n = [i-1] ++ f1 (n-(i-1)*(i-1)) 1
Es funktioniert, aber bei größeren Zahlen gibt er 5 statt 4 Zahlen aus.
Weiß einer Rat, wie man das verhindern kann?????
|
|
| |
|
Hallo,
du gibst auch nirgends an, dass 5 Zahlen verboten sind.
Ich würde einen anderen Ansatz wählen: Da wir wissen, dass es maximal vier Quadrate sind, würde ich einfach vier Generatoren einsetzen, wobei jeder eine Zahl größer/gleich der vorhergehenden erzeugen soll und die Summe der Quadrate gleich unserer Eingabe sein soll. Der erste Generator soll bei Null anfangen.
Davon nimmst du nur das erste Element, bereinigst es ggf. um führende Nullen und hast die kürzeste Liste mit den kleinsten Zahlen, die die Bedingung erfüllen.
Gruß
Martin
|
|
|
| |
|
Aber wie genau mach ich das?
|
|
|
| |
|
Hallo,
weißt du, was Generatorausdrücke sind? Sie haben die Form [f(x) | x<-liste]. Ich glaube, ich habe dafür auch den Ausdruck "list comprehension" gehört. Davon nimmst du dir einen, in dem du allerdings alle vier Zahlen a,b,c und d erzeugst, für die am Ende [mm] a^2+b^2+c^2+d^2=n [/mm] gelten soll. Dabei soll a bei 0 anfangen und die darauffolgenden Zahlen beim aktuellen Wert der jeweils vorangehenden Zahl.
Das erste Element einer Liste bekommst du bekanntlich mit head.
Führende Nullen kannst du mit dropWhile weglassen.
Sag konkreter, was dir noch Schwierigkeiten bereitet.
Gruß
Martin
|
|
|
|
