我需要一个函数,它接受n并返回2n - 1。听起来很简单,但该函数必须是递归的。到目前为止,我只有2n:
我需要一个递归函数,它接收参数n,并返回计算结果2n - 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+...+2n-1,可以用一个递归函数表示(不需要减去2的幂再减1)。
提示:1+2*(1+2*(...))
下面是解决方案,如果你想先尝试提示,请勿查看。
当 n
大于零时(正如问题陈述中实际承诺的那样),此方法有效:
def required_steps(n):
if n == 1: # changed because we need one less going down
return 1
return 1 + 2 * required_steps(n-1)
更健壮的版本也会处理零和负值:
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)
(添加非整数的检查留作练习。)
required_steps(0)
现在会导致无限递归。 - Mulan2^0 - 1
等于 0。为这种情况添加另一个 if
语句。 - h4z3要用递归方法解决问题,你需要找出如何将具有不同输入的相同函数定义为具有给定输入的函数。在这种情况下,由于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
有一个占位符来记住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)
使用一个额外的参数来存储结果,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)
输出结果相同
else
子句。 - rafaelcr * 2
更改为 r << 1
,这难道就“完全不可读”了吗? - Mulann
次,然后减去1。似乎比必要的还不够优雅,尽管整个过程是一种低效性与(1<<n) - 1
之间的对比练习。 - Peter Cordes除了之前提供的所有精彩答案,下面将展示如何使用内部函数实现。
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))
获取“-1”偏移量的一种方法是在第一个函数调用的返回值中使用具有默认值的参数,然后在递归调用期间显式地将偏移参数设置为零。
def required_steps(n, offset = -1):
if n == 0:
return 1
return offset + 2 * required_steps(n-1,0)
1 << n
不会溢出。这似乎是一种将(1<<n)-1
分解成多个步骤的练习,也许像某些答案所显示的那样,逐位设置每个位。 - Peter CordesC:\MyFolder
中包含了什么。 - Flater