import java.util.*;

class BlocG {
    public int parametreN;
    public int adresseDeRetour;
    public int valeurDeRetour;
    BlocG(int ar, int n) {
	adresseDeRetour = ar;
	parametreN = n;
	valeurDeRetour = -1;
    }
    public String toString() {
	return "{n="+parametreN+",retour="+adresseDeRetour+",valeur="+valeurDeRetour+"}";
    }
}

public class EX8_2 {
    public static void main(String []a) {
	boolean fin = false;
	int instruction = -2;
	int x=0;
	Stack pile = new Stack();
	BlocG bg, nouveauBloc, blocRetour;
	while (!fin) {
	    System.out.println("Je dois faire l'instruction "+instruction+" la pile est "+pile);
	    switch (instruction) {
	    case -2: // main, initialisation de x à 10
		x = 10;
		instruction = -1;
		break;
	    case -1: // appel à g(x)
		bg = new BlocG(0,x); // quand calcul de g() terminé, il faudra revenir en 0
		pile.push(bg); // transmission bloc d'activation
		instruction = 1; // saut vers première instruction de g()
		break;
	    case 0:
		bg = (BlocG)(pile.pop()); // suppression bloc activation créé à l'appel
		System.out.println("Résultat="+bg.valeurDeRetour);
		fin = true;
		break;
	    case 1: // première instruction de g()
		// cas g(0)
		bg = (BlocG)(pile.peek());
		if (bg.parametreN==0) {
		    bg.valeurDeRetour = 1; // prépare la valeur de retour pour que l'appelant puisse la retrouver
		    instruction = bg.adresseDeRetour; // saut vers l'instruction qui suit l'appel, on retourne là on l'on nous a dit de retourner
		} else {
		    instruction = 2;
		}
		break;
	    case 2: // cas N pair
		bg = (BlocG)(pile.peek());
		if (bg.parametreN%2==0) {
		    nouveauBloc = new BlocG(3,bg.parametreN/2); // quand calcul de g() terminé il faudra revenir en 3
		    pile.push(nouveauBloc); // transmission bloc activation
		    instruction = 1; // saut vers la première instruction de g()
		} else {
		    instruction = 4;
		}
		break;
	    case 3: // retour de G(n/2)
		blocRetour = (BlocG)(pile.pop()); // on enlève le bloc transmis au moment de l'appel récursif
		bg = (BlocG)(pile.peek()); // on récupère les paramètres de cet appel ci
		bg.valeurDeRetour = bg.parametreN*blocRetour.valeurDeRetour; // on calcule n*g(n/2) qu'on range dans le bloc d'activation courant
		instruction = bg.adresseDeRetour; // on retourne là où l'on nous a dit de retourner
		break;
	    case 4: // cas N impair
		bg = (BlocG)(pile.peek());
		nouveauBloc = new BlocG(5,(bg.parametreN-1)/2); // quand calcul de g() terminé il faudra revenir en 5
		pile.push(nouveauBloc); // transmission bloc d'activation
		instruction = 1; // saut vers la première instruction de g()
		break;
	    case 5: // retour de G(n-1/2)
		blocRetour = (BlocG)(pile.pop()); // on enlève le bloc transmis au moment de l'appel récursif
		bg = (BlocG)(pile.peek()); // on récupère les paramètres de l'appel courant
		bg.valeurDeRetour = blocRetour.valeurDeRetour; // on calcule 1+g((n-1)/2) qu'on range dans le bloc d'activation courant
		instruction = bg.adresseDeRetour; // on retourne là où l'on nous a dit de retourner
		break;
	    }
	}
    }
}