15A: Détermination de terminaison | Cercles informatiques

Les exercices 15A, 15B et 15C peuvent être fait dans n'importe quel ordre.

Dans cet exercice, vous allez résoudre un problème long et complexe qui a été découpé en petites parties pour vous. Cette leçon introduit str.split(), une méthode utile pour découper des chaînes: elle efface tous les espaces et retourne une liste avec tous les mots dans la chaîne. La chaîne d'origine n'est pas modifiée.

Vous pouvez appeler split() avec des arguments spéciaux pour faire du découpage plus sophistiqué mais nous n'en aurons pas besoin ici. Si cela vous intéresse, allez voir la documentation Python.

Maintenant, attelons-nous à la tâche. Le vieux langage de programmation BASIC était célèbre pour ses lignes numérotés et ses instructions goto. Dans cet exercice, vous implémenterez une version simplifiée de BASIC avec seulement cette fonctionnalité. L'entrée de votre programme consistera en plusieurs lignes au format

«label» goto «cible»

où «label» et «cible» sont des nombres positifs. Le label est comme le nom ou l'adresse d'une ligne; tous les labels sont uniques. La cible vous indique le label de la ligne à laquelle il faut aller ensuite. La dernière ligne du programme est le «label» END qui indique que vous devez vous arrêter lorsque vous arrivez à cette ligne. Voici un exemple de programme en BASIC:

5 GOTO 30
10 GOTO 20
20 GOTO 10
30 GOTO 40
40 END

Quand BASIC exécute le programme, voici ce qui se passe. On commence à la première ligne (avec le label 5). La ligne avec le label 5 a comme cible 30 donc nous allons ensuite à la ligne 30. La ligne 30 nous dit d'aller à la ligne 40. La ligne 40 nous dit d'aller à END. Donc le programme se termine avec succès.

D'un autre côté, un programme en BASIC peut boucler pour toujours. Voici un exemple:

10 GOTO 21
21 GOTO 37
37 GOTO 21
40 END

Le programme commence à la ligne 10 puis boucle entre les lignes 21 et 37.

Votre tâche est d'écrire un programme Python qui l‎it un programme BASIC en entrée. Si le programme se termine, votre code affichera le message terminaison. Si le programme entre dans une boucle infinie, votre code affichera boucle infinie. Vous assumerez que chaque cible renvoie à un label existant et que chaque label est unique, de telle manière que vous ne devez pas vérifier s'il y a des erreurs.

Il y a plusieurs manières de résoudre ce problème, mais dans cette leçon, nous avons choisi une approche simple qui divise le problème en trois sous-tâches. (A la leçon 15C, vous aurez un grand problème dont vous devrez définir les sous-tâches vous-même).

Sous-tâche 1: Lire le programme

Pour lire le programme, vous devrez appelez plusieurs fois la fonction input(). Mais il faudra arrêter d'appeler la fonction input() une fois que la dernière ligne aura été lue (celle avec END) pour éviter une erreur EOFError.

Sous-tâche 2: Goto!

Une fois que vous avez lu le programme, il vous faut être capable d'aller de ligne en ligne dans le programme. Pour y arriver, nous vous demandons d'écrire la sous-routine suivante.

Exercice de code : Goto!

Définissez une fonction trouveLigne(prog, cible). Assumez que prog est une liste de chaînes contenant un programme en BASIC du type de celui généré par lireBASIC(); assumez que cible est une chaîne contenant le numéro de ligne qui est la cible de l'instruction GOTO. La fonction retournera l'index i (un nombre entre 0 et len(prog)-1) de façon que prog[i] soit la ligne donc le label est égal à cible. Hint
Exemple d'entrée/sortie: Si vous appelez

trouveLigne(['10 GOTO 20','20 END'], '10')

la valeur retournée sera 0, puisque l'élément 0 de la liste est la ligne avec le label 10.

# Supprimer ce commentaire et entrez votre code ici

Entrez instructions de test comme print(mafonction("argument de test")) ci-dessous.

Sous-tâche 3: Simulation intelligente

Dans les deux exercices précédents, nous nous sommes occupés de la routine d'entrée et de la tâche de recherche. Elles seront utiles pour écrire un programme principal plus court. Il y a cependant encore une question majeure: comment résoudre la problème posé? La manière la plus directe serait de simuler le programme BASIC:

soit prog le programme en BASIC (une liste de chaînes)
démarrer un compteur appelé location à 0, puisque l'on commence à la première ligne du programme
Tant que toujours (while True),
- si prog[location] est la ligne END, retourner "terminaison" et arrêter.
- soit T la chaîne cible indiquée dans prog[location]
- assignons à location la valeur retournée par trouveLigne(prog, T)

Mais il y a un problème de taille: les boucles infinies ne sont pas détectées et si le programme BASIC a une boucle infinie, Python va aussi se répeter indéfiniment. Nous voulions que le programme indique "boucle infinie" dans ce cas. Nous vous laissons résoudre ce problème par vous-même; vous trouverez un indice ci-dessous.

Exercice de code : Simulation intelligente

Ecrivez une fonction execute(prog). Assumez que prog est une liste de chaînes contenant un programme BASIC, comme avant. Votre programme devra retourner "terminaison" ou "boucle infinie" suivant que le programme se termine ou boucle indéfiniment.
Important: vous assumerez que la procédure trouveLigne(prog, cible) définie à la sous-tâche 2 existe déjà, vous ne devez pas la réécrire. Indice

# here is a broken solution to get you started
def execute(prog):
  location = 0
  while True:
    if location==len(prog)-1: return "terminaison"
    #get T from prog[location] via str.split
    location = trouveLigne(prog, T)

Entrez instructions de test comme print(mafonction("argument de test")) ci-dessous.

Mettre tout ensemble

Pour tester votre code comme solution complète, copiez et collez les solutions précédentes ci-dessous.

Si votre langage de programmation est un peu plus compliqué, il est alors impossible d'écrire un programme de verification de terminaison. Ceci est un des théorèmes le plus ancien et le plus important en informatique et il a été démontré par Alan Turing dans les années 1930s. De nos jours on se réfère à ce résultat en disant que "le Problème de l'arrêt est indécidable."