문자열에 피보나치 서열의 일부가 포함되어 있는지 확인하십시오.

Question

주어진 문자열에 피보나치 서열이 존재하는지 알아내는 알고리즘을 생성하려면 어떤 방법을 따라야합니까?

문자열에는 공백이없는 숫자 만 포함되며 둘 이상의 시퀀스가있을 수 있습니다. 모두 찾아야합니다.

Answer 1

여기 제가 어떻게 접근할까요?

주요 알고리즘 은 세 쌍을 검색 할 수 있습니다. 그런 다음 최대한 긴 시퀀스로 확장하려고합니다.

이렇게하면 세 쌍둥이를 찾는 하위 문제가 있습니다. 따라서 피보나치 숫자를 찾기 위해 문자열을 스캔하는 경우, 다음 숫자는 같은 자릿수 또는 하나 이상의 숫자를 가져야한다는 이점이 있습니다.

문자열이 "987159725844"이고 "[987] 159725844"를 고려하고 있다면 다음으로보아야 할 것은 "987 [159] 725844"및 "987 [1597] 25844"입니다. 다음 부분은 "[2584] 4"또는 "[25844]"입니다.

일단 3 자리가 있으면 C - B == B - A으로 산술 진행을 확인할 수 있습니다.그들은 당신이 지금 비율이 대략 1.6인지 확인한 다음 fibonacci 반복을 초기 조건 1,1로 거꾸로 실행하여 fibonacci 시퀀스에 있는지 확인할 수 있습니다. 전체 알고리즘은 다음 폭 1로 시작하는 트리플을 모두 찾고 통해 스캔에 의해 작동합니다

, 그때는 용융없이 (있는 경우에도 가능을 수행하기 위해 매우 열심히해야한다, 2 폭 3 위로

Answer 2

첫 번째 숫자의 숫자가 6 자리 미만이어야한다고 말하면 25 개의 피보나치 숫자 중 하나 (모든 숫자가 6 자리 미만인 경우 25 자리)를 검색하고이 숫자를 확장 해보십시오 1 개의 번호 순서. 당신은 적어도 3 개 개의 숫자의 순서를 찾고있을 경우에도 일을 속도를 높일 수

: 당신의 갱신 후

.

먼저 25 개의 첫 번째 fibonnaci- 숫자 중 하나로 시작하는 25 개의 3-number- 문자열을 미리 작성하십시오. 위의 단일 피보나치 숫자 검색보다 훨씬 적은 일치를 제공해야합니다.

(위에서 설명한 것과 같이 검색된 3 자리 수열을 확장하는 것보다) 검색이 필요합니다.

Answer 3

흥미로운 피보나치 항목 (6 자리 이하의 숫자는 30 개 이하)을 찾아서 배열에 저장해야합니다.

그런 다음, 루프 모든 사용자 입력 문자열의 위치 및시 거기 긴 가능 피보나치 수를 찾아보십시오 (즉, 당신은 배열 뒤로을 찾아야합니다).

일부 Fib 번호가있는 경우 다음 위치 문자열의 모든 항목을 일치 시키려고하는 경우에만 현재 위치에서 끝까지 배열을 통과하는 보조 알고리즘으로 분기해야합니다. 일치가 끝나면 입력 문자열을 현재 위치에서 계속 검색하려면 기본 알고리즘으로 돌아 가야합니다.

이 두 알고리즘은 재귀 적이거나 너무 비싸지 않습니다.

갱신

좋아. 테이블이 허용되지 않는 경우에도 첫 번째 루프에서 bext Fibo 번호를 얻는 방법으로 대체 할 수 있습니다. 인덱싱 대신 공식을 적용하십시오.