Corrections d'exercices du TD3

Voici la correction des deux premiers exercices du TD 3.

Exercice 1 : traduction inversée

Le programme que cet exercice considère est le suivant :

class ProgTrad {
    static int i;
    static int k;

    public static void main(String[] a) {
        int ic=0;

        while (true) {
            switch (ic++) {
                case 0: i=0; break;
                case 1: k=0; break;
                case 2: if (i>=6) ic+=3; break;
                case 3: k+=i; break;
                case 4: i++; break;
                case 5: ic-=4; break;
                case 6: System.exit(0);
            }
        }
    }
}

On rappelle que la post-incrémentation de la variable ic dans le switch(ic++) ajoute 1 à la variable ic après que le choix de quelle branche prendre est fait. Ainsi, par exemple, quand on est dans la branche case 3: la variable ic vaut 4. Voir ici.

  1. Exécuter ce programme en notant l'évolution du contenu des variables.
Étapeikcommentaire
0??
10?
200
300on ajoute i = 0 à k
410
511on ajoute i = 1 à k
621
723on ajoute i = 2 à k
833
936on ajoute i = 3 à k
1046
11510on ajoute i = 4 à k
12510
13515on ajoute i = 5 à k
14615le test i >= 6 est vrai donc on s'arrête
  1. Préciser ce que calcule ce programme

Déjà, on remarque une structure de boucle, avec un saut conditionnel en case 2 et un saut non conditionnel en case 5 vers le saut conditionnel.

On voit que le programme ajoute la valeur courante de i à k à chaque tour de boucle, et que i est incrémenté de 1 à chaque fois. De plus, on commence avec i contenant 0, et on s'arrête dès que i est supérieur ou égal à 6.

Ainsi, le programme calcule 0+1+2+3+4+5 = 15.

  1. Fort de notre analyse du programme, il est naturel d'utiliser une boucle for comme suit. Si l'on veut coller exactement avec ProgTrad au dessus, notamment au niveau de l'ordre où sont initialisées les variables, on peut faire :
class Prog {
    static int i;
    static int j;

    public static void main(String[] a) {
        i = 0;
        k = 0;
        for (; i < 6; i++) {
            k += i;
        }
    }
}

Bien sûr, le code java plus idiomatique est le suivant :

class Prog {
    public static void main(String[] a) {
        int k = 0;
        for (int i = 0; i < 6; i++) {
            k += i;
        }
    }
}
  1. Écrire une variante de ProgTrad qui remplace l'utilisation des variables i et j par des accès à un unique tableau d'entiers mem.

Il s'agit simplement de représenter chaque variable par une case de tableau mem. La convention que j'utilise ici est que i correspond à la case 0, et k à la case 1. Pratiquement, on remplace chaque occurrence de i par mem[0] et chaque occurrence de k par mem[1].

class Prog {
    static int[] mem = new int[1000];

    public static void main(String[] a) {
        int ic=0;

        while (true) {
            switch (ic++) {
                case 0: mem[0]=0; break;
                case 1: mem[1]=0; break;
                case 2: if (mem[0]>=6) ic+=3; break;
                case 3: mem[1]+=mem[0]; break;
                case 4: mem[0]++; break;
                case 5: ic-=4; break;
                case 6: System.exit(0);
            }
        }
    }
}

Exercice 2 : factorielle

On rappelle que \( n! = 1 \times 2 \times \ldots \times (n-1) \times n \), en convenant que \( 0! = 1 \).

  1. Écrire un programme qui calcule la factorielle d'un nombre (ici, 11).

Pour la calculer itérativement, on utilise un accumulateur k qui commencera égal à 1, et qu'on multiplie par 1, puis par 2, puis par 3... dans une boucle.

class Factorielle {
    public static void main(String[] a) {
        int k = 1;
        for (int i = 1; i < 12; i++) {
            k *= i;
        }
        // ici, k contient la factorielle de 11
    }
}
  1. Traduire le programme Factorielle sur le modèle de Prog

On utilise une variable statique de classe pour chaque variable (ici: i et k) et on traduit la boucle comme dans le cas de ProgTrad par la structure:

    case X: // saut conditionnel vers Y+1 si la condition de la boucle est fausse
    ...
    ...
    case Y: // saut inconditionnel vers X à la fin de la boucle
    case Y+1: // première instruction après la boucle

Dans notre cas, cela donne :

class FactorielleTrad {
    static int i;
    static int k;

    public static void main(String[] a) {
        int ic=0;

        while (true) {
            switch (ic++) {
                case 0: i = 1; break;
                case 1: k = 1; break;
                case 2: if (i >= 12) ic += 3; break;
                case 3: k *= i; break;
                case 4: i++; break;
                case 5: ic -= 4; break;
                case 6: System.exit(0);
            }
        }
    }
}

En résumé, on a remplacé k += i par k *= i et on a changé les valeurs initiales des variables.

Exercice 3 : suite de Syracuse

La suite de Syracuse de l'entier \( n \) est définie par: \( u_0 = n\), et pour tout entier \(k\), si \( u_k \) est pair alors \( u_{k+1} = u_k/2 \) et sinon \( u_{k+1} = 3 u_k + 1 \). On veut savoir au bout de combien d'étapes on tombe sur 1.

  1. Ce programme Java calcule cette valeur :
public class Syracuse {
    public static void main(String[] a) {
        int u = 13; // on prend n = 13
        int vol = 0; // le temps de vol
        while (u != 1) {
            if (u % 2 == 0) {
                u = u/2;
            } else {
                u = 3 * u + 1;
            }
            vol += 1;
        }
        System.out.println("Le temps de vol de 13 est " + vol + "!");
    }
}
  1. On suit la méthode détaillée dans dans les rappels de cours. On décide que u correspond à mem[0] et que vol correspond à mem[1].

On commence par l'initialisation de u et l'impression du message. (On omet les break à chaque ligne du switch)

public static class SyracuseTrad {
    static int ic = 0;
    static int[] mem = new int[1000];

    public static void main(String[] a) {
        while (true) {
            switch (ic++) {
            case 0: mem[0] = 13;
              // TODO: traduire la boucle while
            case Z: System.out.println("Le temps de vol de 13 est " + mem[1] + "!");
            case Z+1: System.exit(0);
            }
        }
    }
}

Ensuite on traduit la boucle while avec un saut conditionnel au début et un saut inconditionnel à la fin.

public static class SyracuseTrad {
    static int ic = 0;
    static int[] mem = new int[1000];

    public static void main(String[] a) {
        while (true) {
            switch (ic++) {
            case 0: mem[0] = 13;
            case 1: if (mem[0] == 1) ic += ?; // saut vers Z
            // traduction du if et de vol += 1
            case Z-1: ic -= ?; // saut vers 1
            case Z: System.out.println("Le temps de vol de 13 est " + mem[1] + "!");
            case Z+1: System.exit(0);
            }
        }
    }
}

Pour finir, on traduit le contenu de la boucle:

public static class SyracuseTrad {
    static int ic = 0;
    static int[] mem = new int[1000];

    public static void main(String[] a) {
        while (true) {
            switch (ic++) {
            case 0: mem[0] = 13;
            case 1: if (mem[0] == 1) ic += ?; // saut vers Z
            case 2: if (mem[0] % 2 != 0) ic += 2; // saut vers 5
            case 3: mem[0] = mem[0] / 2;
            case 4: ic += ?; // saut vers Z-1 (fin de la boucle)
            case 5: mem[0] = 3 * mem[0] + 1;
            case Z-1: ic -= ?; // saut vers 1
            case Z: System.out.println("Le temps de vol de 13 est " + mem[1] + "!");
            case Z+1: System.exit(0);
            }
        }
    }
}

On peut finalement remplacer Z par la bonne valeur pour que les adresses des instructions soient continues, et donc on peut remplir les décalages des sauts.

public static class SyracuseTrad {
    static int ic = 0;
    static int[] mem = new int[1000];

    public static void main(String[] a) {
        while (true) {
            switch (ic++) {
            case 0: mem[0] = 13;
            case 1: if (mem[0] == 1) ic += 6; // saut vers la fin
            case 2: if (mem[0] % 2 != 0) ic += 2; // saut vers else
            case 3: mem[0] = mem[0] / 2;
            case 4: ic += 1; // saut vers la fin de la boucle
            case 5: mem[0] = 3 * mem[0] + 1;
            case 6: ic -= 6; // saut vers 1
            case 7: System.out.println("Le temps de vol de 13 est " + mem[1] + "!");
            case 8: System.exit(0);
            }
        }
    }
}

Exercice 4 : Partiel 2011

Il s'agit de traduire le programme suivant :

class Partiel2011 {
    static int[] t;
    static int i;

    public static void main(String[] args) {
        t = new int[20];
        t[0] = 1;
        t[1] = 1;
        for (i = 2; i < 20; i++) {
            t[i] = 2 * t[i-1] + t[i-2];
        }
        System.out.println("Nombre(19) = " + t[19]);
    }
}

On décide que i sera dans la case 0 de mem, et la tableau t dans les cases 1 jusqu'à 20 de mem.

Ensuite on traduit le programme sauf la boucle for:

class Partiel2011Solution {
    public static void main(String[] args) {
        int[] mem = new int[100000];
        int ic = 0;

        while (true) {
            switch (ic++) {
            case 0: mem[1 + 0] = 1;
            case 1: mem[2 + 0] = 1;
               // traduction de la boucle 
            case Z: System.out.println("Nombre(19) = " + mem[1 + 19]);
                break;
            case Z+1: System.exit(0);
            }
        }
    }
}

Il suffit maintenant de traduire la boucle for:

class Partiel2011Solution {
    public static void main(String[] args) {
        int[] mem = new int[100000];
        int ic = 0;

        while (true) {
            switch (ic++) {
            case 0: mem[1 + 0] = 1;
            case 1: mem[2 + 0] = 1;
            case 2: mem[0] = 2; // initialistion
            case 3: if (i >= 20) ic += ??; // saut vers Z
            case 4: mem[1+mem[0]] = 2 * mem[1+ mem[0]-1] + mem[1 + mem[0]-2];
            case Z-2: mem[0]++;
            case Z-1: ic -= ??; // saut vers 3;
            case Z: System.out.println("Nombre(19) = " + mem[1 + 19]);
                break;
            case Z+1: System.exit(0);
            }
        }
    }
}

Et enfin on peut remplacer Z par 7:

class Partiel2011Solution {
    public static void main(String[] args) {
        int[] mem = new int[100000];
        int ic = 0;

        while (true) {
            switch (ic++) {
            case 0: mem[1 + 0] = 1;
            case 1: mem[2 + 0] = 1;
            case 2: mem[0] = 2; // initialistion
            case 3: if (i >= 20) ic += 3; // saut vers 7
            case 4: mem[1+mem[0]] = 2 * mem[1+ mem[0]-1] + mem[1 + mem[0]-2];
            case 5: mem[0]++;
            case 6: ic -= 4; // saut vers 3;
            case 7: System.out.println("Nombre(19) = " + mem[1 + 19]);
                break;
            case 8: System.exit(0);
            }
        }
    }
}