2013 – 6

di

È dato il seguente programma:

#include 

int F(int x) 
{
   if(x <= 0)
      return 0;
   else
      return 1+G(x-1);
}
int G(int x) 
{
   if(x <= 0)
      return 0;
   else
      return 1+F(x-2);
}

void main() 
{
   printf("%d", F(100));
}

Cosa viene visualizzato a video dall'esecuzione di main()?

Soluzione: 67

Osserva

  • F(-1) = 0
  • F(0) = 0
  • F(1) = 1+G(0) = 1+0 = 1
  • F(2) = 1+G(1) = 1+1+F(-1) = 2+0 = 2
  • F(3) = 1+G(2) = 1+1+F(0) = 2+0 = 2
  • F(4) = 1+G(3) = 1+1+F(1) = 2+1 = 3
  • F(5) = 1+G(4) = 1+1+F(2) = 2+2 = 4
  • F(6) = 1+G(5) = 1+1+F(3) = 2+2 = 4
  • ...

quindi

  • 1: (1-2-2)
  • 4: (3-4-4)
  • 7: (5-6-6)
  • 10: (7-8-8)
  • 13: (9-10-10)
  • 16: (11-12-12)
  • ...

cioè

F(3n+1) = 2n+1
F(100) = 67