Gleichungen lösen
-
a+b-c-j=0
c+i-d-e=0
e+g-f=0
j-g-h-i=0bekannt:
a=10
b=7
d=3
e=2
f=3
j=14Wie kann man mehrere Aufgaben dieser Art mit einem Algorithmus (in C++) lösen? Gaußsches Eliminationsverfahren anwenden?
-
Moin am Tag der Toten...
Ich habe jetzt eine Lösung. Aber könnte es sein, dass die 4. Zeile falsch ist?
Hier mal meine Lösung, ich sage nicht, dass die besonders schön ist (schon wegen den magischen Zahlen), aber es ist glaube ich das Eliminationsverfahren:
#include <string> #include <vector> #include <sstream> #include <iostream> using namespace std; const int my_magic1 = 999; const int my_magic2 = -999; void printMatrix1(vector<vector<int>> &matrix1) { printf("Matrix1: (%d x %d)\n", matrix1.size(), matrix1[0].size()); for (int i = 0; i < matrix1.size(); i++) { for (int j = 0; j < matrix1[i].size(); j++) { cout << matrix1[i][j] << " "; } cout << endl; } cout << endl; } void printMatrix2(vector<int> &matrix2) { printf("Matrix2: (%d)\n", matrix2.size()); for (int i = 0; i < matrix2.size(); i++) { cout << " " << (char)('a' + i) << " "; } cout << endl; for (int i = 0; i < matrix2.size(); i++) { printf("% 3d ", matrix2[i]); } cout << endl; cout << endl; } void solveAndPrint(vector<vector<int>> &matrix1, vector<int> &matrix2) { vector<vector<int>> result(matrix1); vector<int> result2(matrix2); for (int i = 0; i < result.size(); i++) { for (int j = 0; j < result[i].size(); j++) { if (result[i][j] != 0) { if (result2[j] != my_magic1) { result[i][j] = result[i][j] * result2[j]; } else if (result[i][j] < 0) { result[i][j] = my_magic2; } else { result[i][j] = my_magic1; } } } } printMatrix1(result); printMatrix2(result2); bool changed = true; while (changed) { changed = false; for (int i = 0; i < result.size(); i++) { int magic_n = 0; int magic_i = 0; bool isneg = false; for (int j = 0; j < result[i].size(); j++) { if (result[i][j] == my_magic1 || result[i][j] == my_magic2) { magic_n++; magic_i = j; if (result[i][j] == my_magic2) { isneg = true; } } } if (magic_n == 1) { int sum = 0; for (int j = 0; j < result[i].size(); j++) { if (j != magic_i) { sum += result[i][j]; } } for (int k = 0; k < result.size(); k++) { if (result[k][magic_i] == my_magic1 || result[k][magic_i] == my_magic2) { result[k][magic_i] = isneg ? sum : -sum; } } if (result2[magic_i] == my_magic1) { result2[magic_i] = isneg ? sum : -sum; } changed = true; break; } } } printMatrix1(result); printMatrix2(result2); } int main(int argc, char const *argv[]) { vector<string> args({"1 1 -1 0 0 0 0 0 0 -1", "0 0 1 -1 -1 0 0 0 1 0", "0 0 0 0 1 -1 1 0 0 0", "0 0 0 0 0 0 -1 -1 -1 1", "0", "10 7 - 3 2 3 - - - 14"}); vector<vector<int>> matrix1; vector<int> matrix2; for (int i = 1;; i++) { printf("Koeffizienten %d. Zeile oder 0:\n", i); string l; // getline(cin, l); l = args[i - 1]; cout << l << endl; if (l == "0") { break; } stringstream ss; ss << l; string segment; vector<int> v; while (getline(ss, segment, ' ')) { v.push_back(stoi(segment)); } matrix1.push_back(v); } { cout << "Bekannte, oder nur -, wenn unbekannt:" << endl; string l; // getline(cin, l); l = args[args.size() - 1]; cout << l << endl; stringstream ss; ss << l; string segment; while (getline(ss, segment, ' ')) { if (segment == "-") { matrix2.push_back(my_magic1); } else { matrix2.push_back(stoi(segment)); } } } solveAndPrint(matrix1, matrix2); return 0; }
Ergebnis:
$ ./a Koeffizienten 1. Zeile oder 0: 1 1 -1 0 0 0 0 0 0 -1 Koeffizienten 2. Zeile oder 0: 0 0 1 -1 -1 0 0 0 1 0 Koeffizienten 3. Zeile oder 0: 0 0 0 0 1 -1 1 0 0 0 Koeffizienten 4. Zeile oder 0: 0 0 0 0 0 0 -1 -1 -1 1 Koeffizienten 5. Zeile oder 0: 0 Bekannte, oder nur -, wenn unbekannt: 10 7 - 3 2 3 - - - 14 Matrix1: (4 x 10) 10 7 -999 0 0 0 0 0 0 -14 0 0 999 -3 -2 0 0 0 999 0 0 0 0 0 2 -3 999 0 0 0 0 0 0 0 0 0 -999 -999 -999 14 Matrix2: (10) a b c d e f g h i j 10 7 999 3 2 3 999 999 999 14 Matrix1: (4 x 10) 10 7 3 0 0 0 0 0 0 -14 0 0 3 -3 -2 0 0 0 2 0 0 0 0 0 2 -3 1 0 0 0 0 0 0 0 0 0 1 17 2 14 Matrix2: (10) a b c d e f g h i j 10 7 3 3 2 3 1 17 2 14
Irgendwo muss aber ein Fehler sein, weil, wie gesagt, Zeile 4 nicht "aufgeht"...
Und dann noch eine Frage, ist so etwas wie
nullptr
invector<int>
erlaubt?Danke
-
Jup, in meinem Code war ein Fehler... Es existiert eine Lösung:
a b c d e f g h i j 10 7 3 3 2 3 1 11 2 14 10+7-3-14 = 0 ✅ 3+2-3-2 = 0 ✅ 2+1-3 = 0 ✅ 14-1-11-2 = 0 ✅
Der Fehler war im
if (magic_n == 1)
-Teil. Der sollte so sein:if (magic_n == 1) { int sum = 0; for (int j = 0; j < result[i].size(); j++) { if (j != magic_i) { sum += result[i][j]; } } for (int k = 0; k < result.size(); k++) { if (result[k][magic_i] == my_magic1 || result[k][magic_i] == my_magic2) { if (isneg) { result[k][magic_i] = result[k][magic_i] == my_magic1 ? sum : -sum; } else { result[k][magic_i] = result[k][magic_i] == my_magic1 ? -sum : sum; } } } if (result2[magic_i] == my_magic1) { result2[magic_i] = isneg ? sum : -sum; } changed = true; break; }
Hm, gibt es denn so etwas wie
nullptr
bzw. Platzhalteelemente in Vektoren? Weil, ich bräuchte 0 und -unbekannt und +unbekannt ...Danke
-
Du könntest mit Fließkommazahlen arbeiten (bedenke dann jedoch die Vergleiche), dann hättest du NaN, +Inf und -Inf.
Für etwas analoges zunullptr
bei Zeigern, könntest du std::optional benutzen, also z.B.std::vector<std::optional<double>>
.
-
@NoIDE sagte in Gleichungen lösen:
a+b-c-j=0
c+i-d-e=0
e+g-f=0
j-g-h-i=0bekannt:
a=10
b=7
d=3
e=2
f=3
j=14Wie kann man mehrere Aufgaben dieser Art mit einem Algorithmus (in C++) lösen? Gaußsches Eliminationsverfahren anwenden?
Zum Lösen eines linearen Gleichungssystems mit Unbekannten braucht man Gleichungen. Die vier Gleichungen führen nur zu (keine Gewähr bezüglich Tippfehler)
so dass noch sechs Gleichungen fehlen. Man kann aber wegen der sechs bekannten Werte noch sechs Gleichungen hinzufügen, so dass man folgende Gleichung erhält.
Diese lässt sich nun über eine der bekannten Methoden z.B. Gauss (auch LU-Zerlegung genannt) oder QR-Zerlegung mit Rücksubstitution lösen.
Wenn Du keine Lust auf selbst programmieren hast. Es gibt fertige Routinen dafür in der LAPACK und davon abgeleiteten Bibliotheken.
-
Danke fürs Aufdröseln!
@john-0 sagte in Gleichungen lösen:
Wenn Du keine Lust auf selbst programmieren hast. Es gibt fertige Routinen dafür in der LAPACK und davon abgeleiteten Bibliotheken.
Das ist lieb gemeint, aber zum einen möchte ich C++ üben (wie man das in echt richtig machen würde...), zum anderen brauche ich das auch praktisch, um kirchhoffsche Maschen in elektrischen Halbleitern zu berechnen.
Ganz vereinfacht gesagt, ist die Summe der zufließenden Ströme gleich der Summe der abfließenden Ströme. Spannungen können dabei auch negativ sein. Ist dies nicht so, stimmt etwas nicht. Es gibt aber viele dieser Maschen.
Und, nennt mich komisch, aber ich kann solche Sachen im Kopf besser berechnen, wenn ich eine genaue Vorstellung und "Rechenvorschrift" (Algorithmus) dafür habe.
-
Dieser Beitrag wurde gelöscht!
-
Dieser Beitrag wurde gelöscht!
-
@NoIDE sagte in Gleichungen lösen:
Das ist lieb gemeint, aber zum einen möchte ich C++ üben (wie man das in echt richtig machen würde...), zum anderen brauche ich das auch praktisch, um kirchhoffsche Maschen in elektrischen Halbleitern zu berechnen.
Es gibt genug Seiten im Internet, die das Gaußsche Eliminationsverfahren beschreiben – z.B. auf wikipedia.org und den Algorithmus in Pseudocode beschreiben. Konkrete Codebeispiele finden sich im Netz massenhaft.
-
Hm, es scheint so, als hättest du den ersten Teil:
@NoIDE sagte in Gleichungen lösen:
aber zum einen möchte ich C++ üben (wie man das in echt richtig machen würde...),
gar nicht gelesen. Aber macht nichts, benötige keine Antwort mehr.
-
Ihr könnt ja noch einmal schauen... Es können jetzt auch Koeffizienten
=/= +-1
gelöst werden* (hoffe ich), und ich bin erst einmal damit zufrieden:*: Also auch Matrizen, die nicht nur aus 1 oder -1 bestehen...
#include <string> #include <vector> #include <sstream> #include <iostream> #include <iomanip> #include <variant> #include <cmath> struct Value { double value = 0.0; bool is_unknown = false; }; using Row = std::vector<Value>; using Matrix = std::vector<std::vector<Value>>; struct System { Matrix coefficients; Row constant_terms; }; double round_to(double value, double precision = 0.01) { return std::round(value / precision) * precision; } std::ostream &operator<<(std::ostream &out, const Value &v) { if (!v.is_unknown) { out << std::setw(6) << std::setfill(' ') << round_to(v.value); } else { out << " --"; } return out; } std::ostream &operator<<(std::ostream &out, const Matrix &matrix) { out << "Matrix: (" << matrix.size() << " x " << matrix[0].size() << ")\n"; for (auto &row : matrix) { for (auto &value : row) { out << value; } out << '\n'; } return out << '\n'; } std::ostream &operator<<(std::ostream &out, const Row &row) { out << "Matrix: (1 x " << row.size() << ")\n"; for (size_t i = 0; i < row.size(); i++) { out << " " << (char)('a' + i); } out << '\n'; for (auto &value : row) { out << value; } out << '\n'; return out << '\n'; } void printSystem(const System &system) { std::cout << system.coefficients; std::cout << system.constant_terms; } System solveAndPrint(const System &input) { System result = input; bool changed = true; while (changed) { changed = false; printSystem(result); for (size_t i = 0; i < result.coefficients.size(); i++) { size_t magic_n = 0; size_t magic_i = 0; for (size_t j = 0; j < result.coefficients[i].size(); j++) { if (result.coefficients[i][j].value != 0 && result.constant_terms[j].is_unknown) { magic_n++; magic_i = j; } } if (magic_n == 1) { double sum = 0; for (size_t j = 0; j < result.coefficients[i].size(); j++) { if (j != magic_i && result.coefficients[i][j].value != 0) { sum -= result.coefficients[i][j].value * result.constant_terms[j].value; } } result.constant_terms[magic_i].value = sum / result.coefficients[i][magic_i].value; result.constant_terms[magic_i].is_unknown = false; changed = true; break; } } } return result; } int main(int argc, char const *argv[]) { std::vector<std::string> args({"2 6 -8", "1 0 -1", "0", "2 - -"}); System input; for (int i = 1;; i++) { std::cout << "Koeffizienten " << i << ". Zeile oder einfach 0, um die Eingabe abzuschließen:\n"; std::string l; // getline(std::cin, l); l = args[i - 1]; std::cout << l << '\n'; if (l == "0") { break; } std::stringstream ss; ss << l; std::string segment; Row r; while (getline(ss, segment, ' ')) { r.push_back(Value()); r.back().value = stod(segment); } input.coefficients.push_back(r); } { std::cout << "Bekannte, oder nur -, wenn unbekannt:\n"; std::string l; // getline(std::cin, l); l = args[args.size() - 1]; std::cout << l << '\n'; std::stringstream ss; ss << l; std::string segment; while (getline(ss, segment, ' ')) { input.constant_terms.push_back(Value()); if (segment == "-") { input.constant_terms.back().is_unknown = true; } else { input.constant_terms.back().value = stod(segment); } } } System result = solveAndPrint(input); return 0; }
Ich hab nun noch keine Fehlerbehandlung umgesetzt... Und Kommentare fehlen auch, wo etwas nicht selbsterklärend wäre.