###### tags: `code`
# c14086167-homework-6-2

#include <iostream>
#include <math.h> 
#define N 20
using namespace std;

double A[N][N] = {};
double e[N][N] = {}; //column of Q 等於Q的轉置
double R[N][N] = {};
double f[N] = {};    //f=Rx=Q^t乘上F 
double F[N] = {};

void initial();
void transposeA();
double inner(double *v, double *w);
void normal(double *v);
void orthogonal();
void defnR();
void defnf();
void matrixSolver();

int main() {
	initial();
	transposeA();	//把A轉置方便orthogonal
	orthogonal();	//得到 column of Q
	defnR();
	defnf();
	matrixSolver();

	for (int j = 0; j < N; j++) {
        //避免小數為0時輸出不為0的問題 但這裡沒差的樣子
		if (fabs(f[j]) < 0.0000000000001) cout << 0 << "\n";
		else cout << f[j] << "\n";
	}
}

//題目
void initial() {
	for (int i = 0; i < N; i++) {
		A[i][i] = -2;
		if ((i + 1) < N) {
			A[i][i + 1] = 1;
			A[i + 1][i] = 1;
		}
		F[i] = (i == N - 1);
	}
}

//轉置A
void transposeA() {
	double t = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < i; j++) {
			t = A[i][j];
			A[i][j] = A[j][i];
			A[j][i] = t;
		}
	}
}

//內積
double inner(double *v, double *w) {
	double sum = 0;
	for (int i = 0; i < N; i++) {
		sum += *(v + i) * *(w + i);
	}
	return sum;
}

//單位化
void normal(double *v) {
	double length = 0;
	length = pow(inner(v, v), 0.5);
	for (int i = 0; i < N; i++) {
		*(v + i) /= length;
	}
}

void orthogonal() {
	for (int i = 0; i < N; i++) {
		//e[i]=A[i]
		for (int j = 0; j < N; j++) {
			*(e[i] + j) = *(A[i] + j);
		}
		//orthogonal e[i] -= <A[j],e[j]>e[j]
		for (int j = 0; j < i; j++) {
			for (int k = 0; k < N; k++) {
				*(e[i] + k) -= inner(A[i], e[j]) * *(e[j] + k);
			}
		}
		normal(e[i]);
	}
}

void defnR() {
	//上三角 A[i]跟e[i]內積組成
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i <= j) R[i][j] = inner(e[i], A[j]);
			else R[i][j] = 0;
		}
	}
}

void defnf() {
	//f =Rx =Q轉置 乘 F  
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			f[i] += e[i][j] * F[j];
		}
	}
}

void matrixSolver() {
	//上三角的反矩陣不知道怎麼處理 所以就用最原始的代入消去處理了
	for (int i = 0; i < N; i++) {
		//將第一項化為一  整個row除上第一項 
		if (R[i][i] != 1 && R[i][i] != 0) {
			for (int j = i + 1; j < N; j++) {
				R[i][j] /= R[i][i];
			}
			f[i] /= R[i][i];
			R[i][i] = 1;
		}
	}
	
	//從下到上 一列一列扣上去 
	for (int i = N - 1; i >= 0; i--) {
		for (int j = 0; j < i; j++) {
			f[j] -= R[j][i] * f[i];
		}
	}
}