在 python 代码中编写递归伪代码问题
Write recursive pseudocode problem in python code
我无法解决以下问题:
我应该在 python 中实现伪代码。 h 只是一些给定的列表。我已经尝试过各种东西,例如最近的:
def _p_recursion(n,i):
if n == 0:
return h[n+i]
for i in range(1,n+1):
s = 0
s = h[i] + _p_recursion(n-i,i)
v.append(s)
return s
v=[]
h =[0,3,11,56,4]
_p_recursion(2,0)
我知道为什么它不起作用,但我无法想出解决方案。这感觉像是一个非常简单的问题,但我已经坚持了几个小时。我对递归函数不是很有经验,只有非常基本的函数。我想不出一个。感觉想出解决方案的最简单方法必须是将 p(n) 的所有可能输出附加到一个数组中,然后可以轻松找到最大值。对于以上代码中的值,列表 v 中缺少 11。任何人都可以提示我如何使用 python 语句解决此问题,如果,而...
提前致谢!
代码
def p(n):
" Implements function shown in image "
if n == 0:
return 0
# Finds the max of h[i] + p(n-i)
# with p(n-i) found recursively
# Gets access to h from the global namespace
return max(h[i] + p(n-i) for i in range(1, n+1))
更明确的递归函数
def p(n):
" Implements function shown in image "
if n == 0:
return 0
# Stores previous results in an array for formula
# then computes max
previous = []
for i in range(1, n+1):
previous.add(h[i] + p(n-i))
return max(previous)
测试
h = range(10)
for i in range(len(h)):
print(i, p(i))
输出
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
性能
darrylg 解决方案
def p_dg(n):
" Implements function shown in image "
if n == 0:
return 0
# Finds the max of h[i] + p(n-i)
# with p(n-i) found recursively
# Gets access to h from the global namespace
return max(h[i] + p_dg(n-i) for i in range(1, n+1))
海报(Karl)解决方案
def p(n,m):
if n == 0:
return 0
for i in range(1,n+1):
s = h[i] + p(n-i,m)
m[n-1].append(s)
return max(m[n-1])
def p_caller(n):
if type(n) != int:
return
m =[]
for g in range(n):
m.append([])
return p(n,m)
带缓存(记忆)的darrylg解决方案
def p_cache(n, cache = {}):
if n in cache:
return cache[n]
if n == 0:
return 0
cache[n] = max(h[i] + p_cache(n-i) for i in range(1, n+1))
return cache[n]
计时(秒)
darrylg method
time taken: 0.20136669999965306
Poster method (Karl)
time taken: 26.77383000000009
darrylg with memoization
time taken: 0.00013790000002700253
因此缓存大大提高了性能。
时序码
import time
import random
# timing software allows timing recursive functions
# Source:
def profile(f):
is_evaluating = False
def g(x):
nonlocal is_evaluating
if is_evaluating:
return f(x)
else:
start_time = time.perf_counter()
is_evaluating = True
try:
value = f(x)
finally:
is_evaluating = False
end_time = time.perf_counter()
print('time taken: {time}'.format(time=end_time-start_time))
return
return g
# darrylg method
@profile
def p_dg(n):
" Implements function shown in image "
if n == 0:
return 0
# Finds the max of h[i] + p(n-i)
# with p(n-i) found recursively
# Gets access to h from the global namespace
return max(h[i] + p_dg(n-i) for i in range(1, n+1))
# Poster (Karl) method
def p(n,m):
if n == 0:
return 0
for i in range(1,n+1):
s = h[i] + p(n-i,m)
m[n-1].append(s)
return max(m[n-1])
@profile
def p_caller(n):
if type(n) != int:
return
m =[]
for g in range(n):
m.append([])
return p(n,m)
# darrylg with caching (Memoization)
@profile
def p_cache(n, cache = {}):
if n in cache:
return cache[n]
if n == 0:
return 0
cache[n] = max(h[i] + p_cache(n-i) for i in range(1, n+1))
return cache[n]
h = [random.randint(0, 100) for _ in range(18)]
l = 17
print('darrylg method')
p_dg(l)
print('Poster method (Karl)')
p_caller(l)
print('darrylg with memoization')
p_cache(l)
我无法在之前的 post 中评论我的代码,因此我将其写在这里:
(我的问题解决方案)
def p(n,m):
if n == 0:
return 0
for i in range(1,n+1):
s = h[i] + p(n-i,m)
m[n-1].append(s)
return max(m[n-1])
def p_caller(n):
if type(n) != int:
return
m =[]
for g in range(n):
m.append([])
return p(n,m)
我永远不会只调用 p() p_caller()
DarrylG 问题解决方案:
def p(n):
if n == 0:
return 0
# Finds the max of h[i] + p(n-i)
# with p(n-i) found recursively
# Gets access to h from the global namespace
return max(h[i] + p(n-i) for i in range(1, n+1))
这些方法在最坏情况下的时间复杂度有何不同?为什么?
我无法解决以下问题:
我应该在 python 中实现伪代码。 h 只是一些给定的列表。我已经尝试过各种东西,例如最近的:
def _p_recursion(n,i):
if n == 0:
return h[n+i]
for i in range(1,n+1):
s = 0
s = h[i] + _p_recursion(n-i,i)
v.append(s)
return s
v=[]
h =[0,3,11,56,4]
_p_recursion(2,0)
我知道为什么它不起作用,但我无法想出解决方案。这感觉像是一个非常简单的问题,但我已经坚持了几个小时。我对递归函数不是很有经验,只有非常基本的函数。我想不出一个。感觉想出解决方案的最简单方法必须是将 p(n) 的所有可能输出附加到一个数组中,然后可以轻松找到最大值。对于以上代码中的值,列表 v 中缺少 11。任何人都可以提示我如何使用 python 语句解决此问题,如果,而...
提前致谢!
代码
def p(n):
" Implements function shown in image "
if n == 0:
return 0
# Finds the max of h[i] + p(n-i)
# with p(n-i) found recursively
# Gets access to h from the global namespace
return max(h[i] + p(n-i) for i in range(1, n+1))
更明确的递归函数
def p(n):
" Implements function shown in image "
if n == 0:
return 0
# Stores previous results in an array for formula
# then computes max
previous = []
for i in range(1, n+1):
previous.add(h[i] + p(n-i))
return max(previous)
测试
h = range(10)
for i in range(len(h)):
print(i, p(i))
输出
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
性能
darrylg 解决方案
def p_dg(n):
" Implements function shown in image "
if n == 0:
return 0
# Finds the max of h[i] + p(n-i)
# with p(n-i) found recursively
# Gets access to h from the global namespace
return max(h[i] + p_dg(n-i) for i in range(1, n+1))
海报(Karl)解决方案
def p(n,m):
if n == 0:
return 0
for i in range(1,n+1):
s = h[i] + p(n-i,m)
m[n-1].append(s)
return max(m[n-1])
def p_caller(n):
if type(n) != int:
return
m =[]
for g in range(n):
m.append([])
return p(n,m)
带缓存(记忆)的darrylg解决方案
def p_cache(n, cache = {}):
if n in cache:
return cache[n]
if n == 0:
return 0
cache[n] = max(h[i] + p_cache(n-i) for i in range(1, n+1))
return cache[n]
计时(秒)
darrylg method
time taken: 0.20136669999965306
Poster method (Karl)
time taken: 26.77383000000009
darrylg with memoization
time taken: 0.00013790000002700253
因此缓存大大提高了性能。
时序码
import time
import random
# timing software allows timing recursive functions
# Source:
def profile(f):
is_evaluating = False
def g(x):
nonlocal is_evaluating
if is_evaluating:
return f(x)
else:
start_time = time.perf_counter()
is_evaluating = True
try:
value = f(x)
finally:
is_evaluating = False
end_time = time.perf_counter()
print('time taken: {time}'.format(time=end_time-start_time))
return
return g
# darrylg method
@profile
def p_dg(n):
" Implements function shown in image "
if n == 0:
return 0
# Finds the max of h[i] + p(n-i)
# with p(n-i) found recursively
# Gets access to h from the global namespace
return max(h[i] + p_dg(n-i) for i in range(1, n+1))
# Poster (Karl) method
def p(n,m):
if n == 0:
return 0
for i in range(1,n+1):
s = h[i] + p(n-i,m)
m[n-1].append(s)
return max(m[n-1])
@profile
def p_caller(n):
if type(n) != int:
return
m =[]
for g in range(n):
m.append([])
return p(n,m)
# darrylg with caching (Memoization)
@profile
def p_cache(n, cache = {}):
if n in cache:
return cache[n]
if n == 0:
return 0
cache[n] = max(h[i] + p_cache(n-i) for i in range(1, n+1))
return cache[n]
h = [random.randint(0, 100) for _ in range(18)]
l = 17
print('darrylg method')
p_dg(l)
print('Poster method (Karl)')
p_caller(l)
print('darrylg with memoization')
p_cache(l)
我无法在之前的 post 中评论我的代码,因此我将其写在这里: (我的问题解决方案)
def p(n,m):
if n == 0:
return 0
for i in range(1,n+1):
s = h[i] + p(n-i,m)
m[n-1].append(s)
return max(m[n-1])
def p_caller(n):
if type(n) != int:
return
m =[]
for g in range(n):
m.append([])
return p(n,m)
我永远不会只调用 p() p_caller() DarrylG 问题解决方案:
def p(n):
if n == 0:
return 0
# Finds the max of h[i] + p(n-i)
# with p(n-i) found recursively
# Gets access to h from the global namespace
return max(h[i] + p(n-i) for i in range(1, n+1))
这些方法在最坏情况下的时间复杂度有何不同?为什么?