nov 20 2009

Implementazione della funzione di Ackermann

Categoria: Programmazione Java — saverio @ 17:55

La funzione di Ackermann è una funzione f(x,y,z) che ha come dominio l’insieme delle terne di numeri naturali e come codominio i numeri naturali.

ackermann

Essa è un esempio di funzione ricorsiva che non è primitiva ricorsiva poiché cresce più velocemente di qualsiasi funzione ricorsiva primitiva.

Qui il codice java che implementa questa funzione:

Ackermann.java

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public class Ackermann {
 
 static long count = 0;
 
 private static long h(long m, long n) {
  
  count++;
  
  if (m == 0) {
   return n + 1;
  }
  if (n == 0) {
   return h(m-1, 1);
  }
  
  return h(m-1, h(m,n-1) );
 }
 
 private static long ack(long n) {
  return h(n, n);
 }
 
 public static void main(String[] args) {
  
  if (args.length != 1) {
   System.out.println("usage: Ackermann <number>\n\twhere number is a positive integer");
   System.exit(1);
  }
  
  long n = Long.valueOf(args[0]);
  
  count = 0;
  long retValue = ack(n);  
  System.out.println("ack(" + n + ") = " + retValue + " [recursive calls = "+ count +"]");
 
  
  System.exit(0);
 }
 
}

Il meccanismo di calcolo della funzione è estremamente semplice quanto pesante dal punto di vista computazionale. Questi sono i risultati ottenuti:

  • ack(0) = 1  [recursive calls = 1]
  • ack(1) = 3  [recursive calls = 4]
  • ack(2) = 7  [recursive calls = 27]
  • ack(3) = 61 [recursive calls = 2432]

Non riesco a calcolare ack(4) causa stack overflow (Exception in thread “main” java.lang.StackOverflowError).

Tags: ,

3 Commenti a “Implementazione della funzione di Ackermann”

  1. Piero says:
    novembre 23rd, 2009 alle 20:46

    Possiede una dimostrazione più precisa della nozione di “crescere velocemente” per giustificare l’affermazione che tale funzione non appartiene alla classe delle PrR ??

  2. tomax says:
    dicembre 31st, 2009 alle 14:49

    Seguo da molto questo blog e devo dire che mi piace molto, c’è il difetto che tra un post e l’altro passano secoli.
    ma nonostante ciò complimenti

  3. ssssssssss says:
    giugno 26th, 2010 alle 23:53

    Perché invece non posti un metodo per calcolare EFFICIENTEMENTE tale funzione, magari non in Java che è l’esatto opposto dell’efficienza? :)

Scrivi un commento