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 ...

 

[oezix]

muss das ; hinter do nicht entfernt werden ?

Edit: sieht so aus als würde die Schleife ohne den Rumpf ausgeführt werden

 

[Thomebau]

Hab ich auch grade festgestellt :facepalm:
Mein Fehler

Es kommt aber immer noch ein Schleifendurchlauf zu viel, ich denke dass sollte mit

for i:=0 to n-1

gelöst sein...

 

[jal2]

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

Mir ging es darum, dass der TE den Zusammenhang zwischen der Definition und dem Code einfacher erkennen kann.

 

[jal2]

Hab ich auch grade festgestellt :facepalm:
Mein Fehler

Es kommt aber immer noch ein Schleifendurchlauf zu viel, ich denke dass sollte mit

for i:=0 to n-1

gelöst sein...

Mit

r:=1;
for i:=1 to n do
  r:=2*r+1;

gilt in jedem Durchlauf nach der Zuweisung f(i) = r, wobei natürlich

for i:= 0 to n-1 do ...

das gleiche Ergebnis liefert. Nur wenn man, wie oben empfohlen, per print debuggt, ist das IMHO einfacher.

 

[jal2]

Eingabe(=n) war 99

Haben Integer in Delphi einen beliebigen Wertebereich??

f(99) = 2^100 - 1

Das würde in C in kein uint32 oder uint64 passen.

EDIT: Gerade nachgesehen - wenn diese Seite stimmt, kann man mit integer maximal f(30) berechnen, mit cardinal f(31) und mit int64 f(62).

@Thomebau - schon mal probiert?

 

[oezix]

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;

Fehler beruht darauf das r mit 1 initialisiert wurde und nicht mit 0

wenn man die Schleife nicht bis n, sondern bis n-1 durchlaufen lässt, stimmt zwar das Ergebnis, sogar auch für n=0 denn in diesem Fall würde die Schleife erst garnicht durchlaufen, aber ich würde trotzdem umändern

 

[Thomebau]

so, aus Spaß an der Freude mal probiert: sämtliche "größeren" zahlen liefern als Ergebnis nur -1.

ansonsten funktioniert es wie es soll:

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




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

falls es interessiert, aufgerufen wird mit:

beginreadln(V);
writeln(Aufgabe1b(V));
readln();
end

 

[jal2]

Fehler beruht darauf das r mit 1 initialisiert wurde und nicht mit 0

Hast recht, das habe ich übersehen (und oben korrigiert).

 

[Thomebau]

hmmm gut das ist aber wohl eher Kosmetik als schwerwiegender Fehler

ob ich jetzt von 1 bis n-1 laufen lasse oder von 0 bis n ...

Die Rekursive Variante ist irgendwie viel intelligenter...

EDIT:
Ganz vergessen

Vielen Dank für eure Hilfe! Einfach einmalig das Forum hier

 

[jal2]

so, aus Spaß an der Freude mal probiert: sämtliche "größeren" zahlen liefern als Ergebnis nur -1.

Mit double oder extended käme man weiter, aber auch da wäre irgendwann Schluss.

Off-Topic: Gibt es Programmiersprachen, in denen die Werte von Integer beliebig gross sein können? Mir fällt da nur LISP ein

 

[Thomebau]

und wie funktioniert das? schreibt das dann einfach an anderen Adressen weiter oder wie?

 

[jal2]

und wie funktioniert das? schreibt das dann einfach an anderen Adressen weiter oder wie?

Wenn Du

Gibt es Programmiersprachen, in denen die Werte von Integer beliebig gross sein können? Mir fällt da nur LISP ein.

meinst, dort werden grosse Integer (sogenannte Bignum) in variabel langen Speicherbereichen abgelegt. Alle Berechnungen damit benötigen Bibliotheksaufrufe
(kein Support durch den Prozessor) und dauern entsprechend lang. Grenzen gibt es trotzdem noch - den Adressraum des Prozesses und eventuell noch die interne
Darstellung, wenn die Länge des Bignum als fixnum kodiert ist, d.h. max. Länge 2^28 Byte o.ä.

EDIT: Sind doch noch mehr Sprachen: http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

 

[vlooe]

Im Prinzip kann man beliebig große Ints mit jeder Programmiersprache Nachbilden.
Wie Komfortabel das geht kommt auf die Sprache an.

Wenn die Sprache Operatorüberladung kann dann sieht man den Unterschied nur bei der Deklaration der Variablen.