Ein paar Scheme-Lösungen

Archiv Algorithmik II
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Ein paar Scheme-Lösungen
Hi Leute,

eigentlich wollte ich die wenigen Scheme-Lösungen, die ich in der Übung mitgetippt habe, in die Wiki stellen.

Da ich weder Zeit für Algo2 noch für die Wiki habe, stelle ich sie mal hier rein…

Aufgabe 30
GeradeUngerade
Aufgabe 38
Aufgabe 36
Aufgabe 35
Aufgabe 32
Aufgabe 31
Aufgabe 26
Hanoi
Aufgabe 37
Aufgabe 29

Die Aufgaben sind teilweise fehlerhaft, da ich öfters mit dem mittippen nicht mitkam (sind wohl Klammerfehler). Außerdem ist in den Dateien oft der Aufruf mit drinnen, so dass ihr die Dinger nur starten müsst.

Vielleicht helfen sie ja dem ein oder anderen.

Viele Grüße,
Sebastian

Attachment:
Scheme.zip: https://fsi.cs.fau.de/unb-attachments/post_41888/Scheme.zip

3

hat vielleicht jemand eine komplette lösung für aufgabe 29? bei meiner lösung gibt’s fast keine primzahlen und wenn, dann auch nur hin und wieder…

danke!

4

Beschreib doch mal, wie deine Loesung aussieht; vielleicht kann dir dann auch geholfen werden, ohne eine komplette Loesung zu haben…
[und wahrscheinlich ist der Lerneffekt so auch groesser :finger: ]

5

wo gibt es da das problm? bei der fastexp-mod oder bei der fermat?

6

hi leute!
hat jemand ahnung wie man funktionen schreibt die beliebige anzahl von parameter annehmen?

Beispiel-Aufgaben Vordiplom Algorithmik SS05 Seite 7
Aufgabe 4 (6 Punkte)
a) Schreiben Sie in Scheme eine Funktion disp, die als Parameter eine beliebige Anzahl
von Argumenten erwartet und als Seiteneffekt die interne Repraesentation dieser Argumente,
durch Leerzeichen voneinander getrennt, auf die Konsole schreibt; der Rueckgabewert
der Funktion soll unspezifiziert sein.
Beispiel:
(disp 'Dies “ist” '(ein) “Test”) liefert dies ist (ein) Test

der anzatz ist klar - man muss die ganzen argumente irgendwie in eine liste stöpfen, aber wie macht man das verstehe ich nicht :frowning:
im beispiel werden die parameter ganz normal (nicht als liste) übergeben…

7

so ungefaehr:
stklos> (define a (lambda x x))
;; a
stklos> (a 42 23)
(42 23)
stklos> (a 25)
(25)

vgl. 3.1.2 in http://gd.tuwien.ac.at/languages/scheme/tutorial-dsitaram/t-y-scheme-Z-H-4.html

8

vielen dank, palmcron ! das lambda-zeug hätte ich mir genauer anschauen sollen :wand:

(define disp
(lambda args

	(define write1 (lambda (x) (and  (display x)(display " "))))
		
	(begin (for-each write1 args)(newline))))

stklos> (disp 1 2 77 '() '(12 23 34 '(1 1 2)))
1 2 77 () (12 23 34 '(1 1 2))

9

tschuldigung, war ein paar tage weg…

ich denke, die fastexp-mod müsste stimmen, ich habe sie nur in 2 prozeduren aufgeteilt, weil ich das übersichtlicher finde…

STk> (define (fastexp a p)
        (if (<= p 1) a 
           (if (= (remainder p 2) 0)
            (fastexp (* a a) (/ p 2))
            (* a (fastexp (* a a) (/ (- p 1) 2))))))
            
fastexp

(define (fastexp-mod a p m)
        (remainder (fastexp a p) m))
fastexp-mod

…die letzte fermat-version, die ich noch finde war

STk> (define (fermat p)
        (let ((a (random 50))) ; höhere Werte brachten auch kein besseres Ergebnis
           (if (= (fastexp-mod a p p) a) #t)#f))
fermat

den rest habe ich wohl leider nicht gespeichert oder mein stk hat sich vorher in einer endlosschleife verrannt… :frowning:

10

@uschi:
Das Problem, das ich bei deiner Lösung sehe ist, dass beim Fermat-Test ja eine Zufallszahl hoch der zu testenden Primzahl genommen wird. Bei kleinen Zahlen funktioniert ja noch alles, aber wenn du mal testen willst, ob 13513 eine Primzahl ist, dann wird es schon etwas langsam erstmal diese riesen Zahl auszurechnen und diese dann modulo (oder remainder) zu nehmen. Deswegen ist es geschickter jedes Ergebnis einzeln modulo zu nehmen, also während man den exponenten einmal halbiert und die basis quadriert gleich mal die Basis modulo m zu rechnen.

Im wiki steht auch noch eine Lösung, die zuerst die Zahl ausrechnet und dann modulo nimmt. Hab meine Lösung einfach mal unten dran gehängt:
http://www.heeen.de/wiki/index.php/Algo2Blatt08

11

super, vielen dank!

dann war meine lösung ja gar nicht so falsch freu - trotzdem, für meinen Geschmack kommt ziemlich oft #f raus…

12

a sollte schon zwischen 1 und p liegen :slight_smile:
Und da fermat nur ein probabilistischer Primzahltest ist, sollte auch oefter als einmal getestet werden (siehe Aufgabenstellung :))
Dann sollte er aber halbwegs zuverlaessig sein.

Gibt er denn auch #f aus fuer Zahlen, von denen du weisst, dass sie Prim sind?