Записать рекурсивную проблему псевдокода в python коде

Question

У меня возникла проблема при решении проблемы ниже:

Я должен реализовать псевдокод в python. ч просто какой-то заданный список. Я перепробовал все виды вещей, совсем недавно, например:

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) в массив, и тогда можно легко найти максимум. Для значений в коде выше 11 отсутствует в списке v. Кто-нибудь может дать мне подсказку, как решить эту проблему, используя операторы python для, если, в то время как ...

Заранее спасибо!

Answer 1

Код

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))

Плакат (Карл ) решение

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: https://stackoverflow.com/questions/29560643/python-counting-executing-time-of-a-recursion-function-with-decorator
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)

Answer 2

Я не смог прокомментировать свой код в предыдущем посте, поэтому я пишу его здесь: (мое решение проблемы)

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))

Какая разница в сложности времени наихудшего случая между этими методами и почему?