5

私は計算に関する本（Minksy 1967）を読み進めており、再帰関数をループで定義された関数に関連付けるのに苦労しています。具体的には、彼は2つの機能間の関係を見つけるように求めています。

アッカーマン関数（すべて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

これを（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)

これらの2つの機能を関連付ける簡単な方法はありますか？霧の中を這い回っているような気がします。この種の問題にどのように取り組むかについての洞察をいただければ幸いです。また、3番目のパラメーターを導入せずに完全再帰ループ関数を実装する方法はありますか？ありがとう。

4

1 に答える 1

1

うーん...これはあまり役に立たないと思います。私もちょっと困惑していますが、ここに私の考えがあります。

  • アッカーマン(0, m) == p(0, m)
  • アッカーマン(1, m + 1) == p(1, m)

編集 - 待ってください関数をミスコピーしたと思います。これについては後で詳しく考えます。また、何か思いついたら更新します。

于 2010-10-24T20:56:10.693 に答える