Im Rahmen des ersten Praktikums implementieren wir die Funktionen rank, unrank und successor für Gray-Code und entwickeln eine verallgemeinerte Form des Gray-Codes.
| Skript-Anfang | Praktikum 1 – Seite 1 |
|---|---|
| Skript-Ende | Praktikum 1 – Seite 2 |
Algorithmen für den Gray-Code
Entwickeln und beschreiben Sie Algorithmen zur Realisierung rank, unrank und successor für Gray-Code \( \Delta_n\), definiert durch:
\( \ \Delta_1 := 0,1 \ \Delta_n := \Delta^R_{n-1}0,\Delta_{n-1}1, n > 1 \)
Nutzen Sie dabei die rekursive Struktur aus. Implementieren Sie die Algorithmen in einer Programmierspache Ihrer Wahl.
Konsolenausgabe des folgenden Quellcodes
rank("000") => 2
rank("001") => 5
rank("010") => 1
rank("011") => 6
rank("100") => 3
rank("101") => 4
rank("110") => 0
rank("111") => 7
unrank(0,3) => 110
unrank(1,3) => 010
unrank(2,3) => 000
unrank(3,3) => 100
unrank(4,3) => 101
unrank(5,3) => 001
unrank(6,3) => 011
unrank(7,3) => 111
succ("110") => 010
succ("010") => 000
succ("000") => 100
succ("100") => 101
succ("101") => 001
succ("001") => 011
succ("011") => 111
succ("111") => 110Includes und Deklarationen
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <math.h>
using std::cout;
using std::endl;
using std::vector;
using std::string;
int rank(string val);
string unrank(unsigned int i, unsigned int n);
string succ(string val);
vector<string> create_GrayCode2(int n, string q);
template<typename T> string toString(T Val);
unsigned int eval(string val);
char cFlip(char c);
vector<string> reverse(vector<string> v);Main()
int main() {
cout << "rank(\"000\") => " << rank("000") << endl;
cout << "rank(\"001\") => " << rank("001") << endl;
cout << "rank(\"010\") => " << rank("010") << endl;
cout << "rank(\"011\") => " << rank("011") << endl;
cout << "rank(\"100\") => " << rank("100") << endl;
cout << "rank(\"101\") => " << rank("101") << endl;
cout << "rank(\"110\") => " << rank("110") << endl;
cout << "rank(\"111\") => " << rank("111") << endl;
cout << endl;
cout << "unrank(0,3) => " << unrank(0, 3) << endl;
cout << "unrank(1,3) => " << unrank(1, 3) << endl;
cout << "unrank(2,3) => " << unrank(2, 3) << endl;
cout << "unrank(3,3) => " << unrank(3, 3) << endl;
cout << "unrank(4,3) => " << unrank(4, 3) << endl;
cout << "unrank(5,3) => " << unrank(5, 3) << endl;
cout << "unrank(6,3) => " << unrank(6, 3) << endl;
cout << "unrank(7,3) => " << unrank(7, 3) << endl;
cout << endl;
cout << "succ(\"110\") => " << succ("110") << endl;
cout << "succ(\"010\") => " << succ("010") << endl;
cout << "succ(\"000\") => " << succ("000") << endl;
cout << "succ(\"100\") => " << succ("100") << endl;
cout << "succ(\"101\") => " << succ("101") << endl;
cout << "succ(\"001\") => " << succ("001") << endl;
cout << "succ(\"011\") => " << succ("011") << endl;
cout << "succ(\"111\") => " << succ("111") << endl;
cout << endl;
return 0;
} // mainRank
int rank(string val) {
/* Rank-Algorithmus fuer den Gray-Code */
int r = 0;
// Abbruchbedingung
if (val.length() == 1) {
//cout << "Abbruchbedingung erfuellt!" << endl;
if (val[val.length() - 1] == '1')
return 1;
else
return 0;
}
if (val[val.length() - 1] == '0') {
// letztes Zeichen entfernen
string tmp = val.substr(0, val.size() - 1);
// neues letztes Zeichen drehen
if (tmp[tmp.length() - 1] == '0')
tmp[tmp.length() - 1] = '1';
else
tmp[tmp.length() - 1] = '0';
//cout << "Rekursion: rank(" << tmp << ")" << endl;
return r + rank(tmp);
} else {
// letztes Zeichen ist eine 1
return r + pow(2, val.size()) / 2 + rank(val.substr(0, val.size() - 1));
}
} // rankUnrank
string unrank(unsigned int i, unsigned int n) {
/* Unrank-Algorithmus fuer den Gray-Code */
string s = "";
// Abbruchbedingung
if (i >= pow(2, n))
return "Keine Berechnung moeglich.";
if (n == 0)
return "";
// Wenn i < Anzahl aller Teilmengen / 2 (2**n / 2)
// 1. i befindet sich in der gespiegelten Haelfte
// 2. Das letzte Zeichen ist eine "0"
if (i < pow(2, n) / 2) {
// Bestimme naechste Stelle
s = unrank(i, n - 1);
// Da wir uns in der gespiegelten Haelfte befinden
// -> drehe das Bit der naechsten Stelle (also vor der "0") um
s[s.size() - 1] = cFlip(s[s.size() - 1]);
return s + "0";
} else {
// Wenn i >= Anzahl aller Teilmengen / 2 (2**n / 2)
// 1. i befindet sich in der nicht gespiegelten Haelfte
// 2. Das letzte Zeichen ist eine "1"
// -> Subtrahiere den Offset (2** n / 2( von i und bestimme naechste Stelle
return unrank(i - (pow(2, n) / 2), n - 1) + "1";
}
} // unrankSuccessor
string succ(string val) {
/* Successor-Implementierung fuer den Gray-Code */
if (eval(val) % 2 == 1) { // Anzahl 0 ungerade
//cout << "Anzahl ungerade" << endl;
val[0] = cFlip(val[0]);
} else { // Anzahl 0 gerade
// Finde erste 0 von links
// oder letzte von rechts
std::size_t found = val.find_first_of("0");
if (found != std::string::npos)
val[found + 1] = cFlip(val[found + 1]);
else
val[val.size() - 1] = cFlip(val.size() - 1);
}
return val;
} // succHilfsfunktionen
template<typename T>
string toString(T Val) {
std::stringstream ss;
ss << Val;
return ss.str();
}
unsigned int eval(string val) {
/* Hilfsfunktion Bestimmung der Anzahl aller Nullen eines Zeichenkette */
// Abbruchbedingung
if (val.size() == 0)
return 0;
if (val[val.size() - 1] == '0')
return eval(val.substr(0, val.size() - 1)) + 1;
else
return eval(val.substr(0, val.size() - 1)) + 0;
} // eval
char cFlip(char c) {
/* Hilfsfunktion: Invertierung eines 'Bits' */
if (c == '0')
return '1';
else
return '0';
} // cFlip
vector<string> reverse(vector<string> v) {
/* Hilfsfunktion: Invertierung von Vektoren */
vector<string> vTmp;
for (unsigned int i = 0; i < v.size(); i++)
vTmp.insert(vTmp.begin(), v[i]);
return vTmp;
} // reverseVerallgemeinerung des Gray-Codes
Entwickeln und implementieren Sie einen Algorithmus zum Erzeugen aller Vektoren der Länge n mit Vektoreinträgen aus {0, 1,…, q – 1}, wobei sich zwei aufeinanderfolgende Vektoren an exakt einer Stelle unterscheiden sollen. Für q = 2 entspricht dies einem Gray-Code. Gehen Sie rekursiv wie für den Fall q = 2 vor.
Konsolenausgabe des folgenden Quellcodes
create_GrayCode2(n=3 q='01') => 110 010 000 100 101 001 011 111
create_GrayCode2(n=3 q='012') => 020 120 220 210 110 010 000 100 200 201 101 001 011 111 211 221 121 021 022 122 222 212 112 012 002 102 202
create_GrayCode2(n=4 q='012') => 2020 1020 0020 0120 1120 2120 2220 1220 0220 0210 1210 2210 2110 1110 0110 0010 1010 2010 2000 1000 0000 0100 1100 2100 2200 1200 0200 0201 1201 2201 2101 1101 0101 0001 1001 2001 2011 1011 0011 0111 1111 2111 2211 1211 0211 0221 1221 2221 2121 1121 0121 0021 1021 2021 2022 1022 0022 0122 1122 2122 2222 1222 0222 0212 1212 2212 2112 1112 0112 0012 1012 2012 2002 1002 0002 0102 1102 2102 2202 1202 0202
create_GrayCode2(n=3 q='AB') => BBA ABA AAA BAA BAB AAB ABB BBB Main()
int main() {
vector<string> vOut;
vOut = create_GrayCode2(3, "01");
cout << "create_GrayCode2(n=3 q='01') => ";
for (unsigned int i = 0; i < vOut.size(); i++) {
cout << vOut.at(i) << " ";
}
cout << endl << endl;
vOut = create_GrayCode2(3, "012");
cout << "create_GrayCode2(n=3 q='012') => ";
for (unsigned int i = 0; i < vOut.size(); i++) {
cout << vOut.at(i) << " ";
}
cout << endl << endl;
vOut = create_GrayCode2(4, "012");
cout << "create_GrayCode2(n=4 q='012') => ";
for (unsigned int i = 0; i < vOut.size(); i++) {
cout << vOut.at(i) << " ";
}
cout << endl << endl;
vOut = create_GrayCode2(3, "AB");
cout << "create_GrayCode2(n=3 q='AB') => ";
for (unsigned int i = 0; i < vOut.size(); i++) {
cout << vOut.at(i) << " ";
}
cout << endl << endl;
return 0;
} // mainGray-Code
vector<string> create_GrayCode2(int n, string q) {
/* Verallgemeinerung des Gray-Code Algorithmus
* -> q kann beliebige Zeichen enthalten
*/
vector<string> v;
// Abbruchbedingung
if (n == 0) { // Leere Menge
v.push_back("");
return v;
}
if (n == 1) { // Minimum
for (unsigned int i = 0; i < q.size(); i++)
v.push_back(toString(q.at(i)));
return v;
}
// Rekursion: Erzeuge "unteren" Vektor (n - 1)
// -> Hinweis: Rekursion endet bei n=1!
// -> Fuer q = 3 waere vNew = {0, 1, 2}
vector<string> vNew = create_GrayCode2(n - 1, q);
// Baue Vektor n fuer jedes Zeichen in q zusammen
for (unsigned int i = 0; i < q.size(); i++) {
vector<string> vTmp;
// Gray-Algorithmus beginnt immer mit invertiertem Vektor
// -> Der dritte, fuenfte etc. Vektor muss wieder invertiert sein (q=2,4,...)
// -> Alle restlos durch zwei teilbaren 'Positionen' sind zu invertieren!
if (i % 2 == 0)
vTmp = reverse(vNew);
else
vTmp = vNew;
// Zeichen anhaengen
for (unsigned int j = 0; j < vTmp.size(); j++)
vTmp.at(j) = vTmp.at(j) + toString(q.at(i));
// In den Hauptvektor kopieren
v.insert(v.end(), vTmp.begin(), vTmp.end());
}
// Vektor fuer das aktuelle n zurueckgeben
return v;
} // create_GrayCode2