Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <vector>
- #include <map>
- #include <set>
- #include <complex>
- #include <ctime>
- #include <iostream>
- #include <cmath>
- #include <stack>
- #include <sstream>
- #include <stdio.h>
- #include <algorithm>
- #include <queue>
- #include <cstring>
- #include <cassert>
- #include <iomanip>
- #include <math.h>
- using namespace std;
- void print(vector<vector<double>> &A)
- {
- cout << "-------------\n";
- for (int i = 0; i < A.size(); i++)
- {
- for (int j = 0; j < A[i].size(); j++)
- cout << A[i][j] << " ";
- cout << "\n";
- }
- cout << "-------------\n";
- }
- double det(vector<vector<double>> &aa)
- {
- vector<vector<double>> a = aa;
- int n = a.size();
- double EPS = 0.00000001;
- double det = 1;
- for (int i = 0; i<n; ++i) {
- int k = i;
- for (int j = i + 1; j<n; ++j)
- if (abs(a[j][i]) > abs(a[k][i]))
- k = j;
- if (abs(a[k][i]) < EPS) {
- det = 0;
- break;
- }
- swap(a[i], a[k]);
- if (i != k)
- det = -det;
- det *= a[i][i];
- for (int j = i + 1; j<n; ++j)
- a[i][j] /= a[i][i];
- for (int j = 0; j<n; ++j)
- if (j != i && abs(a[j][i]) > EPS)
- for (int k = i + 1; k<n; ++k)
- a[j][k] -= a[i][k] * a[j][i];
- }
- return det;
- }
- double scal(vector<double> &a, vector<double> &b)
- {
- double ans = 0;
- for (int i = 0; i < a.size(); i++)
- {
- ans += a[i] * b[i];
- }
- return ans;
- }
- vector<double> proj(vector<double> &b, vector<double> &a)
- {
- double c = scal(a, b) / scal(b, b);
- vector<double> ans(b.size());
- for (int i = 0; i < b.size(); i++) ans[i] = b[i] * c;
- return ans;
- }
- void sub(vector<double> &a, vector<double> &b)
- {
- for (int i = 0; i < a.size(); i++) a[i] -= b[i];
- }
- void normalize(vector<double> &a)
- {
- double e = 0;
- for (int i = 0; i < a.size(); i++)
- {
- e += a[i] * a[i];
- }
- e = sqrt(e);
- for (int i = 0; i < a.size(); i++) a[i] /= e;
- }
- vector<double> getCol(vector<vector<double>> &A, int i)
- {
- vector<double> col(A.size());
- for (int j = 0; j < A.size(); j++) col[j] = A[j][i];
- return col;
- }
- void setCol(vector<vector<double>> &A, int i, vector<double> &col)
- {
- for (int j = 0; j < A.size(); j++) A[j][i] = col[j];
- }
- vector<vector<double>> getOrth(vector<vector<double>> &A)
- {
- vector<vector<double>> B = A;
- for (int i = 0; i < B.size(); i++)
- {
- for (int j = 0; j < i; j++)
- {
- vector<double> bi = getCol(B, i);
- vector<double> bj = getCol(B, j);
- vector<double> ai = getCol(A, i);
- vector<double> pr = proj(bj, ai);
- sub(bi, pr);
- setCol(B, i, bi);
- //sub(B[i], proj(B[j], A[i]));
- }
- vector<double> bi = getCol(B, i);
- normalize(bi);
- setCol(B, i, bi);
- }
- /*for (int i = 0; i < B.size(); i++)
- {
- normalize(B[i]);
- }*/
- //print(B);
- return B;
- }
- vector<vector<double>> transp(vector<vector<double>> &A)
- {
- vector<vector<double>> B = A;
- for (int i = 0; i < A.size(); i++)
- for (int j = 0; j < A[i].size(); j++)
- B[i][j] = A[j][i];
- return B;
- }
- vector<vector<double>> mul(vector<vector<double>> &A, double C)
- {
- vector<vector<double>> res = A;
- for (int i = 0; i < res.size(); i++)
- for (int j = 0; j < res[i].size(); j++) res[i][j] *= C;
- return res;
- }
- vector<double> mul(vector<vector<double>> &A, vector<double> &b)
- {
- vector<double> res = b;
- for (int i = 0; i < A.size(); i++)
- {
- double ans = 0;
- for (int j = 0; j < A.size(); j++) ans += A[i][j] * b[j];
- res[i] = ans;
- }
- return res;
- }
- vector<vector<double>> reverseM(vector<vector<double>> &a)
- {
- vector<vector<double>> res = a;
- vector<vector<double>> res2 = a;
- for (int i = 0; i < res.size(); i++)
- for (int j = 0; j < res.size(); j++)
- {
- vector<vector<double>> alg(res.size() - 1);
- int ii = 0; int jj = 0;
- for (int k = 0; k < res.size(); k++)
- for (int l = 0; l < res.size(); l++)
- {
- if (k == i || l == j) continue;
- if (jj == alg.size()) jj = 0, ii++;
- alg[ii].push_back(res[k][l]);
- jj++;
- }
- res2[i][j] = det(alg);
- if ((i + j) % 2 == 1) res2[i][j] *= -1;
- }
- res2 = transp(res2);
- return mul(res2, 1.0/det(a));
- }
- vector<vector<double>> mul(vector<vector<double>> &A, vector<vector<double>> &B)
- {
- vector<vector<double>> res = A;
- for (int i = 0; i < res.size(); i++)
- for (int j = 0; j < res.size(); j++)
- {
- double ans = 0;
- for (int k = 0; k < res.size(); k++)
- {
- ans += A[i][k] * B[k][j];
- }
- res[i][j] = ans;
- }
- return res;
- }
- pair<vector<vector<double>>, vector<vector<double>>> QR(vector<vector<double>> &A)
- {
- vector<vector<double>> Q = getOrth(A);
- vector<vector<double>> R = mul(transp(Q), A);
- return{ Q,R };
- }
- int main() {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- srand(unsigned(time(nullptr)));
- freopen("input.txt", "r", stdin);
- vector<vector<double>> A;
- int n;
- cin >> n;
- A.resize(n);
- for (int i = 0; i < n; i++)
- {
- A[i].resize(n);
- for (int j = 0; j < n; j++)
- {
- cin >> A[i][j];
- }
- }
- vector<double> b(n);
- for (int i = 0; i < n; i++) cin >> b[i];
- pair<vector<vector<double>>, vector<vector<double>>> P = QR(A);
- vector<double> X = mul(mul(reverseM(P.second), reverseM(P.first)), b);
- for (int i = 0; i < X.size(); i++) cout << X[i] << " ";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement