[python] 재귀 함수로 2 ** n-1을 쓰는 방법?

Program / 글쓴이

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의 전역 값을 할당하고 적절한 비교를 통해 반복합니다.