Übungen zu Rekursive Funktionen über Felder, Rekursive Funktionen über verkettete Listen und Teile-und-Hersche-Verfahren.
Programmiertechnik 2 – Aufgabe 4
Lösung:
Rekursive Funktionen über Felder
main.cpp:
// main.cpp
//
// Andreas Giemza, FH KN
// 2.05.2010
#include <iostream>
#include <stdlib.h>
using namespace std;
// Prototypen
bool isElement(int x, int a[], int n);
bool isSubset(int a[], int n, int b[], int m);
int main()
{
// Testfelder
int a[10] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int b[5] = // Teilmenge von a
{
1, 3, 5, 7, 9
};
int c[5] = // Schnittmenge mit a
{
1, 3, 5, 6, 8
};
int d[5] = // Keine Elemente mit a
{
2, 4, 6, 8, 10
};
// Gebe Variabeln aus
cout << "a[10] = {";
for (int i = 0; i < 10; i++)
{
if (i != 0) cout << ", ";
cout << a[i];
}
cout << "}nb[5] = {";
for (int i = 0; i < 5; i++)
{
if (i != 0) cout << ", ";
cout << b[i];
}
cout << "} // Teilmenge von anc[5] = {";
for (int i = 0; i < 5; i++)
{
if (i != 0) cout << ", ";
cout << c[i];
}
cout << "} // Schnittmenge mit and[5] = {";
for (int i = 0; i < 5; i++)
{
if (i != 0) cout << ", ";
cout << d[i];
}
cout << "} // Keine Elemente mit an";
// Teste
cout << "b ist Teilmenge von a: " << isSubset(a, 10, b, 5) << " (1 = wahr)n";
cout << "c ist Teilmenge von a: " << isSubset(a, 10, c, 5) << " (0 = falsch)n";
cout << "d ist Teilmenge von a: " << isSubset(a, 10, d, 5) << 'n';
}
bool isElement(int x, int a[], int n)
{
// cout << "x: " << x << " a[" << n-1 << "]: " << a[n-1] << 'n';
// Gibt true aus wenn der momentane n Wert (-1 da array) gleich dem x Wert ist
if (x == a[n-1])
return true;
// Wenn es bis n = 1 (im array 0) nicht geklappt hat false ausgeben
else if (n == 1)
return false;
// Ansonsten Funktion neustarten mit n - 1
else
return isElement(x, a, n-1);
}
bool isSubset(int a[], int n, int b[], int m)
{
// cout << "b[" << m-1 << "]: " << b[m-1] << 'n';
// Schauen ob das m-te Element von b in a ist, wenn nicht gibt nen false
if (!isElement(b[m-1], a, n))
return false;
// Wenn er am ende ist war alles da
else if (m == 1)
return true;
// Zum nächsten Elementt gehen in b
else
return isSubset(a, n, b, m-1);
}
makefile:
# Author: Andreas Giemza # Date: 12.09.2007 CC = g++ -g OBJ = main.o BIN = aufg4a $(BIN): $(OBJ) $(CC) -o $(BIN) $(OBJ) main.o: main.cpp $(CC) -c main.cpp
Rekursive Funktionen über verkettete Listen
main.cpp:
// main.cpp
//
// Andreas Giemza, FH KN
// 16.04.2010
#include <iostream>
#include "set.h"
using namespace std;
int main()
{
Set<int> s;
s.insert(1);
s.insert(2);
s.insert(4);
s.insert(5);
s.insert(6);
s.insert(6);
s.insert(6);
s.insert(5);
s.insert(4);
s.insert(3);
s.insert(2);
s.insert(1);
s.print();
}
set.h:
// set.h
//
// Andreas Giemza, FH KN
// 16.04.2010
#ifndef SET_H
#define SET_H
using namespace std;
template <class T>
class Set
{
public:
Set()
{
// Leere Liste erstellen
head = 0;
}
~Set()
{
// Geht die Liste solange durch bis wir am Ende angekommen sind
while (head != 0)
{
Element* q = head;
head = head->next;
delete q;
}
}
void insert(T x)
{
/*if (head == 0)
{
Node* q = new Node;
q->content = x;
q->next = 0;
head = q;
}
else if (head->content > x)
{
if (head->content != x)
{
Node* q = new Node;
q->content = x;
q->next = head;
head = q;
}
}
else
{
Node* p = head;
while (p->next != 0 && x >= p->next->content)
p = p->next;
if (p->content != x)
{
Node* q = new Node;
q->content = x;
q->next = p->next;
p->next = q;
}
}*/
// rufe die Rekursive auf mit head als Startzeiger
insertR(head, x);
}
void print()
{
/*cout << "Normal:n";
if (head != 0 && head->next != 0)
{
cout << head->content;
Node* p = head->next;
while (p != 0)
{
cout << ", " << p->content;
p = p->next;
}
}
else if (head != 0 && head->next == 0)
cout << head->content;
cout << 'n';
cout << "Rekursiv:n";*/
// rufe die Rekursive auf mit head als Startzeiger
printR(head);
}
private:
struct Node
{
Node* next;
T content;
};
Node* head;
void printR(Node* p)
{
if (p != 0)
{
cout << p-> content;
if (p->next != 0)
cout << ", ";
// rufe die Funktion wieder auf mit zeiger auf das nächste Element
return printR(p->next);
}
cout << 'n';
}
void insertR(Node*& p, T x)
{
// Sonderfall für eine leere Liste oder Ende
if (p == 0)
{
Node* q = new Node;
q->content = x;
q->next = 0;
p = q;
}
// Wenn es nach den aktuellen Wert eingefügt wird
else if (p->content > x)
{
Node* q = new Node;
q->content = x;
q->next = p;
p = q;
}
else
// Wenn der Wert noch nicht vorhanden ist gehe zum nächsten
if (p->content != x)
insertR(p->next, x);
}
};
#endif
makefile:
# Author: Andreas Giemza # Date: 12.09.2007 CC = g++ -g OBJ = main.o BIN = aufg4b $(BIN): $(OBJ) $(CC) -o $(BIN) $(OBJ) main.o: main.cpp set.h $(CC) -c main.cpp
Teile-und-Hersche-Verfahren
main.cpp:
// main.cpp
//
// Andreas Giemza, FH KN
// 2.05.2010
#include <iostream>
#include <stdlib.h>
using namespace std;
// Prototypen
bool f(int a[], int li, int re);
int main()
{
// Mein Array
int a[5] = {1, 2, 3, 4, 5};
// Hübche Tabelle
cout << "Aufruft|Tiefett|Werten";
// HuT Funktion aufrufen
f(a, 0, sizeof(a)/sizeof(int)-1);
}
bool f(int a[], int li, int re)
{
// Für die Rekursionstiefe
static int d = -1;
d++;
// Für die Aufrufanzahl
static int e = 1;
// Hübche ausgabe
cout << "--------|---------------|----------n";
cout << e << "t|";
for (int i = 0; i < d; i++)
cout << "==";
cout << "tt|f(a, "<< li << ", " << re <<")" << 'n';
e++;
if (li >= re)
{
d--;
return true;
}
else
{
int m = (li+re)/2;
bool b = a[m] < a[m+1] && f(a,li,m) && f(a,m+1,re);
d--;
return b;
}
}
makefile:
# Author: Andreas Giemza # Date: 12.09.2007 CC = g++ -g OBJ = main.o BIN = aufg4c $(BIN): $(OBJ) $(CC) -o $(BIN) $(OBJ) main.o: main.cpp $(CC) -c main.cpp