Programmes complexes

Les problèmes vus précédemment pouvaient se résoudre avec une seule boucle :

  • Calcul d’une moyenne
  • recherche d’un maximum ou d’un minimum
  • recherche d’un élément dans une collection

Cependant certains problèmes ne peuvent être résolus sans l’utilisation de plusieurs boucles imbriquées. 

Boucle imbriquée

Une boucle est dite imbriquée quand elle s’exécute à l’intérieur  d’une autre boucle, plus particulièrement dans la partie loop d’une macro.

Avec AlgoTouch, il est impossible de construire directement une boucle à l’intérieur d’une boucle. Le seul moyen est d’utiliser une nouvelle macro boucle.

Define Double
  From
    exist = 0 ;
    i = 0 ;
  Until
    (exist == 1)
    (i >= t.length)

  Loop
    Exist ;
    i = i + 1 ;

  Terminate

End
Define Exist
From
j = i + 1 ;
exist = 0 ;

Until
(j >= t.length)
(exist == 1)

Loop
if (t[i] != t[j]) {
j = j + 1 ;
}
else{
// t[i] == t[j] exist = 1 ;
}

Terminate

End

Le code du programme AlgoTouch est disponible Double.alg

Exemple

Dans cette partie du cours, nous allons réaliser une macro , un programme AlgoTouch, qui détermine si un tableau d’entiers contient des valeurs identiques :

  • Le tableau {94, 4, 92, 7, 94, 4, 98, 60, 75, 60 } contient plusieurs fois les valeurs 4, 94 et 60.
  • Le tableau {90, 0, 92, 7, 94, 4, 98, 61, 75, 60 } ne contient que des valeurs différentes.

Recherche de la solution

Dans un premier temps, nous allons rechercher comment déterminer si un tableau d’entiers contient plusieurs valeurs identiques.

Rapidement, après quelques manipulation avec AlgoTouch, l’idée de l’algorithme est trouvée. Une solution consiste à regarder si la valeur à la position 0 est présente dans la suite du tableau. 

Si c’est la cas le calcul est terminé.

Si ce n’est pas le cas, il faut chercher si la valeur à la position 1 est présente dans la suite du tableau.

Le programme s’arrête si une valeur double est trouvée ou si tout le tableau est parcouru.

Génération de la macro Exist

La première étape consiste à générer la macro la plus interne, en l’occurrence Exist sur notre exemple. Cette macro détermine si la valeur en t[i] est présente dans la suite du tableau, c’est-à-dire aux indices après i. Si c’est la cas une variable exist est mise à 1. Dans le cas contraire la variable exist vaut 0.

Génération de la macro Double

Maintenant que la macro Exist est réalisée, l’étape suivante consiste à générer la macro Double qui cherche si des valeurs sont en plusieurs exemplaires dans le tableau t.

Cette macro consiste juste à chercher si t[i] est présent dans la suite du tableau grâce à la macro Exist. Soit c’est le cas et le programme est terminé, soit ce n’est pas le cas et il faut passer à la valeur suivante dans t.

Exercice

To Do

[embedyt] To do[/embedyt]