3
최근 Google Foobar에서 몇 가지 문제를 재미있게 해결해 왔으며 지금은 4 일 이상 그 중 하나에 갇혀있었습니다. 그것은 다음과 같이 정의 된 재귀 함수에 대한 것이다 :재귀 시퀀스 해결
R(0) = 1
R(1) = 1
R(2) = 2
R(2n) = R(n) + R(n + 1) + n (for n > 1)
R(2n + 1) = R(n - 1) + R(n) + 1 (for n >= 1)
도전은 str_S 최대 n되도록 R(n) = S 반환 정수 S의베이스 (10) 문자열 표현되는 함수 answer(str_S) 쓰고있다. 그러한 n이 없으면 "없음"을 반환합니다. 또한 S는 10^25보다 크지 않은 양의 정수가됩니다.
필자는 재귀 함수와 재발 관계를 해결하는 방법에 대해 많은 연구를했지만 운이 없었습니다. 나는 처음 500 개의 숫자를 출력했는데, 나는 각각의 숫자와 아무 관계가 없다는 것을 발견했다. 재귀를 사용하는 다음 코드를 사용 했으므로 숫자가 커지기 시작하면 정말 느려집니다.
def getNumberOfZombits(time):
if time == 0 or time == 1:
return 1
elif time == 2:
return 2
else:
if time % 2 == 0:
newTime = time/2
return getNumberOfZombits(newTime) + getNumberOfZombits(newTime+1) + newTime
else:
newTime = time/2 # integer, so rounds down
return getNumberOfZombits(newTime-1) + getNumberOfZombits(newTime) + 1
: 나는 간단 아무것도 재발 관계를 해결해야하는 경우
Test cases
==========
Inputs:
(string) str_S = "7"
Output:
(string) "4"
Inputs:
(string) str_S = "100"
Output:
(string) "None"
나도 몰라,하지만 하나의 존재로 심지어 홀수 숫자에 대해서도, 나는 그것을하기가 정말로 어렵다고 생각한다. (나는 아직 학교에서 배웠다. 그래서 나는이 주제에 관해서 모든 것이 인터넷 기사에서 나온다).
그래서,이 문제를 마무리하라고 안내 전혀 도움을 환영합니다 :) 대신 수학적으로이 기능을 단순화하기 위해 노력
나는 진보 된 수학과 빠른 매트릭스 지수를 사용해야한다고 생각합니다. –
도움이 될 수도 있습니다 : http://stackoverflow.com/questions/1988804/what-is-memoization-and-how-can-i-use-it-in-python –
@LambdaFairy 아마도 이것입니다! 나는 그것이 많은 차이를 만들지는 않을 것이라고 생각했지만 이전보다 훨씬 빨랐습니다. 감사! 나는 그것을 이것을 구현하려고 노력할 것이다. 만약 내가 트릭을했는지 알려 주겠다. D –