제켄도르프 표현(피보나치 진법) 계산기

모든 양의 정수는 이웃하지 않는 피보나치 수들의 합으로 꼭 한 가지 방법으로 적힌다는 정리입니다. 예를 들어 100은 89 + 8 + 3 하나뿐입니다. 100 = 89 + 8 + 2 + 1도 합은 맞지만 2와 1이 이웃한 피보나치 수라서 제켄도르프 표현이 아닙니다.

남은 값 이하의 가장 큰 피보나치 수를 계속 빼기만 하면 됩니다(그리디). 뒤에 더 좋은 조합이 있을까 걱정할 필요가 없는데, F(k)를 빼고 나면 남는 값이 반드시 F(k−1)보다 작아져 이웃이 뽑힐 수 없기 때문입니다. 동전 거스름돈에서는 그리디가 최적이 아닌 경우가 있지만 피보나치 수에서는 언제나 옳습니다.

흔히 쓰는 1, 1, 2, 3, 5…에서 1을 두 번 두면 4 = 3 + 1이 두 가지로 세어져 «꼭 한 가지»가 깨지기 때문입니다. 그래서 제켄도르프 표현에서는 1, 2, 3, 5, 8, 13…을 씁니다.

제켄도르프 표현을 낮은 자리부터 비트로 적고 끝에 1을 덧붙인 것입니다. 이웃한 1이 없으므로 «11»이 나오는 곳이 곧 한 수의 끝이 되어, 길이를 따로 적지 않고도 이어 붙인 부호열을 다시 하나씩 가를 수 있습니다(접두 부호). 자료 압축에서 작은 정수를 담을 때 쓰며, 한 비트가 깨져도 다음 «11»에서 다시 맞춰지는 성질이 있습니다.

이웃한 피보나치 수의 비가 황금비 1.618…로 다가가는데, 마일을 킬로미터로 바꾸는 값 1.609344가 그것과 거의 같습니다. 그래서 제켄도르프 표현의 피보나치 수를 한 칸씩 위로 밀면 그대로 어림이 됩니다. 8마일 ≈ 13km(실제 12.87), 89마일 ≈ 144km(실제 143.2)처럼 대개 1% 안쪽으로 맞습니다.

이 계산기가 확인해 줍니다. 값이 7만 이하일 때는 피보나치 수의 모든 부분집합을 전수로 훑어 «이웃 없는 합»이 그 값이 되는 경우가 몇 가지인지 세고, 그 개수를 결과에 냅니다. 언제나 1이 나와야 합니다.

자리값이 1, 2, 4, 8이 아니라 1, 2, 3, 5, 8, 13입니다. 그리고 이진법과 달리 «이웃한 두 자리에 동시에 1이 올 수 없다»는 제약이 붙습니다. 그 제약 덕분에 표현이 유일해지고 접두 부호가 됩니다. 대신 같은 수를 적는 데 비트가 조금 더 듭니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.