Tri de nombres dans l’ordre croissant

jeudi 15 mai 2014
par  Alain BUSSER

Pour qu’un nombre soit triable, il suffit avec jQuery-UI, de le déclarer comme tel (« sortable » en anglais). Mais pour que l’exercice soit intéressant, les nombres sont d’abord permutés au hasard, à l’aide de underscore (petit logiciel de gestion des tableaux en JavaScript)

Tri d’entiers naturels

Algorithmes

Pour commencer, le nombre d’entiers à trier est choisi aléatoirement entre 10 et 20, à l’aide de

  1. taille = _.random 10, 20

Ensuite, les entiers eux-mêmes sont choisis par un tirage sans remise effectué dans la liste des entiers entre 1 et 500. Pour simuler ce tirage sans remise, on permute aléatoirement ("shuffle) les 500 entiers (étape assez longue) puis on choisit les taille premiers d’entre eux :

  1. urne = (_.shuffle [0..500])[0...taille]

Si ça dure trop longtemps, on peut modifier avec l’algorithme suivant :

  • effectuer un tirage avec remise par une boucle ;
  • supprimer les doublons avec la fonction « uniq » de underscore

Quelque chose comme ça :

  1. urne = []
  2. for indice in [0...taille]
  3.     urne.push _.random 0, 500
  4. urne = _.uniq urne

Télécharger

Voici le fichier, à ouvrir dans un autre onglet :

ranger des entiers naturels dans l’ordre croissant
exercice de tri avec aide

Ce fichier, comme les autres de l’article, est muni d’une double aide :

  • la liste des nombres est affichée en ligne, en bas de la page
  • si on cherche à valider la réponse, et que celle-ci est fausse, on peut continuer quand même.

Pour que le professeur utilise ce genre d’exercice en classe, il peut être souhaitable d’enlever ces aides. Voici donc le même exercice que ci-dessus, mais avec une seule chance pour soumettre une réponse (au-delà, il faut recommencer l’exercice en cliquant sur la flèche arrondie en haut du navigateur) :

trier des entiers naturels
cette fois-ci, c’est du sérieux, une seule chance !

Tri d’entiers relatifs et de décimaux

Une légère variante du premier fichier, où les entiers peuvent être négatifs :

ranger des entiers relatifs dans l’ordre croissant
exercice de tri en ligne, portant sur des entiers relatifs

Un exercice similaire, où les nombres sont à nouveau positifs, mais décimaux :

ranger des nombres décimaux dans l’ordre croissant
exercice de tri en ligne, portant sur des décimaux

Fractions et expressions

Les nombres décimaux ci-dessus sont parfois un peu grands, c’est parce qu’on a fait une approximation décimale (à trois décimales) de fractions aléatoires. La version sans approximations est ici :

ranger des fractions dans l’ordre croissant
tri de fractions positives

En fait, des fractions sont une ébauche de calcul littéral.

Mais c’est pas grave

La conversion de fractions écrites au valeurs approchées décimales se fait par

  1. (eval(x.innerHTML) for x in $("#sortable li"))

où $("#sortable li") est la liste des fractions à trier, qui contiennent des chaînes de caractères [1]. Donc x.innerHTML est une fraction générique (le contenu au format html de l’élément à trier ; donc une chaîne de caractères). Et eval effectue un calcul d’expression JavaScript, qui renvoie la valeur approchée à la précision permise par le machine. En résumé, eval permet de passer d’une expression littérale à un nombre.

Une variante permet donc de demander le tri d’entiers eux aussi donnés sous forme d’expressions littérales (somme de produits). C’est ici :

ranger des entiers naturels dans l’ordre croissant
Les entiers ne sont pas précalculés, une calculatrice peut donc être utile pour faire cet exercice (ou du calcul mental ?)

Une autre variante : Avec des racines carrées

Algorithme

Le principe consiste à remplacer chaque occurence de « √ » par « *Math.sqrt ». Par exemple, « 2+3√(5) » devient « 2+3*Math.sqrt(5) » qui est correct du point de vue de JavaScript. La liste des valeurs approchées s’obtient avec

  1. eval(x.innerHTML.replace("√","*Math.sqrt")) for x in $("#sortable li")

La boucle sur x parcourt la liste des élements (« li ») de la liste à trier. Donc les contenus html de ces éléments sont les expressions à évaluer.

Voici le fichier :

ranger des expressions avec radicaux
tri dans l’ordre croissant, de réels (parfois) irrationnels

Et une petite variante où les racines carrées sont remplacées par π, et où il s’agit donc d’ordonner des « angles remarquables » en radians [2] :

ranger des angles orientés
tri de mesures d’angles en radians. Les mesures ne sont pas nécessairement principales.

Équations

Et tant qu’on est à faire du calcul littéral, autant carrément demander de trier dans l’ordre croissant les solutions d’une collection d’équations du premier degré [3].

Origine de l’exercice

Cet exercice est inspiré d’un « niveau » du jeu enigma appelé « Esprit 50 », de Sven Siggelkow, et où dont le but est de ranger chacune des 4 billes blanches dans son creux à elle :

Chaque creux est caractérisé par un nombre à calculer, et l’un des 4 nombres est solution d’une équation (en bas de l’écran) :

Le fichier final, à tester dans un autre onglet (et pourquoi pas ouvrir aussi un onglet sur ekoarun pour une petite aide ?) :

ranger les solutions d’une collection d’équations
exercice de tri en ligne, qui nécessite de résoudre des équations

Et la version antitriche :

ranger les solutions d’une collection d’équations
Cette fois-ci, une seule chance « c’est votre dernier mot ? »

Comment résoudre une équation ?

Chaque équation est une chaîne de caractères, comprenant un signe « = », deux signes « + » et deux fois la lettre « x ». Alors on la découpe d’abord en prenant pour séparateur la chaîne « x+ », ce qui renvoie le premier facteur, le dernier terme et, entre les deux, le reste. Par exemple, avec « 3x+2=5x+7 », on a un tableau contenant

  • 3
  • 2=5
  • 7

Ceci donne déjà deux coefficients, et il suffit de faire pareil avec la chaîne du milieu, en la séparant par le signe « = », pour avoir les deux autres coefficients. On doit convertir en entiers ces coefficients (jusque là ce sont des chaînes de caractères) pour effectuer le calcul de la solution. Celle-ci est donnée sous forme approchée :

  1. solution = (equation) ->
  2.         listeTermes = equation.split('x+')
  3.         a = parseInt listeTermes[0]
  4.         d = parseInt listeTermes[2]
  5.         listeTermes = listeTermes[1].split('=')
  6.         b = parseInt listeTermes[0]
  7.         c = parseInt listeTermes[1]
  8.         (d-b)/(a-c)

Télécharger

En effet l’équation ax+b=cx+d peut s’écrire ax-cx=d-b ou (a-c)x=d-b ce qui donne, par division, la formule utilisée dans le script.


[1] un entier puis le caractère « / » puis un entier.

[2] ce qui n’a aucun sens, puisque la mesure d’un angle orienté n’est pas unique. Mais algébriquement, l’exercice conserve son intérêt.

[3] ce qui suppose de les résoudre avant, c’est tout l’intérêt de cet exercice, qui est un exercice de résolution d’équations déguisé.


Commentaires

Navigation

Articles de la rubrique