Banque de problèmes LARP

Problème 11.2

 

Titre :

Programme d’emplacement d’usines

Date :

24 avril 2006

Référence :

Tools for Structured Design – An introduction to programming logic, 5th Edition

M.Bohl & M. Rynn

1989, Prentice-Hall

P. 257 (Sample Problem 11.2)

Solutions :

Philippe Turcotte

 

Description du problème

 

Concevoir un algorithme qui trouve le pays où se situe l’usine d’une entreprise à l’aide d’un code. L’entreprise possède un total de 50 usines et chacune d’entre elles est située dans un pays différent. Pour trouver le pays, l’algorithme doit utiliser une recherche binaire. Une recherche binaire s’effectue de la façon suivante :

 

                  à début = 0

                  à fin = nbÉlément – 1

 

                  à milieu = (int)( (début + fin) / 2 )

 

                  Si la valeur recherchée est < que le milieu :

                             à début = ne change pas

                             à fin = milieu – 1

 

                  Si la valeur recherchée est > que le milieu :

                             à début = milieu + 1

                             à fin = ne change pas

 

 

L'algorithme doit lire, d’un tampon ou d’un fichier (pour Java), le code et le pays de localisation des 50 usines de l’entreprise.

Ces deux données sont stockées dans deux tableaux distincts. Il doit ensuite lire de l’utilisateur, un code à être recherché tant que le code entré n’est pas égal à 0. L’algorithme doit ensuite afficher le code et le pays d’emplacement de l’usine.

 

***Attention : On suppose que le tampon / fichier contient exactement 100 données. ( 50 usines * (1 code + 1 pays) )

 

Solutions du problème

 

Cet algorithme doit avoir au moins un module auxiliaire. Celui-ci doit détermine, à l’aide de la rechercher binaire, si le code recherché correspond à une usine. Il retourne l’index du code si le code est trouvé, sinon il retourne une valeur négative.

 

Premièrement, on initialise les tableaux avec les données du tampon / fichier, tout en s’assurant qu’il est bien en ordre croissant. Puis si le tableau de code est en ordre, on recherche le code entré par l’utilisateur. Si le code est trouvé, on l’affiche et on affiche aussi le pays correspondant à ce code. Sinon, on affiche un message d’erreur approprié.

 

Puis, on lit un autre code de l’utilisateur et s’il est différent de « 0 », on recommence à nouveau.

 

Solution organigramme LARP :

BohlRynn_P257_BinarySearch_Org.larp

Solution pseudo-code LARP :

BohlRynn_P257_BinarySearch_Pseudo.larp

Solution Java :

BohlRynn_P257_BinarySearch.java, BohlRynn_P257_BinarySearch_emplacements.txt

 

Note : L'accès aux fichiers de projet LARP ci-dessus est réservé aux détenteurs d'une clé de débridage pour LARP afin d'en assurer l'exclusivité aux enseignants. Tous ont cependant accès à la solution Java proposée.