187 lines
4.2 KiB
Plaintext
187 lines
4.2 KiB
Plaintext
----------------------- Recherche d'un élément dans un tableau -----------------------
|
||
|
||
Données :
|
||
L un tableau de nombre
|
||
N le nombre d'éléments dans le tableau
|
||
E l'élément que l'on cherche
|
||
|
||
Résultat :
|
||
Vrai : si l'élément est dans le tableau
|
||
Faux : S'il n'y est pas
|
||
|
||
Algorithme :
|
||
pour compteur allant de 0 à N-1 faire
|
||
si L[compteur] <- E alors
|
||
on renvoie Vrai et on termine le programme
|
||
finsi
|
||
finpour
|
||
on renvoie Faux
|
||
|
||
|
||
----------------------- Calcul de la moyenne des nombre d'un tableau -----------------------
|
||
|
||
Données :
|
||
L un tableau de nombre
|
||
N le nombre d'éléments dans le tableau
|
||
|
||
Résultat :
|
||
la moyenne des éléments de L
|
||
|
||
Algorithme :
|
||
M <- 0
|
||
compteur <- 0
|
||
pour compteur allant de 0 à N-1 faire
|
||
M <- M+L[compteur]
|
||
finpour
|
||
M <- M/N
|
||
|
||
|
||
|
||
|
||
|
||
----------------------- Calcul de la somme des nombres d'un tableau -----------------------
|
||
|
||
Données :
|
||
L un tableau de nombre
|
||
N le nombre d'éléments dans le tableau
|
||
|
||
Résultat :
|
||
la somme des éléments de L
|
||
|
||
Algorithme :
|
||
<- 0
|
||
compteur <- 0
|
||
pour compteur allant de 0 à N-1 faire
|
||
m <- M+L[compteur]
|
||
finpour
|
||
|
||
|
||
|
||
----------------------- Recherche du minimum d'un tableau -----------------------
|
||
|
||
Données :
|
||
L un tableau de nombre
|
||
N le nombre d'éléments dans le tableau
|
||
|
||
Résultat :
|
||
le minimum des éléments de L
|
||
|
||
Algorithme :
|
||
<- L[0]
|
||
compteur <- 0
|
||
pour compteur allant de 0 à N-1 faire
|
||
si M > L[compteur] alors
|
||
M <- L[compteur]
|
||
finsi
|
||
finpour
|
||
|
||
|
||
----------------------- Tri par sélection -----------------------
|
||
Données :
|
||
T : Un tableau d’éléments indexés de 0 à N-1
|
||
|
||
Résultat :
|
||
T : Le tableau sera trié
|
||
|
||
Algorithme :
|
||
N <- longeur(T)
|
||
pour i allant de 0 à N-2 faire
|
||
Imin <- i
|
||
pour j allant de i+1 à N-1 faire
|
||
si T[j] < T[Imin] alors
|
||
Imin <- j
|
||
finsi
|
||
finpour
|
||
échanger T[i] et T[Imin]
|
||
finpour
|
||
|
||
|
||
----------------------- Tri par insertion -----------------------
|
||
Données :
|
||
T : Un tableau d’éléments indexés de 0 à N-1
|
||
|
||
Résultat :
|
||
T : Le tableau sera trié
|
||
|
||
Algorithme :
|
||
N <- longeur(T)
|
||
pour i allant de 1 à N-1 faire
|
||
j <- i
|
||
tant que j>0 et T[j] > T[j-1] faire
|
||
échanger T[j] et T[j-1]
|
||
j <- j-1
|
||
fintantque
|
||
finpour
|
||
|
||
|
||
|
||
----------------------- Recherche dichotomique -----------------------
|
||
|
||
Données :
|
||
L : un tableau trié par ordre croissant et non vide, indexé de 0 à N-1
|
||
El : l'élément que l'on cherche
|
||
|
||
Résultat :
|
||
Trouvé : Si l'élément est dans le tableau
|
||
Pas trouvé : Sinon
|
||
|
||
Algorithme :
|
||
Bmin <- 0
|
||
Bmax <- longueur(L)-1
|
||
tant que Bmin <= Bmax faire
|
||
med <- (Bmin+Bmax) // 2
|
||
si L[med] > El alors
|
||
Bmax <- med-1
|
||
sinon si L[med] < El alors
|
||
Bmin <- med+1
|
||
sinon faire
|
||
renvoyer 'Trouvé'
|
||
finsi
|
||
fintantque
|
||
renvoyer 'Pas trouvé'
|
||
|
||
|
||
----------------------- Rendu de monaie -----------------------
|
||
|
||
Données :
|
||
P le tableau de pièces que l'on peut rendre
|
||
arendre le montant à rendre
|
||
|
||
Algorithme :
|
||
pour compteur allant de 0 à longueur(L):
|
||
tant que P[compteur] <= arendre faire
|
||
rendre P[compteur]
|
||
arendre <- arendre - P[compteur]
|
||
fintantque
|
||
finpour
|
||
|
||
----------------------- K plus proches voisins -----------------------
|
||
Notes :
|
||
- Seul le principe est à connaitre, pas le calcul spécifique de la distance.
|
||
|
||
Données :
|
||
T un tableau (0,N-1) contenant les données d’entrainement
|
||
Chaque élément du tableau est un tuple contenant la position sur le
|
||
graphique et la classe : (X, Y, nom)
|
||
E un élément dont on connait la position et dont on veut estimer la classe
|
||
C’est également un tuple mais sans classe : (X, Y)
|
||
k le nombre de voisins dont on va regarder la classe
|
||
|
||
Algorithme :
|
||
# Ce tableau contiendra des tuples (distance, classe)
|
||
distances <- tableau vide de taille N
|
||
pour i allant de 0 à N-1 faire
|
||
distances[i] <- ( racine( (E[0]-T[i][0])^2 + (E[1]-T[i][1])^2) , T[i][2])
|
||
finpour
|
||
|
||
distances_triées <- distances trié par distance croissante
|
||
|
||
voisins <- []
|
||
pour i allant de 0 à k-1 faire
|
||
voisins <- voisins suivi de distances_triées[i][1]
|
||
finpour
|
||
|
||
Compter le nombre d’occurence de chaque classe dans le tableau voisins
|
||
classe <- la classe avec le plus d’occurences
|
||
renvoyer classe
|