글 읽기 - 1196번 데이터가 정확한가요?

kev0960 9년 전 0

결과적으로 구해야 하는게 H_n = 1/1 + 1/2 + ... + 1/n 이라 한다면, n * (H_n - H_(n-m)) 인건데, 왜 결과가 틀렸다고 나올까요 ㅠㅠ

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

double gammac = 0.577215664901532860606512090082;
double harmonic(double n, double m)
{
    return m * log(n) + m * gammac + 0.5 * m / n - m /(12 * n * n) + (m / (120 * n * n)) / (n * n);
}
double harmonic_calc(double n, double m) 
{
    double sum = 0;
    for(int i = 1; i <= n; i ++) {
        sum += (m / i);
    }
    return sum;
}

int main()
{
    double n, m;
    cin >> n >> m;
    
    cout << setprecision(15);
    
    double sum = 0;
    if(m > 100000000) {
    	for(long long i = 1; i <= m; i ++) {
        	sum += (n / (n - m + i));
    	}
        cout << sum << endl;
    }
    else {
        double first = harmonic(n, n);
        double second;
        if(n - m < 100000000) second = harmonic_calc(n - m, n);
        else second = harmonic(n - m, n);
        cout << first - second << endl;
    }
    return 0;
}

baekjoon 9년 전 0

왜냐하면 log함수 때문입니다.

log함수는 1에 가까운 값을 넣었을 때, 올바른 값을 리턴하지 않습니다. 이럴때는 log1p 함수를 사용하세요.

kev0960 9년 전 0

그래서 n 이 10000000 이상일 때만 로그함수를 사용하는 harmonic 함수를 호출하고, 아니면 그냥 harmonic_calc 함수를 호출하였는데요ㅠㅠ

(항상 n > m 이므로 m > 100000000 임을 검사하는 첫번째 if 문에서 이를 처리한 것으로 생각됩니다.)

baekjoon 9년 전 0

컴퓨터에서 소수점은 정확한 값을 갖지를 못하는데, 저런식으로 누적하다보면, 오차는 점점 커지게 됩니다.

그리고 10^18을 for문을 이용해서 돌면 시간 초과를 받게 됩니다.

zzapCoder 9년 전 0

이 문제는 어떻게 푸는지 정말 궁금하네여....

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1196번 데이터가 정확한가요?

kev0960 9년 전 0

baekjoon 9년 전 0

kev0960 9년 전 0

baekjoon 9년 전 0

zzapCoder 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말