algospot : https://algospot.com/judge/problem/read/ROOTS
github : https://github.com/junho0956/Algorithm
algospot ROOTS 단변수 다항 방정식 해결하기 문제입니다.
풀이는 코드에 주석처리 되어있으며 문제해결기법을 참조하였습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
/*
실수 근만을 갖는 ax2 + bx + c = 0과 같은 형태의 단변수 다항 방정식이 주어질 때
이들의 근을 계산하는 프로그램을 작성하세요.
*/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
// 모든 해의 절대값은 10 이하라고 가정해도 좋습니다.
const int L = 10;
// 단일 변수 다항식p의 계수가 주어질 때 미분한 결과 p'의 계수를 반환한다
vector<double> differentiate(const vector<double>& poly) {
int n = poly.size() - 1;
vector<double> res;
for (int i = 0; i < n; i++) {
res.push_back(poly[i] * (n - i));
}
return res;
}
// 1차 혹은 2차 방정식을 푼다
vector<double> solveNative(const vector<double>& poly) {
int n = poly.size() - 1;
vector<double> res;
if (n == 1) {
res.push_back((-1) * (poly[1] / poly[0]));
return res;
}
if (n == 2) {
double a, b, c;
a = poly[0], b = poly[1], c = poly[2];
res.push_back(((-b) + (sqrt(pow(b, 2) - 4 * a * c))) / (2 * a));
res.push_back(((-b) - (sqrt(pow(b, 2) - 4 * a * c))) / (2 * a));
sort(res.begin(), res.end());
return res;
}
}
// 다항식 f(x)의 계수 poly가 주어질 때, f(val)를 반환한다
double evaluate(const vector<double>& poly, double val) {
double ans = 0;
int n = poly.size() - 1;
for (int i = 0; i <= n; i++) {
ans += pow(val, n - i) * poly[i];
}
return ans;
}
// 방정식의 근을 반환한다
vector<double> solve(const vector<double>& poly) {
// 방정식의 계수를 확인한다
int n = poly.size() - 1;
// 만약 2차 이하라면 바로 해결한다
if (n <= 2) return solveNative(poly);
// 3차 이상이라면 미분한 방정식을 구한다
vector<double> different = differentiate(poly);
// 미분한 방정식에 대한 극점을 재귀를 통하여 구한다
vector<double> sol = solve(different);
// 왼쪽, 오른쪽 끝의 극점은 그 옆에 또 다른 극점이 존재하지 않으므로 근을 구할 수 없다.
// 그러므로 초기화 해놓은 L을 이용하여 근을 구한다.
// 각 극점을 이분법을 이용하여 근을 구한다
vector<double> res;
for (int i = 0; i < sol.size()-1; i++) {
double x1 = sol[i], x2 = sol[i + 1];
double y1 = evaluate(poly, x1), y2 = evaluate(poly, x2);
// y가 같은 부호이면 근이 존재할 수 없다.
if (y1 * y2 > 0) continue;
// 불변 조건 : 이분법의 진행과정에 따라 반드시 f(x1) < f(x2) 일 수는 없다.
// f(x1) <= 0 < f(x2) 를 강제하여 이분법 상의 두 부분중 어느곳을 선택해야 할지 판단한다.
if (y1 > y2) {
swap(y1, y2);
swap(x1, x2);
}
// while 이 아닌 최대 100 정도의 for문으로 이분법을 돌리는 것은
// 이분법 과정에서 무한루프를 방지할 수 있다.
for (int i = 0; i < 100; i++) {
double x = (x1 + x2) / 2;
double y = evaluate(poly, x);
if (y <= 0) x1 = x;
else x2 = x;
}
res.push_back(x1);
}
sort(res.begin(), res.end());
return res;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
// 입력의 첫 줄에는 테스트 케이스의 수 C(C<=50)가 주어집니다.
// 각 테스트 케이스의 첫 줄에는 방정식의 차수 n(2 <= n <= 5)이 주어지고,
// 그 다음 줄에 n+1개의 실수로 방정식의 차수가 고차항부터 주어집니다.
int C; cin >> C;
while (C--) {
int n; cin >> n;
vector<double> poly;
for (int i = 0; i < n + 1; i++) {
double val; cin >> val;
poly.push_back(val);
}
// 각 테스트 케이스마다 n개의 실수로 오름차순으로 정렬된 방정식의 해를 출력합니다.
// 방정식의 해는 모두 다르다고 가정해도 좋습니다.
// 10 - 8 이하의 상대 / 절대 오차가 있는 답은 정답으로 처리됩니다.
vector<double> res = solve(poly);
sort(res.begin(), res.end());
cout << fixed;
cout.precision(10);
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}
cout << endl;
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm > algospot' 카테고리의 다른 글
| algospot PASS486 (0) | 2020.02.27 |
|---|---|
| algospot FOSSIL (0) | 2020.02.26 |
| algospot RATIO (0) | 2020.02.25 |
| algospot LOAN (0) | 2020.02.24 |
| algospot FESTIVAL (0) | 2019.10.27 |
