REKURSION + ITERATION

REKURSION + ITERATION

Bemerkung:Die in den folgenden Folien

angegebenen "Herleitungen" sind keine exakten Beweise, sondern

Plausibilitätsbetrachtungen.Die exakten Beweise wurden dazu

in einem anderen Dokument gemacht.

Produktion von wunderbaren Zahlen.

Dazu werden natürlich wieder die Regeln (zur Produktion) verwendet.

Diese sind…

--- 3

--- 5

{r; s} ------ wobei rX={1; 2; 3; ...} und sX und r s

r+s

Regel 1, kurz R1

Regel 2, kurz R2

Regel 3, kurz R3

Zu einer Regel, an der die leere Menge beteiligt ist, sagt man auch Axiom.Wir sagen zu den "Produkten" 3 und 5 jeweils Atom.

Die Produktion beginnt wie üblich mit dem

"Urknall" (= leere Menge).D0 =

Welche Menge D1 wird dann danach produziert ?

Welche Regel kann man dazu anwenden (verwenden)?

Da es für den "Urknall" nur 2 Regeln gibt, kann man

nur R1 und R2 verwenden. Also…

Aus dieser wird dann wieder (mit Hilfe von R1 und R2) die Menge D1

gebastelt

3

Mit der leeren Menge beginnt alles

5

Wie sieht die Menge D2 aus? Wie wird sie gebastelt?

Man darf jetzt beliebige Teilmengen aus D1 auswählen

und auf diese eine Regel anwenden. Was ist die kleinste

Teilmenge in D1?3 5

Das ist die leere Menge. Welche Regeln kann man darauf anwenden?

R1 und R2, also bekommt man die Elemente…

3 5 Auf welche weitere Teilmenge von D1 kann man welche Regel anwenden ?

Auf die Menge {3;5} . Dies ergibt das neue Element 3+5 = 8

8

D1

D2

Man darf jetzt beliebige Teilmengen aus D2 auswählen

und auf diese eine Regel anwenden. Was ist die kleinste

Teilmenge in D2?

3 5

Das ist die leere Menge. Welche Regeln kann man darauf anwenden?

R1 und R2, also bekommt man die Elemente…

3

5

Auf welche weitere Teilmenge von D2 kann man welche Regeln anwenden ?

Auf die Mengen {3;5}. Dies ergibt dann das neue Element 3+5 = 8

D2

D3

8

8

3 5

3

5

D2

D3

8

8

Auf welche weitere Teilmengen von D2 kann man welche Regeln anwenden ?

Auf die Mengen {3;8}, {5;8} . Dies ergibt dann die neuen Elemente 3+8=11, 5+8=13

11 13

3

5 D3

8

Auf die leere Menge als Teilmenge von D3 kann man welche Regeln anwenden? Was ergibt dies für neue Elemente von D4

Regel R1 und R2. Diese ergibt 3 und 5

11 13

3 5

D4

8

11

13

Auf welche weitere Teilmengen von D3 kann man R3 anwenden?Was ergibt das für neue Elemente ?

{3,5} --> 8 {3,8} --> 11

{5,8} --> 13 {3,13} --> 1616 {5,13} --> 18

18

{8,13} --> 21

21 {11,13} --> 2424 {5,11} --> 16

16 {8,11} --> 1919

3

5 D3

8

11 13

3 5

D4

8

11

13 16

18

21

16 19

Dies geht unendlich oft weiter …

Die Vereinigung all dieser Mengen ist die zu konstruierende GesamtmengeD = {3;5;8;11;13; …} der wunderbaren Zahlen

Welche mengentheoretische Beziehung besteht zwischen D0, D1, D2, D3, usw. ?

D0 D1 D2 D3 … D

24

Uns interessiert nun, ob eine Zahl zu der Gesamtmenge D gehört oder nicht. Dazu definiert man die Funktion e (wie evaluate) mit …

e(x) = 1 <==> x D unde(x) = 0 <==> x D

Berechnen Sie dazu e(1), e(2), e(3), e(4), e(5), e(6), e(7), e(8)e(1)=0, e(2)=0, e(3)=1, e(4)=0, e(5)=1, e(6)=0, e(7)=0, e(8)=1

1 könnte man auch als W (wahr) und 0 als F (falsch) interpretieren.

3 5 8

11

13 16

18

21 24

16 19

D4

Man könnte nun eine Funktion e(int z) implementieren, die feststellt, ob die Zahl z zu D gehört oder nicht.Wie könnte man dies iterativ machen?

Wiederholt werden aus der alten Menge die neuen Elemente berechnet und dieser Menge hinzugefügt. Dies muß hinreichend oft gemacht werden.

Wie kann dies rekursiv realisiert werden …?Beachten Sie dazu folgende Informationen ...

D = {3 ; 5 ; 8 ; 11; 13; ...}

3D und 5D ==> ?

Was folgt daraus, d.h. welche Zahl gehört dann auch zu D ?

D = {3 ; 5 ; 8 ; 11; 13; ...} Man sieht sofort:

3D und 5D ==> 3+5D

D = {3 ; 5 ; 8 ; 11; 13; ...} Allgemeiner:rD und sD ==> ?

Was folgt daraus, d.h. welche Zahl gehört dann auch zu D ?

D = {3 ; 5 ; 8 ; 11; 13; ...} Allgemeiner:rD und sD ==> r+sD

D = {3 ; 5 ; 8 ; 11; 13; ...} Gilt dies auch umgekehrt ?D.h:r+sD ==> rD und sDWenn dies nicht gelten sollte, geben Sie bitte ein Gegenbeispiel an.

D = {3 ; 5 ; 8 ; 11; 13; ...} r+sD ==> rD und sDDiese Aussage ist falsch, denn aus 8D folgt NICHT 1D und 7D

D = {3 ; 5 ; 8 ; 11; 13; ...} r+sD ==> rD und sDKann man diese Aussage so abändern, daß sie korrekt wird ? Bedenken Sie dazu, daß zwar ...

D = {3 ; 5 ; 8 ; 11; 13; ...} 8D ==> 1D und 7D falsch, aber8D ==> 3D und 5D richtig ist.

8D <==> 1D 7D 2D 6D 3D 5D

d.h. in mindestens einer Zerlegung müssen alle 2 Zahlen aus D sein !

8D <==> 1D 7D 2D 6D 3D 5D

bzw. wenn man die Schreibweise mit e(...) verwendet ...

e(8)=1 <==> e(1)=1 e(7)=1 e(2)=1 e(6)=1 e(3)=1 e(5)=1

oder wenn man statt und lieber * und + schreibt:

e(8)=1 <==> e(1)=1 * e(7)=1 + e(2)=1 * e(6)=1 + e(3)=1 * e(5)=1

Wie kann man e(8) aus e(1), ..., e(7) berechnen?e(8)=e(1)+e(2)+...e(7) wäre z.B. nicht korrekt!

e(8) = e(1) * e(7) +

e(2) * e(6) +

e(3) * e(5)

Welchen Wert haben e(1), ..., e(7) und wie berechnet man daraus e(8) ?

1 1

0 0

001

e(8) = e(1) * e(7) +

e(2) * e(6) +

e(3) * e(5)

e(8) wird rekursiv, d.h. durch die Verwendung von "vorigen" Werten e(1), ..., e(7) berechnet.

1 1

0 0

001

Die dahinter stehende Struktur kann man anschaulich durch einen sogenannten UND-ODER-Baum darstellen.Dies ist ein Baum, in dem UND-Gatter und ODER-Gatter vorkommen, also folgende Form haben:

..................................... usw. .....................................................

blaue Gebilde : ODER-Gatter

rote Gebilde : UND-Gatter

e(1)e(6) e(2)

e(3)

e(7)

e(1) e(5) e(2)e(4)

e(1) e(3)

e(5) e(4)

e(1) e(3)

10

0

0

00 1

00

00

0

0 1

0

0

110

0 0

jetzt wird von den grünen Blättern ausgehend nach oben hin der Baum ausgwertet.

0

Dies kann man auch etwas mathematischer darstellen:

e(8) = e(x1) * e(x2) {x1,x2}K(8)

wobei K(x) die zu x gehörende Kandidatenmenge ist.K(8) = { {1, 7}, {2, 6}, {3, 5} }

Weitere rekursive Berechnungen?

e(5) = ?Wie berechnet man aber e(5) rekursiv, d.h. kann e(5) durch Verwendung von e(1), ..., e(4) berechnet werden ?

Nein, denn 5wird direkt aus der leeren Menge produziert Also ist e(5) = 1

e(2) = ?Wie berechnet man aber e(2) rekursiv, d.h. kann e(2) durch Verwendung von e(1) berechnet werden ?

Nein, denn 2 kann nicht als Summe zweier verschiedener Zahlen ≥1 dargestellt werden. Da 2 auch nicht aus der leeren Menge produziert wird, gilt e(2) = 0

Rekursive Berechnung von e(7) Aus welchen Elementen aus D könnte die 7 theoretisch produziert worden sein?

7

1, 6 3, 42, 5

1, 50

00 0

0

1 0

1

1

Wie groß ist jeweils e(b), d.h. welchen Wert haben die roten Blätter ?

e(6)= 0*1+0*0

e(7)= 0*0+0*1+1*0

2, 4

1, 310

1, 3100

e(4)=0*1

e(4)=0*10

Insgesamt ergibt dies die folgende mathematische Formel:

// Kandidatenmenge leer:Fall: K(x) = ==> e(x) = 0

// x kommt direkt nach dem Urknall:Fall: K(x) ==> e(x) = 1

Fall: sonste(x) = e(x1) * e(x2) {x1,x2}K(x)

Bevor wir die zugehörige Funktion e(...) implementieren, machen wir noch ein paar Überlegungen ...

Wie kann man die folgende Formel implementieren?

e(x) = e(x1) * e(x2) {x1,x2}K(x)

Man kann die zu x gehörige Kandidaten K(x) bestimmen und in ein Feld v eintragen.Für K(15) wäre dies z.B:

1 14 2 13 3 12 4 11 5 10 6 9 7 8

Was muß dann noch berechnet werden ?

e(1)*e(14) + e(2)*e(13) + e(3)*e(12) + e(4)*e(11)+

e(5)*e(10) + e(6)*e(9) + e(7)*e(8)

Angenommen, die Funktion e(x) würde schon implementiert sein.Implementieren Sie e(1) * e(14) + ... + e(7) * e(8)

e(15) =

...int sum=0;

for(i=1;i<15;i=i+2){ sum = e(i)*e(15-i)+sum;}...

Annahme: Das Feld v ist sehr groß.

Wie könnte man die Laufzeit (Performance) des Programms verbessern ?

Beachten Sie dazu Folgendes:

e(1)*e(14) + e(2)*e13) + e(3)*e(12) + e(4)*e(11) + e(5)*e(10) + e(6)*e(9) + e(7)*e(8)

Welche Werte können e(1) , ... , e(14) annehmen ?

0 oder 1

Angenommen, man interpretiert den obigen Term als logischen Ausdruck (* als das logische UND und + als das logische ODER). Welchen Wert (Integer-Zahl) hat dann der obige Term, wenn er FALSCH ist ?Welchen Wert (Integer-Zahl) hat dann der obige Term, wenn er WAHR ist ?

Wenn er FALSCH ist, dann muß e(1) , ... , e(14) gleich 0 sein, also hat der Term den Wert 0.Wenn er WAHR ist, dann können e(1) , ... , e(14) alle gleich 1 sein, also hat der Term einen Wert zwischen 1 und 7.Kurz: FALSCH entspricht 0WAHR entspricht ≥ 1

Aufgabe:Angenommen, die Funktion e(x) würde schon implementiert sein.Implementieren Sie e(1) * e(14) + ... + e(7) * e(8)unter der Bedingung, daß sich das Laufzeitverhalten verbessert.

int sum=0;

for(i=0;i<14;i=i+2){ sum = e(i)*e(15-i); if (sum==1) break;}

Wenn sum das 1. Mal den Wert 1 hat, ist der Wahrheitswert W, unabhängig davon, was die nachfolgenden Produkte für Werte haben.

Aufgabe:Erstellen Sie die Funktion

eRek(int zahl), die berechnet, ob eine Zahl zu den

wunderbaren Zahlen gehört (oder nicht)

Lösung:

#include "stdafx.h"int eRek(int zahl);

int main(){ int erg, i; for(i=1;i<20;i++){ erg = eRek(i); printf("%d %d\n", i,erg); } return 0;}

int eRek(int zahl){ int i,erg,zahl1,zahl2; if(zahl==3 || zahl==5) // K(zahl) erg=1; else { // K(zahl) bestimmen for (i=1;i<=zahl-1;i++){ zahl1=i; zahl2=zahl-zahl1; if(zahl1!=zahl2){ // sonst erg=eRek(zahl1)*eRek(zahl2); if(erg==1) return 1; } } erg=0; // K(zahl)= } return erg;}

Weiteres Beispiel:Regulärer Ausdruck

Zuerst ein paar Definitionen

Alle folgenden Zeichenketten sollen aus dem Alphabet A = { a , b , c }bestehen. D.h. eine beliebige Zeichenkette darf nur aus diesen 3 Zeichen bestehen.Die Menge aller Zeichenketten, die aus dem Alphabet A hergestellt werden, bezeichnen wir mit X.

Wenn eine Zeichenkette über dem Alphabet A die Länge n hat, schreibt man dafür kurz:| z | = n

Beispiel:| abca | = 4

Beispiele von Zeichenkette über A

und keinen Zeichenketten über A

cabababamit mammaaaaaahhh(a+b)abbaacbacbacbacbcbbacbac

ZK über A

Was sind Zeichenketten über dem Alphabet A, was nicht ?

ZK über A

keine ZK über A

keine ZK über A

keine ZK über A

keine ZK über A

ZK über A

ZK über A

Jetzt zu den regulären Ausdrücken

Für das Alphabet A gilt im Folgenden:

A = {a, b, c}

a* bedeutet die Menge aller Zeichenketten, die aus beliebig vielen a besteht. Das Zeichen * bedeutet Wiederholung.Aus welchen Elementen besteht dann also die Menge X aller Zeichenketten der Form a* ?

X = {a, aa, aaa, aaaa, ...}

a | bbedeutet die Menge aller Zeichenketten, die entweder aus dem Zeichen a oder dem Zeichen b besteht.Das Zeichen | bedeutet oder.Aus welchen Elementen besteht dann also die Menge X aller Zeichenketten der Form a|b ?

X = {a, b}

a* | b*

Aus welchen Elementen besteht dann also die Menge X aller Zeichenketten der Form a* | b* ?

X = {a, aa, aaa, ..., b, bb, bbb, ...}

Dies könnte man mengentheoretisch auch schreiben als ...

X = {a, aa, aaa, ...} {b, bb, bbb, ...}

a (a | b | c)*

Die Klammer bedeutet, daß der Ausdruck in der Klammer zuerst abgearbeitet wird.Aus welchen Elementen besteht dann also die Menge X aller Zeichenketten der Form a (a | b | c)* ?

X = Menge aller Zeichenketten (über A), die mit dem Zeichen a beginnen.

a c* a

Aus welchen Elementen besteht dann also die Menge X aller Zeichenketten der Form a a c* a ?

X = Menge aller Zeichenketten (über A), die mit dem Zeichen a beginnen und enden und dazwischen nur aus beliebig vielen(auch 0) Zeichen c bestehen.Mengentheoretisch geschrieben ...

X = {aa, aca, acca, accca, ...}

Aufgabe:Geben Sie die Regeln an, die die Zeichenketten der

Form a* erstellen.

--- a

{z} ----- wobei zX=Menge aller az Zeichenketten über A

Regel 1, kurz R1

Regel 2, kurz R2

Aufgabe:Geben Sie die MengenD0, D1, D2, D3, ... an.

D0 = D1 = {a}D2 = {a, aa}D3 = {a, aa, aaa}...

Wie kann man rekursiv berechnen, ob eine

Zeichenkette ein regulärer Ausdruck der Form a* ist

oder nicht ?

Schauen wir uns dazu die Formel von vorher an:





Da hier K(x) nur aus einer einelementigen Menge produziert wird, gilt:e(x) = e(x1) {x1}K(x)



Fall: sonste(x) = e(x1) {x1}K(x)

Bei welchen Zeichenketten ist

dies der Fall?

Wenn die Zeichenkette ein Zeichen ist (Länge = 1) und dieses Zeichen a ist. Bei welchen Zeichenketten

ist dies der Fall?

Wenn die Zeichenkette ein Zeichen ist (Länge = 1) und dieses Zeichen a ist.

Was ist z.B. K(aaabc) ?

K(aaabc) = { aabc }d.h. K(aaabc) besteht nur aus einem Element.

Bevor wir die zugehörige Funktion eRek(...) implementieren, machen wir noch ein paar Überlegungen ...


e(x) = e(x1) {x1}K(x)

Man kann den zu x gehörigen Kandidaten K(x) bestimmen und in ein Feld v eintragen.Für K(aaabc) wäre dies z.B:

aabc


e(v)

Dies könnte analog zu den wunderbaren Zahlen implementiert werden.Dann müßte man noch ein Feld erstellen. Wenn man dies nicht will, kann man dies wie folgt machen:

aaabc

aabc

↑ string

Wo beginnt diese Zeichenkette bzgl. der Zeichenkette string ?

begin+1

↑

begin

Man übergibt der Funktion e nicht nur eine Zeichenkette string, sondern auch den Beginn dieser Zeichenkette:Für K(aaabc) wäre dies z.B:e(aaabc,begin)wobei hier begin = 0 wäre.Die Kandidatenmenge K(aaabc) wäre wieder:


eRek(...) die berechnet, ob eine

Zeichenkette ein regulärer Ausdruck der Form a* ist

oder nicht.

#include "stdafx.h"#include <string.h>

int e(char string[], int begin, int end);

int main(){ int erg; char string[] = "aaaaaaaab"; erg=e(string,0,strlen(string)); if(erg==1) printf("ZK ist von der Form a^*\n\n"); else printf("ZK ist nicht von der Forma^*\n\n"); return 1;}

Berechnet Länge einer Zeichenkette

Deswegen muß entsprechende Header-Datei eingefügt werden.

int e(char string[], int begin, int end){ int len; int erg; len = end - begin + 1; if(len==1){ if(string[begin]=='a'){ erg=1; } else{ erg=0; } } else{ if(string[begin]=='a'){ erg=e(string, begin+1, end); return erg; } } return erg;}

Weiteres Beispiel:Terme

Alle folgenden Zeichenketten sollen aus dem Alphabet A = { a , b , ) , ( , + }bestehen. D.h. eine beliebige Zeichenkette darf nur aus diesen 5 Zeichen bestehen.Die Menge aller Zeichenketten, die aus dem Alphabet A hergestellt werden, bezeichnen wir mit X.

Wenn eine Zeichenkette über dem Alphabet A die Länge n hat, schreibt man dafür kurz:| z | = n

Beispiel:| baba | = 4

Beispiele für Zeichenketten über A:aba(b+bb(a)(a+b)++++bbba+++)aa(bbb+++a((a+a)+(b+b))

Unter einem mathematischen Term verstehen wir hier :

1) Einfache Variablen (das sind die Zeichen a und b

2) Zeichenketten der Form: (a+b), ((a+b)+b), ((b+a)+(b+(a+b))), usw.

Bemerkung: a+b ist kein Term

Weitere Bemerkungen: d ist ... kein Terma ist ... ein Term(a+b ist ... kein Terma+b+c ist ... kein Term(a*b) ist ... kein Term((b+b)+(a+a)) ist ... ein Term

Aufgabe:Geben Sie die Regeln (Regelmenge) an, mit denen man Terme induktiv definieren kann.

--- a

--- b

{z; s} ------ wobei zX und sX

(z+s)

Regel 1, kurz R1

Regel 3, kurz R3

Regel 2, kurz R2

Aufgabe:Geben Sie die MengenD0, D1, D2, D3 an.

D0 =

D1 = {a, b}

D2 = { a, b, (a+b), (b+a), (a+a), (b+b) }

D3 = { a, b, (a+b), (b+a), (a+a), (b+b),(a+(a+b)), (a+(b+a)), (a+(a+a)), (a+(b+b)),(b+(a+b)), (b+(b+a)), (b+(a+a)), (b+(b+b)),((a+b)+a), ((a+b)+b), ((a+b)+(a+b)), ((a+b)+(b+a)),((a+b)+(a+a)), ((a+b)+(b+b)),((b+a)+a), ((b+a)+b), ((b+a)+(a+b)), ((b+a)+(b+a)),((b+a)+(a+a)), ((b+a)+(b+b)),((a+a)+a), ((a+a)+b), ((a+a)+(a+b)), ((a+a)+(b+a)),((a+a)+(a+a)), ((a+a)+(b+b)),((b+b)+a), ((b+b)+b), ((b+b)+(a+b)), ((b+b)+(b+a)),((b+b)+(a+a)), ((b+b)+(b+b)) }

Wie kann man rekursiv berechnen, ob eine

Zeichenkette ein Term ist oder nicht ?

Schauen wir uns dazu die Formel von vorher an:

Fall: K(x) = ==> e(x) = 0Fall: K(x) ==>e(x) = 1Fall: sonste(x) = e(x1) * e(x2) {x1,x2}K(x)

wobei K(x) die zu x gehörende Kandidatenmenge ist.z.B: x = (a+b+b)K(x) = ?

x= (a+b+b)K(x) besteht dann aus den folgenden Elementen:{a, b+b} , {a+b,b}Diese bekommt man, indem man …

x= (a+b+b)K(x) besteht dann aus den folgenden Elementen:{a, b+b} , {a+b,b}…an jedem vorkommenden + die linke und rechte (bzgl. des Zeichens + ) Teilzeichenfolge betrachtet (abzüglich der linken Klammer bzw. der rechten Klammer), also:

1. Kandidatenelement von:

x= (a+b+b)

a

b+b

(a abzüglich der linken Klammer ergibt:

b+b) abzüglich der rechten Klammer ergibt:

Teilzeichenkette links des 1. + Zeichens:

Teilzeichenkette rechts des 1. + Zeichens:

also: {a, b+b}

Bestimmen Sie das 2. Kandidatenelement von:x= (a+b+b)

2. Kandidatenelement von:

x= (a+b+b)Teilzeichenkette links des 2. + Zeichens:(a+b abzüglich der linken Klammer ergibt: a+b

Teilzeichenkette rechts des 2. + Zeichens:b) abzüglich der rechten Klammer ergibt: b also: {a+b, b}

Weiteres Beispiel:x= a+b+c)

K(x) = ?

x= a+b+c)K(x) = Denn es gibt keine Regel mit der man x produzieren kann. Regel 2 produziert nämlich links die Klammer ( und rechts die Klammer ) und Regel 1 verlangt, daß x ein Zeichen ist.

Weiteres Beispiel:x ist eine aus mehreren Zeichen bestehende Zeichenkette, die am Anfang keine öffnende Klammer ( oder am Ende keine schließende Klammer ) hat.

K(x) = ?

K(x) = Denn es gibt keine Regel mit der man x produzieren kann. Regel 2 produziert nämlich links die Klammer ( und rechts die Klammer ) und Regel 1 verlangt, daß x ein Zeichen ist.

Weiteres Beispiel:x= ae(x) = ?Warum braucht man hier nicht K(x) zu berechnen?Weil x direkt von der leeren Menge produziert wird, also K(x). Also ist

e(x) = 1

Weitere Beispiele:z2 mit |z2|=2, z3 mit |z3|=3 und z4 mit |z4|=4 seien Zeichenketten über dem Alphabet A (siehe oben) mit den Längen 2, 3, und 4.

K(z2) = ?K(z3) = ?K(z4) = ?

Weitere Beispiele:z2 mit |z2|=2, z3 mit |z3|=3 und z4 mit |z4|=4 sind Zeichenketten über dem Alphabet A (siehe oben) mit den Längen 2, 3, und 4.

K(z2) = K(z3) = K(z4) =

((a+(b+a)+b)

(a , (b+a)+b (a+(b+a) , b (a+(b , a)+b0 0 0

0

10

Wie groß ist jeweils e(…), d.h. welchen Wert haben die roten Blätter ?

e(((a+(b+a)+b))=0*0+0*0+1*0*1

1

0

a , (b+a1 0

=e((a+(b+a))

0

a+(b , a

1*0+0*1

Bevor wir die zugehörige Funktion eRek(...) implementieren, machen wir noch ein paar Überlegungen ...


e(x) = e(x1) * e(x2) {x1,x2}K(x)

Man kann die zu x gehörige Kandidaten K(x) bestimmen und in ein Feld v eintragen.Für K((((a+b)+c)+(a+c))) wäre dies z.B:

((a b)+c)+(a+c) ((a+b) c)+(a+c)


e(v[0])*e(v[1]) + e(v[2])*e(v[3]) + e(v[4])*e(v[5]) + e(v[6])*e(v[7])Dies könnte analog zu den wunderbaren Zahlen implementiert werden.Doch bräuchte man dazu noch ein paar selbstgeschriebene Funktionen, wie z.B. das Splitten (aufteilen) einer Zeichenkette in eine Zeichenkette links von + und rechts von +. Da dies etwas aufwendig ist, machen wir dies wie folgt:

((a+b)+c) (a+c) ((a+b)+c)+(a c)

Feld v geht hier weiter

Man übergibt der Funktion e nicht nur eine Zeichenkette string, sondern auch den Beginn und das Ende dieser Zeichenkette:Für K((((a+b)+c)+(a+c))) wäre dies z.B:e((((a+b)+c)+(a+c)),begin, end)wobei hier begin = 0 und end = 16 wäre.

Die Kandidatenmenge K((((a+b)+c)+(a+c))) wäre wieder:

((a b)+c)+(a+c) ((a+b) c)+(a+c)

((a+b)+c) (a+c) ((a+b)+c)+(a c)

Diese Indizes i1 bis i4 könnte man in einer for-Schleife ermitteln.

↑ ↑ ↑ ↑Index(Stelle) i4

Index(Stelle) i3Index(Stelle) i1

Index(Stelle) i2

Mit i1 bis i4 werden die Indizes der Rechenzeichen bezeichnet.

(((a+b)+c)+(a+c))

((a b)+c)+(a+c) ((a+b) c)+(a+c)

((a+b)+c) (a+c) ((a+b)+c)+(a c)

↑ ↑ ↑ ↑ i1 i2 i3 i4

string

Wo beginnen bzw. enden diese 8 Zeichenketten bzgl. der Zeichenkette

string ?

begin+1, i1-1

↑ ↑begin end

i1+1 , end-1 begin+1, i2-1 i2+1 , end-1

begin+1, i3-1

i3+1 , end-1

begin+1, i4-1 i4+1 , end-1

(((a+b)+c)+(a+c))

((a b)+c)+(a+c) ((a+b) c)+(a+c)

((a+b)+c) (a+c) ((a+b)+c)+(a c)

↑ ↑ ↑ ↑ i1 i2 i3 i4

string

Wo beginnen bzw. enden diese 8 Zeichenketten bzgl. der Zeichenkette

string ?

↑ ↑begin end

Was wird in dieser Funktion nun berechnet (aufgerufen)?

sum = sum + e(string,begin+1,i-1)*e(string,i+1,end-1)

sum am Anfang 0 sein muß und i die Werte zwischen begin und end durchläuft und die Bedingung string[i]== '+' gelten muß.

wobei sum = ... und ...


eRek(…), die berechnet, ob eine Zeichenkette ein Term

ist oder nicht.

int eRek(char string[], int begin, int end){ int i; int len; int erg;

len = end - begin + 1; // K(zahl) if(len==1 && (string[begin]=='a' || string[begin]=='b')){ erg=1; } // gleich geht es weiter

else{ // Zerlegungen versuchen for(i=begin+1; i<end; i++){ if(len<=3) break; else{ if(string[i]=='+' && string[begin]=='(' && string[end]==')'){ // sonst erg= eRek(string, begin+1, i-1) * eRek(string, i+1, end-1); if(erg==1){ return 1; } } } } erg=0; // K(zahl)=

} return erg;}

Documents

REKURSION + ITERATION