숫자의 negafibonacci 표현을 찾는 욕심 많은 알고리즘?

Question

Zeckendorf's theorem에 따르면 모든 양의 정수는 비 연속적 피보나치 수의 합계로 고유 한 방식으로 기록 될 수 있습니다. 이러한 분해는 그리 디 알고리즘은, 예를 들면, 적합한 큰 피보나치 수를 감산 본질적으로 구성되는 반복 쉽게 발견 될 수있다 :

20 = 13 + 7 = 13 + 5 + 2

그러나 정리는 의미도 정수 (< = 0 그) 별개의 비 연속 negaFibonacci 수의 합으로서 고유 분해를 갖고, 그 순서를이다

0, 1, -1, 2, -3, 5, -11, ...

또는 F_ (- n) = (-1)^(n + 1) F_n. 몇 가지 예 :

-4 = - 3 - 1

4 = 5 + 1

11 = 13 - 3 + 1

이 방법으로 주어진 정수를 분해 알려진 쉬운 알고리즘이 있습니까?

Answer 1

네가 피보나치에서 숫자를 나타내는 데 사용할 수있는 좋은 욕심 많은 알고리즘이 있습니다.

이 알고리즘의 배경은 정수를 피보나치 수 (양수의 경우)와 홀수 피보나치 수 (음수의 경우)의 쌍으로 구분 된 범위로 나누는 것입니다. 특히, 우리는

• F를 범위로 양수를 나눌 수 있습니다 + 1 F , 포함,
• F에 + 1 F , 포함,
에
• F _{포함 F 6, 4} + 1
• F _{6F 8 포괄적,}
• F에 ₈ + 1 F ₁₀ 포괄적,
• ...
• F에 2K + 1 F _{에 2K + 2} , 포함,
• ...

우리는 유사 부정적인 피보나치 수에 의해 경계가이 범위에 n 개의 숫자를 나눌 수 있습니다 :

• -F 은 + 1, 포함,
• -F를 -F하기 ₃는 -F 01,237,184,218에
• -F 5 _{를 포함한 5} + 1, -F 할
• -F _{7는 9} + 1을 포함하는 -F 6백51경6천1백55조7천7백62억4천3백94만3천2백10 7 + 1 (포함),
• ...
• -F 2K-1 _{2K + 1 -F 할} + 1 (포함),
• ...

다음과 같은 알고리즘은 탐욕 진행 : 01,235

16,

• 개수가 긍정적이면, N을 포함하는 범위 [F _2K + 1, F _{2K + 2}]를 찾아 표현에 F _{2K + 1}를 추가 감산 F _{2K + 1} n에서. 숫자가 음수이면, 범위 검색
• [-F _2K-1을 -F _{2K + 1} + 1] 함유 n은 상기 표현 -F _2K를 추가하고, 추가 F _2K 총계에.
• 숫자가 0이면 완료됩니다.

예를 들어 보겠습니다. 27 개를 negafibonacci로 변환하고 싶다고 가정 해보십시오. 21 + 1 55입니다. (홀수 인덱스) 피보나치 숫자 34를 샌드위치하므로 합계에 34를 더한 다음 27-34 = -7을 negafibonacci로 변환하려고 시도합니다.

다음에, 우리는 5 + 1 13이므로 7 함유 범위에 개재되는 것을 알아 차리는 (짝수) 횟수 8. 우리는 따라서 전체로 -8을 추가 negafibonacci 1을 변환하려고 피보나치 .

지금, 우리는 (여 색인) 그러므로 우리는 전체에 1을 추가하고 negafibonacci에 0을 변환 할 수 1. 피보나치 0 + 1 1, 그래서 1이 포함 된 범위에 끼워진 것을 알 수 있습니다.

총 0 개가 남았습니다. 이제 끝났습니다! 그리고 헤이! 34 - 8 + 1 = 27.

먼저 정당성을 주장합시다.우선, 피보나치 양수를 더하면 홀수 피보나치 수 (F _{2k + 1})를 선택해야하며 음수 피보나치 수를 더하면 반드시 음수 짝수 피보나치 수 (-F _2k 형태의 것을 선택하기 때문에). 추가 된 각 번호는 적절한 부호를 갖습니다.

다음으로 해지 사실을 입증하겠습니다. 긍정적 인 경우를 먼저보십시오. [F _2k +1, F _{2k + 2}] 범위의 숫자가 발견되면 F _{2k + 1}을 뺍니다. 수에 상한이 2K + 2 후 F _{인 - F 2K 2K + 1} = F _{때문에 나머지를 함유하는 큰 간격이 범위로하는 것 [F 2K-2 + 1, F 2k] 피보나치 수는 F 2k-1입니다. 따라서 이전에 제거한 피보나치 수를 반복 할 수 없으며 빼낸 양수 사이에 간격이 생깁니다. 수에 결합}

하부는 F 2K + 1 - F _{2K + 1 = -F 2K-1 + 1을 의미} 그 숫자가 음수이면, "최고"음의 간격 [F _2k-1 +1, F _2k-3]이므로 F2k-2 인 가장 높은 음수 피보나치 수를 얻을 수 있습니다. 그러므로 우리는 더 낮은 차수의 피보나치 수를 꺼낼 것입니다.

피보나치 수를 음수로 설정하면 우리 창을 한 단계 아래로 이동하는 것과 비슷한 수학을 나타낼 수 있습니다.

우리가 세 개의 연속 피보나치 수를 추적 할 수 있으며,이를 효과적으로 구현하기 위해 (F _K-1, F _K, F _{K + 1}) 우리가 발견 될 때까지 (또는 하향) 위쪽으로 이동 계속 번호 n를 포함한 범위 우리는 우리의 (아마도 부정적인) 피보나치 수를 빼고 우리가 끝날 때까지 창을 0쪽으로 되돌릴 수 있습니다. 전체적으로 이것은 시간 O (log n)에서 실행됩니다.