DS Algorithme
Emna Hamrouni LBD1
Exercice 1:
Procédure algo1
Début écrire ("veuillez saisir un nombre") // O(1)
Lire(n) // O(1)
Pour i de 1 a n pas 1 faire // O (log n)
T <- 1
tant que T <= n faire // O(n)
Écrire ("hello world !") // O(1)
T <- T*2
Fin tant que
Fin pour
Fin
la complexité de l'algorithme est O(n log (n))
Exercice 2:
1) fonction initialiser_liste (): ^liste_entier
retourner NIL
fin fonction
2) procédure ajout_fin(L: ^liste_entier, x: entier)
si L = NIL alors
L <- nouvelle cellule(x)
Sinon
cellule_courante <- L
tant que cellule_courante^.suiv ≠ NIL faire
cellule_courante <- cellule_courante^.suiv
fin tant que
cellule_courante^.suiv <- nouvelle_cellule(x)
fin si
fin procédure
fonction nouvelle_cellule(valeur: entier): ^cellule
nouvelle <- allouer_memoire_pour_cellule()
nouvelle^.val <- valeur
nouvelle^.suiv <- NIL
retourner nouvelle
fin fonction
3) fonction taille_liste(L: ^liste_entier): entier
si L = NIL alors retourner 0
sinon
retourner 1 + taille_liste(L^.suiv)
fin si
fin fonction
4) procédure supprimer_pos(L: ^liste_entier, p: entier)
si L = NIL alors
retourner
fin si
si p = 1 alors
cellule_a_supprimer <- L
L <- L^.suiv
libérer_mémoire(cellule_a_supprimer)
retourner
fin si
cellule_precedente <- L
pour i de 1 à p-2 faire
si cellule_precedente = NIL alors
retourner
fin si
cellule_precedente <- cellule_precedente^.suiv
fin pour
si cellule_precedente^.suiv = NIL alors
retourner
fin si
cellule_a_supprimer <- cellule_precedente^.suiv
cellule_precedente^.suiv <- cellule_a_supprimer^.suiv
libérer_mémoire(cellule_a_supprimer)
fin procédure
5) Algorithme principal
N, p, élément, i: entiers
L: ^liste_entier
L <- initialiser_liste()
Ecrire( "Entrez le nombre d'éléments à ajouter à la liste : ")
lire( N)
pour i de 1 à N faire
écrire( "Entrez l'élément ", i, " : " )
lire (élément)
ajout_fin(L, élément)
fin pour
répéter
écrire ("Entrez la position de l'élément à supprimer (1 à ", taille_liste(L), ") : ")
lire( p)
tant que p < 1 ou p > taille_liste(L)
supprimer_pos(L, p)
fin Algorithme