Félicitations! Vous voici de retour pour une deuxième session à
la prestigieuse université «University for Computers Landbehrt of
America» (UCLA)! Cette université virtuelle est située à
Blainville, mais elle peut être itinérante à l’occasion.
Je suis Landbehrt, votre professeur pour tous les cours que vous
aurez à suivre jusqu’à l’atteinte de votre diplôme. Tous les cours
seront donnés en français, heureusement pour vous mes étudiants
Québécois, et se termineront chacun par un examen final qui vous
permettra de trouver une cache.
Alors bienvenue à votre troisième cours, «Informatique 201 –
Techniques de programmation». Nous allons apprendre et mettre en
pratique ici quelques techniques de programmation qui vous
permettront de réussir ce troisième cours. Le langage de
programmation qui sera utilisé pour ce cours est le BASIC (francisé
pour les besoins du cours).
Il est important de mentionner que la réussite du cours
«
Informatique 101 – Logique de programmation» est un pré-requis
à la réussite de ce troisième cours.
Voici la théorie:
En programmation, il est fréquent d'avoir à trier des
informations de toutes sortes: noms, catégories, montants, etc.
Pour ce faire, les programmeurs utilisent des algorithmes de
tri.
Plusieurs différents algorithmes de tri existent: par insertion,
par sélection, bulle, Shell, de Batcher, indirect, fusion, maximier
et rapide entre autres. Pour ce cours, vous allez comparer les
performances des tris bulle et Shell.
Notions de niveau intermédiaire du langage
BASIC:
| - Une variable indicée est une zone de
mémoire dans laquelle on stocke plusieurs valeurs. Ces valeurs sont
accessibles à l'aide d'un indice. Exemples : LAISSE Noms$[1]
= "L'Exocet" indique que la première valeur de Noms$ devient
"L'Exocet". Ainsi, si A = 1, alors la valeur de Noms$[A] est
"L'Exocet". |
Verbes de niveau intermédiaire du langage
BASIC:
| REMARQUE : Indique une remarque au
programme. Tout ce qui suit, sur la même ligne, le verbe
REMARQUE n'est pas exécuté. Exemple : REMARQUE "***
Ceci est une remarque. |
| ALLER-RETOUR À (numéro de ligne) : Permet
de poursuivre le traitement au numéro de ligne qui suit le verbe.
Exemples : ALLER-RETOUR À 500 indique de poursuivre le
traitement à la ligne 500. |
| RETOUR : Quand le verbe RETOUR est
rencontré, le traitement se poursuit à la ligne qui suit le dernier
ALLER-RETOUR À exécuté. |
| DIMENSIONNE (variable)[(indice de
départ):(indice de fin)] : Définie une zone de
mémoire indicée. Exemple : DIMENSIONNE Noms$[1:10] indique
que la variable noms$ peut contenir 10 valeurs. |
| POUR (condition) JUSQU'À (borne de
fin) SAUT (incrément) (verbes) SUIVANT (variable) :
Ces verbes permettent la répétition de l'exécution de verbes un
certain nombre de fois, ce nombre étant déterminé par la condition
et la borne de fin. Le verbe SUIVANT augmente l'indice de la
valeur du SAUT et évalue de nouveau la condition. Si
l'indice dépasse la borne de fin, le traitement se poursuit à la
ligne qui suit le verbe SUIVANT. Exemple : POUR
indice = 1 À 10 SAUT 1; IMPRIME indice;
SUIVANT indice, cela permet d'imprimer les nombres de 1 à
10. |
| RÉPÉTER (verbes) JUSQU'À CE QUE
(condition) : Ces verbes permettent la répétition de l'exécution de
verbes un certains nombre de fois, ce nombre étant déterminé par la
condition du verbe JUSQU'À CE QUE. Si la condition est
fausse, le traitement se poursuit à la ligne qui suit le verbe
RÉPÉTER. Si la condition est vraie, le traitement se
poursuit à la ligne qui suit le verbe JUSQU'À CE QUE.
Exemple : LAISSE indice = 0; RÉPÉTER; LAISSE
indice = indice + 1; IMPRIME indice; JUSQU'À CE QUE
indice = 10, cela permet d'imprimer les nombres de 1 à
10. |
| SORTIR À (numéro de ligne) : Permet de
quitter prématurément une boucle POUR...SUIVANT ou
RÉPÉTER...JUSQU'À CE QUE pour poursuivre le traitement au
numéro de ligne indiqué après le verbe SORTIR À. Exemples :
SORTIR À 500 indique de poursuivre le traitement à la ligne
500. |
Voici la pratique:
10 REMARQUE "*** Les variables «A», «B», «C», «D», «E» et «F»
ci-dessous doivent prendre la valeur des coordonnées de la cache du
cours «Informatique 101».
20 LAISSE A = Degres_Latitude_101
30 LAISSE B = Minutes_Latitude_101
40 LAISSE C = Milliemes_Latitude_101
50 LAISSE D = Degres_Longitude_101
60 LAISSE E = Minutes_Longitude_101
70 LAISSE F = Milliemes_Longitude_101
80 REMARQUE
90 LAISSE Tri$ = "Tri bulles"
100 ALLER-RETOUR À 630
110 LAISSE Tests = 0
120 LAISSE Permutations = 0
130 LAISSE Limite = 6
140 POUR Premier_Indice = 1 JUSQU'À Limite SAUT 1
150 LAISSE Tests = Tests + 1
160 SI Noms$[Premier_Indice + 1] > Noms$[Premier_Indice] ALORS
ALLER À 210 FINSI
170 LAISSE Permutations = Permutations + 1
180 LAISSE Temporaire$ = Noms$[Premier_Indice]
190 LAISSE Noms$[Premier_Indice] = Noms$[Premier_Indice + 1]
200 LAISSE Noms$[Premier_Indice + 1] = Temporaire$
210 SUIVANT Premier_Indice
220 LAISSE Limite = Limite - 1
230 SI Limite > 1 ALORS ALLER À 140 FINSI
240 ALLER-RETOUR À 740
250 LAISSE Tests_Bulle = Tests
260 LAISSE Permutations_Bulle = Permutations
270 REMARQUE
280 LAISSE Tri$ = "Tri Shell"
290 ALLER-RETOUR À 630
300 LAISSE Tests = 0
310 LAISSE Permutations = 0
320 LAISSE Intervalle = 4
330 POUR Premier_Indice = Intervalle + 1 JUSQU'À 7 SAUT
Intervalle
340 LAISSE Deuxieme_Indice = Premier_Indice
350 LAISSE Troisieme_Indice = Deuxieme_Indice - Intervalle
360 RÉPÉTER
370 LAISSE Tests = Tests + 1
380 SI Noms$[Troisieme_Indice] <= Noms$[Deuxieme_Indice] ALORS
SORTIR À 460
390 LAISSE Permutations = Permutations + 1
400 LAISSE Temporaire$ = Noms$[Deuxieme_Indice]
410 LAISSE Noms$[Deuxieme_Indice] = Noms$[Troisieme_Indice]
420 LAISSE Noms$[Troisieme_Indice] = Temporaire$
430 LAISSE Deuxieme_Indice = Deuxieme_Indice - Intervalle
440 LAISSE Troisieme_Indice = Troisieme_Indice - Intervalle
450 JUSQU'À CE QUE Troisieme_Indice < 1
460 SUIVANT Premier_Indice
470 SI Intervalle = 4 ALORS LAISSE Intervalle = 2; ALLER À 330
FINSI
480 SI Intervalle = 2 ALORS LAISSE Intervalle = 1; ALLER À 330
FINSI
490 ALLER-RETOUR À 740
500 LAISSE Tests_Shell = Tests
510 LAISSE Permutations_Shell = Permutations
520 REMARQUE
530 LAISSE Degres_Latitude_201 = A
540 LAISSE Minutes_Latitude_201 = B - Permutations_Bulle +
Permutations_Shell
550 SI Tests_Shell > Tests_Bulle ALORS LAISSE
Milliemes_Latitude_201 = F - E SINON LAISSE Milliemes_Latitude_201
= F - B - Tests_Bulle - Permutations_Shell FINSI
560 LAISSE Degres_Longitude_201 = D
570 LAISSE Minutes_Longitude_201 = Tests_Bulle * 1.5 + Tests_Shell
+ Permutations_Shell
580 SI Tests_Bulle + Permutations_Shell > Tests_Shell +
Permutations_Bulle ALORS LAISSE Milliemes_Longitude_201 = D + E + A
- B SINON LAISSE Milliemes_Longitude_201 = D + A + Tests_Bulle +
Permutations_Shell FINSI
590 REMARQUE
600 IMPRIME "Les coordonnées de la cache sont :
N",Degres_Latitude_201,"°
",Minutes_Latitude_201,".",Milliemes_Latitude_201,"
W",Degres_Longitude_201,"°
",Minutes_Longitude_201,".",Milliemes_Longitude_201
610 FIN
620 REMARQUE
630 REMARQUE "*** Initialisation des noms de géocacheurs à
trier
640 DIMENSIONNE Noms$[1:7]
650 LAISSE Noms$[1] = "Misouris"
660 LAISSE Noms$[2] = "Unoyt"
670 LAISSE Noms$[3] = "Big JohnP"
680 LAISSE Noms$[4] = "OpusTerra"
690 LAISSE Noms$[5] = "Ze Team Bebenoir"
700 LAISSE Noms$[6] = "Wallaby77"
710 LAISSE Noms$[7] = "L'Exocet"
720 RETOUR
730 REMARQUE
740 REMARQUE "*** Impression des résultats du tri
750 POUR Premier_Indice = 1 JUSQU'À 7 SAUT 1
760 IMPRIME Noms$[Premier_Indice]
770 SUIVANT Premier_Indice
780 IMPRIME "Nombre de tests (",Tri$,"): ",Tests
790 IMPRIME "Nombre de permutations (",Tri$,"): ",Permutations
800 IMPRIME "*****************************************"
810 RETOUR
Pour réussir ce cours, vous devez simplement résoudre l'énigme
ci-dessus et signer le registre de visites situé quelque part dans
un boisé près d'une piste cyclable de Blainville.
Le contenu initial de la cache est:
- Disquette
- Fil réseau
- Fil pour disque dur
- CD ROM
- Tapis à souris
- Sachet contre l'humidité
- Registre de visites
- Feuille explicative
- Crayon à mine
- Aiguisoir (ce n'est pas un item à échanger)
Et bien entendu, pour le P.A.T., le traditionnel gratteux!
Testez vos coordonnées ici!
Indice d'accessibilité : H15541
