黄金分割探索 ARC054B - ムーアの法則
WAの原因が分かりません。
競技プログラミングの初心者です。
ARC054B - ムーアの法則を解きました。三分探索を使ったコードではACできましたが、三分探索より効率の良い方法として黄金分割探索があることをネットで知り、そちらでも解いてみたいと思いました。
しかし、書いてみたコードでは入力に対して期待されるものとは異なるものが出力されてしまいます。ChatGPTに聞いてみるなどしたのですが解決できませんでした。原因を教えてほしいです。
三分探索でACしたコードも載せておきました。
ソースコード （黄金分割探索・WA） ＊4/30修正
#include <bits/stdc++.h>
using namespace std;
double P;
double f(double x) {
return x + P / pow(2, x / 1.5);
}
int main() {
cin >> P;
double gold = (1 + sqrt(5)) / 2;
double l = 0, r = P;
double c1 = (l * gold + r) / (1 + gold);
double c2 = (l + r * gold) / (1 + gold);
double f_c1 = f(c1);
double f_c2 = f(c2);
while (r - l > 0.00000001) {
if (f_c1 > f_c2) {
l = c1;
c1 = c2;
f_c1 = f_c2;
c2 = (l * gold + r) / (1 + gold);
f_c2 = f(c2);
}
else {
r = c2;
c2 = c1;
f_c2 = f_c1;
c1 = (l + r * gold) / (1 + gold);
f_c1 = f(c1);
}
}
cout << fixed << setprecision(10) << f(l) << endl;
}
入力例１→ 実際の出力
2.8798910904
入力例２→ 実際の出力
0.0400000000
入力例３→ 実際の出力
447213595499958336.0000000000
ソースコード （三分探索・AC）
#include <bits/stdc++.h>
using namespace std;
double P;
double f(double x) {
return x + P / pow(2, x / 1.5);
}
int main() {
cin >> P;
double l = 0, r = P;
while (r - l > 0.00000001) {
double c1 = (2 * l + r) / 3;
double c2 = (l + 2 * r) / 3;
if (f(c1) > f(c2)) l = c1;
else r = c2;
}
cout << fixed << setprecision(10) << f(l)<< endl;
}
0
