TD3.
Corrigé
Exercice 1
Algorithme GesEtud
Type
Etudiant : Enregistrement
Ident : Entier
Nom : chaine[30]
Prénom : chaine[20]
Fin Etudiant
TAB : Tableau de 10 Etudiant
Var
ET : TAB
n : Entier
Procédure Remplissage(m : Entier ; var T : TAB)
Var
i : Entier
Début
Pour i de 1 à m faire
Ecrire("Etudiant n°",i," :")
Ecrire("Identifiant : "),Lire(T[i].Ident)
Ecrire("Nom : "),Lire(T[i].Nom)
Ecrire("Prénom : "),Lire(T[i].Prénom)
Fin Pour
Fin
Procédure Affichage(m : Entier ; T : TAB)
Var
i : Entier
Début
Ecrire("Identifiant Nom Prénom : ")
Ecrire("-------------------------------------------------")
Pour i de 1 à m faire
Ecrire(T[i].Ident," ",T[i].Nom," ",T[i].Prénom)
Fin Pour
Fin
{Programme principal}
Début
n ←10
Remplissage(n,ET)
Affichage(n,ET)
Fin
{Programme C}
# include <stdio.h>
# include <stdlib.h>
typedef struct {
int id;
char Nom[20];
char Prenom[20];
} etudiant;
/////////////////////////////////////////////////////////////////////
void remplissage(int m, etudiant T[m]){
int i;
for(i=0; i<m;i++){
printf ("Etudiant n°%d :identifiant =",i+1);
scanf ("%d",&T[i].id);
printf ("Nom =");
scanf ("%s",T[i].Nom);
printf ("Prénom =");
scanf ("%s",T[i].Prenom);
}
}
////////////////////////////////////////////////////////////////////
void affichage(int m, etudiant T[m]){
int i;
printf ("Identifiant | Nom |Prénom");
for (i=0;i<m;i++)
printf("%d | %s | %s\n",T[i].id, T[i].Nom,T[i].Prenom);
//////////////////////////////////////////////////////////////////
void main()
{
int n =10;
etudiant Tab[n];
remplissage(n,Tab);
affichage(n,Tab);
}
Exercice 2
Algorithme GesEtud
Type
Notes : Enregistrement
noteCc : Réel
noteEx : Réel
Fin Notes
Etudiant : Enregistrement
Ident : Entier
Nom : chaine[30]
Prénom : chaine[20]
Note : Notes
Fin Etudiant
TAB : Tableau de 10 Etudiant
Var
ET : TAB
n : Entier
Procédure SaisiNotes(var E : Etudiant)
Var
noteEntrer : Réel
Début
Répéter
Ecrire("Note contrôle continu : "), Lire(noteEntrer)
Jusqu’à noteEntrer ≥ 0 ET noteEntrer ≤ 20
E.Note.NoteCc ← noteEntrer
Répéter
Ecrire("Note examen : "), Lire(noteEntrer)
Jusqu’à noteEntrer ≥ 0 ET noteEntrer ≤ 20
E.Note.NoteEx ← noteEnter
Fin
Procédure Remplissage(m : Entier ; var T : TAB)
Var
i : Entier
Début
Pour i de 1 à m faire
Ecrire("Etudiant n°",i," :")
Ecrire("Identifiant : "), Lire(T[i].Ident)
Ecrire("Nom : "), Lire(T[i].Nom)
Ecrire("Prénom : "), Lire(T[i].Prénom)
SaisiNotes(T[i])
Fin Pour
Fin
Procédure AfficheNotes(E : Etudiant)
Début
Ecrire("Note Contôle Continu Note Examen ")
Ecrire("------------------------------------")
Ecrire(E.Note.NoteCc," ",E.Note.NoteEx)
Fin
Procédure Affichage(m : Entier ; T : TAB)
Var
i : Entier
Début
Ecrire("Identifiant Nom Prénom : ")
Ecrire("-------------------------------------------------")
Pour i de 1 à n faire
Ecrire(T[i].Ident," ",T[i].Nom," ",T[i].Prénom)
AfficheNotes(T[i])
Fin Pour
Fin
Fonction MeilleureNote(m : Entier ; T : TAB) : Réel
Var
i : Entier
NoteMax : Réel
Début
NoteMax ← T[1].Note.NoteEx
Pour i de 2 à m Faire
Si T[i].Note.NoteEx > NoteMax Alors
NoteMax ← T[i].Note.NoteEx
Fin Si
Fin Pour
MeilleureNote ← NoteMax
Fin
Fonction MoyenneGénérale(m : Entier ; T : TAB) : Réel
Var
i : Entier
som : Réel
Début
som ← 0
Pour i de 1 à m Faire
som ← som + 0.3 * T[i].Note.noteCc + 0.7 * T[i].Note.noteEx
Fin Pour
MoyenneGénérale ← som / m
Fin
{Programme principal}
Début
n ← 10
Remplissage(n,ET)
Affichage(n,ET)
Ecrire("Meilleur note examen :", MeilleureNote(n,ET), " Moyenne générale de la classe :",
MoyenneGénérale(n,ET))
Fin
{Programme C}
# include <stdio.h>
# include <stdlib.h>
typedef struct{
float noteCc, noteEx;
} notes;
typedef struct {
int id;
char Nom[20];
char Prenom[20];
notes Note;
} etudiant;
/////////////////////////////////////////////////////////////////////
void saisieNotes(etudiant *E){
do{
printf ("Note controle continu : ");
scanf("%f",&E->Note.noteCc);
} while (E->Note.noteCc < 0 || E->Note.noteCc > 20);
do{
printf ("Note examen : ");
scanf("%f",&E->Note.noteEx);
} while (E->Note.noteEx < 0 || E->Note.noteEx > 20);
/////////////////////////////////////////////////////////////////////
void remplissage(int m, etudiant T[m]){
int i;
for(i=0; i<m;i++){
printf ("Etudiant n°%d :identifiant =",i+1);
scanf ("%d",&T[i].id);
printf ("Nom =");
scanf ("%s",T[i].Nom);
printf ("Prénom =");
scanf ("%s",T[i].Prenom);
saisieNotes(&T[i]);
}
}
////////////////////////////////////////////////////////////////////
void affichage(int m, etudiant T[m]){
int i;
printf ("Identifiant | Nom |Prénom |Note Controle |Note Exam\n");
for (i=0;i<m;i++)
printf("%d | %s | %s | %2.f | %2.f\n",T[i].id, T[i].Nom,T[i].Prenom, T[i].Note.noteCc,
T[i].Note.noteEx);
///////////////////////////////////////////////////////////////////
float maxNote (int m, etudiant t[]){
int i;
float max = t[0].Note.noteEx;
for (i=1;i<m;i++)
if (t[i].Note.noteEx > max)
max = t[i].Note.noteEx;
return (max);
}
//////////////////////////////////////////////////////////////////
float moyGenerale (int m, etudiant t[]){
int i;
float som = 0;
for (i=0;i<m;i++)
som=som + 0.7*t[i].Note.noteEx+0.3*t[i].Note.noteCc;
return (som/m);
}
//////////////////////////////////////////////////////////////////
void main()
{
int n =2;
etudiant Tab[n];
remplissage(n, Tab);
affichage(n, Tab);
printf ("Meilleure note examen :%.2f \n Moyenne générale de la classe :
%.2f",maxNote(n,Tab),moyGenerale(n,Tab));
}
Exercice 3
# include <stdio.h>
# include <stdlib.h>
typedef struct {
char Nom[20];
int age ;
int Soduku_init[9][9] ;
char niveau ;
int Soduku_final[9][9] ;
int temps ;
} candidat;
/////////////////////////////////////////////////////////////////////
void remplissage(int m, candidat T[m]){
int i;
for(i=0; i<m;i++){
printf ("Candidat n°%d :identifiant =",i+1);
printf ("Nom =");
scanf ("%s",T[i].Nom);
printf ("Age =");
scanf ("%d",T[i].age);
printf ("Niveau =");
scanf ("%s",T[i].niveau) ;
printf ("Temps =");
scanf ("%d",T[i].temps) ;
remplissage_soduku(initial, T[i]) ;
remplissage_soduku(final, T[i]) ;
}
}
////////////////////////////////////////////////////////////////////
void affichage(int m, candidat T[m]){
int i;
printf ("Nom | Age | Niveau | Temps \n");
for (i=0;i<m;i++)
printf("%s | %d | %s |%d \n", T[i].Nom, T[i].age, T[i].niveau, T[i].temps);
printf("Grille Initiale : \n");
affichage_soduku(initial, T[i]) ;
printf("\nGrille Finale : \n");
affichage_soduku(final, T[i]) ;
printf("\n\n");
}
/////////////////////////////////////////////////////////////////
void remplissage_soduku(char etape[20], candidat* cand) {
int i,j ;
if (etape = "initial"){
for(i=0 ; i<9 ; i++){
for(j=0 ; j<9 ; j++){
printf ("Donner l’élément de la grille initiale numéro%d ;%d", i, j) ;
scanf("%d", cand->Soduku_init[i][j]) ;
}
else if (etape = "final"){
for(i=0 ; i<9 ; i++){
for(j=0 ; j<9 ; j++){
printf ("Donner l’élément de la grille finale numéro%d ;%d", i, j) ;
scanf("%d", cand->Soduku_final[i][j]) ;
}
else printf ("erreur choix étape \n") ;
//////////////////////////////////////////////////////////////////
void affichage_soduku(char etape[20], candidat* cand) {
if (etape = "initial"){
for(i=0 ; i<9 ; i++){
for(j=0 ; j<9 ; j++){
printf ("%d", cand->Soduku_initial[i][j]) ;
}
printf("\n") ;
}
else if (etape = "final"){
for(i=0 ; i<9 ; i++){
for(j=0 ; j<9 ; j++){
printf ("%d", cand->Soduku_final[i][j]) ;
}
printf("\n") ;
}
else printf ("erreur choix étape \n") ;
//////////////////////////////////////////////////////////////////
void main() {
int x ;
printf("Donnez le nombre de candidats") ;
scanf("%d", &x)
candidat Tab[x];
remplissage(x,Tab);
affichage(x,Tab);
}
Partie B : Les listes chaînées
Exercice 1
1)
Type
Cellule : Enregistrement
val: Entier
suiv : Liste
Fin Cellule
Liste : ^cellule
2)
Var
L : Liste
3)
Procédure CréerListe(n : Entier ; var L : Liste)
Var
Tete, p : Liste
i : Entier
Début
Allouer(Tete)
Ecrire("Entrer élément Tête :")
Lire(Tete^.val)
Tete^.suiv ← nil
L ← Tete
Pour i de 2 à n faire
Allouer(p)
Ecrire("Entrer élément n° :",i)
Lire(p^.val)
p^.suiv ← nil
L^.suiv ← p
L←p
Fin Pour
L ← Tete // pointer sur la tête de la liste
Fin
4)
Procédure AffichageIter(L : Liste)
Var
p : Liste
Début
p←L
Tant que p ≠ nil Faire
Ecrire(p^.val)
p ← p^.suiv
Fin Tant que
Fin
Procédure AffichageRecu(L : Liste)
Début
Si L ≠ nil Alors
Ecrire(L^.val)
AffichageRecu(L^.suiv)
Fin Si
Fin
5)
Version itérative
Fonction Recherche(x : Entier ; L : Liste) : Booléen
Var
p : Liste
Début
p←L
Tant que ((p ≠ nil) ET (p^.val ≠ x)) Faire
p ← p^.suiv
Fin Tant que
Si (p = nil) Alors
Recherche← Faux
Sinon
Recherche← Vrai
Fin Si
Fin
Version récursive
Fonction Recherche(x : Entier ; L : Liste) : Booléen
Début
Si L = nil Alors
Recherche← Faux
Sinon
Si L^.val = x Alors
Recherche ← Vrai
Sinon
Recherche ← Recherche(x, L^.suiv)
Fin Si
Fin Si
Fin
6)
Procédure AjouterTete(x : Entier ; var L : Liste)
Var
Tete : Liste
Début
Allouer(Tete)
Tete^.val ← x
Tete^.suiv ← L
L←Tete
Fin
7)
Version itérative
Procédure Supprimer(x : Entier ; var L : Liste)
Var
P,Q : Liste
Début
Si L = nil Alors
Ecrire("Liste vide, impossible de supprimer ",x)
Sinon
Si L^.val = x Alors
P←L //mémorisation de l’élément à supprimer
L ← L^.suiv
Sinon
P ← L^.suiv
Tant que ((P ≠ nil) ET (P^.val ≠ x)) Faire
Q←P
P ← P^.suiv
Fin Tant que
Si P ≠ nil Alors
Q^.suiv ← P^.suiv
Fin Si
Fin Si
Libérer(P)
Fin Si
Fin
Version récursive
Procédure Supprimer(x : Entier ; var L : Liste)
Var
P : Liste
Début
Si L ≠ nil Alors
Si L^.val = x Alors
P ←L
L ← L^.suiv
Libérer(P)
Sinon
Supprimer(x, L^.Suiv)
FinSi
FinSi
Fin
Exercice 2
Procédure Inverse (var L : Liste)
Var
P=Old_First,Q=New_First : Liste
Début
Old_First ←nil
Tant que L ≠ nil Faire
New_First ← L^.suiv
L^.suiv ← Old_First
Old_First ← L
L ← New_First
Fin Tant que
Fin
Exercice 3
Procédure Tri_Bulle( L : Liste)
Var
P : Liste
Temp : Entier
Trié : Booleen
Début
Si L = nil OU L^.suiv = nil Alors
Ecrire ("La liste est vide ou contient un seul élément : rien à trier !")
Sinon
Trié = Faux
P←L
Répéter
Trié← Vrai
P←L // pointeur sur le premier élément
Tant que P^.suivant ≠ nil Faire
Si P^.val > P^.suiv^.val Alors
Temp ← P^.val
P^.val ← P^.suiv^.val // Permutation
P^.suiv^.val ← Temp
Trié ← Faux
Fin Si
P ← P^.suiv
Fin tant que
Jusqu’à Trié = Vrai
Fin Si
Fin
Exercice 4
Procédure Concatener(L1, L2 : Liste)
var
L3 : Liste
Début
Si L1 = nil ET L2 = nil Alors
L3 ← nil
Sinon Si L1 ≠ nil ET L2 = nil Alors
L3 ← L1
Sinon Si L1 = nil ET L2 ≠ nil Alors
L3 ← L2
Sinon
//affectation de la première liste L1
L3 ← L1
// pointer sur le dernier élément de L3
Tant que L3^.suiv ≠ nil Faire
L3 ← L3^.suiv
Fin Tant que
//affectation de la liste L2 à la fin de L3
L3^.suiv ← L2
Fin Si
Fin
Exercice 5
Procédure Fusion( var L1 :Liste ; L2 : Liste ; var L3 : Liste)
Var
Tete, P, Q, S : Liste
Début
Si L1 = nil Alors // L1 est vide
L1 ← L2
Sinon
Si L2 ≠ nil Alors
P ←L1 //mémorisation de L1
Q ←L2 //mémorisation de L2
Si L1^.val < L2^.val Alors
L3^.val ← L1^.val
L1 ← L1^.suiv
Sinon
L3^.val ← L2^.val
L2 ← L2^.suiv
FinSi
S ← L3
L3 ← L3^.suiv
Tant que L1 ≠ nil ET L2 ≠ nil Faire
Si L1^.val < L2^.val Alors
L3^.val← L1^.val
L1← L1^.suiv
L3 ← L3^.suiv
Sinon
L3^.val← L2^.val
L2← L2^.suiv
L3 ← L3^.suiv
Fin Si
Fin Tant que
Si L1 ≠ nil Alors
//continuer avec L1
Tant que L1 ≠ nil Faire
L3^.val← L1^.val
L1← L1^.suiv
L3 ← L3^.suiv
Sinon Si L2 ≠ nil Alors
//continuer avec L2
Tant que L1 ≠ nil Faire
L3^.val← L2^.val
L2← L2^.suiv
L3 ← L3^.suiv
Fin Tant que
Fin Si
L1 ← S //pointer L1 à la tête de la liste
Fin Si
Fin Si
Fin
Exercice 7
Fonction Palindrome(L : Liste) :Booléen
Var
Stop : Booléen
Deb, Fin, Q : Liste
Début
Deb← L // Pointeur sur le premier élément
Fin←L// Pointeur sur le dernier élément
Si Deb = nil Alors
Palindrome← Faux
Sinon
Tant que Fin^.suiv ≠ nil Faire // Récupérer le pointeur sur le dernier élément de la liste
Fin ← Fin^.suiv
Fin Tant que
Tant que Deb^.val = Fin^.val ≠ nil ET Deb ≠ Fin Faire
Deb ← Deb^.suiv
Q ← Deb
Tant que Q^.suiv ≠ Fin Faire
Q ← Q^.suiv
Fin Tant que
Fin ← Q
Fin Tant que
Si Deb ≠ Fin Alors
Palindrome← Faux
Sinon
Palindrome← Vrai
Fin Si
Fin Si
Fin
