Programmieren I Übungsblatt 4

DocEvil

Trainee

Posts: 109

Date of registration: Oct 14th 2002

Location: Erschaffen aus Glut und Feuer, stärker als die Grundfesten der Erde

Occupation: CvD ;)

1

Saturday, November 9th 2002, 8:57pm

Sagt mal, hat da einer schon irgendwas gemacht, und könnte mir mal nen kleinen gedankenanstoß geben wie ich aus der rekursiven prozedur ne iterative machen kann?

Irgendwie komm ich da auf keinen algorithmus der irgendwie sinnvoll wäre.

Bei Aufgabe 2 übrigens auch nicht, die andern aufgaben hab ich mir vorsichtshalber ersteinmal gar nicht angeschaut, sonst wär ich ja gleich so demotiviert

gruß Doc

Doch weder Mensch noch Wolf noch Balrog hätte Morgoth zum Ziele geführt,
ohne den Verrat der Menschen.

---Das Silmarillion---

Go to the top of the page

Pak

Zuhörer

Posts: 2

Date of registration: Oct 21st 2002

Location: H.

2

Saturday, November 9th 2002, 10:27pm

Oh Shit! Wenn nicht mal du drauf kommst...

Go to the top of the page

Jethro

Junior Schreiberling

Posts: 185

Date of registration: Oct 15th 2002

3

Saturday, November 9th 2002, 11:10pm

Hi,
hab grade Aufgabe 1 fertiggemacht. Also um dir den Spaß nicht zu nehmen, hier nur ein paar kleine Anregungen:
Wir haben in der Vorlesung letzte Woche mal die Fibonacci-Zahlen so untereinandergeschrieben und dann so Pfeile drangemalt, was wie entstanden ist.
Mir hat es geholfen, Aufgabe 1 genauso anzugehen. Du rechnest einfach so die ersten 5 Folgen oder so aus und schreibst sie auf. Dann musst du die Erzeugungsvorschriftenherausfinden. Man muss quasi alles von hinten aufrollen, damit keine Operationenn verzögert werden. Wenn man es herausgefunden hat, ärgert man sich wie einfach es im Grunde ist

Ist wahrscheinlich meist so...
Also, viel Vergnügen

Information is like a mist, you have to breath it in

(De-Phazz - Information)

Go to the top of the page

DocEvil

Trainee

Posts: 109

Date of registration: Oct 14th 2002

Location: Erschaffen aus Glut und Feuer, stärker als die Grundfesten der Erde

Occupation: CvD ;)

4

Saturday, November 9th 2002, 11:13pm

Aufgabe 1 hab ich jetzt. Mit freundlicher unterstützung allerdings, vielen dank nochmal. Ist halt gar nicht so kompliziert, wenn man mal auf den algorithmus kommen würde.

gruß Doc

[edit] Aufgabe 2 hab ich auch geschafft, ich glaub langsam komm ich dahinter [/edit]

Doch weder Mensch noch Wolf noch Balrog hätte Morgoth zum Ziele geführt,
ohne den Verrat der Menschen.

---Das Silmarillion---

Go to the top of the page

Tara

Junior Schreiberling

Posts: 131

Date of registration: Apr 21st 2002

5

Sunday, November 10th 2002, 12:50pm

Zu Aufgabe 1: iterativ
Schön wärs wenns mir auch so ginge.

Im Grunde ist mir klar was die Prozedur machen soll, aber irgendwie klappt das alles nicht. Kann mir hier vielleicht wer helfen? Was genau mein Problem ist weiß ich leider auch nicht.
Danke schonmal

Go to the top of the page

EvilHomer

Junior Schreiberling

Posts: 214

Date of registration: Dec 12th 2001

Location: Region Hannover

Occupation: Da kommt Ihr nie drauf ;-)

6

Sunday, November 10th 2002, 1:55pm

Moin,

dann will ich mal ein paar Hinweise geben.

Ich habe folgeden Prozedur definiert:

(define (f-iter n counter x y z)

Der Algo lautet wie folgt:

(f-iter n (+ counter 1) y z (+ z (* 2 y) (* 3 x)))))

x, y und z von f-iter enthalten den aktuell vovorletzen, vorletzten und letzten Wert von f.

counter zählt alle Durchgänge, die f bereits berechnet hat, durch.
Der counter startet bei 3 und endet bei n+1, da bereits n Werte berechnet worden sind, folglich f(n).

__________
Mittlerweile habe ich noch eine 2. Version programmiert. Diese Prozedur ist verständlicher als die Erste, aber eigentlich gleich.

;; x = f(n + 2)
;; y = f(n + 1)
;; z = f(n)

(define (f-iter n)
(f-it 2 1 0 n))

(define (f-it x y z n)
(if (***)
*
(f-it ****))
*
*
(***))))

Das sollte nun aber genug Hilfe sein, wer immer noch Probleme hat kann ja mal in der Blockzeit seinen Betreuer fragen.

cu EH

When people look like ants - pull
When ants look like people - pray

Go to the top of the page

Benjamin

Segelnder Alter Hase

Posts: 3,827

Date of registration: Oct 1st 2002

Location: Region Hannover

Occupation: Alumni

7

Sunday, November 10th 2002, 5:13pm

hm
also Nummer 1 ging....

Nummer 2 hab ich auch nun eine iterative Lösung, doch ich frag mich was dieser Text unter der Aufgabe soll. Was sollen die von mir?

Also ich hab ne iterave O(log n) Prozedur, doch dieses andere mit beachten sie und ab^n solle sich nicht verändern....

häääh?

ich mach erstma weiter glaube ich

Es gibt nur eine bessere Sache als auf dem Wasser zu sein: Noch mehr auf dem Wasser sein.

Go to the top of the page

Jethro

Junior Schreiberling

Posts: 185

Date of registration: Oct 15th 2002

8

Monday, November 11th 2002, 11:35am

Kann es sein, dass der gegebene Algorithmus aus Aufgabe 2 (Prozedur fast-expt) die gleiche Laufzeit hat wie der iterative Algorithmus den man erstellen sollte?
Dann wäre ja 'nur' der Speicherbedarf verschieden..
Hoffe das sit richtig, bei mir arbeiten die nämlich so ziemlich gleichschnell:

Für 2^150000
fast-expt: 04:81 sec
iter-expt: 05:03 sec
Bei höherer Größenordnung holt iter-expt auf, aber nicht so viel, dass man eine andere Laufzeit annehmen könnte

@metalhen
Der Parameter a den man einführen soll, ist einfach ne Art Counter, der bei 1 beginnt und dann immer einen gewissen Wert annimmt, so dass a am Ende (!!) , nicht also zwischendurch, dass Ergebnis von b^n ist.

Information is like a mist, you have to breath it in

(De-Phazz - Information)

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

9

Monday, November 11th 2002, 12:34pm

also das mit der hilfe dass man sich die folgen aufschreiben soll bringts mir irgendwie nicht so

1 -> 1
2 -> 2
3 -> 4
4 -> 11
5 -> 25
6 -> 59
7 -> 142

irgendwie bin ich blind und seh da nix abzuleitendes

hilfe

hm habs jetzt auch, man muss eigentlich nur erkennen wie sich eine zahl zusammensetzt aus den vorherigen 2en

ich fand es schwierig genug

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

DocEvil

Trainee

Posts: 109

Date of registration: Oct 14th 2002

Location: Erschaffen aus Glut und Feuer, stärker als die Grundfesten der Erde

Occupation: CvD ;)

10

Monday, November 11th 2002, 4:09pm

Hi,

so ich bräucht nochmal Hilfe bei Aufgabe 3 (gerade als ich dacht ich wüßte wie das geht, las ich aufgabe 3 und wurde deprimiert) Kann mir mal irgendwer sagen welcher von den beiden Aufrufen end-rekursiv sein soll, für mich sehen die beide gleich aus.

Gruß Doc

P.S. Zu Aufgabe 2, woran erkenne ich das es ein O(log n) laufzeitverhalten hat?

Doch weder Mensch noch Wolf noch Balrog hätte Morgoth zum Ziele geführt,
ohne den Verrat der Menschen.

---Das Silmarillion---

Go to the top of the page

Benjamin

Segelnder Alter Hase

Posts: 3,827

Date of registration: Oct 1st 2002

Location: Region Hannover

Occupation: Alumni

11

Monday, November 11th 2002, 5:03pm

Quoted

woran erkenne ich das es ein O(log n) laufzeitverhalten hat?

wenn du in diesem Beispiel den Exponenten immer halbierst...
also allgemein, wenn man die Zählervariable oder was auch immer man abarbeitet nicht linear abarbeitet z.B: X:=(x-1) sondern es Halbierungen, oder Drittelungen usw gibt.
So hab ich das verstanden zumindest.

Müssen wir eigentlich bei 3 die Funktion ganz verstehen? dann steh ich vor nem Rätsel.. Teil 3.2 geht ja... doch das blöde bei der Funktion is, wenn man denbkt man hat das komplette System verstanden so stellt man ja immer wieder fest, dass ein Nachrechnen nicht möglich ist auf grund der grooßen Zahlen für rel. kleine x, y

Es gibt nur eine bessere Sache als auf dem Wasser zu sein: Noch mehr auf dem Wasser sein.

Go to the top of the page

Ray-D

Alter Hase

Posts: 690

Date of registration: Oct 9th 2002

Location: Zimbabwe-Island Ost Beiträge: 3.427

Occupation: Informatiker

12

Monday, November 11th 2002, 5:04pm

ich dachte programmieren soll spass machen...so langsam bekomm ich genug davon

ich kann doch mit dem wissen dass ich bisher habe unmöglich dieses blatt lösen!!! jede aufgabe wirft mehr fragen auf als man im stande ist zu beantworten und wenn man es zu fuß ausrechnen will dann dauert das mindestens 2 wochen und man verrechnet sich sowieso andauernt.
*frustablass*

danke fürs zuhören und mitleiden

"ob ich alles weiss, was wir wissen, weiss ich auch nicht, aber ich weiss natürlich niemand von uns weiss etwas was er nicht weiss" - Wolgang Schäuble
Freiheit wird nicht erbettelt, sondern erkämpft

Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von »Ray-D« (Heute, 04:29)

Go to the top of the page

Joachim

Guru

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

13

Monday, November 11th 2002, 5:27pm

Quoted

Original von Ray-D
ich dachte programmieren soll spass machen...

Wer hat dir das denn erzählt?

Quoted

so langsam bekomm ich genug davon ich kann doch mit dem wissen dass ich bisher habe unmöglich dieses blatt lösen!!! jede aufgabe wirft mehr fragen auf als man im stande ist zu beantworten und wenn man es zu fuß ausrechnen will dann dauert das mindestens 2 wochen und man verrechnet sich sowieso andauernt.

Auch, wenn du es wahrscheinlich nicht hören willst: Das wird im Laufe der Zeit sogar noch schlimmer ...

Im Ernst:

Es wird einem zu Beginn jedes Semesters so gehen, daß man (bestenfalls) nur die Hälfte versteht. Das ist ganz normal.

Aber gerade deswegen sollte man sich umso mehr reinhängen und versuchen, es zu verstehen. Wenn man irgendwann kapituliert, kommt überhaupt nicht mehr mit. Und in der Woche vor der Klausur kann man den Stoff einen ganzen Semesters auch nicht mehr aufholen (versuch' es gar nicht erst).

Also: Wenn man etwas nicht versteht, sollte man sich intensiv mit dem Thema beschäftigen (z. B. Literatur) und/oder einen der Übungsleiter fragen. Genau deswegen haben die nämlich Sprechstunden -- die nutzt nur leider fast niemand.

Das klingt jetzt zwar alles ganz einfach, aber ich weiß natürlich selber, daß es das nicht ist. Aber so schwer, wie es am Anfang scheint, ist es auch wieder nicht.

The purpose of computing is insight, not numbers.

– Richard Hamming, 1962

Go to the top of the page

Ray-D

Alter Hase

Posts: 690

Date of registration: Oct 9th 2002

Location: Zimbabwe-Island Ost Beiträge: 3.427

Occupation: Informatiker

14

Monday, November 11th 2002, 7:00pm

das es spass machen soll hat mir herr parchmann gesagt. das erste was man uns in dne vorlesungen übermitteln möchte ist der spass am programmieren.

"ob ich alles weiss, was wir wissen, weiss ich auch nicht, aber ich weiss natürlich niemand von uns weiss etwas was er nicht weiss" - Wolgang Schäuble
Freiheit wird nicht erbettelt, sondern erkämpft

Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von »Ray-D« (Heute, 04:29)

Go to the top of the page

DocEvil

Trainee

Posts: 109

Date of registration: Oct 14th 2002

Location: Erschaffen aus Glut und Feuer, stärker als die Grundfesten der Erde

Occupation: CvD ;)

15

Monday, November 11th 2002, 7:13pm

Quoted

Original von Ray-D
das es spass machen soll hat mir herr parchmann gesagt. das erste was man uns in dne vorlesungen übermitteln möchte ist der spass am programmieren.

Tja, da hat er wohl gelogen

gruß Doc

Doch weder Mensch noch Wolf noch Balrog hätte Morgoth zum Ziele geführt,
ohne den Verrat der Menschen.

---Das Silmarillion---

Go to the top of the page

mDev

Erfahrener Schreiberling

Posts: 282

Date of registration: Oct 10th 2002

Location: Hannover

Occupation: Wissenschaftlicher Mitarbeiter

16

Monday, November 11th 2002, 8:04pm

bis jetzt hatte es mir auch eigentlich spaß gemacht, aber
nach aufgabe 1 hab ich heut auch kapituliert, wenigstens hab ich die geschafft...

Go to the top of the page

Ray-D

Alter Hase

Posts: 690

Date of registration: Oct 9th 2002

Location: Zimbabwe-Island Ost Beiträge: 3.427

Occupation: Informatiker

17

Monday, November 11th 2002, 8:20pm

Quoted

Tja, da hat er wohl gelogen

dann lüge ich jetzt auch und sage das macht ja riesig spass

"ob ich alles weiss, was wir wissen, weiss ich auch nicht, aber ich weiss natürlich niemand von uns weiss etwas was er nicht weiss" - Wolgang Schäuble
Freiheit wird nicht erbettelt, sondern erkämpft

Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von »Ray-D« (Heute, 04:29)

Go to the top of the page

mDev

Erfahrener Schreiberling

Posts: 282

Date of registration: Oct 10th 2002

Location: Hannover

Occupation: Wissenschaftlicher Mitarbeiter

18

Tuesday, November 12th 2002, 2:55pm

was bedeutet eigentlich end- und was echt-rekursiv?

und hat irgendjemand den sinn von 3.2 h gecheckt?

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

19

Tuesday, November 12th 2002, 5:28pm

Quoted

Original von mDev
was bedeutet eigentlich end- und was echt-rekursiv?

und hat irgendjemand den sinn von 3.2 h gecheckt?

end-rekursiv bedeutet so viel wie, wenn die rekursive prozedur iterativ ist, also immer mit neuem ergebnissen rekursiv weitergerechnet wird.
echt-rekursiv heißt dann quasi das die funktion an der stelle eben rekursiv ist, also normal halt der speicher wächst und der rechner sich die ergebnisse an der stelle merken muss.
verstanden?

zu 3.2h geb ich dir mal folgenden tipp: die funktion mit der du diese prozedur ausdrücken willst, ist rekursiv ...
hilft dir das? wenn nicht geb ich dir nen größeren tipp

<hr width=100%>
kann mir wer zu aufgabe 4 was sagen? ich mein die funktion die dort entstehen soll hängt ja offensichtlich mit der letzten zeile dort zusammen:
d_n+2 := (n+1)(d_n+1 + d_n) n e N

heißt das mit dem (n+1) davor dass der term dahinter multipliziert wird oder wie habe ich das zu verstehen? also in dem sinne (n+1) mal die Summe aus den beiden vorherigen ergebnissen?

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

20

Tuesday, November 12th 2002, 6:20pm

hab noch mal nachgeschlagen und ne genaue definition gefunden:
Ein Aufruf einer rekursiven Methode heißt endrekursiv, wenn er die letzte Anweisung der rekursiven Methode ist.

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

Fachrat Informatik - Forum

Programmieren I Übungsblatt 4

Quoted

Quoted

Quoted

Quoted

Quoted

Quoted