Besten Weg durch Pyramide finden
-
Der Kurs muss ja richtig gut sein, wenn man da goto lernt ...
-
Ich habe mal gelesen, dass goto nicht so schlimm ist, wie alle sagen, wenn man damit aus einer verschachtelten Schleife herausgeht. War nicht bei SoloLearn, aber der Kurs dort ist wirklich nicht gut, ich mach ihn gar nicht. Ich lese Bücher und die Referenz und manchmal Web-Einträge von schlauen Menschen.
(it - 1) hat bei mir einen Kompilierfehler ausgelöst von wegen bidirektionale Iteratoren unterstützen kein Minus. Minus ist hier auch nicht aufgeführt:
http://www.cplusplus.com/reference/iterator/BidirectionalIterator/
Wenn Herr Stroustrup meint, Minus wäre grundsätzlich zu teuer, um implementiert zu werden, kann ich da nichts für.
Bei Random-Access ist die big O-Notation fürs Löschen viel höher.
Also, wie sollte ich irgendeine Zeile anders schreiben? Ich ärger mich da ja selber drüber. Eine Klasse, die von list erbt mit einer Klasse, die von list::iterator erbt mit Minus-Operation würde es ja auch komplizierter machen.
-
Hab ne Idee:
template <typename Bi_It> Bi_It mns1(Bi_It it) { // returns it - 1 Bi_It returnme = ++it; --it; return returnme; }
-
Ich habe mal gelesen,
Man kann auch lesen, dass die Erde flach ist.
dass goto nicht so schlimm ist, wie alle sagen, wenn man damit aus einer verschachtelten Schleife herausgeht
Das heißt aber nicht, dass Anfänger damit rumspielen sollten.
-
Irgendeiner Lektüre muss man ja vertrauen, wenn man sich selber noch kein genaues Bild machen kann. Das goto-Statement war ja auch gar nicht der Fehler, auch, wenn es unnötig war und ich es tatsächlich nicht hätte machen sollen.
-
Stimmt, -1 und +1 gehen nicht bei Bidi-Iteratoren. Aber
std::next
undstd::prev
funktionieren. Ich nutze nur praktisch niestd::list
.Hier mal eine schnelle Lösung basierend auf deinem Code. Ich habe 2 Varianten gebaut. Die eine ermittelt wirklich nur das Maximum, aber nicht den Weg. Die zweite speichert auch alle Wege und macht eine Tiefensuche.
#include <algorithm> #include <iostream> #include <sstream> #include <vector> using namespace std; struct path { int value; vector<int> data; void print(ostream &os, const vector<vector<int>> &pyramid) const; }; void path::print(ostream& os, const vector<vector<int> >& pyramid) const { os << value << ": "; for (size_t idx = 0; idx < data.size(); ++idx) { os << pyramid[idx][data[idx]] << " -> "; } os << "end."; } vector<vector<int>> read_pyramid(istream &is) { vector<vector<int>> result; while (1) { vector<int> line; for (size_t i = 0; i <= result.size(); ++i) { int n; if (is >> n) line.push_back(n); } if (!is) { if (!line.empty()) cout << "unvollständige letzte Zeile ignoriert\n"; break; } result.push_back(move(line)); } cout << "Pyramid contains " << result.size() << " lines.\n"; return result; } void dfs_internal(const vector<vector<int>> pyramid, path &p, vector<path> &best_paths) { if (p.data.size() < pyramid.size()) { int left = p.data.empty() ? 0 : p.data.back(); auto line = p.data.size(); p.data.push_back(left); p.value += pyramid[line][left]; dfs_internal(pyramid, p, best_paths); ++p.data.back(); p.value += pyramid[line][left + 1] - pyramid[line][left]; dfs_internal(pyramid, p, best_paths); p.value -= pyramid[line][left + 1]; p.data.pop_back(); } else if (best_paths.empty() || p.value >= best_paths.front().value) { if (!best_paths.empty() && p.value > best_paths.front().value) { best_paths.clear(); } best_paths.push_back(p); } } vector<path> dfs(const vector<vector<int>> &pyramid) { vector<path> best_paths; if (!pyramid.empty()) { path p = {pyramid[0][0], {0}}; dfs_internal(pyramid, p, best_paths); } return best_paths; } int max_path_value(vector<vector<int>> pyramid) { // call by value, d.h. wir können pyramid modifizieren. if (pyramid.empty()) return 0; for (size_t line = 1; line < pyramid.size(); ++line) { pyramid[line].front() += pyramid[line - 1].front(); for (size_t col = 1; col < pyramid[line].size() - 1; ++col) { pyramid[line][col] += max(pyramid[line - 1][col - 1], pyramid[line - 1][col]); } pyramid[line].back() += pyramid[line - 1].back(); } auto &last_line = pyramid.back(); return *max_element(last_line.begin(), last_line.end()); } int main() { stringstream testinput( " 1 " " 1 3 " " 3 9 2 " " 9 1 1 1 " ); stringstream testinput2( " 7 " " 3 8 " " 8 1 0 " " 2 7 4 4 " " 4 5 2 6 5 " ); auto pyramid = read_pyramid(testinput); // alternativ einfach read_pyramid(cin); machen, um Eingabe von stdin zu lesen cout << "max_path_value = " << max_path_value(pyramid) << '\n'; auto best_paths = dfs(pyramid); for (const auto &path : best_paths) { path.print(cout, pyramid); cout << '\n'; } }
Beide Lösungen können noch optimiert werden.
Bei max_path_value braucht man eigentlich nicht alles zu kopieren, bei der Tiefensuche kann man z.B. die hohen Zahlen zuerst nehmen, um dann schlechtere Äste früher abzuschneiden. Wie auch immer, so funktioniert es jedenfalls
-
Erstmal vielen Dank, dass du dir die Zeit genommen hast, den Code vollständig zu überarbeiten.
Ich hab ne Frage: In Zeile 37 geht line ja eigentlich out of scope. Verlängert move() die Lebenszeit oder müsste line static sein?
Und bei vector<vector<int>> wird >> ohne Leerzeichen glaube ich als Operator gelesen, kann mich aber auch täuschen.
Zumindest wird in "Accelerated C++" gesagt, man soll vector< vector<int> > schreiben, das Buch ist aber von 2000.
-
Timon Paßlick schrieb:
Ich hab ne Frage: In Zeile 37 geht line ja eigentlich out of scope. Verlängert move() die Lebenszeit oder müsste line static sein?
line geht in Zeile 38 (eine nach 37) out of scope, nämlich mit der
}
. Move verlängert keine Lebenszeit und da muss auch nichts static sein.Ich möchte mit dem move nur eine Kopie des Line-Vectors sparen. Nach dem
move(line)
darf ich mit dem line-Objekt praktisch außer löschen (und neu zuweisen) nichts mehr machen. Und in Zeile 38 wird gelöscht. Also alles gut.
-
Das heißt, dein vector hat Elemente, die out of scope sind, das macht aber nichts?
-
Timon Paßlick schrieb:
Das heißt, dein vector hat Elemente, die out of scope sind, das macht aber nichts?
Hä? Verstehe die Frage nicht.
-
Hat sich erledigt, habe die Referenz zu move() durchgelesen.
War tatsächlich alles in Ordnung.
-
Habe max_path_value() ein wenig optimiert:
int max_path_value(vector< vector<int> > pyramid) { // call by value to modify pyramid for (size_t line = pyramid.size() - 2; line <= pyramid.size() - 1; --line) for (size_t col = 0; col != pyramid[line].size(); ++col) pyramid[line][col] += max(pyramid[line + 1][col], pyramid[line + 1][col + 1]); return pyramid[0][0]; }
Ich geh einfach von unten nach oben und spar damit Rechenaufwand. Cool, oder?
-
Habe jetzt den SoloLearn Eintrag geändert und euch Credits gegeben:
https://code.sololearn.com/cllzC9Lc4Evg/?ref=app#cpp
-
So ein Müll, jetzt hab ich wieder ne Speicherzugriffsverletzung:
/* Challenge: 'The Golden Mountain' At one international Olympiad in Informatics, the following task was given. Let's solve it! 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 The figure shows an example of a triangle of numbers. Write a program that calculates the largest sum of numbers through which the path starts, starting at the top and ending somewhere on the bottom. Each step can go diagonally down to the right or diagonally to the left. In the example - this is the path 7 -> 3 -> 8 -> 7 -> 5, given a max amount of 30. */ /* This code was created together with some friendly people of the German C++ forum (particularly a user called wob): https://www.c-plusplus.net/forum/345800-full */ #include <algorithm> #include <iostream> #include <sstream> #include <vector> using namespace std; struct path { int value; vector<int> data; void print(ostream &os, const vector< vector<int> > &pyramid) const { os << value << ": "; for (int i = data.size() - 1; i > 0; ++i) os << pyramid[i][data[i]] << " -> "; os << pyramid[0][data[0]] << endl; /* os << value << ": "; const auto last_elem_idx = data.size() - 1; for (int i = 0; i < last_elem_idx; ++i) os << pyramid[i][data[i]] << " -> "; os << pyramid[last_elem_idx][data[last_elem_idx]] << endl; */ } }; vector< vector<int> > read_pyramid(istream &is) { vector< vector<int> > result; while (true) { vector<int> line; for (int i = 0; i <= result.size(); ++i) { int n; if (!(is >> n)) { if (!line.empty()) cout << "The last line is not complete and therefore ignored." << endl; return result; } line.push_back(n); } result.push_back(move(line)); } } void dfs_internal(const vector< vector<int> > pyramid, path &p, vector<path> &best_paths) { if (p.data.size() < pyramid.size()) { int left = p.data.empty() ? 0 : p.data.back(); auto line = p.data.size(); p.data.push_back(left); p.value += pyramid[line][left]; dfs_internal(pyramid, p, best_paths); ++p.data.back(); p.value += pyramid[line][left + 1] - pyramid[line][left]; dfs_internal(pyramid, p, best_paths); p.value -= pyramid[line][left + 1]; p.data.pop_back(); } else if (best_paths.empty() || p.value == best_paths.front().value) best_paths.push_back(p); else if (p.value > best_paths.front().value) { best_paths.clear(); best_paths.push_back(p); } } vector<path> dfs(const vector< vector<int> > &pyramid) { vector<path> best_paths; if (!pyramid.empty()) { path p = { pyramid[0][0],{ 0 } }; dfs_internal(pyramid, p, best_paths); } return best_paths; } path best_path(const vector< vector<int> > &pyramid) { vector<path> good; for (int i = 0; i != pyramid.back().size(); ++i) good.push_back(path{ pyramid.back()[i],{ i } }); for (int line = pyramid.size() - 2; line >= 0; --line) { vector<path> newgood; for (int col = 0; col != pyramid[line].size(); ++col) { auto right_path = (good[col].value > good[col + 1].value) ? good[col] : good[col + 1]; right_path.value += pyramid[line][col]; right_path.data.push_back(col); newgood.push_back(right_path); } good = newgood; } return good[0]; } int max_path_value(vector< vector<int> > pyramid) { // call by value to modify pyramid for (int line = pyramid.size() - 2; line >= 0; --line) for (int col = 0; col != pyramid[line].size(); ++col) pyramid[line][col] += max(pyramid[line + 1][col], pyramid[line + 1][col + 1]); return pyramid[0][0]; } int main() { stringstream testinput( " 1 " " 1 3 " " 3 9 2 " " 9 1 1 1 " ); stringstream testinput2( " 7 " " 3 8 " " 8 1 0 " " 2 7 4 4 " " 4 5 2 6 5 " ); auto pyramid = read_pyramid(testinput); // change to "read_pyramid(cin)" for custom input cout << "max_path_value = " << max_path_value(pyramid) << '\n'; auto best = best_path(pyramid); best.print(cout, pyramid); /*auto best_paths = dfs(pyramid); for (const auto &path : best_paths) path.print(cout, pyramid);*/ }
-
Stimmt, von unten nach oben ist es deutlich kürzer, aber praktisch nicht schneller.
Um schneller zu werden, muss man die Kopie vermeiden. Zum Beispiel so:
int max_path_value_no_copy(const vector<vector<int>> &pyramid) { vector<int> workline(pyramid.back()); for (size_t line = pyramid.size() - 2; line != (size_t) -1; --line) for (size_t col = 0; col != pyramid[line].size(); ++col) workline[col] = pyramid[line][col] + max(workline[col], workline[col + 1]); return workline[0]; }
Ich habe es mal gebenchmarkt:
----------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------- BM_MPV/8 581 ns 581 ns 1223745 BM_MPV/64 5938 ns 5937 ns 117898 BM_MPV/512 221748 ns 221722 ns 3200 BM_MPV/1024 1135833 ns 1135691 ns 617 BM_MPV2/8 552 ns 552 ns 1273185 BM_MPV2/64 5911 ns 5910 ns 119182 BM_MPV2/512 220894 ns 220866 ns 3180 BM_MPV2/1024 1201114 ns 1200935 ns 582 BM_MPV_NO_COPY/8 90 ns 90 ns 7887087 BM_MPV_NO_COPY/64 1224 ns 1224 ns 582609 BM_MPV_NO_COPY/512 54624 ns 54618 ns 12835 BM_MPV_NO_COPY/1024 264116 ns 264087 ns 2591
MPV ist mein Original, MPV2 deine Modifizierung von unten nach oben und NO_COPY spricht für sich
-
Timon Paßlick schrieb:
So ein Müll, jetzt hab ich wieder ne Speicherzugriffsverletzung
Vielleicht solltest du mal einen Debugger nutzen?
Deine Loop im Print sieht falsch aus:
for (int i = data.size() - 1; i > 0; ++i)
Im 2. Durchlauf ist i gleich der size und dann kracht es.
-
NO_COPY ist ja wirklich extrem kürzer.
-
Habe noch die Pfadsuche mit der workline implementiert, bin mir aber nicht sicher, wie effektiv das ist:
/* Challenge: 'The Golden Mountain' At one international Olympiad in Informatics, the following task was given. Let's solve it! 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 The figure shows an example of a triangle of numbers. Write a program that calculates the largest sum of numbers through which the path starts, starting at the top and ending somewhere on the bottom. Each step can go diagonally down to the right or diagonally to the left. In the example - this is the path 7 -> 3 -> 8 -> 7 -> 5, given a max amount of 30. */ /* This code was created together with some friendly people of the German C++ forum (particularly a user called wob): https://www.c-plusplus.net/forum/345800-full */ #include <algorithm> #include <iostream> #include <sstream> #include <vector> using namespace std; struct path { int value; vector<int> data; void print(ostream &os) const { if (data.empty()) { os << "0: empty" << endl; return; } os << value << ": "; for (size_t i = data.size() - 1; i != 0; --i) os << data[i] << " -> "; os << data[0] << endl; } }; vector< vector<int> > read_pyramid(istream &is) { vector< vector<int> > result; while (true) { vector<int> line; for (int i = 0; i <= result.size(); ++i) { int n; if (!(is >> n)) { if (!line.empty()) cout << "The last line is not complete and therefore ignored." << endl; return result; } line.push_back(n); } result.push_back(move(line)); } } // returns the top most left best path path best_path(const vector< vector<int> > &pyramid) { if (pyramid.empty()) return path{ 0,{} }; if (pyramid.size() == 1) return path{ pyramid[0][0],{ pyramid[0][0] } }; vector<path> workline(pyramid.back().size()); for (int i = 0; i != workline.size(); ++i) workline[i] = path{ pyramid.back()[i],{} }; for (size_t line = pyramid.size() - 2; line != size_t(-1); --line) for (int col = 0; col != line + 1; ++col) { auto right_col = (workline[col].value >= workline[col + 1].value) ? col : col + 1; workline[col].value = pyramid[line][col] + workline[right_col].value; workline[col].data = workline[right_col].data; workline[col].data.push_back(pyramid[line + 1][right_col]); } workline[0].data.push_back(pyramid[0][0]); return workline[0]; } int max_path_value(const vector< vector<int> > &pyramid) { if (pyramid.empty()) return 0; if (pyramid.size() == 1) return pyramid[0][0]; vector<int> workline(pyramid.back()); for (size_t line = pyramid.size() - 2; line != size_t(-1); --line) for (size_t col = 0; col != pyramid[line].size(); ++col) workline[col] = pyramid[line][col] + max(workline[col], workline[col + 1]); return workline[0]; } int main() { stringstream testinput1( " 1 " " 1 3 " " 3 9 2 " " 9 1 1 1 " ); stringstream testinput2( " 7 " " 3 8 " " 8 1 0 " " 2 7 4 4 " " 4 5 2 6 5 " ); auto pyramid = read_pyramid(testinput1); // change to "read_pyramid(cin)" for custom input cout << "max_path_value = " << max_path_value(pyramid) << '\n'; auto best = best_path(pyramid); best.print(cout); }