Принцип действия Аккермана
6 Hummus [2012-10-01 20:30:00]
Мне сложно понять, как работает функция Аккермана. Я думаю, что мое понимание рекурсии ошибочно?
Вот код в Python:
def naive_ackermann(m, n):
global calls
calls += 1
if m == 0:
return n + 1
elif n == 0:
return naive_ackermann(m - 1, 1)
else:
return naive_ackermann(m - 1, naive_ackermann(m, n - 1))
Если я выполняю вызов функции naive_ackermann (3,4), как и почему я получаю 125?
Комментарии будут оценены.
Спасибо
function python recursion
6 ответов
12 Решение Abhranil Das [2012-10-01 21:13:00]
Вычисление A (3,4) не так просто или коротко, как может показаться сначала из небольших значений аргументов. Сложность (# шагов итерации) функции Аккермана растет очень быстро с ее аргументами, как и вычисленный результат.
Вот определение функции Аккермана от Wikipedia:
Как вы можете видеть, на каждой итерации значение m уменьшается до тех пор, пока оно не достигнет 0 в том, что будет последним шагом, после чего окончательное значение n (+1) дает вам ответ. Поэтому для ответа вам нужно только проследить, как изменяется n, когда вы проходите рекурсивные итерации. Для того, почему функция Аккермана растет настолько быстро, вы можете взглянуть на подраздел this вики.
Как уже упоминал Йоран Бисли, A (3,4) действительно 125, как написано в Википедии. Однако процесс достижения этого результата не очень короткий. Фактически, как я выяснил, требуется вычислить по рекурсии 315 значения функции Аккермана, чтобы получить A (3,4), количество требуемых итераций примерно пропорционально таковому.
Если вы все еще хотите представить себе, как этот результат достигнут, вы можете взглянуть на на этой странице, который оживляет вычисление каждого шага рекурсии. Будьте осторожны, однако, что A (3,4) займет навсегда, чтобы закончить анимацию здесь, но по крайней мере вы можете получить представление об этом процессе с меньшими аргументами.
7 Janne Karila [2012-10-01 21:30:00]
Здесь версия, которая выводит объяснение:
def A(m, n, s="%s"):
print s % ("A(%d,%d)" % (m, n))
if m == 0:
return n + 1
if n == 0:
return A(m - 1, 1, s)
n2 = A(m, n - 1, s % ("A(%d,%%s)" % (m - 1)))
return A(m - 1, n2, s)
print A(2,2)
С аргументами 2,2 это результат. (С 3,4 он становится уже слишком большим)
A(2,2)
A(1,A(2,1))
A(1,A(1,A(2,0)))
A(1,A(1,A(1,1)))
A(1,A(1,A(0,A(1,0))))
A(1,A(1,A(0,A(0,1))))
A(1,A(1,A(0,2)))
A(1,A(1,3))
A(1,A(0,A(1,2)))
A(1,A(0,A(0,A(1,1))))
A(1,A(0,A(0,A(0,A(1,0)))))
A(1,A(0,A(0,A(0,A(0,1)))))
A(1,A(0,A(0,A(0,2))))
A(1,A(0,A(0,3)))
A(1,A(0,4))
A(1,5)
A(0,A(1,4))
A(0,A(0,A(1,3)))
A(0,A(0,A(0,A(1,2))))
A(0,A(0,A(0,A(0,A(1,1)))))
A(0,A(0,A(0,A(0,A(0,A(1,0))))))
A(0,A(0,A(0,A(0,A(0,A(0,1))))))
A(0,A(0,A(0,A(0,A(0,2)))))
A(0,A(0,A(0,A(0,3))))
A(0,A(0,A(0,4)))
A(0,A(0,5))
A(0,6)
7
3 Joran Beasley [2012-10-01 20:36:00]
ackerman(3,4)
=ackerman(2,ackerman(3,3)) = ackerman(2,61) #ackerman(3,3) = 61 ...
=ackerman(1,ackerman(2,60)) = ackerman (1,123) #ackerman(2,60) = 123...
=ackerman(0,ackerman(1,122)) = ackerman (0,124) #ackerman(1,122) = 124...
= 124+1 = 125
см. http://goo.gl/jDDEA здесь, чтобы визуализировать ackerman(2,3) (слишком долго было визуализировать 3,4)
0 user7217035 [2016-11-27 20:58:00]
def ackermann(m,n):
"""computes the value of the Ackermann function for the input integers m and n.
the Ackermann function being:
A(m,n)=n+1 if m=0
=A(m-1,1) if m>0 and n=1
=A(m-1,A(m,n-1) if m>0 and n>0"""
if m==0:
print (n+1)
return n+1
elif m>0 and n==0:
print ("ackermann(",m-1,",",1,")") #just 2 chk intrmdt val. and no. of steps invlvd.can be dltd if necessary
return ackermann(m-1,1)
elif m>0 and n>0:
print ("Ackermann(",m-1,",","Ackermann(",m,",",n-1,")",")") #just 2 chk intrmdt val. and no. of steps invlvd.can be dltd if necessary
return ackermann(m-1,ackermann(m,n-1))
Просто сделайте простую модификацию вашего кода, чтобы программа печатала все шаги, а не только результат. Код должен выглядеть примерно так, как в конце этой страницы. Запустите его (может занять несколько секунд), а затем вы сможете оценить, как вычисляется функция Ackermann.
0 Lajos Arpad [2012-10-01 23:24:00]
Вот реализация Java:
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package ackerman;
import java.util.Vector;
/**
*
* @author LajosArpad
*/
public class Main {
public static String status = "ackerman(3, 4)";
public static int ackerman(int m, int n)
{
String temp = status.substring(status.lastIndexOf("ackerman"));
while (temp.indexOf("))") >= 0)
{
temp = temp.substring(0, temp.length() - 2);
}
boolean foo = status.indexOf(")") == status.lastIndexOf(")");
String t1 = foo ? "" : status.substring(0, status.lastIndexOf("ackerman") - 1);
String t2 = foo ? "" : status.substring(status.lastIndexOf("ackerman"));
if (t2.length() > 0)
{
t2 = t2.substring(t2.indexOf(")") + 1);
}
if (m == 0)
{
status = t1 + (n + 1) + t2;
System.out.println(" = " + status);
return n + 1;
}
else if (n == 0)
{
status = t1 + "ackerman(" + (m - 1) + ", 1)" + t2;
System.out.println(" = " + status);
return ackerman(m - 1, 1);
}
else
{
status = t1 + " ackerman(" + (m - 1) + ", ackerman(" + m + ", " + (n - 1) + "))" + t2;
System.out.println(" = " + status);
return ackerman(m - 1, ackerman(m, n - 1));
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
System.out.println(Main.ackerman(3, 4));
// TODO code application logic here
}
}
Просто запустите этот код, и вы узнаете, как работает ackerman. Я не владею Python, но надеюсь, что это не проблема.
0 Maksym Polshcha [2012-10-01 20:49:00]
Вот очень хорошее описание, что это такое, для чего оно и его место в теории вычислимости http://en.wikipedia.org/wiki/Ackermann_function