تمارينla partie 7 des algorithme

PARTIE 7
Enonce des Exercices

Exercice7.1

Ecrivez un algorithme qui permette de saisir un nombre quelconquede valeurs, et qui les range au fur et à mesure dans un tableau. Le programme,une fois la saisie terminée, doit dire si les éléments du tableau sont tousconsécutifs ou non.

Par exemple, si le tableau est :

12

13

14

15

16

17

18

ses éléments sont tous consécutifs. En revanche, si le tableau est :

9

10

11

15

16

17

18

ses éléments ne sont pas tous consécutifs.

Exercice7.2

Ecrivez un algorithme qui trie un tableau dans l’ordredécroissant.

Vous écrirez bien entendu deux versions de cet algorithme, l'uneemployant le tri par insertion, l'autre le tri à bulles.

Exercice7.3

Ecrivez un algorithme qui inverse l’ordre des éléments d’untableau dont on suppose qu'il a été préalablement saisi (« les premiersseront les derniers… »)

Exercice7.4

Ecrivez un algorithme qui permette à l’utilisateur de supprimerune valeur d’un tableau préalablement saisi. L’utilisateur donnera l’indice dela valeur qu’il souhaite supprimer. Attention, il ne s’agit pas de remettre unevaleur à zéro, mais bel et bien de la supprimer du tableau lui-même ! Sile tableau de départ était :

12

8

4

45

64

9

2

Et que l’utilisateur souhaite supprimer la valeur d’indice 4, le nouveautableau sera :

12

8

4

45

9

2

Exercice7.5

Ecrivez l'algorithme qui recherche un mot saisi au clavier dans undictionnaire. Le dictionnaire est supposé être codé dans un tableaupréalablement rempli et trié.

PARTIE7

Corrigés des Exercices

Exercice 7.1
Variables Nb, i enEntier
Variable Flag en Booleen
Tableau T() en Entier
Debut
Ecrire "Entrez le nombre de valeurs :"
Lire Nb
Redim T(Nb-1)
Pour i ← 0 à Nb - 1
Ecrire "Entrez le nombre n° ", i + 1
Lire T(i)
i Suivant
Flag ← Vrai
Pour i ← 1 à Nb - 1
Si T(i) <> T(i – 1) + 1 Alors
Flag ← Faux
FinSi
i Suivant
Si Flag Alors
Ecrire "Les nombres sont consécutifs"
Sinon
Ecrire "Les nombres ne sont pas consécutifs"
FinSi
Fin
Cetteprogrammation est sans doute la plus spontanée, mais elle présente le défautd'examiner la totalité du tableau, même lorsqu'on découvre dès le départ deuxéléments non consécutifs. Aussi, dans le cas d'un grand tableau, est-elledispendieuse en temps de traitement. Une autre manière de procéder serait desortir de la boucle dès que deux éléments non consécutifs sont détectés. Ladeuxième partie de l'algorithme deviendrait donc :
i ← 1
TantQue T(i) = T(i – 1) + 1 et i < Nb - 1
i ← i + 1
FinTantQue
Si T(i) = T(i – 1) + 1 Alors
Ecrire "Les nombres sont consécutifs"
Sinon
Ecrire "Les nombres ne sont pas consécutifs"
FinSi

Exercice 7.2
Onsuppose que N est le nombre d’éléments du tableau. Tri par insertion :
…
Pour i ← 0 à N - 2
posmaxi = i
Pour j ← i + 1 à N - 1
Si t(j) > t(posmaxi) alors
posmaxi ← j
Finsi
j suivant
temp ← t(posmaxi)
t(posmaxi) ← t(i)
t(i) ← temp
i suivant
Fin
Trià bulles :
…
Yapermut ← Vrai
TantQue Yapermut
Yapermut ← Faux
Pour i ← 0 à N - 2
Si t(i) < t(i + 1) Alors
temp ← t(i)
t(i) ← t(i + 1)
t(i + 1) ← temp
Yapermut ← Vrai
Finsi
i suivant
FinTantQue
Fin
Exercice 7.3
Onsuppose que n est le nombre d’éléments du tableau préalablement saisi
…
Pour i ← 0 à (N-1)/2
Temp ← T(i)
T(i) ← T(N-1-i)
T(N-1-i) ← Temp
i suivant
Fin
Exercice 7.4
…
Ecrire "Rang de la valeur à supprimer ?"
Lire S
Pour i ← S à N-2
T(i) ← T(i+1)
i suivant
Redim T(N–1)
Fin
Exercice 7.5
Nest le nombre d'éléments du tableau Dico(), contenant les mots du dictionnaire,tableau préalablement rempli.
Variables Sup,Inf, Comp en Entier
Variables Fini en Booléen
Début
Ecrire "Entrez le mot à vérifier"
Lire Mot
Ondéfinit les bornes de la partie du tableau à considérer
Sup ← N - 1
Inf ← 0
Fini ← Faux
TantQue Non Fini
Compdésigne l'indice de l'élément à comparer. En bonne rigueur, il faudra veiller àce que Comp soit bien un nombre entier, ce qui pourra s'effectuer dedifférentes manières selon les langages.
Comp ← (Sup + Inf)/2
Sile mot se situe avant le point de comparaison, alors la borne supérieurechange, la borne inférieure ne bouge pas.
Si Mot Alors
Sup ← Comp - 1
Sinon,c'est l'inverse
Sinon
Inf ← Comp + 1
FinSi
Fini ← Mot = Dico(Comp) ou Sup < Inf
FinTantQue
Si Mot = Dico(Comp) Alors
Ecrire "le mot existe"
Sinon
Ecrire "Il n'existe pas"
Finsi
Fin