les structures de données : complet!

Les structures de données (rappel)

Niveau : 3eme scientifique
Lycée Ibn Ibn Mandhour ​
Trabelsi I
2023/2024

Tout les algorithmes, quelques soit leurs complexités, ont la structure suivante :

​

​Un algorithme est un ensemble de pas ordonnés permettant de résoudre un problème.

• L'ordinateur stocke, les données et autres objets utilisés dans le programme, dans des variables.

• Une variable est un emplacement dans la mémoire vive qui peut changer de contenu à tout moment.

• NB: une variable ne peut contenir qu'une seule valeur à la fois, et c'est toujours la dernière valeur obtenu.

• Pour donner une valeur à une variable on peut soit utiliser :

  • La saisie : lire(le_nom_de_la_variable)

  • l'affectation : le_nom_de_la_variable <-- une valeur compatible au type de la variable

Les variables

• Contrairement à une variable, la constante ne change pas de valeur tout le long du programme..

• Avec la constante, on ne peut ni utiliser :

  • La saisie : lire(le_nom_de_la_constante)

  • l'affectation : le_nom_de_la_constante <-- une valeur compatible avec sa valeur

Les constantes

Les opérateurs arithmétiques

Les opérateurs sur le types numériques (entier (int ) et réel (float))

​Algorithme	​Python	​Type de résultat
​+	​+	​entier ou réel
​-	​-	​​entier ou réel
​*	​*	​​entier ou réel
​/	​/	​réel
​Div	​//	​entier
​Mod	​%	​entier

Les opérateurs logiques

​Algorithme	​Python	​Type de résultat
​=	​==	Booleén
​≠	​!=	Booléen
​<	​<	Booléen
​>	​>	​Booléen
​≤	​<=	​Booléen
​≥	>=	​Booléen
∈	...<=...<=...	Booléen

saisir un entier formé par deux chiffres et l'inverser.
Exp : pour N= 34 le programme affichera R=43

​

​App1

​​Algorithme inverse
Début
Ecrire ("donner un entier de 2 chiffres")
Lire(N)
a<-- N div 10
b<-- N mod 10
R<--b*10+a
écrire (R)
Fin

​​Implémentation Python

Nom ​	​Type/Nature
​N, a, b, R	​entier

​TDO

• Pourquoi mon algorithme, ne fonctionne pas correctement avec un entier de 3 ou 4 chiffres?

• Comment "obliger" l'utilisateur à saisir seulement des entiers de 2 chiffres?

​

• Il faut ajouter un contrôle de saisie :

  ==> Le programme demandera à l'utilisateur de saisir un entier de 2 chiffres

• il va ensuite tester le nombre donné pour voir s'il est formé par 2 chiffres.

• si la réponse est non, alors il répétera la demande de saisie, jusqu'à ce que l'utilisateur donne un entier formé par 2 chiffres

• si la réponse est oui alors le nombre sera accepté, et l'ordinateur passera au traitement.

​​Algorithme inverse_version_2
Début
Répeter
Ecrire ("donner un entier de 2 chiffres")
Lire(N)
Jusqu'a N dans [10,99]
a<-- N div 10
b<-- N mod 10
R<--b*10+a
écrire (R)
Fin

​​Implémentation Python

Nom ​	​Type/Nature
​N, a, b, R	​entier

​TDO

saisir un entier formé par 3 chiffres et afficher la somme de ses chiffres.
Exp : pour N= 346 le programme affichera R=3+4+6 = 13

​

​App2

​​Algorithme somme_chiffres
Début
Répéter
Ecrire ("donner un entier de 3 chiffres")
Lire(N)
Jusqu'a N dans [10,99]
a<-- N div 100
b<-- N mod 100 div 10
c<-- N mod 10
R<--a+b+c
écrire (R)
Fin

​​Implémentation Python

Nom ​	​Type/Nature
​N, a, b,c, R	​entier

​TDO

Quelques fonctions arithmétiques standards sur les entiers et réels

​Rôle	Nom algorithmique ​	Nom en python	Type d'entrée​	type de résultat​
​retourne la valeur la plus proche	​y<--arrondi(x)	​y=round(x)	réel ou entier​	entier​
​retourne la valeur absolue	​y<-abs(x)-	y=abs(x)	réel ou entier​	réel ou entier​
​retourne la racine carré	​y<--racine(x)	from math import *	réel ou entier​	réel​
​retourne la partie entière	​y<--ent(x)	y=int(x)	réel ou entier​	entier​
​retourne un entier entre a et b	​y<--alea(a,b)	from random import *	2 entiers	​1 entier

Le type booléen (Vrai/ Faux )

​Les opérations logiques sur les booléens:

​Opérateur en algorithme	Opérateur en python​	Signification​
​non	not​	​Négation (le contraire)
​ou	or / |	​Conjonction
​et	​and / &	​Disjonction

Manipulation des opérateur (la table de vérité)

​A	B​	non(A)	A et B	A ou B
​Vrai	​Vrai	​Faux	​Vrai	​Vrai
Vrai	Faux​	Faux​	Faux​	Vrai​
Faux​	Vrai​	Vrai​	Faux​	Vrai​
Faux​	Faux	Vrai	Faux​	Faux

A chaque caractère, correspond, un code ASCII (c'est un entier entre entre 0 et 255)

Les caractères

​Rôle	Algorithme​	Python​	Entrée​	Sortie​
​retourne le code ASCII d'un caractère	​a<--ord(b)	​a=ord(b)	​b: caractère	​a:entier
​retourne le caractère correspondant à un code ASCII	​c<--chr(d)	c=chr(d)	d:entier​	c:caractère​

​Fonctions standards sur les caractères

Correction Application minuscule

Écrire un programme qui permet de saisir un caractère alphabétique majuscule et de trouver puis afficher sa minuscule.
Exp : pour c="F" le resultat sera r="f"

​​Algorithme minuscule
Début
répéter
Écrire ("donner un caratére alphabétique majuscule")
Lire(c)
jusqu'a c ∈ ["A","Z"]
a<--ord(c)+32
r<-- chr(a)
écrire (R)
Fin

​​Implémentation Python

Nom ​	​Type/Nature
​c, R	​caractère

​TDO

Les chaines de caractères

• Une chaine de caractères est une suite de n caractères. avec n >=0.

• Si n= 0, on dit qu'on a une chaine vide : ""

• Une valeur de type chaine est toujours écrite entre guillemets ".

• une chaine peut contenir n'importe quel caractère.

• le caractère espace est présenté entre 2 guillemets " "

• Les caractères de la chaine sont indexés de 0 (indice du premier caractères ) à n-1 (n étant le nombre de caractères de la chaine)
  ou de -1 (indice du dernier caractère) à -n

​"H	e​	l​	l​	o​	​	w​	o​	r​	l​	d​	!​"
​0	1​	2​	3​	4​	5​	6​	7​	8​	9​	10​	11​
​-12	​-11	​-10	​-9	​-8	​-7	​-6	​-5	​-4	​-3	​-2	-1​

​ch[i] : est le caractère numéro i de la chaine ch.
avec i ∈ [0,n-1] # n = nombre de caractères de la chaine
ou i ∈ [-1, -n]

​Remarque importante

En python, une chaine de caractère et immuable --> on peut pas modifier les caractères de la chaine directement dans la chaine.
Exemple pour ch = "bonjour"
ch[0]<-- "B" est interdit
ch<--"Bonne journée" est permis

Les fonctions prédifinis sur les chaines

L<--long(ch) # on affecte à l'entier L le nombre de caractères de ch.
En python :
L=len(ch)

​Longueur de la chaine

On peut concaténer 2 ou plus chaines.
La concaténation n'est pas commutative (ch1+ch2 ≠ ch2+ch1)

La concaténation (+)

x<-- sousChaine(ch,D,F)

• On affecte à x, les caractères de ch, compris entre D et F-1

• ch[F] n'est pas inclu

• D et F 2 entiers

• D<=F

en python:
x=ch[D:F]

copier une partie de la chaine

effacer une partie de la chaine

ch<-- efface(ch,D,F)

• On affecte à ch, les caractères de ch, sans ceux compris entre D et F-1

• ch[F] n'est pas inclu

• D et F 2 entiers

• D<=F

en python:
ch=ch[0:D]+ch[F:len(ch)]

ch<-- majus(ch)

• On transforme ch en toute majuscule.

• s'applique aussi avec les variables de type caractères.

• majus("a")="A"

• majus("A")="A"

• majus("8")="8"

en python:
ch=ch.upper()

transformer la chaine en majuscule

chercher la position de ch1 dans ch2

p<-- pos(ch1,ch2)

• On affecte à p, la première position de ch1 dans ch2 si ch1 existe dans ch2, sinon p=-1

• p entier

• p ∈ [-1,long(ch)-1]

en python:
p=ch2.find(ch1)

N<-- valeur(ch)

• On affecte à N la valeur de ch

• ch doit être numérique !!

• Il y aura erreur si ch n'est pas numérique

• N peut être de type entier ou réel

en python:
N=int(ch) ou float(ch)

transformer la chaine en valeur numérique

convertir une valeur numérique en chaine

ch<-- convch(N)

• On affecte à ch, la valeur de N entre guillemets

• N peut être entier ou réel

en python:
N= str(N)

Vérifier si une chaine est numérique

B<-- estnum(ch)

• On affecte à B, la valeur vrai si ch est numérique, faux sinon

en python:
B= ch.isdigit()