rekursiv -> iterativ umwandeln Abitur 2010 Informatik

[Thomebau]

Hi,
ich brauche mal ein bisschen Hilfe bei einer Abiaufgabe im Fach Informatik aus dem Jahr 2010.
Leider sind die Sachen wie Rekursion, Schleifen etc. schon ziemlich lange her

kurz:
Es geht um folgende Aufgabe:


Teil 1 habe ich ohne Probleme gelöst (f(3)=15).
Teil 2a) ist kein Problem, hier meine Lösung:

function Aufgabe1a(n:integer) :integer;    
    begin;
         if n<>0 then
               begin
                    result:=2*Aufgabe1a(n-1)+1;
               end
         else
         result:=1
    end;

Teil 2b) bereitet mir Probeleme ^^
Ich finde einfach keine Funktion die diese Werte erzeugt wie die rekursive.
Die Wertetabelle ist zwar irgendwie regelmäßig, aber dennoch nicht auf Anhieb zu entschlüsseln.
[TABLE="class: grid, width: 50"]
[TR]
[TD]1[/TD]
[TD]2[/TD]
[TD]3[/TD]
[TD]4[/TD]
[/TR]
[TR]
[TD]3[/TD]
[TD]7[/TD]
[TD]15[/TD]
[TD]31[/TD]
[/TR]
[/TABLE]


Irgendjemand eine Idee wie ich das angehe?
(Die Lösung alleine hilft mir hier nicht weiter, ich muss es ja können ^^)

EDIT: Und ja ich weis es ist wahrscheinlich sehr einfach, ich bekomms nur einfach nicht hin ...

 

[afo]

.ah mist. Aufgabe vorher lesen hilft. Vergiss was hier vorher stand.

Aber die Formel für die untere Folge ist doch offensichtlich.

 

[oezix]

wenn ich mich nicht verrechnet habe müsste f=2^(n+1) - 1 sein

 

[Thomebau]

Stimmt :facepalm:

Sowas sehe ich nicht, keine Chance, dafür bin ich zu schlecht in Mathe :crying:

 

[jal2]

Stimmt :facepalm:

Sowas sehe ich nicht, keine Chance, dafür bin ich zu schlecht in Mathe :crying:

Ich schreibe mir bei solchen Aufgaben immer zuerst die Differenz zweier aufeinanderfolgender Werte hin, hier also 4,8,16. Hilft oft.

EDIT: Du wolltest doch die vollstaendige Loesung fuer 2b).

mit sturem, wiederholten Einsetzen (fuer n > 0):

f = 2 * f(n-1) + 1
f = 2 * ( 2 * (f(n-2) + 1) + 1 = 4 * f(n-2) + 2 + 1
f = 8 * f(n-3) + 4 + 2 + 1
...
f = 2^k * f(n-k) + (2^(k-1) + 2^(k-2) + ... + 2 + 1)

und dann fuer k=n:

f = 2^n * f(0) + (2^(n-1) + ... + 2 + 1) = 2^n + 2^n - 1 = 2^(n+1) - 1

Am Ende noch mal testen, ob die Formel auch fuer n=0 gilt, weil wir oben n > 0 angenommen haben. Macht sie aber.

EDIT2: Gerade gesehen, eine geschlossene Formel zu finden war ja gar nicht die Aufgabe.

 

[thf001]

f=2^(n+1)-1 ist aber nicht iterativ. Es ist doch gar nicht nach einer geschlossenen Formel gefragt.

Das hier sollte es meiner Meinung nach tun:

f = 1
for (int i=1; i<=n; i++) {
    f = 2*f+1;
}

 

[vlooe]

Ich denke das umformen ist aber nicht die gesuchte iterative lösung ;-)

Iterativ heißt immer eine Schleife machen und von untern anfangen

alt = 1 //f(1)
wiederhole n mal
  neu = 2*alt + 1
  alt = neu

 

[oezix]

@thf001 hast recht :thumbup:

 

[Thomebau]

Ich weis dass eine Schleife gesucht ist, ich bin da aber bisher nicht sonderlich weit gekommen.

function Aufgabe1b(n:integer) :integer;
var i:integer;
    begin;
    for i:=n to 0 do;
        n:=2*n-1;
    result:=n;
end;

Was nicht funktioniert

 

[vlooe]

Probiers mal so ;-)
Das ist +1 nicht -1

function Aufgabe1b(n:integer) :integer;
var i:integer;
    begin;
    for i:=n to 0 do;
        n:=2*n+1;
    result:=n;
end;

 

[afo]

Was nicht funktioniert

Es wäre hilfreich würdest du den falschen Output in deinem Post wiedergeben. Und wer sagt denn, dass du für die Variablen der Zählschleife und die mit der gerechnet wird die gleiche Variable nehmen mußt? Im Moment sieht mir das nach Endlosschleife aus.

 

[thf001]

Da das eigentliche Problem jetzt gelöst ist, noch ein Hinweis zur geschlossenen Formel: Sauber beweisen würde man die Formel mit vollständiger Induktion (mann, das waren noch Zeiten). Im Prinzip das was jal2 gemacht hat (nur da rückwärts):

n=0:
f(0) = 2^1 - 1 = 1

n-1 -> n:
f = 2 * f(n-1) + 1 = 2 * (2^n - 1) + 1 = 2^(n+1) - 2 + 1 = 2^(n+1) - 1

 

[oezix]

ich kenn mich mit Pascal nicht aus und hoffe das ich kein mist geschrieben habe

function Aufgabe2b(n:integer) :integer;
var i:integer;
var f:integer;
f:=0;
begin;
for i:=0 to n do
f:=2*f+1;
result:=f;
end;

 

[jal2]

Hmm, ich finde es so uebersichtlicher. r enthaelt am Ende jedes Schleifendurchlaufes f(i).
Bin mir nicht sicher, ob die Syntax korrekt ist.

function Aufgabe1b(n:integer) :integer;
 begin
     var i,r:integer;
     for i:=0 to n do
        if  i = 0 then
           r:=1
        else
           r:=2*r+1;;
     result:=r;
   end

EDIT: zu spaet.

 

[oezix]

wieso machst du eine Fallunterscheidung ?
2*0+1 ist doch 1

ist es nicht besser gleich mit r=0 zu initialisieren ?

 

[jal2]

wieso machst du eine Fallunterscheidung ?
2*0+1 ist doch 1

ist es nicht besser gleich mit r=0 zu initialisieren ?

Weil das naeher an der Vorschrift fuer f aus der Aufgabenstellung dran ist.

 

[oezix]

f wurde rekursiv definitiert, aber bei der Aufgabe muss es iterativ berechnet werden und da kann man getrost auf die Fallunterscheidung verzichten

 

[Thomebau]

hmmm das funktioniert nicht.
Das Ergebnis ist immer =n falsch, das Ergebnis ist immer 3 ??? (ich nehme an er liest das irgendwo aus dem Speicher?)
(ich hoffe ich hab den Sinn nicht verändert als ich die Syntax korrigiert habe)

function Aufgabe1b(n:integer) :integer;var i,r:integer;
begin;
     r:=1;
     for i:=0 to n do;
         r:=2*r+1;
     result:=r;
end;

 

[vlooe]

Tip zur Fehlersuche:
Mach in jedem Schleifendurchlauf eine Ausgabe und überlege ob das so gewollt ist.

Gewollt ist dann die Ausgabe 1,3,7,.....

 

[Thomebau]

Danke für den Tipp.

Das verstehe ich nicht:
Eingabe(=n) war 99
folgende Ausgabe:
r: 3
i: 99
n: 99

und das Ergebnis: =3