Advertisement
Guest User

Untitled

a guest
Oct 25th, 2016
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.92 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <complex>
  6. #include <ctime>
  7. #include <iostream>
  8. #include <cmath>
  9. #include <stack>
  10. #include <sstream>
  11. #include <stdio.h>
  12. #include <algorithm>
  13. #include <queue>
  14. #include <cstring>
  15. #include <cassert>
  16. #include <iomanip>
  17. #include <math.h>
  18.  
  19. using namespace std;
  20.  
  21. void print(vector<vector<double>> &A)
  22. {
  23. cout << "-------------\n";
  24. for (int i = 0; i < A.size(); i++)
  25. {
  26. for (int j = 0; j < A[i].size(); j++)
  27. cout << A[i][j] << " ";
  28. cout << "\n";
  29. }
  30. cout << "-------------\n";
  31. }
  32. double det(vector<vector<double>> &aa)
  33. {
  34. vector<vector<double>> a = aa;
  35. int n = a.size();
  36. double EPS = 0.00000001;
  37. double det = 1;
  38. for (int i = 0; i<n; ++i) {
  39. int k = i;
  40. for (int j = i + 1; j<n; ++j)
  41. if (abs(a[j][i]) > abs(a[k][i]))
  42. k = j;
  43. if (abs(a[k][i]) < EPS) {
  44. det = 0;
  45. break;
  46. }
  47. swap(a[i], a[k]);
  48. if (i != k)
  49. det = -det;
  50. det *= a[i][i];
  51. for (int j = i + 1; j<n; ++j)
  52. a[i][j] /= a[i][i];
  53. for (int j = 0; j<n; ++j)
  54. if (j != i && abs(a[j][i]) > EPS)
  55. for (int k = i + 1; k<n; ++k)
  56. a[j][k] -= a[i][k] * a[j][i];
  57. }
  58. return det;
  59. }
  60.  
  61.  
  62. double scal(vector<double> &a, vector<double> &b)
  63. {
  64. double ans = 0;
  65. for (int i = 0; i < a.size(); i++)
  66. {
  67. ans += a[i] * b[i];
  68. }
  69. return ans;
  70. }
  71.  
  72. vector<double> proj(vector<double> &b, vector<double> &a)
  73. {
  74. double c = scal(a, b) / scal(b, b);
  75. vector<double> ans(b.size());
  76. for (int i = 0; i < b.size(); i++) ans[i] = b[i] * c;
  77. return ans;
  78. }
  79. void sub(vector<double> &a, vector<double> &b)
  80. {
  81. for (int i = 0; i < a.size(); i++) a[i] -= b[i];
  82. }
  83. void normalize(vector<double> &a)
  84. {
  85. double e = 0;
  86. for (int i = 0; i < a.size(); i++)
  87. {
  88. e += a[i] * a[i];
  89. }
  90. e = sqrt(e);
  91. for (int i = 0; i < a.size(); i++) a[i] /= e;
  92. }
  93.  
  94. vector<double> getCol(vector<vector<double>> &A, int i)
  95. {
  96. vector<double> col(A.size());
  97. for (int j = 0; j < A.size(); j++) col[j] = A[j][i];
  98. return col;
  99. }
  100. void setCol(vector<vector<double>> &A, int i, vector<double> &col)
  101. {
  102. for (int j = 0; j < A.size(); j++) A[j][i] = col[j];
  103. }
  104.  
  105. vector<vector<double>> getOrth(vector<vector<double>> &A)
  106. {
  107. vector<vector<double>> B = A;
  108. for (int i = 0; i < B.size(); i++)
  109. {
  110. for (int j = 0; j < i; j++)
  111. {
  112. vector<double> bi = getCol(B, i);
  113. vector<double> bj = getCol(B, j);
  114. vector<double> ai = getCol(A, i);
  115. vector<double> pr = proj(bj, ai);
  116. sub(bi, pr);
  117. setCol(B, i, bi);
  118. //sub(B[i], proj(B[j], A[i]));
  119. }
  120. vector<double> bi = getCol(B, i);
  121. normalize(bi);
  122. setCol(B, i, bi);
  123. }
  124. /*for (int i = 0; i < B.size(); i++)
  125. {
  126. normalize(B[i]);
  127. }*/
  128. //print(B);
  129. return B;
  130. }
  131.  
  132. vector<vector<double>> transp(vector<vector<double>> &A)
  133. {
  134. vector<vector<double>> B = A;
  135. for (int i = 0; i < A.size(); i++)
  136. for (int j = 0; j < A[i].size(); j++)
  137. B[i][j] = A[j][i];
  138. return B;
  139. }
  140. vector<vector<double>> mul(vector<vector<double>> &A, double C)
  141. {
  142. vector<vector<double>> res = A;
  143. for (int i = 0; i < res.size(); i++)
  144. for (int j = 0; j < res[i].size(); j++) res[i][j] *= C;
  145. return res;
  146. }
  147. vector<double> mul(vector<vector<double>> &A, vector<double> &b)
  148. {
  149. vector<double> res = b;
  150. for (int i = 0; i < A.size(); i++)
  151. {
  152. double ans = 0;
  153. for (int j = 0; j < A.size(); j++) ans += A[i][j] * b[j];
  154. res[i] = ans;
  155. }
  156. return res;
  157. }
  158. vector<vector<double>> reverseM(vector<vector<double>> &a)
  159. {
  160. vector<vector<double>> res = a;
  161. vector<vector<double>> res2 = a;
  162. for (int i = 0; i < res.size(); i++)
  163. for (int j = 0; j < res.size(); j++)
  164. {
  165. vector<vector<double>> alg(res.size() - 1);
  166. int ii = 0; int jj = 0;
  167. for (int k = 0; k < res.size(); k++)
  168. for (int l = 0; l < res.size(); l++)
  169. {
  170. if (k == i || l == j) continue;
  171. if (jj == alg.size()) jj = 0, ii++;
  172. alg[ii].push_back(res[k][l]);
  173. jj++;
  174. }
  175. res2[i][j] = det(alg);
  176. if ((i + j) % 2 == 1) res2[i][j] *= -1;
  177. }
  178.  
  179. res2 = transp(res2);
  180. return mul(res2, 1.0/det(a));
  181. }
  182.  
  183. vector<vector<double>> mul(vector<vector<double>> &A, vector<vector<double>> &B)
  184. {
  185. vector<vector<double>> res = A;
  186. for (int i = 0; i < res.size(); i++)
  187. for (int j = 0; j < res.size(); j++)
  188. {
  189. double ans = 0;
  190. for (int k = 0; k < res.size(); k++)
  191. {
  192. ans += A[i][k] * B[k][j];
  193. }
  194. res[i][j] = ans;
  195. }
  196. return res;
  197. }
  198.  
  199. pair<vector<vector<double>>, vector<vector<double>>> QR(vector<vector<double>> &A)
  200. {
  201. vector<vector<double>> Q = getOrth(A);
  202. vector<vector<double>> R = mul(transp(Q), A);
  203. return{ Q,R };
  204. }
  205.  
  206.  
  207.  
  208. int main() {
  209. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  210. srand(unsigned(time(nullptr)));
  211. freopen("input.txt", "r", stdin);
  212. vector<vector<double>> A;
  213. int n;
  214. cin >> n;
  215. A.resize(n);
  216. for (int i = 0; i < n; i++)
  217. {
  218. A[i].resize(n);
  219. for (int j = 0; j < n; j++)
  220. {
  221. cin >> A[i][j];
  222. }
  223. }
  224. vector<double> b(n);
  225. for (int i = 0; i < n; i++) cin >> b[i];
  226. pair<vector<vector<double>>, vector<vector<double>>> P = QR(A);
  227.  
  228. vector<double> X = mul(mul(reverseM(P.second), reverseM(P.first)), b);
  229. for (int i = 0; i < X.size(); i++) cout << X[i] << " ";
  230.  
  231. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement