Jetzt soll ich noch das mit dem berechnen machen. Ich hab da mal was geschrieben, jedoch blicke ich da noch nicht richtig durch, wie ich das realisieren soll, dass der überübernächste kontrolliert werden soll.
Da sind wir ja schon zwei.
Ich dachte da an eine geschachtelte for in for Schleife aber dann ist es doch nicht mehr rekursiv oder ?
Naja - auch mit 2 Schleifen kann sich eine Funktion noch selbst aufrufen...
Da ich dir nicht die Arbeit abnehmen will, aber dennoch einen guten Rat geben kann, habe ich mal ein Beispiel in C++ implementiert. Das ist ähnlich genug, um den Algorithmus zu zeigen, aber weit genug entfernt, dass man nicht mit "1 zu 1" umschreiben davonkommt. Am besten lässt du das Beispiel durch einen C++ Compiler, um die Resultate zu sehen:
C++:
#include <iostream>
#include <time.h>
#include <vector>
#include <string>
constexpr size_t blockcount = 10;
struct Stein {
Stein(int a, int b)
: v1(a), v2(b) {
}
std::string format(bool normal = true) const {
auto a = normal ? v1 : v2;
auto b = normal ? v2 : v1;
return "(" + std::to_string(a) + "|" + std::to_string(b) + ")";
}
std::string format(int expect) const {
return format(expect == v1);
}
int v1;
int v2;
};
std::vector<int> berechne(std::vector<int> used, const std::vector<Stein>& all, int i, int orientation)
{
// Copy the existing path as a reference return value
decltype(used) maxpath = used;
// Check all bricks
for (size_t j = 0; j < all.size(); ++j)
{
// Check if the current brick being checked is not already used
bool not_this = false;
for (size_t f = 0; f < used.size(); ++f) {
if (used[f] == j) {
not_this = true;
continue;
}
}
if (not_this) continue; // Skip if already used
// Copy the orientation
decltype(orientation) new_orientation = orientation;
// If not the first block
if (i != -1)
{
// Set the orientations of the next blocks
if (orientation == 1 || orientation == 0) {
// "Normal"
if (all[i].v2 == all[j].v1) {
// orientation stays the same
new_orientation = 1;
}
else if (all[i].v2 == all[j].v2) {
// swap
new_orientation = -1;
}
else continue;
}
else if (orientation == -1 || orientation == 0) {
// Inverted
if (all[i].v1 == all[j].v1) {
// swap
new_orientation = 1;
}
else if (all[i].v1 == all[j].v2) {
// still -1
new_orientation = -1;
}
else continue;
}
else {
// No match in any orientation, continue
continue;
}
}
// Copy the current state
auto cpy = used;
// Add the selected value to the copied state
cpy.push_back(j); // Add to list
// Recurse
auto r = berechne(cpy, all, j, new_orientation);
// Assign the maxpath if the path was deeper (As this is DFS)
if (maxpath.size() < r.size())
maxpath = r;
}
// Return the found path
return maxpath;
}
int main(int argc, char* argv[])
{
// Randomize and fill
srand(time(NULL));
auto rf = []() { return (rand() % 10) + 1; };
std::vector<Stein> steine;
for (size_t i = 0; i < blockcount; ++i) {
steine.push_back(Stein(rf(), rf()));
}
// Start by setting any start block (-1) and a fixed orientation
std::vector<int> used;
auto ret = berechne(used, steine, -1, 1);
// Dump info for all bricks
std::cout << "All bricks: " << std::endl;
for (const auto& x : steine) {
std::cout << x.format() << " => ";
}
// Dump info about the sorting
std::cout << std::endl << "Sorted bricks: " << std::endl;
int lastval = -1;
for (const auto& x : ret) {
if (lastval == -1) {
// We know that we started with orientation = 1
lastval = steine[x].v2;
std::cout << steine[x].format(true) << " => ";
}
else {
std::cout << steine[x].format(lastval) << " => ";
lastval = steine[x].v1 == lastval ? steine[x].v2 : steine[x].v1;
}
}
std::cout << "\n (missing " << steine.size() - ret.size() << " brick(s))" << std::endl;
return 0;
}
Kurze Theorie dazu: Das ist ein DFS (depth first search) basierter Ansatz, der sehr teuer ist, was Stack / Speicher angeht, aber einfach zu verstehen.
Im Prinzip wird in jeder Tiefe geschaut, welche Steine passen. Für jeden der passenden Steine wird das Problem verkleinert (minus den Stein, der gerade genommen wurde) und wieder gelöst.
Ich habe keine Ahnung, wie es mit nur den 2 Parametern i und j gehen soll, und es macht auch keinen Sinn, Rekursion und Iteration (mit Speicher ausserhalb) zu mischen.
Dieser Code findet immer einen Optimalen Pfad. Als Übung kannst du den Beweis dazu schreiben
Vielleicht hilft das ja als Ansatz.
Tipps für C++ => C:
1) push_back fügt ein Element ans Ende des Arrays an. In C macht man das normalerweise, indem man einen genügend grossen Array reserviert und eine Iterationsvariable hat, an deren Position eingefügt wird, und dann wird diese Variable um 1 erhöht. Es gibt hier aber auch elegantere Methoden (da ohnehin kopiert wird) mit memcpy.
2) decltype übernimmt den Typ einer Variable.
3) auto übernimmt den Typ der zugewiesenen Variable
4) In diesem Beispiel werden die Vektoren by value übergeben. C-Arrays müssen zuerst kopiert werden!
5) std::cout kann man mit printf() ersetzen, std::string mit const char*. Aber: Scopes im Auge behalten! (Compilerwarnungen lesen, -Wall -Wextra)
6) Stein ist ein Struct mit einem Konstruktor. Die Memberfunktionen kannst du ebenfalls schnell umschreiben.
Gruss
cwriter
