Struktogramm < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:02 Do 21.08.2008 | | Autor: | tynia |
| Aufgabe | | Das Newton-Verfahren zur Bestimmung einer Nullstelle angewandt auf [mm] f(x)=(x-\bruch{1}{2})^2 [/mm] ergibt die Iterationsvorschrift [mm] x_{i+1}=\bruch{1}{2}*x_{i}+\bruch{1}{4}.Wie [/mm] lautet zu gegebenen Werten [mm] x_{0}und [/mm] n das n-te Folgenglied? |
Ich sollte jetzt zwei Struktogramme entwerfen, einmal iterativ mit for-Schleife, und einmal rekursiv.
Jetzt würde ich gerne wissen ob das auch richtig ist. wäre schön, wenn mir da einer weiter helfen könnte.
danke schonmal im voraus
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:57 Sa 23.08.2008 | | Autor: | uliweil |
Hallo Tina,
nach dem Lesen der Aufgabenstellung hätte ich eher vermutet, dass hier eine rein mathematische Frage gestellt wird, nämlich die nach einer Formel für das n-te Folgenglied, aber sei's drum.
Zu Deinen Struktogrammen: Das iterative sieht bis auf ein paar kleine Unschönheiten (y[0] = x sollte man außerhalb der Schleife setzen, sonst wird es unnötigerweise bei jeder Iteration durchlaufen; was ist, wenn einer ein n größer 100 oder kleiner 1 eingibt?) und der Tatsache, dass es nicht erforderlich ist alle Iterationswerte in einem Array aufzuheben, wenn man nur am letzten interessiert ist, ganz richtig aus.
Das Struktogramm zur Rekursion allerdings, ist keine Rekursion, sondern eine in ein Unterprogramm verlagerte Iteration. Für eine Rekursion müsste aus dem Unterprogramm das Unterprogramm (direkt oder über Umwege) wieder aufgerufen werden, dies erfolgt aber hier nicht. Darüber hinaus ist das auch hier unnötigerweise benutzte Array y nicht deklariert. Bei rekursivem Vorgehen ist ein Array übrigens auch dann überflüssig, wenn man die einzelnen Iterationswerte zwischenspeichern will, denn dies geschieht "automatisch" in den im Stack angelegten Speicherbereichen für die jeweiligen (rekursiven) Unterprogrammaufrufe.
Gruß
Uli
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:04 Sa 23.08.2008 | | Autor: | tynia |
könntest du mir vielleicht ein Beispiel für ein rekursives Struktogramm geben? Ich verstehe das nämlich nicht so ganz?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:19 Sa 23.08.2008 | | Autor: | uliweil |
Hallo Tina,
Rekursion bedeutet: in der Definition der Funktion wird die Funktion selbst benutzt.
Das Paradebeispiel für eine Rekursion ist das Berechnen der Fakultät:
iterativ hingeschrieben: n! = 1*2*3*... *n.
rekursiv hingeschrieben: n! = n * (n-1)!
die rekursive Definition braucht eine Zusatzinformation: 0! = 1
Ich habe Dir dieses Beispiel in ein Programm umgesetzt (nicht in ein Struktogramm, das war mir zu aufwändig zum zeichnen). Dafür ist das Programm getestet. Die Sprache ist übrigens Pascal und es wir Dir leicht gelingen, das in ein Struktogramm umzusetzen, wenn nötig.
Hier erstmal das Programm:
program Fakultaet;
var n:integer;
function fak(n:integer):integer;
begin
if n > 0 then
fak := n * fak (n-1)
else
fak := 1
end;
begin
writeln(' n eingeben');
readln(n);
if n >= 0 then
writeln(fak(n))
else
writeln(' n negativ')
end.
Das Unterprogramm fak (eine function, was bedeutet, dass der Name selbst einen Wert trägt), wird rekursiv (von sich selbst und zwar in der Zeile fak := n * fak (n-1) ) aufgerufen. Die If-Abfrage sorgt dafür, dass die ganze Geschichte terminiert.
Ich hoffe, Du kommst klar.
Gruß
Uli
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:27 Mi 03.09.2008 | | Autor: | uecki |
Hallo, ich bin eine Kommilitonin von tynia.
Ich habe das mit dem rekursiv irgendwie noch nicht ganz begriffen.
Habe mal bei Newton eine ausgelagerte Funktion als "rekursiv" gemacht, weiß halt nicht ob das so stimmen kann.
Ich dachte mir das so:
for (i=n-1;i>=0;i--)
y[i]=0.5*y[i-1]+0.25
Ist damit rekursiv gemeint? Also einfach "rückwärts" rechnen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:36 Mi 03.09.2008 | | Autor: | uliweil |
Hallo uecki,
aber nein, rekursiv ist nicht rückwärts! Deine for-Schleife wird keine Ergebnisse liefern, denn wenn Du y[n] berechnen willst brauchst Du y[n-1] und um das zu berechnen brauchst Du y[n-2] und ...
Ich versuchs mal zuerst mit etwas Mathematik. Definition durch Rekursion bedeutet, dass eine Folge von Zahlen durch ihren Anfangswert, sagen wir [mm] a_{0} [/mm] und durch eine Berechnungsformel der Art [mm] a_{n + 1} [/mm] = "irgendwas mit [mm] a_{n}" [/mm] bestimmt wird und nicht durch [mm] a_{n} [/mm] = "irgendwas mit n". Beispiel siehe Fakultät aus meiner letzten Antwort. Dass eine solche Definition durch Rekursion überhaupt korrekt möglich ist, liegt am Prinzip der vollständigen Induktion, dem 5. Peanoaxiom, deshalb nennt man rekursive Definitionen auch: Definition durch vollständige Induktion.
Nun zur Datenverarbeitung: Rekursive Programmierung setzt zunächst einmal voraus, dass dies von der benutzten Programmiersprache unterstützt wird. Die erste Programmierprachen, wie z.B. Fortran oder Cobol konnten dies nicht. Pascal war eine der ersten Sprachen, die dies konnten: durch den Aufruf einer Prozedur oder Funktion werden die von ihr benutzten Variablen auf einem Stack abgelegt ("Kellerspeicher"). Wird nun diese Prozedur oder Funktion direkt (oder über Umwege) wieder aufgerufen, ohne dass sie vom vorherigen Aufruf her beendet worden wäre, spricht man von rekursivem Aufruf der Prozedur / Funktion. Die nun erneut benötigten Variablen der Prozedur / Funktion (die unverschämterweise auch noch genauso heißen) kommen wiederum auf den Keller und so weiter. Werden nun im Laufe der weiteren Berechnung die gestarteten Prozeduren / Funktionen beendet, kommen die gekellerten Variablen wieder an die Oberfläche des Kellers und haben ihren vorher dort abgelegten Wert. Somit existiert (lebt) eine rekursiv aufgerufene Prozedur / Funktion während der Programmausführung nicht nur einmal, sondern so oft, wie sie aufgerufen (und noch nicht beendet) wurde.
Puh!!!!!
Ich gebe zu, dass man von diesen Dingen einen Knoten in den Kopf bekommen kann. Mein Tipp wäre, ein solches rekursives Programm mal mit einem Debugger Schritt für Schritt durchzugehen, oder, wenn man den nicht hat, das Ganze auf dem Papier zu tun.
Als Literatur dazu empfehle ich: N. Wirth, Algorithmen und Datenstrukturen, Teubner
Gruß
Uli
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 06:36 Do 04.09.2008 | | Autor: | Somebody |
> aber nein, rekursiv ist nicht rückwärts!
Man muss aber zugeben, dass das Beispiel der Fakultät insofern etwas unglücklich gewählt war, als es leicht in eine Iteration umgewandelt werden kann. Ganz allgemein kann bei solchen ![[]](/images/popup.gif) endrekursiven Funktionen der rekursive Aufruf einfach durch einen Sprung an den Anfang der Funktion ersetzt werden.
Dadurch entsteht leicht der falsche Eindruck, es handle sich bei der rekursiven Definition einer Funktion lediglich um eine Form der Iteration.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:35 So 14.09.2008 | | Autor: | tynia |
Ich habe eine rekursive Gleichung für das Newton-Verfahren zur Bestimmung einer nullstelle gefunden, die so lautet:
[mm] x_{i+1}= x_{i} [/mm] - [mm] \bruch{f(x_{i})}{f'(x_{i})}
[/mm]
Kann mir jemand sagen wie ich das in ein Struktugramm übertrage. Ich meine jetzt speziell [mm] f(x_{i}) [/mm] und so.
Danke schonmal
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:39 So 14.09.2008 | | Autor: | Loddar |
Hallo tynia!
Im ersten Post dieses Threads hast Du doch selber ein Struktogramm geliefert. Da muss tDu halt lediglich die spezielle Funktion durch die allgemeinen Funktionsterme [mm] $f(x_i)$ [/mm] bzw. [mm] $f'(x_i)$ [/mm] ersetzen.
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:52 Mo 15.09.2008 | | Autor: | uecki |
Ich habe dazu mal ein Programm geschrieben. Und zwar:
# include <iostream>
using namespace std;
void main()
{
double x,y[10];
int i,n;
cout << "Bitte geben Sie Ihren x0 Wert und Ihr n ein: [mm] \n";
[/mm]
cout << "x0 = ";
cin >> x;
cout << "n = ";
cin >> n;
y[0]=x;
for (i=0;i<n;i++)
{
y[i+1]= y[i]- (((y[i]-0.5)*(y[i]-0.5))/(2*y[i]-1));
cout << "Ihr Folgeglied lautet: x[" << i << "]=" << y[i+1] << [mm] "\n";
[/mm]
}
}
Ist das die rekursive Berechnung?
|
|
|
| |
|
> Ist das die rekursive Berechnung?
Nein, das ist nicht rekursiv. Das was du machst ist iterativ.
Rekursiv bedeutetm das sich ein unterprogramm/ eine Funktion selbst wieder aufruft.
Hier ist ein Beispiel mit erläuterung.
lg
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 12:56 Mi 17.09.2008 | | Autor: | tynia |
So. Das ist der letzte Versuch. Dann gebe ich auf
Also ich habe das jetzt rekursiv so programmiert:
#include <iostream>
using namespace std;
void main ()
{
float x;
double y (double,double);
int n,i;
cout << "Gib x0 und n ein: [mm] \n";
[/mm]
cout << "x0= ";
cin >> x;
cout << "n= ";
cin >> n;
cout <<"Ihr n-tes Folgeglied lautet: [mm] \n";
[/mm]
cout <<"xn= [mm] \n";
[/mm]
cout << y(x,n)<< endl;
}
double y (double x, double n)
{
if(n==0)
return x;
else return (0.5*y(x,--n) + 0.25);
}
Ich habe jetzt kein Array benutzt. Ich glaube nicht das man das unbedingt braucht,oder? Wär schön, wenn mir jemand zu meinem Quellcode und der Sache mit dem Array was sagen könnte. Danke schonmal
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:20 Fr 19.09.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
