Le problème algorithmique PMG (PMG = Petit Moyen Grand)                       gilles.hunault "at" univ-angers.fr   Présentation du problème On dispose de 3 variables d'entrée a,b,c et on veut écrire un algorithme qui met dans les 3 variables de sortie p,g,m respectivement la plus petite valeur, la plus grande et celle du milieu. On a ici écrit volontairement p,g,m au lieu de p,m,g. Partie 1. Fournir au moins les 5 solutions dirigées suivantes dont la progression pédagogique est imposée. Solution 1 : on n'utilisera que des structures SI simples, sans SINON ni imbrication. Pas de tableau. Solution 2 : on pourra utiliser des structures SI plus complexes avec SINON et imbrications possibles. Toujours pas de tableau. Solution 3 : aucune structure SI n'est autorisée, mais on dispose des fonctions de deux variables min(x,y) et max(x,y). Pas de tableau. Attention, c'est difficile pour la valeur du milieu. Solution 4 : on peut utiliser un tableau mais aucune fonction sur tableau n'est prédéfinie. Solution 5 : on peut utiliser un tableau et toutes les fonctions possibles et imaginables sur tableau. Partie 2. On veut généraliser le problème. Réfléchir aux questions suivantes : - quelle(s) solution(s) seraient les plus adaptées, quitte à les modifier un peu, si on avait non plus 3 variables a,b,c mais 4 variables a,b,c,d ? - quelle est la solution la plus courte à écrire ? la plus lisible ? la plus simple ? la plus rapide ? ################################################# # # # é partir de valA, valB et valC, # # on met dans tpetit la plus petite valeur # # dans milieu la valeur du milieu # # et dans tgrand la plus grande valeur # # # ################################################# ################################################# # # solution 1 sans fonction de R (et sans else) # ################################################# # # les cas sont triés par ordre alphabétique : # valA valB valC puis valA valC valB etc. if ( (valA<valB) & (valB<valC) ) { tpetit <- valA milieu <- valB tgrand <- valC } # fin si cas 1 if ( (valA<valC) & (valC<valB) ) { tpetit <- valA milieu <- valC tgrand <- valB } # fin si cas 2 if ( (valB<valA) & (valA<valC) ) { tpetit <- valB milieu <- valA tgrand <- valC } # fin si cas 3 [...] # il y a 6 cas en tout é écrire if ( (valC<valA) & (valA<valB) ) { tpetit <- valC milieu <- valA tgrand <- valB } # fin si cas 6 ################################################# # # solution 2 sans fonction de R avec si emboités # ################################################# if (valA<valB) { if (valB<valC) { tpetit <- valA milieu <- valB tgrand <- valC } else { tpetit <- valA milieu <- valC tgrand <- valB } # fin si valB<valC } else { if (valA<valC) { [...] # il y a 6 cas en tout é écrire } # fin si valA<valB ################################################# # # solution 3 sans fonction de R avec si en cascade # ################################################# if ( (valA < valB) & (valB < valC) ) { # ordre valA, valB, valC } else { if ((valA < valC) et (valC < valB) ) { # ordre valA, valC, valB } else { if ((valB < valA) et (valA < valC)) { # ordre valB, valA, valC } else { if ((valB < valC) et (valC < valA)) [...] } # fINSI (valB < valC) et (valC < valA) } # finsi (valB < valA) et (valA < valC) } # FINSI (valA < valC) et (valC < valB) } # FINSI (valA < valB) et (valB < valC) ################################################# # # solution 4 -- non évidente -- avec fonctions de R # ################################################# tpetit <- min( valA, min(valB,valC) ) milieu <- min( max(valA,valB), min( max(valA,valC),max(valB,valC) ) ) tgrand <- max( valA, max(valB,valC) ) ################################################# # # solution 5 avec fonctions de R # ################################################# tri <- sort( c(valA,valB,valC) ) tpetit <- tri[ 1 ] milieu <- tri[ 2 ] tgrand <- tri[ 3 ] - dans quels langages de programmation a-t-on une fonction de tri native ? - si on devait utiliser des objets plus compliqués que de simples variables avec des critères de comparaison multiple, que faudrait changer pour trouver le meilleur objet, le pire, et l'objet moyen ? - comment se définit la tendance centrale en statistiques ? et les multi-centroides pondérés en «Big Data» ? - en admettant qu'on dispose d'une "liste" de valeurs ("vraie" liste, vecteur, tableau, etc.) est-ce que ce serait simple de trouver en plus des extrema leur nombre d'occurences, la position de leur première occurence, celle de leur dernière occurence, le tout en un seul parcours de la liste pour des raisons d'efficacité ? Quelques remarques Pour savoir si on a réussi l'exercice, il faut tester 3!=6 cas selon les valeurs de a, b et c quand ces variables sont toutes distinctes deux à deux. Il faut donc avoir au moins 6 lignes avec a,b,c en entrée et les bons p,m,g en sortie pour pouvoir conclure. Grâce à l'associativité des fonctions min(x,y) et max(x,y), il est assez facile de trouver p et g dans le cadre de la solution 3. Comme le typage ne fait pas partie de l'énoncé, en fait toutes les solutions doivent s'adresser aussi bien à des chaines de caractères qu'à des nombres, entiers ou réels ou même à n'importe quelles données, comme des fractions "symboliques", pourvu qu'on ait une relation d'ordre total. C'est pourquoi il est important de traiter le problème avec des valeurs a, b et c, même si l'ordre lexicographique pour les lettres françaises accentuées est "intrinsèquement rébarbatif" et "non conceptuel". Un problème pour public plus averti consiste à comparer des programmes d'optimisation avec plusieurs critères d'évaluation. Parmi les objectifs pédagogiques visés par cet exercice, on peut noter l'entrainement à l'instruction SI et à l'imbrication, l'aptitude à établir des critères de choix pour comparer les solutions, l'introduction de variables ou de structures de données complémentaires pour résoudre le problème comme ici le tableau, la volonté de généricité de code pour faire abstraction du typage.   Code-source PHP de cette page.

 

 

   Retour à la page principale de   (gH)