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

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 :

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 :

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

Voici le fichier, à ouvrir dans un autre onglet :

HTML - 81.4 ko
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) :

HTML - 81.5 ko
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 :

HTML - 81.4 ko
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 :

HTML - 81.6 ko
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 :

HTML - 81.5 ko
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

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

$("#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 :

HTML - 81.6 ko
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

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 :

HTML - 81.6 ko
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] :

HTML - 81.6 ko
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 ?) :

HTML - 81.9 ko
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 :

HTML - 82 ko
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 :

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

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.


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

[2ce 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.

[3ce 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

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 12 avril 2017, 14h-18h, campus du Tampon, amphi 120C
- Mercredi 3 mai 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mardi 13 juin 2017, 14h-18h, campus du Tampon
- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6


Brèves

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

jeudi 20 avril 2017

Publication

737 Articles
Aucun album photo
130 Brèves
11 Sites Web
126 Auteurs

Visites

762 aujourd'hui
904 hier
1990960 depuis le début
36 visiteurs actuellement connectés