n을 취하고 2 n -1을 반환하는 함수가 필요합니다 . 충분히 간단하게 들리지만 함수는 재귀 적이어야합니다. 지금까지 나는 단지 2 n :
def required_steps(n):
if n == 0:
return 1
return 2 * req_steps(n-1)
운동 상태 : “매개 변수 n이 항상 양의 정수이고 0보다 크다고 가정 할 수 있습니다.”
답변
2**n -1
또한 1 + 2 + 4 + … + 2 n-1 이며 단일 재귀 함수로 만들 수 있습니다 (두 번째는 2의 거듭 제곱에서 1을 빼지 않음).
힌트 : 1 + 2 * (1 + 2 * (…))
아래 해결책은 먼저 힌트를 시도하고 있는지 확인하지 마십시오.
이것은 n
실제로 문제 설명에서 약속 한 것처럼 0보다 큰 것이 보장되는 경우 작동합니다 .
def required_steps(n):
if n == 1: # changed because we need one less going down
return 1
return 1 + 2 * required_steps(n-1)
보다 강력한 버전은 0과 음수 값도 처리합니다.
def required_steps(n):
if n < 0:
raise ValueError("n must be non-negative")
if n == 0:
return 0
return 1 + 2 * required_steps(n-1)
(정수가 아닌 사람에 대한 검사 추가는 연습으로 남습니다.)
답변
재귀 접근 방식의 문제를 해결하려면 다른 입력을 사용하는 동일한 함수의 관점에서 주어진 입력으로 함수를 정의하는 방법을 찾아야합니다. 이 경우 이후부터 f(n) = 2 * f(n - 1) + 1
수행 할 수 있습니다.
def required_steps(n):
return n and 2 * required_steps(n - 1) + 1
그래서:
for i in range(5):
print(required_steps(i))
출력 :
0
1
3
7
15
답변
정말 재귀적인 부분을 다른 함수로 추출 할 수 있습니다
def f(n):
return required_steps(n) - 1
또는 플래그를 설정하고 빼기시기 만 정의 할 수 있습니다.
def required_steps(n, sub=True):
if n == 0: return 1
return 2 * required_steps(n-1, False) - sub
>>> print(required_steps(10))
1023
답변
결과에 추가 매개 변수를 사용하여 r
–
def required_steps (n = 0, r = 1):
if n == 0:
return r - 1
else:
return required_steps(n - 1, r * 2)
for x in range(6):
print(f"f({x}) = {required_steps(x)}")
# f(0) = 0
# f(1) = 1
# f(2) = 3
# f(3) = 7
# f(4) = 15
# f(5) = 31
비트 왼쪽 시프트를 사용하여 쓸 수도 있습니다 <<
.-
def required_steps (n = 0, r = 1):
if n == 0:
return r - 1
else:
return required_steps(n - 1, r << 1)
출력은 같습니다
답변
바로 그 첫 번째 단계 즉위한 후 원래 N의 값을 기억하는 자리 가지고 n == N
, 수익을2^n-1
n = 10
# constant to hold initial value of n
N = n
def required_steps(n, N):
if n == 0:
return 1
elif n == N:
return 2 * required_steps(n-1, N) - 1
return 2 * required_steps(n-1, N)
required_steps(n, N)
답변
“-1″의 오프셋을 얻는 한 가지 방법은 기본값을 가진 인수를 사용하여 첫 번째 함수 호출의 리턴에이를 적용한 다음 재귀 호출 중에 오프셋 인수를 명시 적으로 0으로 설정하는 것입니다.
def required_steps(n, offset = -1):
if n == 0:
return 1
return offset + 2 * required_steps(n-1,0)
답변
이전에 제공된 모든 멋진 답변 외에도 아래는 내부 함수를 사용한 구현을 보여줍니다.
def outer(n):
k=n
def p(n):
if n==1:
return 2
if n==k:
return 2*p(n-1)-1
return 2*p(n-1)
return p(n)
n=5
print(outer(n))
기본적으로 n에 k의 전역 값을 할당하고 적절한 비교를 통해 반복합니다.