Bài tập | NEU OJ

Cho hệ $Ax=d$ với $A$ là ma trận ba đường chéo (tridiagonal) cấp $n$ : đường chéo chính $b_i$ ( $i=1..n$ ), đường chéo dưới $a_i$ (hệ số của $x_{i-1}$ trong phương trình thứ $i$ , $i=2..n$ ), đường chéo trên $c_i$ (hệ số của $x_{i+1}$ trong phương trình thứ $i$ , $i=1..n-1$ ). Giải hệ bằng thuật toán truy đuổi (Thomas algorithm — một dạng khử Gauss chuyên biệt, độ phức tạp $O(n)$ ): khử tiến để loại $a_i$ , sau đó thế ngược để tính nghiệm.

Định dạng đầu vào:
Dòng 1: số nguyên $n$ ( $2 \le n \le 8$ ). Dòng 2: $n$ số thực $b_1,\dots,b_n$ . Dòng 3: $n-1$ số thực $a_2,\dots,a_n$ . Dòng 4: $n-1$ số thực $c_1,\dots,c_{n-1}$ . Dòng 5: $n$ số thực $d_1,\dots,d_n$ .
Ràng buộc đầu vào:
Dữ liệu đảm bảo quá trình khử không gặp phần tử chia bằng 0 và hệ có nghiệm duy nhất; $|b_i|,|a_i|,|c_i|,|d_i| \le 100$ .
Định dạng đầu ra:
In ra $n$ số thực là nghiệm $x_1,\dots,x_n$ trên một dòng, cách nhau khoảng trắng, làm tròn 4 chữ số sau dấu phẩy.

solution

Đề bài: [Toán cho CNTT] Giải hệ ba đường chéo bằng thuật toán truy đuổi