www.jammni.de

Gepostet:
21.12.2008 19:42

Int-Wurzel - Rekursiv

Hi,
ich bin noch ein Haskell-Laie und sitze momentan an folgender Aufgabe:

"The integer square root of a positiv integer n is the largest integer whose square is less than or equal to n. For instance, the integer square root of 15 and 16 are 3 and 4, respectively. Give a primitive recuresive definition of this funtion."

Auf gut deutsch lautet die Aufgabe ja "Wurzel n = x, wobei x die größte natürlich Zahl ist, deren Quadrat n nicht übersteigt."

Zur Lösung habe ich mir folgenden Algorithmus überlegt:

Ich ziehe von n einfach n-1 ab, erhalte dadurch m, quadriere m und vergleiche dieses dann mit n.
Im zweiten Schritt ziehe ich dann n-2 von n ab, im 3. Schritt dann n-3 usw. Sobald m² größer als n ist, weiss ich was die Wurzel ist, nämich (m-1)
Hier mal ein Beispiel zu diesem Algorithmus:

Gesucht: Wurzel aus 17

(17-16) = 1
1² = 1 | 1 ist < als 17, also gehe zu Schritt 2.

(17-15) = 2
2² =4 | 4 ist < als 17, also gehe zu Schritt 3.

(17-14) = 3
3² = 9 | 9 ist < als 17, also gehe zu Schritt 4.

(17-13) = 4
4² =16 | 16 ist < als 17, also gehe zu Schritt 5

(17-12) = 5
5² = 25 | 25 ist > als 17, also Ist die Wurzel (5-1) = 4

Ich hab schon viel rumprobiert, komme aber einfach nich darauf, wie ich das in Haskell schreiben muss...

Die Aufgabe ist übrigens aus dem Buch : "The Craft of Functional Programming" (2nd Edition) von Simon Thompson, Seite 64, Aufgabe 4.8 (falls das hilft).

Bis jetz hab ich das :

>	intRoot :: Int -> Int
>	intRoot n  
>		| n == 1 = 1
>		| n > 1 = check   ?????   (<--- an der stelle muss irgendwie noch divRoot sich selbst aufrufen)

>	check :: Int -> Int -> Int   
>	check m n 
>		| (m - n)^2 >= m = ((m-n)-1)
>		| otherwise        = error "Falsch"

Erläuterung zu der Sache: "check" bekommt 2 Zahlen "m" und "n". dann kontrolliert "check", ob das quadrat von (m-n) größer oder gleich m ist, ist dies der fall, gibt die Funktion den Wert von (m-n)-1 aus.
Dieses "check" soll in der Hauptfunktion "intRoot" kontrollieren, ob dies für n und (n-1) gilt und dann den passenden Wert liefern.
Irgendwie muss ich den teil, wo die unterstrichenen Fragenzeichen sind, so umschrieben, das dort rekursiv "check n (n-1)" kontrolliert wird, dann "check n (n-2)" usw. Nur irgendwie steh ich da aufm Schlauch...

Zum Seitenanfang

Siracusa

Gepostet:
23.12.2008 05:58

Hallo,

die Rekursion sollte hier nicht in der Funktion intRoot, sondern in der Funktion check sein, d.h. check ruft sich selbst wieder auf. Am Anfang wird "check 1 n" (oder auch "check (n - (n-1)) n", ist das gleiche ;-) ) in intRoot aufgerufen und m dann in jedem Schritt hochgezählt. check sieht dann etwa so aus:

check :: Int -> Int -> Int
check m n
    | m^2 >= n  = ...
    | otherwise = ... rekursiver Aufruf ...

Viele Grüße,

Siracusa

Zum Seitenanfang

Setag19

Gepostet:
03.01.2009 11:44

gelöst ;-)

Hallo,
nach einiger Zeit antworte ich nun hier. Da ich Ferien habe, habe ich mir mit der Lösung der Aufabe etwas Zeit gelassen.

Eben habe ich mich dann nochmal an die Aufgabe gesetzt und sie dank Siracusa´s Hilfe lösen können.
Ich dachte mir, dass ich meine Lösung dann auch einfach mal hier hinschreiben kann.

>	intRoot :: Int -> Int
>	intRoot m
>		| m==1  = 1
>		| m > 1 = check m 1

>	check :: Int -> Int -> Int
>	check m n 
>		| (m-n)^2 <= m  = (m-n)
>		| otherwise     = check m (n+1)

Danke für die Hilfe ;-)

Zum Seitenanfang

Haskell-Forum