Ackermann işlevi n iç içe döngülere karşı

Question

Hesaplama ile ilgili bir kitap (Minksy 1967) üzerinde çalışıyorum ve döngüsel olarak tanımlanan bir işleve özyinelemeli bir işlevi ilişkilendirmek için zor bir zaman geçiriyorum.

Ackermann fonksiyonu (Python ile tüm kodu):

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

Ve n iç içe döngüler ile hesaplar bir işlevi:

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

A Özellikle o iki fonksiyonları arasındaki ilişkiyi bulmak için sorar Bunu yazmanın özyinelemeli yolu (bir döngü ile):

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

Ya da tamamen tekrarlar Bunu yazmanın yolu:

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) 

Bu iki işlevle ilgili basit bir yol var mı? Bir sisin içinde geziniyormuşum gibi hissediyorum - bu tür problemlere nasıl yaklaşacağımı bana verebileceğin herhangi bir anlayış büyük ölçüde takdir edilecek. Ayrıca, üçüncü bir parametrenin girilmesi olmadan tamamen özyinelemeli döngü işlevini uygulamak için bir yolu var mı? Teşekkürler.

Answer 1

Uhm ... Bunun size çok yardımcı olacağını sanmıyorum, ben de biraz şaşırdım, ama işte benim düşüncelerim.

• Ackerman (0, m) == (p 0, m)
• Ackerman (1, m + 1) == (p 1, m)

düzenle - beklemek işlevi yanlış anladım. Daha sonra bunu daha çok düşüneceğim ve eğer bir şey düşünürsem güncelleme yapacağım!