Функция Аккермана против n вложенных циклов - PullRequest
Новая
       37

Функция Аккермана против n вложенных циклов

5 голосов
/ 25 октября 2010

Я работаю в своей книге по вычислениям (Minksy, 1967) и с трудом связываю рекурсивную функцию с функцией, определенной в терминах циклов. В частности, он просит найти связь между двумя функциями:

Функция Аккермана (весь код на python): 

def a(n,m):
    if n==0:
        return m+1
    if m==0:
        return a(n-1,1)
    return a(n-1,a(n,m-1))

И функция, которая вычисляет n вложенных циклов: 

def p(n,m):
    for i_1 in range(m):
        for i_2 in range(m):
           ...
             for i_n in range(m):
                  m+=1

Рекурсивный способ написать это (с одним циклом): 

def p(n,m):
     if n==0:
         return m+1
     for i in range(m):
         m=p(n-1,m)
     return m

Или полностью рекурсивный способ написать это будет: 

def p(n,m):
    return P(n,m,m)
def P(n,k,m):
    if n==0:
        return m+1
    if k==1:
        return P(n-1,m,m)
    m=P(n,k-1,m)
    return P(n-1,m,m)

Есть ли какой-то простой способ связать эти две функции? Я чувствую, что ползаю в тумане - любая оценка, которую вы могли бы дать мне в том, как подходить к такого рода проблемам, будет принята с благодарностью. Кроме того, есть ли способ реализовать полностью рекурсивную функцию цикла без введения третьего параметра? Спасибо.

1 Ответ

1 голос
/ 25 октября 2010

Хм ... Не думаю, что это вам сильно поможет, я тоже немного сбит с толку, но вот мои мысли.

  • Аккерман (0, м) == р (0, м)
  • Аккерман (1, м + 1) == р (1, м)

edit - подождите, я думаю, что я неправильно скопировал функцию. Я подумаю об этом позже, и если я что-нибудь придумаю, я обновлюсь!

...