[일반] 피보나치 이렇게 풀면 틀렸다고 나오네

[익명(114.71)]

n = int(input().strip())

r5 = sqrt(5)

npowof2 = 1 << n 

print(int(1 / (r5 * npowof2) * ((1 + r5)**n - (1 - r5)**n)))

예제 답들 제대로 나오는데 왜 안되지

[익명(218.50)]

실수오차

[익명(114.71)]

n 커지면 틀림? 틀린만큼 보정해주는 알고리즘은 없어?

[익명(223.39)]

실수오차보정 알고리즘이어딨농

[익명(apg2fwpfgsz5)]

Decimal써서 정확도 임의로 늘릴 수 있긴한데, ps에서 바라고자 하는것도 아니고, 속도도 느려지긴 함.

[익명(211.33)]

정수로 풀리는 문제는 실수 왠만하면 쓰면 안됨 문제 자체에서 실수 의도했을경우만 써 - dc App

[익명(118.235)]

그나마 반올림이 오차 줄여줄텐데 그마저도 한계는 있음

[Bubbler(bubbler)]

정수로 16~17자리 넘어가면 실수형은 일의 자리도 정확히 표현을 못함. n=90 근처부터는 확실히 틀릴듯 - dc App

[익명(118.235)]

안되는 알고리즘임 피보나치는 유명해서 다른 방법이 많이 있으니 찾아보셈

[익명(175.223)]

실수 자료형에 대해 한 번 알아보는게 좋을듯? 기본적으로 정수가 1의 자리까지 정확해야 하면 무조건 중간에 정수만 나오게 해주면 됨 보통은. 특이 케이스 아니면 정수 정답 계산에 실수를 쓸 일이 별로 없어. 피보나치 수열 일반항의 경우에는 만약 저렇게 하려고 든다면 이항 계수 구하고 sqrt(5)항 다 사라지니까 제곱항 계수 다 따서 계산을 할 수는 있을건데, 굳이 그러는 것보다 2로 나눠서 log 시간 안에 n번째 피보나치 수를 찾을 수 있음.