Introduction à Python et contrôle logique
Transféré par
cour.mael.peyreIntroduction à Python et contrôle logique
Transféré par
cour.mael.peyreI - Introduction aux structuresdecontrôleetàlalogiquealgorithmiqueen
Python
ythonestunlangagedeprogrammationcrééàlafindesannées1980parGuidovanRossum
P
auxPays-Bas.Sapremièreversionaétépubliéeen1991.InspirédeslangagesABC,Pythona
étéconçupourêtresimple,lisibleetpuissant,permettantainsidedévelopperrapidementdes
programmes tout en restant facile à comprendre.
1 – Affichage de texte, suite d'instructions
n Python, pour afficher du texte, on utilise la fonction print(). Elle permet d’afficher un
E
message à l'écran. Par exemple, pour afficher le texte "Hello world!", on écrit :
print("Hello world!")
emarque 1.1 : Si 'il y a un espace en trop, une majuscule au lieud'uneminuscule,ou
R
toute autre différence par rapport au texte exact, le programme ne fonctionnera pas
correctement. Il est donc important de respecter exactement la syntaxe et les caractères
spécifiés.
Si on oublie une parenthèse, cela produit une des erreurs suivantes :
SyntaxError: unexpected EOF while parsing
Syntax Error: invalid syntax
Si on ne place pas correctement les guillemets, cela produit une des erreurs suivantes :
SyntaxError: EOL while scanning string literal
NameError: name 'Bonjour' is not defined
SyntaxError: invalid syntax
emarque 1.2 : Par la suite, nous indiquerons le résultat d'un programme avec un trait
R
rouge et une petite flèche. Par exemple :
I mportant:Gestiondeserreursliéesauxfonctionsnondéfinieslorsducontrôled'un
module :Lorsque l'on pilote un module, comme un robot, il est important d'inclure les
lignes nécessaires pour accéder aux fonctions permettant de le contrôler. Si on oublie la
lignequifournitlesinstructionspourbougerlerobot,commedansleprogrammesuivant:
haut()
droite()
bas()
gauche()
n observe une erreur : NameError: name 'haut' is not defined. Cela signifie que le
O
programme ne reconnaît pas la fonction haut().Pourcorrigercela,ilfauts'assurerquele
programmeinclutbienlalignequipermetd'accéderauxfonctionsdurobot(parexemple,
une instruction import). Prenez le temps de comprendre ce qui ne va pas, puis modifiez
votre programme de sorte qu'il marche la prochaine fois.
2-Répétitions d'instructions
n Python, pour répéter une action plusieurs fois, on utilise la boucle for. On fera par
E
exemple :
ans ce programme,forloopinrange(5):permetderépéteruneinstructionplusieurs[Link]
D
ne faut pas oublier les deux-points : à la fin de la ligne for,carcelaindiqueledébutdela
boucle. L'indentation (lesespacesavantleprint)estnécessairepourmontrerquecetteligne
fait partie de la boucle. Cela rend le code beaucoup plus simple et évite de répéter
manuellement l'instruction à chaque fois.
emarque 2.1 : Pour l’indentation vous pouvez utiliser la touche tabulation de votre
R
clavier pourmodifierleniveaud'indentation,plutôtqued'écrirevous-mêmelesespacesà
la main.
orsque vous revenez à la ligne, l'indentation est conservée, ce qui vous permet d'écrire
L
facilementdesinstructionsaumêmeniveau.Pourrevenirauniveauprécédent,vousdevez
appuyer sur la touche tabulation pendant que la touche majuscule est enfoncée, comme
lorsque vous écrivez une lettre majuscule.
( il s'agit de la touche majuscule, pas de la touche verrouillage majuscule située juste
au-dessus (et juste en dessous de la touche tabulation))
Le niveau d'indentation :
- augmente (Tab) lorsque l'on rentre dans la boucle,
- et il diminue (Maj+Tab) lorsqu'on sort de la boucle.
Attentionàtoujoursutiliser3espacespourindenterlecodesivousutilisezlesespaces.Si
l'indentation n'est pas toujours la même, vous obtiendrez une erreur si vous utilisez
l'indentation avec des espaces normaux.
stuce 2.2 : Les commentaires servent à ajouter des explications dans lecode,ignorées
A
lors de l'exécution. En Python, un commentaire sur une lignecommencepar#.Pourdes
commentaires multi-lignes, on utilise trois guillemets triples """.
3-Calculs et découverte des variables
A-Les calculs de base en python
ourafficherunnombreenPython,onutiliselafonctionprint().Parexemple,pourafficher
P
le nombre 111, on écrit :
On peut aussi effectuer des calculs avec des opérateurs arithmétiques :
- ddition : +
A
- Soustraction : -
- Multiplication : *
- Division : /
Exemple : print(2 + 3) affiche 5.
es opérations peuvent être combinées, et la priorité des opérations suit les règles des
L
mathématiques. Les parenthèses permettent de contrôler l'ordre des calculs. Par exemple :
- p rint((12 - 3) * 4) affiche 36
- print(12 - 3 * 4) affiche 0
es espaces autour des opérateurs ne sont pas nécessaires, mais ils rendent le code plus
L
lisible.
B-Notion de variable
nprogrammation,unevariableestunesortede"boîte"oùl’onpeutstockerdesvaleurspour
E
pouvoir les réutiliser par la suite. Cela nous évite de répéter lesmêmesvaleursàplusieurs
endroitsdansnotre[Link]Python,pourcréerunevariable,ilsuffitdedonnerunnom
à la variable et de lui attribuer une valeur à l’aide d’un =. Par exemple :
stuce3.1:Dansleslangagesdeprogrammation,lechoixdunomd'unevariableestassez
A
libre. Voici les règles générales.
- L'identifiant se constitue de caractères collés (pas d'espace).
- Les caractères autorisés sont essentiellement :
- les lettres majuscules et minuscules naturelles :
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ ;
-les chiffres 0123456789 ;
-le caractère « _ » (appelé « sous-tiret »).
- Le premier caractère du nom d'une variable ne peut pas être un chiffre ; le nom
1erNombre est donc invalide.
- Les mots-clés du langage ne peuvent être utilisés pour nommer desvariables.En
Python, c'est par exemple le cas du mot for.
Dans le cas du langage Python, les accents sont acceptés dans les identifiants.
ous devez profiter de cette flexibilité pour choisir des noms qui aideront àcomprendre
V
votre programme.
I mportant :Lesprogrammesutilisentsouventplusieursvariablespourstockerdifférentes
valeurs et effectuer des calculs ou gérer différentes informations simultanément. Donc,
chaque variable peutcontenirunevaleurdifférente.Lorsqu'oneffectuedescalculsoudes
actions, on peut utiliser plusieurs variablesensemble.Chaquevariablepeutêtremodifiée
indépendamment, et les valeurs peuvent être réutilisées dans le programme. Si on tente
d'utiliser une variable qui n'a pasétédéfinie,uneerreursurvient.Ilestcrucialdevérifier
que toutes les variables nécessaires sont bien initialisées avant leur utilisation. Les
variablessontsensiblesàlacasse,cequisignifiequenometNomsontconsidéréescomme
deux variables différentes. Il faut être précis dans l’écriture et la syntaxe des noms des
variables pour éviter des erreurs.
nprogrammation,pourmodifierlavaleurd'unevariable,onutilisel'opérationd'affectation.
E
Cela consiste à attribuer une nouvelle valeur à une variable en réécrivant soncontenu.Par
exemple, si une variable x contientlavaleur10,etquevousaffectezàxlavaleur20,vous
dites que x a changé de valeur.
'utilisationdusymboled'égalitépeutvousparaîtreparticulière.Eneffet,enmathématiques,
L
l'égalitéénonceunfait.Ainsi,dansuncontextedonné,x=y−zsignifiequ'ilestvraiquexa
lamêmevaleurquey−z.L'affectationcontenance=contenance-15enrevanche,décritune
action:l'enregistrementdelavaleurplacéeàdroitedu=danslavariableindiquéeàgauche.
Le contenudelavariablecontenancechangeradonclaprochainefoisquel'onaffecteraune
valeur à la variable.
Astuce 3.2 : Lorsqu'on définit une variable, il estimportantdechoisirunnomdescriptif
q uireflèteclairementcequecettevariablereprésente.Onpeututiliserplusieursmotspour
créer un nom précis, et la convention la plus courante est le CamelCase, oùchaquemot
commenceparunemajusculesauflepremier.Exemple:longueurFeuille,nbPiècesJaunes,
maxHauteurPiquets. Il est déconseillé d'utiliser des noms trop courts ou non descriptifs
comme a, b ou i, car cela rend le code difficile à comprendre.
I mportant :Lors de l'exécution d'un programme, il est crucial de suivre l'évolution des
variablespourcomprendrecommentelleschangentàchaqueétape.Celapermetdemieux
saisir le flux du programme et d'identifier d’éventuelles erreurs.
4-Lecture de l'entrée
ette partietraitedel'interactionentreunprogrammePythonetl'utilisateur,spécifiquement
C
de la gestion des entrées utilisateur et de l'affichage des résultats.
nPython,lafonctioninput()estutiliséepourdemanderdesinformationsàl'utilisateur.Cela
E
permet de rendre le programme dynamique et interactif.
arexemple,sileprogrammedoitrecevoirunnomouunâge,onutiliseinput()pourafficher
P
un message invitant l'utilisateur à entrer une donnée. L'exemple suivant illustre cela :
'entrée correspond aux données que l'utilisateur ou un autre système fournit à un
L
programme. En Python, l'entrée se fait principalement à l'aide de la fonction input().Cette
fonction permet de capturer des valeurs saisies par l'utilisateur via le clavier.
La sortiecorrespondauxinformationsqueleprogrammeafficheàl'utilisateurouàunautre
système. En Python, la fonction principale pour afficher des résultats est print().
Parlasuite,nousindiqueronslesdonnéesd'entréed'unprogrammeavecuntraitbleuetune
petite flèche (ce qui les distinguera des sorties au trait rouge). Par exemple, pour le
programme ci-dessous :
I maginonsqueleprogrammedemandeunentiermaisquel'utilisateurfournisseuntexte,par
exemple«coucou».Leprogrammedéclarealorsuneerreur,car«coucou»nepeutpasêtre
interprété comme un nombre.
otez qu'une erreur similaire peut se produire si vous ajoutez des lignes vides avant un
N
nombre.
I mportant:Sionoublieleint(...)etquel'onécritjusteinput()àlaplacedeint(input()),on
peut avoir de grosses surprises, comme le montre l'exemple suivant.
ionoublieleint(...)autourduinput(),lesvaleursnesontpastraitéescommedesentiers
S
mais comme du texte. Le symbole + agit alors comme un opérateur qui concatène
(c'est-à-dire qui met bout à bout) deux textes, et du coup on obtient 11 collé à 22
(c'est-à-dire 1122) à la place de 11 additionné à22(c'est-à-dire33).Faitesdonctoujours
attention à ne pas utiliser input() tout seul. De plus, si les résultats des calculs sont
manifestement faux, pensez à vérifier si les nombres ne sont pas traités comme du texte.
J usqu'à présent, chaque foisqu'onvoulaitafficherunechaînedecaractères,unevariableou
une autre valeur, on utilisait une instruction print.
nfait,avecunseulprint,ilestpossibled'afficherautantdevaleursquel'onveut!Ilsuffit
E
pour cela de les séparer par une virgule entrelesparenthèses.Onpourraiteneffetécrirele
programme précédent ainsi :
aisoùestpasséel'espace?Lesdifférentesvaleurssontautomatiquementséparéesparune
M
espaceàl'affichage.Enfait,toutcommeleretouràlaligneàlafin,cetteespaceséparatrice
peut être affectée paruneoption:sep.Justeavantdefermerlaparenthèsed'uneinstruction
print, on peut indiquer les valeurs de sep et de end. Par exemple :
outefois,danscertainscas,ilpeutêtredifficiledeserepérerdansuneinstructionprinttrès
T
longue.N'hésitezdoncpasàenutiliserplusieursàlasuitesicelarendlalectureplusagréable
! De manière générale, le langagedeprogrammationpermetdeformulerlamêmechosede
différentesfaçons.Certainesécrituressontcependantplusagréablespourunhumain:c'està
vousdelestrouver;enaucuncasl'ordinateurnevousyaidera!Lorsqu'uneécriturevousest
inhabituelle, prenez un peu de temps pourcherchercommentl'écriredesortequ'ellesoitla
plus « propre » (jolie, optimale, demandant moins d'effort de lecture à une personne
quelconque) possible, afin de vous en servir automatiquement la prochaine fois. Lescodes
quenousprésentonsdanslescoursetlescorrectionssontgénéralementdebonnesréférences
(sachant que nous n'utilisons que les notations que nous avons vues jusqu'alors).
I mportant:UneerreurcouranteenPythonsurvientlorsqu'unprogrammetentedeliretrop
dedonnées,cequientraîneunmessaged'erreur"EOFError"."EOF"signifie"EndOfFile"
(fin de fichier). Cela se produit lorsqu'un programme essaie de lire une donnée
supplémentaire alors qu'iln'yenaplusàlire.L'erreurseproduitgénéralementlorsqu'une
entréeattendueparinput()n'estpasfournie,parexemple,lorsqu'ons'attendàunecertaine
quantité de données mais qu'elles ne sont pas disponibles.
emarque4.1:Enprogrammation,lesvariablessontutiliséespourstockerdesdonnéeset
R
lesmanipulerdansunprogramme.Cependant,uneerreurfréquenteseproduitlorsquel'on
essaie d'utiliser une variable qui n'a pas été définie dans le contexte d'exécution, ce qui
entraîne des erreurs. Cette erreur est souvent liée à la portée des variables.
5-Tests et conditions
I l est souvent nécessaire de tester uneconditionpuissoncontraire.Parexemple,sionveut
vérifiersionpeutrangertouslesœufsdansuneseuleboîtede12compartiments,onpourrait
testerdeuxconditions:unepourlesœufs≤12etuneautrepourlesœufs>12.Celapeutse
fairedemanièrepluséléganteenutilisantelse.L'instructionifpermetdetesterunecondition.
Si elle est vraie, le programme exécute le code associé. Si la condition est fausse, le code
dans le bloc else sera exécuté. Par exemple, on a :
Remarque 5.1 :Si l'on place un else sans if qui leprécède, on obtient une erreur :
i vousobtenezunetelleerreur,vérifiezdoncquechacundevoselseestbienconnectéà
S
un if qui le précède.
I mportant :En Python, après avoir effectué un test avec une condition if, vous pouvez
exécuter plusieurs instructions si la condition est vraie. Ces instructions doivent être
indentées correctement pour qu'elles soient exécutées dans le cadre du même bloc. Par
exemple :
our vérifier si deux valeurs sont égales enPython,onutilisel'opérateur==.Cetopérateur
P
compare deux valeurs et retourne True si elles sont égales, sinon il retourne False.
- = : L'opérateur d'affectation. Il sert à attribuer une valeur à une variable.
- Exemple : ageMarie = 25 (ici, on assigne la valeur 25 à la variable ageMarie).
- == : L'opérateur de comparaison. Il sert à tester si deux valeurs sont égales.
- Exemple : ageMarie == ageRobin (on teste si les valeurs de ageMarie et
ageRobin sont égales).
orsqu'on veut uniquement tester si deux valeurs sont différentes, on utilise l'opérateur!=,
L
qui se lit « différentde».Parexemple,lecodesuivantafficheunmessagesiunanimaln'a
aucune chance d'être une araignée car il n'a pas 8 pattes.
6-Structures avancées
ous avez déjà appris que, lorsqu'on place une bouclederépétitionàl'intérieurd'uneautre
V
bouclederépétition,laboucleimbriquée(cellequisesitueàl'intérieurdel'autre)doitavoir
tout son code indenté (décalé vers la droite). De la même manière, il faut indenter
correctementlecodelorsqu'unblocconditionnel(«si»ou«si/sinon»)estplacéàl'intérieur
d'une boucle de répétition ou d'un autre bloc conditionnel, ou bien lorsqu'une boucle de
répétitionestplacéàl'intérieurducorpsd'untest.Leprogrammesuivantillustreceladansle
cas d'une boucle de répétitionplacéàl'intérieurd'unif.Ceprogrammelitunentiernommé
cible.Sicibleestunnombrepositif,leprogrammeaffichetouslesentierscomprisentre1et
cible à l'aide d'une boucle de répétition. Sinon, le programme affiche le texte « Rien à faire ».
Observez la manière dont est indenté le code qui se trouve entre le if et le else.
7-Conditions avancées, opérateurs booléens
n Python, on utilise les conditions pour tester si une situation est vraie ou fausse. Cela
E
permet d'exécuter différentes actions en fonction de la situation.
'opérateur and est utilisé pour vérifier si deux conditions sont vraies enmêmetemps.Par
L
exemple,sionveutsavoirsiunâgeestentre12et25ans,onpeuttesterlesdeuxconditions
suivantes :
Explication de l'exemple :
1 . E ntrée : Le programme demande à l'utilisateur d'entrer son âge avec input().
2. Condition : Le programme teste si l'âge est à la fois supérieur ou égal à 12 et inférieur
ou égal à 25.
3. Si la condition est vraie : Si l'âge est entre 12 et 25, le programme affiche "Carte
possible".
4. Sinon : Si l'âge n'est pas dans cette plage, le programme affiche "Carte impossible".
emarque 6.1 : En Python, une valeur booléenne peut être soit True (vrai), soit False
R
(faux).Uneconditionesttoujourssoitvraie,soitfausse.Cesvaleurssontutiliséespourles
comparaisons et permettent de prendre des décisions dans le programme.
Les opérateurs booléens, comme and et or, permettent de combiner ces valeurs :
- a nd : Les deux conditions doivent être vraies.
- or : Au moins une condition doit être vraie.
esopérateursbooléens,commel'opérateurand,permettentdemanipulerlesvaleursTrue
L
et False, de la même manière que les opérateurs numériques manipulent les nombres. Il
existe un ordre de prioritéentrelesopérateursbooléensetnumériquesenPython,maisil
est toujours préférable d'utiliser des parenthèses pour rendre le code plus clair et
compréhensible.
I mportant :Une erreur courante avec les booléens est de tester explicitement si une
variableestégaleàTrueouFalse,cequiestinutile,carlavariableelle-mêmeestdéjàTrue
ouFalse.Ilestpréférabledetesterdirectementlavariableelle-même,sansutiliser==True
ou == False. Pour tester la négation d'une valeur booléenne, on peut utiliser l'opérateur
not(). Un programme ne doit jamais contenir de == True ou==False.Ilestplusclairet
plus efficace de tester directement la variable ou d'utiliser not() pour la négation.
ousavezvucommentcombinerdeuxconditionslorsqu'onveutquelesdeuxsoientvraiesen
V
même temps. On veut parfois en avoir au moins une des deux, c'est-à-dire soit l'une, soit
l'autre,soitlesdeux.Parexemple,onpeutavoiruneréductionsionamoinsde25ansousi
on a plusde60ans.Onaiciutilisélemot"ou",quiestuneautremanièredecombinerdes
conditions et qui se traduit en Python par l'opérateur booléen or :
anslaréalité,ilfautenfaitavoirentre12et25ansetnonpassimplementmoinsde25ans.
D
On peut donc combiner lesconditionsenutilisantàlafoisun"et"etun"ou",enn'oubliant
pas de mettre les bonnes parenthèses :
n peut donc combiner facilement les opérateurs booléens pour construire des conditions
O
complexes à partir de conditions simples.
8-Répétitions conditionnées
n a parfois besoin derépétercertainesinstructionsjusqu'àcequ'uncertainchangementce
O
soit produit. Par exemple, demander un mot de passe tant que l'utilisateurn'apasdonnéle
bon. On a ici utilisé dans la phrase le terme « tant que », ce qui signifie qu'on abienune
condition pour savoir quand s'arrêter. On ne peut pas utiliser notre boucle « répéter »
habituelle, car on ne sait pas combien de fois l'utilisateur vasetromper!Onvadoncfaire
intervenir une autre boucle : la boucle « tant que », que nous allons manipuler dans ce
chapitre.Ellesenommewhiledansleslangagesdeprogrammation(traductionenanglaisde
« tant que »).
insi, tant que la condition motDePasse ≠ secret est vraie, on continue à demander un
A
nouveau mot de passe. Il est bien sûr possible d'utiliser des opérateurs booléens pour
combiner des conditions et les valeurs booléennes sont également utilisables.
ans un code utilisant une boucle « tant que », si on utiliseunemauvaisecondition,ilest
D
possible que le programme ne s'arrête jamais.
I ci,onamisvaleur-1aulieudevaleur+1;ducoup,lavariablevaleurnefaitquediminuer
au lieu d'augmenter. Elle ne sera donc jamais plus grande que 10 et le programme ne
s'arrêtera jamais (en supposant les limites des entiers infinies) ! Si vous écrivez un tel
programme, le système d'évaluation automatique du site vous indiquera que « votre
programme a dépassé la limite de temps ». En effet, pour éviter les programmes qui ne
s'arrêtentjamais,nousavonsunsystèmequilesbloqueautomatiquements'ilsmettenttropde
tempsàdonnerleurréponse.Sivousvoyezuntelmessage,essayezdevérifierlesconditions
dans vos boucles.
II- Bases de la programmation informatique : structures et outils essentiels
1-Nombres à virgules et autres outils
nPython,lesnombresàvirgules(ounombresdécimaux)nes'écriventpasavecunevirgule
E
maisavecun"point",commelefontlesanglaisoulesaméricains.Ainsi,sionveutafficher
le nombre "3,14" on va écrire le programme suivant :
our affecteràunevariableunevaleurdécimale(c'est-à-direnonentière),oupourfairedes
P
calculs, on fait comme pour les entiers.
ttention de bien utiliser un point et pas une virgule quand vous écrivez des nombres « à
A
virgule », sinon vous aurez des surprises. Regardons simplement quelques exemples
d’erreurs:
I l faut donc toujours utiliser un point pour les "nombres à virgule".
Commeenmathématiques,sionveutdiviserdeuxnombres,onlessépareparlesymbole/Il
est très simple de diviser entre eux des nombres à virgule ou des entiers, on obtiendra
toujours un nombre à virgule comme résultat :
Remarque 1.1: Pour lire un nombre à virgule on utilisele code suivant :
ela ressemble donc beaucoup à la lecture d'un nombre entier, on utilise simplement
C
float(input())aulieudeint(input()).(Lemot"float"vientdel'anglais"floating-point"qui
signifie "à virgule flottante".)
I mportant:Quesepasse-t-ilsionessaiedelireunentieralorsquelenombrequ'onnous
donne est un nombre décimal ?.
eprogrammes'attendaitdoncàavoirunentiermaisilyavaitunnombredécimal,cequia
L
provoqué une erreur.
orsque l'on travaille avec des nombres à virgule, le résultat peut être approximatif, car
L
seulement 17 chiffres seront conservés.
es calculs peuvent ainsi donner des résultats surprenants, comme des erreursd'arrondi.À
L
l'inverse, avec des nombres entiers, les résultats sont exacts et lesvaleurspeuventêtretrès
grandes. Lors d'une division, le résultat est toujours un nombre à virgule, ce qui peut
provoquer une perte d'information, comme dans le cas d'un nombre entier modifiéparune
division. Les nombres à virgule ne peuvent pas être stockés avec une précisionparfaiteen
mémoire,cequipeutentraînerdelégèreserreurs,mêmesurdescalculssimples.Deplus,les
tests d'égalité avec des nombres à virgule ne sont pas fiables, car ces valeurs sont des
approximations.Enrésumé,ilestpréférabled'utiliserdesentierspourlescalculslorsquec'est
possible, et d'éviter lestestsd'égalitéoud'inégalitésurlesnombresàvirgule.Ilvautmieux
convertir en nombres décimaux le plus tard possible dans le programme.
uand un nombre à virgule a beaucoup de chiffres il est affiché avec ce qu'on appelle la
Q
notation scientifique :
Si on ne retenait pas que les 17 premiers chiffres, le résultat serait égal à
15241578858405731126352.69
= 1524157885840573112635.269 * (10)
= 152415788584057311263.5269 * (10 * 10)
= ......................................
= 1.524157885840573112635269 * (10 * 10 * ... * 10 * 10 * 10)
<- 22 fois le nombre 10 ->
On ne garde que les 17 premiers chiffres en faisant un arrondi c'est-à-dire
1.524157885840573112635269 * (10 * 10 * ... * 10 * 10 * 10)
<- 22 fois le nombre 10 ->
soit
1.524157885840573 * (10 * 10 * ... * 10 * 10 * 10)
<- 22 fois le nombre 10 ->
Qu'on note donc, en notation scientifique :
1.524157885840573e+22
nmathématique,onvaaussinotercettevaleur1.524157885840573×1022,où"1022"selit
E
"10 exposant 22" et vaut donc "(10 * 10 * ... * 10 * 10 * 10)" avec 22 fois le nombre 10.
I mportant:DansPython,touteslesfonctions(enparticulierlesfonctionsmathématiques)
ne sont pas disponibles par défaut. Elles sont rangéesdanscequ'onappelledesmodules
(ou bibliothèques) qu'onpeutvoircommedes"boitesàoutils".Quandonveututiliserun
"outil"ilfautd'abord"ouvrirlaboite".Ainsi,pouraccéderauxfonctionsmathématiquesde
façon simple on utilise la commande suivante :
from math import *
Elle peut se traduire par "importer tout ce qui est dans le module math".
ettecommandeestàplacertoutenhautdufichieretpermetensuited'utiliserdansvotre
C
programme toutes les fonctions ou constantes définies dans ce module. On dit qu'on a
importé le module.
'arrondi d'un nombre décimal consiste à le transformer en entier, avec deux méthodes
L
principales : l'arrondi à l'entier inférieur et l'arrondi à l'entier supérieur.
n Python, pour effectuer ces arrondis, il faut importer le module math et utiliser les
E
fonctions floor() pour l'entier inférieur et ceil() pour l'entier supérieur.
esfonctionsretournentunentier,pasunnombredécimal.Ilestimportantdenoterquepour
C
les nombres négatifs, l'arrondi suit la même logique, mais l'entier inférieur sera plus petit.
ous avons vu comment calculer un arrondi à l'entierinférieurousupérieuravecfloor()et
N
ceil(). La fonctionround()arrondit un nombre à l'entierle plus proche.
i la valeur est à mi-chemin (ex. 1.5), l'arrondi dépend de la méthode choisie. Par défaut,
S
Python utilise l'arrondi bancaire, qui arrondit vers l'entier pair.
Cas particulier de 0.5 : différentes possibilités d'arrondi
- u plus petit : Prendre l'entier inférieur.
A
- Au plus grand : Prendre l'entier supérieur.
- Vers zéro : Prendre l'entier le plus proche de zéro.
- Vers l'infini : Prendre l'entier le plus éloigné de zéro.
Bancaire : Prendre l'entier pair lorsqu'il y a égalité (ex. 1.5 → 2 et 2.5 → 2).
'arrondi bancaire est utilisé pour éviter l'accumulationd'erreursdansdessériesdecalculs.
L
En Python, si une valeur estexactementàmi-chemin,elleseraarrondieversl'entierpairle
plus proche.
emarque 1.2 : La divisionentièrepermetdediviserunnombreenunquotiententieret
R
un reste. On a :
- ividende : Le nombre à diviser.
D
- Diviseur : Le nombre par lequel on divise.
- Quotient : Le résultat entier de la division.
- Reste : La partie restante après la division.
Si le reste est égal à 0, le diviseur est un diviseur exact du dividende.
Division Euclidienne
adivisioneuclidienneconsisteàdiviserunnombre(dividende)parunautre(diviseur),de
L
manière à obtenir un quotient et un reste. Elle est définie par la relation :
ini
Copier
dividende = diviseur * quotient + reste
où 0 <= reste < diviseur.
En Python
- L 'opérateur // permet de calculer le quotient.
- L'opérateur % permet de calculer le reste.
Division Euclidienne avec des nombres négatifs
a divisioneuclidiennefonctionneaussipourlesnombresnégatifs,engarantissantquele
L
reste soit toujours positif ou nul et inférieur au diviseur.
aprioritédesopérateursenPythonsuitlesrèglesdesmathématiques:lesmultiplicationset
L
divisions sont effectuées avant les additions et soustractions. Les opérateurs de division
entière//etdemodulo%suiventlamêmeprioritéquelesopérateursdemultiplicationetde
division.Celasignifiequ'ilssontcalculésavantlesadditionsetsoustractions.Lorsdecalculs
complexes,lesparenthèsespermettentd'évitertouteambiguïtéetd'assureruncalculcorrect.
Si un calcul semble ambigu, il est recommandé de toujours utiliser des parenthèses pour
clarifier l'ordre des opérations et éviter des erreurs.
2-Découverte des tableaux
A-La boucle “for”
a boucle for en Python permet de répéter une action plusieurs fois. Elle fonctionne avec
L
range(), qui génère une séquence de nombres.
Exemple simple :
range()prend trois arguments: début, fin, et saut.Par défaut, le début est 0 et le saut est 1.
La syntaxe peut être simplifiée :
- S ans spécifier le saut : for nombre in range(10):
- Sans spécifier début et saut : for nombre in range(10):
B-Les tableaux
u lieu d'utiliser 12 variables pour chaque mois de l'année, vous pouvez utiliser un tableau
A
pour stocker les nombres de jours. Un tableau permet de regrouper plusieurs valeurs sous un
même nom.
Pour créer un tableau, on utilise le code suivant (Exemple de tableau) :
I ci, le tableau nbJours contient les jours de chaque mois. Les indices vont de 0 à 11 (pas de 1
à 12, car la numérotation commence à 0 en Python).
Pour accéder à un élément du tableau, on utilise son indice :
ela permet d'éviter de multiplier les variables et rend le code plus compact, surtout si vous
C
avez beaucoup de données à gérer.
'une des erreurs les plus courantes avec les tableaux est d'essayer de lire un élément qui
L
n'existe pas, c'est-à-dire d'utiliser un indice trop grand :
'erreur a donc lieu à la ligne 5 : les 3 premières valeurs se sont doncaffichéescommeil
L
fallait mais commeiln'existepasd'élémentd'indice3(lesindicesvontde0à2)uneerreur
est survenue. Si on essaie de traduire ce message cela veut donc dire "Erreur d'indice :
l'indice du tableau est en dehors de l'intervalle" Que se passe-t-il si on essaie d'utiliser un
indice négatif ? Cela ne produit pas d'erreur mais n'affiche pas ce qu'on veut.
emarque 2.1 : Comme pour toute autrevariableilestbiensûrpossibledemodifierles
R
élémentsd'untableau.Parexemplesionsouhaitedéclareruntableaudetaille7,modifier
lesvaleursauxindices0et6,puislireunentieretlemettreàlapositiond'indice3ilfaut
utiliser le code suivant :
stuce 2.1 : Nous avons abordé la création d'un tableau de taille fixe avec des valeurs
A
initialesprécises.Cependant,latailledutableaupeutparfoisêtreplusgrandeoudépendre
d'une entrée dynamique.
I l est possible de définir un tableau de taille déterminéeenmultipliantunélémentinitial
(comme un zéro ou une autre valeur) par la taille du tableau. Cette approche permet
d'adapter facilement la taille du tableau à des besoins variés,quecesoitavecunevaleur
fixe ou une variable comme valeur initiale.
I l est facile de trier un tableau en Python car un algorithme de triestdéjàfourni.Voiciun
code complet, nous l'expliquerons en dessous :
I lsuffitdoncd'appelerlafonctionsort()surletableau,àl'aideducodeafindedemanderletri
du tableau.
I ci,nousavonssimplementutiliséuntriquiexistedéjàdansPython.Ilestbiensurpossible
deprogrammersonpropretri(etilexistebeaucoupdetrisdifférents!)maispourlemoment
le plus simple est d'utiliser le tri déjà fourni. Nous aurons l'occasion de vous présenter les
différents algorithmes de tri plus tard.
I maginez qu'on vousdemandedeliretroisentierspuisdelesafficherséparéspardestirets.
Unpremierprogrammepourraitêtreécritdemanièrerépétitiveenimprimantchaqueélément
un par un avec des tirets entre eux. Cela fonctionne, mais ce n'est pas très pratiquenitrès
agréable à écrire.
ne façon plus simple consiste à utiliser une méthode qui permet d'insérerdirectementles
U
valeurs dans une chaîne de caractères formatée. Cette approche rendlecodeplusconciset
lisible. Vous pouvez placer des élémentsàl'endroitsouhaitédanslachaîne,puislesinsérer
automatiquementenutilisantdesargumentsdansunefonctiondeformatage.Celafonctionne
non seulement pour des entiers, mais aussi pour d'autres types de données comme des
nombres à virgule ou du texte.
Tableaux et indices négatifs :
Regardons sur un exemple :
nremarquedoncquel'indice"-1"correspondaupremierélémentenpartantdelafin,que
O
"-2" correspond au second élément en partant de la fin et ainsi de suite. Attention cependant :
n remarque doncquel'indice"-1"correspondaupremierélémentenpartantdelafin,que
O
"-2" correspond au second élément en partant de la fin et ainsi de suite. Attention cependant :
nobtientuneerreurpourl'indice"-4"carlequatrièmeenpartantdelafinn'existepas.Les
O
indices négatifs sont donc valables en Python mais nous vous conseillons de ne pas les
utiliser car ils sont source d'erreurs.
ans les exercices de ce chapitre, vous travailliez avec des tableaux dont la taille était
D
généralement sauvegardée dans une variable. Cependant, Python offre une méthode pour
connaître la taille d'un tableaudirectement,sansavoiràseréféreràunevariableexterne.Il
suffit d'utiliser une fonction qui permet d'obtenir la taille d'un tableau, ce qui simplifie la
gestion des données. Cette approche rend le code plusflexibleetévitededevoirstockerla
taille manuellement.
3-Chaînes de caractères
nordinateurnesaitmanipulerquedesnombres,ainsisionsouhaitemanipulerdutexte,on
U
va associer à chaque caractère (lettre, chiffres, ponctuation...) un entier en choisissant une
convention (par exemple que la lettre "A" est représentée par l'entier 65). On appelle ces
conventions des encodages, et il en existe un grand nombre, qui ne sont pas forcément
compatibles entre eux !
ur ce site, nous avons fait le choix d'utiliser l'encodage UTF-8 qui est le plus générique,
S
permettant de gérer de la même manière les caractères de toutes les langues. Certains
langages de programmation, comme Java ou Python,sontcapablesdemanipulerdestextes
encodés en UTF-8, mais ce n'est pas le cas de C ou C++ par exemple.
ussi,danslesexercicesmanipulantdutexte,nousn'utiliserontquedescaractères"simples"
A
quisontreprésentésdelamêmemanièreenUTF8etenASCII,l'encodagequeCetC++sont
capables de manipuler simplement.
Vous avez déjà vu comment en Python il était possible d'afficher du texte.
Mais il est possible de faire beaucoup plus de choses que simplement afficher du texte.
Il est possible de stocker du texte dans une variable, afin de l'afficher plus tard.
On peut aussi demander une ligne de texte à l'utilisateur
n parlera également de chaîne de caractères pour désigner une suite de caractères,
O
possiblement sur plusieurs lignes.
stuce3.1:EnPython,ilestpossibledecomparerdeuxchaînesdecaractèresselonl'ordre
A
alphabétique (appelé également ordre lexicographique).
n peut donc comparer directement deux chaînes de caractères et tous les opérateursde
O
comparaisons sont disponibles, c'est-à-dire <, <=, ==, !=, => et >.
stuce 3.2 : Quand on nous donne une chaîne de caractères on a parfois besoin de
A
connaître sa longueur, c'est-à-dire le nombre de caractères qu'elle contient. EnPython,il
existe une fonction pour cela, comme on peut le voir sur le code suivant :
Danscechapitre,vousavezapprisàlireunelignecomplète.Cependant,ilpeutarriverque
v oussouhaitiezlireunseulmotpourpouvoirlemanipulerindépendammentdurestedela
ligne.Unmotestdéfininaturellementcommeunesuitedelettressansespaces,qu'ilssoient
des espaces réels, des retours à la ligne ou des tabulations.
upposonsquevousdeviezlireunentieretunmotsurlamêmeligne,puisaffichercemot
S
un certain nombre de fois. Python permet de lire une ligne entière, mais il est possible
d'extraire les mots ou nombres individuels de cette ligne en utilisant des outils spécifiques.
insi, il est facile de découper une ligne en mots et d'accéder à desmotsspécifiquesen
A
utilisant des méthodes comme split() , qui permet dediviserunechaînedecaractères
enuntableaudemots.Unefoiscelafait,vouspouvezfacilementmanipuleretafficherces
mots, ou encore lesconvertirend'autrestypessinécessaire,commeunentierdanslecas
d'un nombre.
ivousvoulezlireplusieursmotssurunemêmeligne,commeunnomdepaysetuneville,
S
vous pouvez utiliser une méthode qui permet de séparer la ligne en mots et d'affecter
directement ces mots à des variables. Cela rend le code plus court et plus lisible.
e manière similaire, si vous souhaitez lire plusieurs entiers sur la même ligne, vous
D
pouvezutiliseruneméthodesimilaire.Cependant,vousdevrezconvertirchaqueélémenten
entier, ce qui peut être optimisé grâce à une fonction comme
map() , qui permet de
convertir directement touslesélémentsd'unelignesansavoiràlestraiterunparun.Cela
simplifie encore davantage l'écriture du programme.
J usqu'à présent nous avons vu comment manipuler des chaînes de caractères dans leur
ensemble,maisilesttoutàfaitpossibledemanipulerchacundescaractèresdelachaîne.Par
exemple, voici comment on peut lire et afficher le premier et le sixième caractère d'une
chaîne de caractères :
nremarquequepourleschaînesdecaractèreslesindicesdémarrentà0.Ainsi,silongueur
O
est la longueur de la chaîne de caractères, alors il est possible d'accéder aux caractères
d'indices 0, 1, 2, ..., longueur-1. C'est donc pareil que pour les tableaux.
ous avez déjà appris à comparer des chaînes de caractères en fonction de l'ordre
V
alphabétique. Il est également possible de comparer des caractèresindividuelsdirectement.
En Python, les opérateurs de comparaison classiques (<, <=, ==, !=, >=, >) peuvent être
utilisés pour comparer des caractères entre eux. Vous pouvez aussi comparer un caractère
d'une chaîne à un caractère spécifique, que ce soit un caractère extrait de la chaîne ou un
caractère défini explicitement dans le code. Il est important de noter que, en Python, un
c aractèreestenréalitéunechaînedecaractèresd'uneseulelettre,cequipermetd'utiliserles
mêmes techniques que pour les chaînes de caractères pour effectuer des comparaisons.
Il est aussi possible de déclarer un caractère indépendamment d'une chaîne.
n Python, il n'existe pas de type distinct pour uncaractèreindividuel.Uncaractèreesten
E
réalité une chaîne de caractères d'une seule lettre. Cela signifie que les mêmes principes
appliqués aux chaînes de caractères peuvent égalementêtreutiliséspourtravailleravecdes
caractères.
e plus, il est possible de demander un caractère à l'utilisateur et de l'afficherdelamême
D
manière que pour une chaîne classique.
I l arrive parfois qu'il soit nécessaire de modifier les caractères d'une chaîne de caractères.
Cependant, en Python, les chaînes de caractères sont immuables,cequisignifiequ'ellesne
peuvent pasêtremodifiéesdirectement.Poureffectuerdesmodifications,ondoitpasserpar
d'autres structures de données, comme les tableaux. Ainsi, pour modifier une chaîne de
caractères,ilfautd'abordlaconvertirenuntableaudecaractères.Unefoisquevousavezun
tableau,vouspouvezfacilementmodifierseséléments.Aprèsavoirapportéleschangements
nécessaires,vouspouvezreconvertirletableaudecaractèresenunechaînepourl'afficherou
l'utiliser comme bon vous semble. Cela permet de contourner la limitation des chaînes
immuables tout en permettant une modification flexible et pratique des données.
4-Fonction
Parallèle avec les fonctions mathématiques
a notion de fonction utilisée enprogrammationetalgorithmiqueserapprochedecelledes
L
mathématiques sur certains points. En mathématiques, une fonction associe àunparamètre
unevaleur.Àpartirdecetteassociation,unefoisqu'elleestdéfinieetposée,onpeutfaireune
étude sur les diverses propriétés de la fonction.
omme c'est souvent le cas avec les notions, en informatique, le principe de fonction va
C
ressembleràceluidesmathématiques.L'objectifn'estcependantpasdefaireuneétude,mais
de fonctionner d'une certaine manière avec l'ordinateur.
Nom et paramètres
Voici l'exemple d'une fonction mathématique prenant un paramètre
𝑥
x :
𝑓:𝑥↦4𝑥+1
f:x↦4x+1
On peut aussi écrire l'égalité :
𝑓(𝑥)=4𝑥+1
f(x)=4x+1
n programmation, on utilise généralementdesnomslongs,toutcommepourlesvariables,
E
car c'est encore une occasion de mieux décrire ce que fait notre programme. Ensuite, une
fonctiongéreraenprincipeunnombrefixedeparamètres(ouarguments),quipeutêtrenulou
multiple. Au seindelafonction,cesparamètresserontnaturellementdesvariables(avecun
nom les décrivant si possible).
Valeur de retour
nmathématiques,unefonctionassocieàsesparamètresunevaleur.Enprogrammation,cela
E
pourraêtrelecas:onditalorsquelafonctionretourneunevaleur.Néanmoins,unefonction
pourra également se contenter d'exécuter des instructions.
Écriture
anslaplupartdeslangagesdeprogrammation(généralementimpératifs;tousceuxdusite
D
sauf OCaml), la définition d'une fonction ne ressemble pas du tout à celle que l'on fait en
mathématiques. Enrevanche,unerequêteàunefonction,dite«appel»,enesttrèsproche:
par exemple fonction(arg1, arg2, arg3) pour une fonction à trois paramètres.
etteécriturevouséveillecertainementquelquechose?Etoui:nousavonsdéjàfaitappelà
C
denombreusesfonctions,notammentpourlesopérationsterminalesdenotrerobot:afficher
du texte, récupérer la saisie, se déplacer, bouger des objets.
Allons-y !
ans le chapitre, nous commencerons par manipuler des fonctions sans aucun argumentet
D
sans valeur de retour. Nous verrons ensuite que les fonctions peuvent être bien plus
intéressantes lorsqu'elles sont paramétrables ; et enfin, nous écrirons des fonctions qui
retournent une valeur.
ans le cas où l'on modifierait la valeur d'un paramètre,ilestimportantdenoterquecette
D
modification n'a d'effet qu'à l'intérieur de la fonction. Si le paramètre a été passé sous la
formed'unevariableaumomentdel'appel,celle-cineserapasmodifiée,commelemontrele
témoin suivant :
ngarderaentêtequelorsquel'onpasseunevaleurenparamètreàunefonction,cettevaleur
O
est copiée dans une variable de la fonction correspondant à ce paramètre. Vous ne pouvez
donc pas pour l'instant modifier la valeur d'une variable à partir d'une fonction.
I lfautcependantnoterladifférenceentrelavariableetsavaleur:siunevaleurestmodifiée,
alorscelaaaussiunimpactàl'extérieurdelafonction.C'estlecasparexemplesionajoute
unecaseàuntableau.Nousneproposonspasencoredecoursquiestclairsurcesujet—qui
est d'ailleurs souvent assez confus dans l'enseignement de l'informatique.
ans le cas d'une fonction qui affiche plusieurs fois un caractère, on peut imaginer que le
D
nombrederépétitionsdececaractèrevarieàchaqueappeldelafonction.Pourcela,ilsuffit
d'ajouterunparamètresupplémentairelorsdel'appeldelafonction,quispécifiecombiende
fois afficher le caractère.
our que la fonction accepte ce paramètre, il faut le déclarer lors de la définition de la
P
fonction.Chaqueparamètreestséparéparunevirguledansladéclarationdelafonction.Vous
pouvez ensuite utiliser ce paramètre dans les instructions de la fonction.
i une fonction prend plusieurs paramètres, elle doit être appelée en fournissant tous les
S
arguments nécessaires. Cependant, Python permet derendrecertainsparamètresoptionnels,
ce qui offre une certaine flexibilité dans l'appel des fonctions.
esfonctionsquenousavonsvuesjusqu'àprésenteffectuaientdescalculsoudesopérations,
L
maisellesnemodifiaientpasdirectementledéroulementduprogramme.Imaginonsquenous
ayons souvent besoin de calculer la valeur absolue d'un nombre.
ouspouvonscréerunefonctionquiprendenentréeunnombreetcalculesavaleurabsolue.
N
Mais pour que cette fonction influence l'exécution du programme, elle doit retourner une
valeur. Cettevaleurpeutensuiteêtreutiliséedansleprogramme,assignéeàunevariableou
traitée comme n'importe quel autre résultat.
our que la fonction renvoie un résultat à l'appelant, il faut utiliser l'instruction
P return
.
Cetteinstructionpermetderenvoyerunevaleuretdequitterlafonctionentransmettantcette
valeur à l'appel du programme.
Quelques remarques sur l'instruction return :
- I l est possible d'avoir plusieurs instructions return dans une fonction, chacune
renvoyant une valeur.
- Il est essentiel qu'une fonction qui doit retourner une valeur exécute une instruction
return pour transmettre le résultat.
- Dans une fonction qui ne renvoie aucune valeur, il est également possible d'utiliser
return sans valeur. Cela provoque simplement la sortie immédiate de la fonction sans
retourner de résultat. En Python, une absence de valeur signifie None, qui est l'objet
spécial qui représente l'absence de valeur.
uand on veut utiliser une fonction, pour l'appeler, on a besoin des informations
Q
suivantes :
- s on nom ;
- ses paramètres et leur type ;
- le type de la valeur de retour (s'il y en a une).
es informations sont communément appelées le prototype de la fonction. Cela
C
correspond en fait, dans le code source, à l'en-tête de la fonction. En voici deux
exemples pour vous y ramener :
'est ce qu'il est nécessaire de connaître pour appeler une fonction. Notez toutefois
C
qu'en Python, l'en-tête de la fonction n'impose pas le type des paramètres et de la
valeur de retour (en pratique, celle-ci respecte toutefois un certain format, qu'il faut
connaître pour utiliser la fonction).
Utiliser une fonction non définie
n Python, vous devez définir toutes vos fonctions avant de les appeler, sinon vous
E
obtiendrez une erreur. Si vous essayez d'appeler une fonction qui n'a pasétédéfinie,
Python renverra une erreur NameError.
Nombre de paramètres
ivousappelezunefonctionavecunnombreincorrectdeparamètres,Pythongénérera
S
une erreur TypeError. Cela indique que vous n'avez pas fourni le bon nombre
d'arguments à la fonction.
Valeur de retour
i vous oubliez d'utiliser return dans une fonction qui estcenséerenvoyerunevaleur,
S
Python renverra None par défaut. Cela peut poser un problème si vous attendez une
autre valeur.
Erreurs peu explicites
i vous faites une erreur de syntaxe, comme séparer des paramètres par un
S
point-virgule au lieu d'une virgule, cela générera une erreur de syntaxe. Python vous
indiqueraqu'ilyauneerreur,maisilestparfoisnécessairedebienlirelemessagepour
en comprendre la cause exacte.
Résumé
nPython,chaqueerreurdesyntaxeoudelogiquerenverraunmessaged'erreur.Ces
E
messages peuvent parfois être difficiles à comprendre, surtout en cas de fautes de
syntaxeoud'appelincorrectdesfonctions.Ilestimportantdetoujourslireattentivement
lesmessagesd'erreuretdevérifierlecodeàl'endroitspécifiépouridentifierlacausedu
problème.
Décomposer pour simplifier
es fonctions sont un outil essentiel dans la programmation pour rendre le code plus
L
lisible et réutilisable. Elles permettent de diviser un problème complexe en
sous-problèmes plus simples. En décomposant un problème, on le rend plus facile à
aborder et à résoudre.
orsqu'unproblèmeestdivisé,chaquesous-problèmedevientplusfacileàcomprendre.
L
Deplus,cetteapprochepermetdetraiterchaquepartiedemanièreindépendanteetde
se concentrer sur une seule tâche à la fois, réduisantainsilacomplexitéduproblème
global.
es fonctions permettent d'appliquer cette méthode dans la création d'un programme.
L
Ellessontutiliséespourregrouperdestâchesspécifiquesetrépétitives,cequiévitede
dupliquer du code et facilite les modifications futures. En organisant le programmeen
petites unités de travail (les fonctions), on améliore la lisibilité et la maintenance du
code.
Bonnes pratiques pour organiser son code :
● U tiliser des fonctions pour chaque action distincte :Chaque fonction doit
effectuer une tâche bien définie et isolée.
● Nommer les fonctions de manière descriptive :Choisirdes noms de fonctions
clairs, qui expliquent ce que fait chaque fonction.
● Réduire les répétitions :Éviter de répéter des blocsde code similaires en les
regroupant dans des fonctions.
● L
imiter la taille des fonctions :Les fonctions ne doivent pas être trop longues.
Il est conseillé de ne pas dépasser une certaine longueur (comme 25 lignes par
exemple) pour garantir la lisibilité.
L'importance de l'organisation du code :
n code bien organisé facilite non seulement la compréhension immédiate, mais il
U
permet également de rendre le programme plus évolutif et plus facile à maintenir. En
prenant le temps de structurer le code de manière claire dès le départ, on évite de
perdredutempsplustardàchercherdesbugsouàajouterdenouvellesfonctionnalités
dans un code désorganisé.
Les commentaires :
es commentaires sont utiles pour rendre un code plus compréhensible, mais ils ne
L
doivent pas être utilisés pour compenser unmanquedeclartédanslecodelui-même.
Un code bien structuré et bien écrit n'a pas besoin de commentaires excessifs. Les
commentaires doivent être réservés aux parties complexes du code ou aux sections
nécessitant des explications supplémentaires.
III-Fondations et Concepts Avancés
1- Lecture/écriture rapide
Jusqu'à présent, pour lire une ligne de l'entrée, vous utilisiez :
ligne
=
input
()
nsuite,vouspouviezlaconvertirenunouplusieursentiersoutoutautreaction
E
sur cette ligne de l'entrée.
e problème est que la fonction input est très lente car elle gère des
L
fonctionnalités avancées destinées à une interface enlignedecommande(donc
sans intérêt dans nos exercices). Ainsi, pour certains des problèmes qui vont
suivre, elle ne vous permettra pas d'être suffisamment efficace.
Ilfautdoncutiliserunefonctionplusbasique.Ellesetrouvedanslemodulesys,
qu'il faut importer :
import
sys
Puis après, on utilise :
ligne
=
[Link]()
ette nouvelle fonction est jusqu'à 8 fois plus rapide que la précédente ! Tout
C
commeinput,elleretournelaprochainelignesurl'entrée;parcontreellelaissele
retour à la ligne (
\n ) à la fin. Si vous convertissez la chaîne en une ou plusieurs
aleurs (entiers, flottants), cela ne devrait pas vous déranger ; sinon, faites
v
attention.
otez que l'on peut aussi plus simplement remplacer la fonction input par
N
[Link]au tout début de son programme:
import
sys
input
=
[Link]
Écriture rapide
Ilestpossibledefaireplusrapidequeprintmaisonnegagneque50 %detemps,
ce qui n'est pas si intéressant. Cela peut cependant servir parfois ; ainsi, voici
comment faire :
import
sys
texte
=
"ABCDE"
entier
=
42
[Link](
"Texte : "
)
[Link](texte)
[Link](
str
(entier)
+
"\n"
)
↳
Texte : ABCDE42
Ilfautdoncutiliser[Link].Cettefonctionprendunetunseulparamètre
(alors que print pouvait en prendre n'importe quelle quantité, et comportait les
deux options sep et end) : la chaîne de caractères à afficher. Pour afficher une
valeur,ilfautdonclaconvertirenchaînedecaractèresaveclafonctionstr.Sil'on
veut afficher plusieurs textes, il faut appeler plusieurs fois la fonction, ou
concaténerleschaînesdecaractèresàafficher.Notezquecettefonctionn'insère
pas de retour à la ligneàlafindel'affichagecommelefaisaitprint:ilfautdonc
rajouter le\nsoi-même si l'on s'en sert.
2-Utiliser une fonction main
'interpréteur Python met beaucoup detempsàexécuterdesinstructionsquise
L
trouvent en dehors de toute fonction. Dans le programme suivant :
def
dedans(nbFois):
for
numFois
in
range
(nbFois):
print
(
"
Dedans"
)
nbFois
=
int
(
i
nput
())
for
numFois
in
range
(nbFois):
print
(
"
Dehors"
)
dedans(numFois)
les instructions en dehors de la fonction peuvent mettre plus de temps à
s'exécuter que celles qui se trouvent à l'intérieur ! En effet, le programme qui
exécute les scripts Python effectue beaucoup plus de traitements et demiseen
contexte pour les instructions du corps global (nous vous décrirons peut-être
lesquelles un de ces jours).
ourremédieràcela,ilsuffitdemettrelesinstructionsducorpsglobaldansune
P
fonction, que l'on nommera main pour se conformer aux langages exigeant une
tellefonction(C,C++etJavaparexemple).Onappelleradonccettefonctiondans
le corps global, et ce sera la seule instruction s'y trouvant :
def
dedans(nbFois):
for
numFois
in
range
(nbFois):
print
(
"
Dedans"
)
def
main():
nbFois
=
int
(
i
nput
())
for
numFois
in
range
(nbFois):
print
(
"
Dehors"
)
dedans(numFois)
main()
elapeutnettementaccélérercertainsprogrammesetvousseranécessairedans
C
certains exercices.
3-Modification raccourcie
orsque l'on veut modifier une variable en fonction de sa propre valeur, la
L
notation est un peu lourde. Prenons par exemple cette instruction qui permet
d'augmenter la variablenombrede 1, ce que l'on afait tant de fois :
nombre
=
nombre
+
1
;
e langage Python propose en fait un opérateur combinant l'addition et
L
l'affectation : . Il existe également de tels opérateurs pour tous les calculs
+=
arithmétiques du langage (et même d'autres opérations). Nous vous en
présentons ci-dessous ceux qui correspondent aux opérations que nous avons
utilisées jusqu'à présent.
nombre
+=
ajout
nombre
-=
retrait
nombre
*=
facteur
nombre
**=
exposante
nombre
/=
diviseur
nombre
//=
diviseur
# pour des entiers
nombre
%=
modulateur
Observez alors que si l'on écrit :
lapins
*=
lapins
+
agitation
our appliquer la croissance d'une population de lapins, on multiplie lapins par
p
lapins+agitation. C'est donc équivalent à une affectationavec des parenthèses :
lapins
=
lapins
*
(lapins
+
agitation)
Conclusion
ousemploieronsdésormaiscesopérateursdanslescoursetcorrections.Nous
N
vousencourageonsàvousenservirégalementpourrendrevotrecodeplusclair
et plus concis.
4-Opérations vectorielles
Concaténation rapide de liste/tableau
e langage Python est optimisé pour traiter des listes de données globalement. Ainsi
L
certaines opérations peuvent aller des dizaines, voir des centaines de fois plusvitesi
l'on en tient compte. Par exemple :
nbItems
=
5*
1
000
liste
=
[]
for
item
in
range
(nbItems):
liste
=
liste
+
[item
%
10
]
est très lent alors que
nbItems
=
5*
1
000
liste
=
[item
%
10
for
item
in
range
(nbItems)]
ou
nbItems
=
5*
1
000
liste
=
[]
for
item
in
range
(nbItems):
[Link](item
%
10
)
est 100 fois plus rapide. Une alternative également rapide est :
nbItems
=
5*
1
000
liste
=
[
N
one
]
*
nbItems
for
item
in
range
(nbItems):
liste[item]
=
item
%
10
IlfautcomprendrequelestableauxenPythonnesontnivraimentdestableaux,nides
listes, mais un compromis entre les deux. Ajouter unélémentàunelistepar
liste
+
[element]
,neprovoquepasseulementdesallocationsdemémoiremaislarecopiedu
tableau/liste dans son intégralité.
arcontre,danslesdeuxcasrapides,toutsepassecommesilamémoireétaitallouée
P
en une seule fois et un seul bloc. Il n'y a aucune recopie inutile.Danslaréalité,c'est
plus compliqué mais nous ne souhaitons pas l'expliquer ici.
Itérateurs
n peut penser que ces méthodes sont possibles caronpeutprévoirdèsledépartla
O
taille du tableau. Que faire si l'on ne peut prévoir cette taille à l'avance ?
anslecasoùcelaestraisonnableonpeutcommencerparsur-dimensionnerletableau
D
pour ensuite le recopier en une seule fois à sa plus juste taille :
maxItems
=
5
*
1
000
listeTemp
=
[
N
one
]
*
maxItems
nbItems
=
0
for
item
in
range
(maxItems):
if
item
%
7
==
0
:
listeTemp[nbItems]
=
item
%
10
nbItems
=
nbItems
+
1
liste
=
[
N
one
]
*
nbItems
for
item
in
range
(nbItems):
liste[item]
=
listeTemp[item]
listeTemp
=
[]
Ilyaunmoyenplus«pythonesque»d'obtenirexactementlemêmerésultat,plusrapide
et plus lisible.
maxItems
=
5
*
1
000
iste
l =
[item
%
10
for
item
in
range
(maxItems)
if
item
%
7
==
0
]
t que faire si les éléments à mettre dans la liste sont difficiles à construire et à
E
énumérer ? C'est là qu'intervient unedesconstructionslespluspuissantesdePython,
les itérateurs. Pour comprendre comment ils fonctionnent le mieux est deregarderun
exemple.
def
maListe(nbItems):
for
item
in
range
(nbItems):
if
item
%
7
==
0
:
yield
item
%
10
maxItems
=
5
*
1
000
liste
=
[item
for
item
in
maListe(maxItems)]
e programme calcule exactement la même liste que le précédent et aussi
C
efficacement. Par contre le mécanisme est beaucoup plus puissant car l'itérateur
maListe()peutêtretrèscompliqué.L'instruction
yieldenestlaclef,elleressembleà
une instruction
returnà ceci près quelorsdel'itérationlecodeseraappeléplusieurs
foisetreprendrajusteaprèsladernièreinstruction yield .Cetteinstructionnefaitdonc
pasquerenvoyerunrésultat,ellemémoriseégalementl'étatd’exécutionducalculpour
pouvoir ensuite le continuer !
Notons que l'on aurait pu remplacer la dernière ligne par le plus simple :
liste
=
list
( maListe(maxItems) )
nutilisesouventlafonction
O mapenliaisonavecunitérateurpourenfabriquerunautre
plus complexe. Ainsi le résultat de :
print
(
list
(
map
(
str
,
range
(
1
0
) ) ) )
est
↳
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
Voyons cela :
range(10)est un itérateur qui génère les entiers de 0 à9, map(str,
range(10)
)applique la fonction
strà tous ces entiers et est donc un itérateur qui
génèreleschainesdecaractèresde'0'à'9',finalement list( map( str, range(10)
) )construit une liste à partir de ces chaines.
Concaténation rapide de chaines de caractères
a concaténation des chaines de caractères pose le même problème que celle des
L
listes. Cela est d'autant plus gênant que la fonction
printestlente.Onaimeraitdonc
l'appelerrarementavecdelongueschainesplutôtquesouventavecdepetiteschaines.
Or si l'on fabrique une chaine assez longue avec de multiples utilisations de
+cela
prend encore plus de temps.
Il y a une solution à ce problème. L'utilisation de la fonction
joinqui construit une
chaine de caractères à partir de fragments par un simple parcours. Ainsi
nbItems
=
10
*
1
000
for
item
in
range
(nbItems):
print
(item)
est lent et
nbItems
=
10
*
1
000
message
=
""
for
item
in
range
(nbItems):
message
=
message
+
str
(item)
+
"\n"
print
(message,end
=
"
")
est pire mais
nbItems
=
10
*
1
000
message
=
"\n"
.join(
map
(
str
,
range
(nbItems) ) )
print
(message)
est bien plus rapide !
Affichage d'un grand nombre d'objets
Danslecasoùl'ondésireafficheruntableauilyauneméthodeplussimple.Lafonction
printadmet la syntaxe étendue
print
(item1,item2,...,sep
=
séparateur,end
=
a
ffichage_en_fin)
et par défaut
print
(item1,item2,...,sep
=
" "
,end
=
"\n"
)
le séparateur est un blanc et l'affichage se termine par un passage à la ligne.
Or, si
fest une fonction les codes
f(
1
,
2
,
3
,
4
,
5
)
et
liste
=
[
1
,
2
,
3
,
4
,
5
]
f(
*
l
iste)
sont équivalents.
On pourra donc afficher une liste à raison d'un élément par ligne en écrivant
print
(
*
l
iste,sep
=
"\n"
)
et sur une seule ligne en séparant les éléments par un blanc par
print
(
*
l
iste)
5-Limite du nombre de récursions
orsqu'une fonction appelle une autre fonction qui elle-même en appelle une autre et
L
ainsi de suite, on s'intéresse au nombre maximum d'appels qui peuvent s'enchaîner
ainsilesunsdanslesautres.Cettequestionprenddel'importancelorsquenousfaisons
appel à la récursivité.
ardéfaut,enPython,onnepeutfaireque1 000appelsrécursifs.Sivousavezbesoin
P
de faire plus d'appels, ajoutez ceci au début de votre programme :
import
sys
[Link](
1000
)
nremplaçant1 000parlabonnevaleur.Ilfaudrapeut-êtrelamultiplierpar2,par10ou
e
par 100, à vous de le déterminer.
otez cependant qu'en pratique, il faut essayer d'éviter de fonctionner ainsi ; il est
N
généralementpréférabled'éviterlesappelsrécursifsetd'utiliserdesbouclesàlaplace.
N'utilisez cette technique que pour vous y exercer, ou alors quand vous n'avez pas
d'autre choix.
6-Introduction à la complexité
orsquevousécrivezunprogrammeinformatiqueilestimportantquecelui-cisoit
L
correct, c'est-à-direqu'ilfassebiencequ'ilestsupposéfaire!Qu'unprogramme
soit correct est essentiel, mais il faut aussi qu'il soit efficace. Imaginez par
exemple qu'après avoir cherché quelque chose sur un moteur de recherche, il
faille attendre plusieurs heurespouravoirlerésultat!Lesmoteursderecherche
n'auraient pas autantdesuccès...Ilfautdoncêtreattentifàcequ'unprogramme
soit assez rapide. Il ne s'agit pas de gagner un peu de temps en faisant une
opérationdemoins,ilfauttrouverl'idée,l'algorithmequisoitleplusefficacepour
résoudre le problème qu'il nous est posé.
Regardons quelques situations pour lesquelles plusieurs algorithmes existent :
Pour calculer le nombre de pages d'un livre on peut :
● C ompter les pages une par une (la première, la deuxième,...) jusqu'à arriver
à la fin du livre.
● Regarder directement le numéro de la dernière page du livre.
De même, quand on va faire ses achats avec sa liste de courses, on peut :
● P
asser dans chaque rayon l'un après l'autre en prenant les produits s'ils
sont sur la liste.
● A
ller chercher dans le bon rayon chacun des produits de la liste, l'un après
l'autre, dans l'ordre dans lequel ils sont écrits.
ans les deux situations ci-dessus, chacune des techniques proposées (des
D
algorithmes utilisés) est correcte car elle donnera le bon résultat. Cependant,
certainessontbeaucouppluslentesqued'autresetonnelesutiliseraitjamaisen
pratique. Il nous faut donc un moyen (autre que notre bon sens !) pourpouvoir
comparer deux algorithmes, afin de savoir lequel seraleplusrapide.Eneffet,si
cela est parfois simple dans les situations ci-dessus, ce ne sera pas toujours
aussi évident.
Vitesse de calcul d'un processeur
eprocesseurestl'unitédecalculdel'ordinateur.Vouspouvezl'imaginercomme
L
une grosse boîte noire qui va prendre des données (sous forme de signaux
électriques) et donner des résultats (toujours sous la forme de signaux
électriques).Lesdonnéespeuventvenirdelamémoiredel'ordinateur(oudecelle
du processeur) et correspondent par exemple à la valeur decertainesvariables.
Le processeur peut faire un certain nombre de calculs sur les données, par
exemple les opérations mathématiques de base.
efaitdeprendredesdonnées,faireuncalcul,etdonnerunrésultats'appelleun
L
cycle de calcul du processeur. Un processeur estcapabledefaireuntrèsgrand
nombredecyclesdecalculàchaqueseconde.Onmesurecenombreen"Hz"qui
est une unité de mesure indiquantun"nombredefoisparseconde",c'est-à-dire
une fréquence. Comme le processeur est très rapide, on utilise plutôt (de nos
jours) le GHz : 1GHz correspond à 1 milliard de cycles par seconde ! Le
processeurdevotreordinateuratypiquementunefréquencedequelquesGHz(de
1 à 4).
n cours d'un cycle de calcul,leprocesseurestcapabledecalculerdeschoses
U
simples (comme une addition), mais il lui faudra parfois plusieurs cycles pour
calculer des choses plus complexes comme unedivision.Dèsqu'ilfautallerlire
oumodifierlavaleurd'unevariableilfautégalementplusdetempscaraccéderà
lamémoireestbeaucouppluslent:letempsd'allerlirelavaleurd'unevariable,le
processeur à eu le temps d'exécuter plusieurs dizaines de cycles !
n pratique les choses sont un plus complexes avec les processeurs actuels
E
(multi-coeurs, multi-threads, caches...) que cette petite explication mais elle est
suffisamment proche de la réalité pour que vous puissiez utiliser ce modèle
simplifié d'un processeur dans vos raisonnements.
Temps de calcul
i on considère un programme typique effectuant des opérations diverses
S
(lecture,calculs,écritures)alorslenombred'opérationspouvantêtreeffectuéesà
chaque seconde sur un processeur à 1GHz est d'environ 1 à 10 millions.
otezquecenombrepeutmonterà100millionssionnefaitquedesopérations
N
mathématiques simples ou descendre sionutiliseunlangageassezlentcomme
Python. Il faudra donc adapter ce nombre "le mieux possible", selon le
programmequ'onétudieetlelangagequ'onutilise.Enpratiquevousverrezqu'on
estrarementàunfacteur10prèsquandils'agitdechoisirlebonalgorithme.Vous
verrez dans le chapitre sur la "Complexité avancée" comment mesurerletemps
pris par les opérations de base, afin de pouvoir faire des estimations plus
précises.
achant combien d'opérations peuvent être faites en une seconde sur le
S
processeur, ilnoussuffitdoncd'estimerlenombred'opérationsquevaeffectuer
leprogrammepouravoiruneestimationdesontempsdecalcul:onappliqueune
simplerègledeproportionalité!Onvadoncdiviserlenombred'opérationsestimé
par1à10millions(pourunprocesseurà1GHz),pourobtenirletempsdecalcul.
Toutcecin'estpastrèsprécismaisfonctionnebienenpratiquepourlesexercices
que nous vous poserons, avec une limite de temps pour l'exécution de votre
programme. La question est alors bien souvent de savoir si on doit utiliser un
algorithme linéaire ou quadratique (ou une autre complexité) afin que le
programme se termine assez vite.
ur un exemple, supposons que le nombre d'opérations de l'algorithme vaut
S
environ5Net queNvaut 100 000 alors :
● u n algorithme linéaire fera 500 000 (5*100 000) opérations soit entre 0.05s
(500 000/10 millions) et 0.5s (500 000/1 million) de temps de calcul,
● un algorithme quadratique fera 50 000 000 000 (5*100 000*100 000)
opérations soit entre environ 1h20 et 13h de temps de calcul.
●
7-Efficasiter d’un programme en python
n programmeestefficaces'ilestcapablededonnerrapidementlebonrésultat,
U
mais comment comparer deux programmes afin de savoir lequel est le plus
efficace ? En effet, entre votre programme Python, qui met 1s à seterminersur
votre ordinateur et le programme C++ de votre ami, qui met 1.5s sur son
ordinateur, lequel est vraiment le plus efficace ?
our que la comparaison soit équitable, il f audrait déjà comparer ces deux
P
programmes sur la même machine ! Mais cela ne serait pas suffisant, car
onvertirunprogrammed'unlangageàunautrepourraitlerendreplusrapide(ou
c
plus lent au contraire). Il y a en réalité un grandnombredecritèresquipeuvent
changer le temps que met un programme pour se terminer :
● le langage de programmation utilisé,
● le processeur (l'unité de calcul) de l'ordinateur utilisé,
● le type de mémoire (plus ou moins rapide) de l'ordinateur utilisé,
● le talent du programmeur (sa connaissance du langage de programmation),
● les autres programmes s'exécutant sur l'ordinateur (qui peuvent ralentir le
programme),
...
●
nesecondedecalculpeutsignifierdeschosestrèsdifférentesselonl'ordinateur
U
utilisé !
insi,comparerletempsdecalculdedeuxprogrammesn'est(engénéral)pasle
A
meilleur moyen de comparer l'efficacité des algorithmes qui sont utilisés. Nous
allons vous apprendre à comparer deux algorithmes entre eux, sans regarder
leurs implémentations, c'est-à-dire sansregarderlesprogrammesquimettenten
œuvre ces algorithmes.
eprenons le premier exemple de l'introduction et essayons de c
R ompter le
nombre d'actions nécessaires pour mettre en œuvre les deux techniques
proposées. On suppose que le livre contient 1000 pages.
● T echnique 1 : on doit regarder chacune des pages, donc on va devoir en
regarder 1000 au total.
● Technique 2 : on ne doit regarder que la dernière page, donc on ne regarde
que 1 page au total.
a deuxième technique est donc 1000 fois plus rapide que la première sur cet
L
exemple de livre. Si le livre avait 10 000 pages, alors cette deuxième technique
serait 10 000 fois plus rapide !
find'avoirunrésultatgénéralisable(pourdeslivresdetaillesautresque1000ou
A
10 000), on va supposer que le livre contient N pages. La technique 1 va alors
regarderNpages au total et elle est doncNfoisplus lente que la seconde.
insi pour évaluer l'efficacité d'un algorithme nous allons compter le nombre
A
d'opérationsqu'ileffectue.Ilseraalorsbienplusfaciledelecompareràunautre
algorithme résolvant le même problème.
uestion : pour chacune des deux techniques du second exemple de
Q
l'introduction(fairesescourses)essayezderéfléchiraunombred'opérations(ici
des déplacements) nécessaires dans le pire cas.
8-Nombre d'opérations d'un algorithme
findepouvoircompterlenombred'opérationseffectuéesparunalgorithme,ilfauttout
A
d'abordsavoircequ'onappelleUNEopération.Estconsidéréecommeuneopérationle
fait de :
● u tiliser une opération mathématique de base (addition, soustraction,
multiplication, division,...),
● utiliser la valeur d'une variable (il faut aller chercher cette valeur en mémoire),
● donner une nouvelle valeur à une variable (il faut aller écrire cette valeur en
mémoire),
● lire une valeur simple (entier, décimal) donnée par l'utilisateur,
● écrire une valeur simple (entier, décimal),
● effectuer un test,
● utiliser une opération booléenne ("et", "ou", "non").
armi ces opérations certaines prennent enpratiqueplusdetempsqued'autresmais,
P
afin de simplifier les calculs, nous ferons l'approximation qu'elles sont toutes aussi
rapides.Ilexistebienentendud'autresopérationsmaiscellesindiquéesci-dessoussont
suffisantes pour le moment.
9-Notation O()
ous avons vu jusqu'à présent comment déterminer la complexité d'un algorithme que
N
ce soit une des complexités classiques qui ont leur propre nom ou des complexité du
type "proportionnelle à ...". Il existe une notation simple qui évite de répéter à chaque
fois la phrase "proportionnelle à ...". Par exemple si la complexité d'un algorithme est
proportionnelle à
𝑁
2
N2 alors on notera que la complexité de l'algorithme est un
𝑂(
𝑁
2
)
O(N2) qu'on lira "grand Ô de
𝑁
N au carré".
Pour les complexités classiques, on a donc :
● n algorithme cubique à une complexité en
U
● (
𝑂
●
𝑁
● 3
● )
● O(N3).
● Un algorithme quadratique à une complexité en
● (
𝑂
●
𝑁
● 2
● )
● O(N2).
● Un algorithme linéaire à une complexité en
● (𝑁)
𝑂
● O(N).
● Un algorithme constant à une complexité en
● (1)
𝑂
● O(1).
e pas oublier que cette notation revient à dire "si N est assez grand alors la complexité
N
est proportionnelle à ...". En particulier, si on a un algorithme en
𝑂(
𝑁
3
)
O(N3) et un autre en
𝑂(
𝑁
2
)
(N2) alors exécuter ces deux algorithmes l'un après l'autre donne un temps de calcul
O
en
𝑂(
𝑁
3
)
O(N3) car le
𝑂(
𝑁
2
)
O(N2) est négligeable par rapport au
(
𝑁
3
)
(N3).
Il existe une véritable définition derrière cette notation, mais nousneverronspascela
toutdesuite,nousauronsl'occasiondeprésenterleschosesplusformellementdansle
chapitre sur la "Complexité avancée".
9-Gestion de caractères
useind'unlangagedeprogrammationlescaractèressontreprésentés(sionsimplifie
A
les choses) sous forme de nombres selon ce qu'on appelle le code ASCII (American
Standard Code for Information Interchange). Le tableau ci-dessous indique cette
correspondance, ce qui nous intéresse étant les colonnes "Dec" (code décimal) et
"Char" (caractère associé).
a plupart des 31 premiers caractères sont ce qu'on appelle des "caractères de
L
contrôle", on ne s'y intéressera pas. Remarquez tout le même qu'ils contiennent la
tabulation (Dec = 9) ou les retours à la ligne (Dec = 10 par exemple).
e qui est intéressant c'est qu'il est possible de convertir un caractère vers son code
C
ASCII, et inversement.
Caractère -> code
caractere
=
"U"
code
=
ord
(caractere)
print
(code)
↳
85
Code -> Caractère
code
=
111
caractere
=
chr
(code)
print
(caractere)
↳
o
Encodage réel
n Python, les chaînes de caractères sont en réalité codées en UTF-8, un code (ou
E
encodage)plusgénéralquel'ASCIIetquipermetdereprésenterplusdecaractères,par
exemples les caractères chinois. En UTF-8, Les caractères d'indices inférieurs à 128
sont exactement les mêmes que en ASCII : le tableau ci-dessus fonctionne donc.
Afficher la liste des caractères
i-dessous, vous trouverez un petit code permettant d'afficher la liste des caractères
C
existants avec leur code associé. Les caractères d'indice inférieur à 32 sont affichés
sous la forme d'un espace car les affichernormalementposeraitdesproblèmes,étant
donné qu'ils ont un sens spécial. Le code peut faire appelàdesélémentsdesyntaxe
que vous n'avez pas encore vu, il est simplement donné à titre d'exemple.
# Caractères 0 à 1023
for
bloc
in
range
(
8
)
:
for
lig
in
range
(
16
):
for
col
in
range
(
8
)
:
code
=
128
*
bloc
+
16
*
col
+
lig
caractere
=
chr
(code)
if
code <
32
:
caractere
=
" "
print
(
"
{:04d} {} "
.
format
(code, caractere),
end
=
"")
print
()
print
()
10-Convertir en maj/min
Convertir un caractère
caractereMin
=
"d"
caractereMaj
=
"J"
print
([Link]())
print
([Link]())
↳
D
j
otez que ces fonctions ne passeront en majuscule (resp. minuscule) que les
N
caractères qui sont en minuscule (resp. majuscule). Il n'y a donc pas pas besoin de
tester la casse des caractères avant de pouvoir les utiliser !
Convertir une chaîne de caractère
texte
=
"Texte avec 1 majuscule et 29 minuscules !"
print
([Link]())
print
([Link]())
↳
TEXTE AVEC 1 MAJUSCULE ET 29 MINUSCULES !
texte avec 1 majuscule et 29 minuscules !
n remarquera que les caractères spéciaux ne sont pas modifiés, uniquement les
O
lettres.
11-Classe de caractère
tant donné un caractère, on souhaiterait savoir s'il appartient à certaines classes de
É
caractères (chiffre, lettre, minuscule, majuscule…) afin d'effectuer des opérations
différentes au sein du programme. Nous allons voir comment faire pour quelques
classes très courantes.
caractere
=
input
()
if
[Link]():
print
(
"
Il s'agit d'un chiffre"
)
if
[Link]():
print
(
"
Il s'agit d'une lettre minuscule"
)
if
[Link]():
print
(
"
Il s'agit d'une lettre majuscule"
)
if
[Link]():
print
(
"
Il s'agit d'une lettre"
)
↳
Il s'agit d'une lettre majuscule
Il s'agit d'une lettre
Avec des comparaisons de caractères
Il est préférable d'utiliser les fonctions toutes faites, mais il est aussi possible de se
baser directement sur des comparaisons de caractères.
caractere
=
input
()
if
"0"
<=
caractere
and
caractere <
=
"9"
:
print
(
"
Il s'agit d'un chiffre"
)
if
"a"
<=
caractere
and
caractere <
=
"z"
:
print
(
"
Il s'agit d'une lettre minuscule"
)
if
"A"
<=
caractere
and
caractere <
=
"Z"
:
print
(
"
Il s'agit d'une lettre majuscule"
)
f
i (
"a"
<
=
caractereand
caractere
<
=
"z"
)
or
(
"
A"
<=
caractere
and
caractere <
=
"Z"
):
print
(
"
Il s'agit d'une lettre"
)
↳
Il s'agit d'une lettre majuscule
Il s'agit d'une lettre
ttention, le code ci-dessus ne va fonctionner qu'avec des caractères non accentués,
A
c'est-à-dire les seuls que nous manipuleront dans les exercices. Si voussouhaitezun
jour manipuler des caractères accentués, utilisez les fonctions toutes faites, qui elles
marcheront.
Sur une chaîne complète
Les mêmes fonctions sont disponibles pour des chaînes de caractères complètes :
texte
=
input
()
if
[Link]():
print
(
"
Le texte ne contient que des chiffres"
)
if
[Link]():
print
(
"
Le texte ne contient que des lettres minuscules"
)
if
[Link]():
print
(
"
Le texte ne contient que des lettres majuscules"
)
if
[Link]():
print
(
"
Le texte ne contient que des lettres"
)
12-Tableau de chaînes de caractères
uand on commence à avoir beaucoup de chaînes de caractères à stocker dans un
Q
programme, utiliser une variable pour chaque chaîne de caractères n'est pas très
efficace, il vaut mieux créer un tableau de chaînes de caractères.
lignes
=
[""]
*
3
for
idLigne
in
range
(
3
)
:
lignes[idLigne]
=
input
()
Initialiser un tableau
Pour initialiser un tableau de chaînes de caractères, il faut utiliser la syntaxe suivante :
lignes
=
[
"
Premier texte"
,
"Second texte"
,
"Troisieme
texte"
]
ous avez déjà vu dans le chapitre sur les tableaux comment trier des tableaux
V
d'entiers, nous allons voir comment trier des tableaux de chaînes de caractères.
lignes
=
[
"
Texte C"
,
"Texte A"
,
"Texte B"
]
[Link]()
print
(lignes[
0
])
↳
Texte A
a syntaxe est donc très similaire à ce que nous avions déjà vu sur les tableaux
L
d'entiers.
aire une copie d'une chaîne de caractères : Lorsqu'on a besoin de
F
faire une copie d'une chaîne de caractères, il faut utiliser le code
suivant : texte = "Exemple de texte" texteCopie = texte
print(texteCopie) ↳ Exemple detexteLecodeestdonctrèsintuitif,il
n'y a pas de remarques particulières à faire.
orsqu'on a besoin de former une grande chaîne de caractères à
L
partir de chaînes plus petites, on dit qu'on concatène leschaînesde
caractères.texteDebut="Ceciest"texteFin="unephrasecomplete"
texteComplet = texteDebut + texteFinprint(texteComplet)↳Ceciest
une phrase complete Le code est donc très intuitif, il n'y a pas de
remarquesparticulièresàfaire.Remarquesurdepossiblelenteurs:Il
faut ABSOLUMENT éviter de concaténer des chaînes au sein d'une
boucle, avec un code de la forme suivante : monTexte = "" Répéter
1000 fois monTexte = Concaténer monTexte et "X" Un tel code fera
des copies multiples de monTexte et son temps d'exécution sera
proportionnelà1000*1000etnonpasà1000.Sacomplexitéestdonc
très mauvaise et peut rendre votre programme trop lent pour être
accepté.N'hésitezpasàlirelechapitresurlacomplexitépourréviser
ce concept et à relire le cours sur la modification d'une chaîne de
caractère.
Imaginons qu'on souhaite afficher les lettres de A à F. On pourrait bien sûr utiliser 6
commandes d'affichage mais on sent que cela n'est pas des plus efficace. Voici la
solution la plus simple :
for
ascii
in
range
(
o
rd
(
'A'
),
ord
(
'
F'
)
+
1
)
:
print
(
c
hr
(ascii))
↳
A
B
C
D
E
F
On est donc obligé de faire la boucle en itérant sur les codes ASCII des caractères.
13-Tableaux avancés
1. Tableaux en Python :
○ Un tableau 1D est une liste d’éléments.
○ Un tableau 2D est une liste de listes.
○ L’accès aux éléments se fait via deux indices : un pour la
ligne, un pour la colonne.
2. Moteur de rendu simplifié (dessin de rectangles) :
○ L’image est un tableau 2D de caractères.
○ Chaque pixel est initialement un caractère par défaut.
○ Des rectangles sont dessinés en suivant les coordonnées
fournies et dans l’ordre donné.
○ L’image finale est affichée sous forme de texte.
3. Vérification d’un carré magique :
○ Une grille carrée où chaque nombre est unique et où les
sommes des lignes, colonnes et diagonales sont
identiques.
○ Lecture des valeurs, vérification des conditions, affichage
du résultat.
14- TRier un tableau
IlestfaciledetrieruntableauenPythoncarunalgorithmedetriestdéjàfourni.Voiciun
code complet, nous l'expliquerons en dessous :
# Défini le tableau
poids
=
[
4
5
,
80
,
2
]
# Tri le tableau
[Link]()
# Affiche le tableau
for
indice
in
range
(
3
)
:
print
(poids[indice])
↳
2
45
80
Il suffit donc d'appeller la fonction
sort()sur letableau, à l'aide du code
[Link]()
afin de demander le tri du tableau.
Algorithmes de tri
Ici, nous avons simplement utilisé un tri qui existe déjà dans Python. Il est bien sur
possible de programmer son propre tri (et il existe beaucoup de tris différents !) mais
pour lemomentleplussimpleestd'utiliserletridéjàfourni.Nousauronsl'occasionde
vous présenter les différents algorithmes de tri plus tard.
15-Recurrsivité
u cours des chapitres précédents, nous avons eu l'occasion d'utiliser des fonctions,
A
que ce soit pour éviter de recopier plusieurs fois le même code, ou pour découper le
codeenpartiesplussimples.Danscechapitre,nousallonsvoiruneautreutilisationdes
fonctions, qui en fait unoutiltrèspuissantpourécriredesalgorithmes.Cetteutilisation
est ce que l'on appelle larécursivité.
arécursivitéestunprincipeassezgénéral,quineselimitepasàlaprogrammationet
L
l'algorithmique.Ceprincipedécritlapropriétédeconceptsoud'objetsquisedéfinissent
à partir d'eux-mêmes.
n pourrait penser qu'un objet qui est défini à partir de lui-même n'a pas de sens :
O
commentcomprendrelesensd'unmot,sisadéfinitionutilisecemot?Pourcomprendre
la définition du mot, ne faudrait-il pas déjà le connaître ?Nousallonsvoirqu'unetelle
définition,sil'onprendquelquesprécautions,peutaucontraireêtretrèsclaire,souvent
plus claire qu'une définition ne faisant pas appel au mot lui-même.
Prenons un exemple de définition récursive d'un objet :
ne poupée russe est un objet en forme de personnage, qui contient souvent une
U
poupée russe semblable, mais plus petite.
our décrire ce qu'est une poupée russe, on a bienutilisélenomdel'objetlui-même.
P
Cette définition est pourtant très claire, même pour quelqu'un qui n'a jamais vu untel
objet.
es poupées russes sont très loin d'être les seuls objets pour lesquels une définition
L
récursive a un sens. De très nombreuses notions se définissent naturellement de
manière récursive, et on en trouve beaucoup en informatique. Voici un autre exemple :
n répertoire est un élément informatique qui peut contenir des fichiers et des
U
répertoires.
auriez-vous définir la notion de répertoire sans réutiliser le mot répertoire, et sans
S
rendre la définition incomplète ?Pasfacile...unrépertoireestenlui-mêmeunconcep
récursif.
n peut remarquer plusieurs points communs entre nos deux exemples,quidécrivent
O
pourtantdeschosestrèsdifférentes:l'unestunobjetdumonderéel,tandisquel'autre
n'est qu'une abstraction, qui n'existe que d'un point de vue logiciel.
epremierpointcommunestquedanslesdeuxcas,ondécritunobjetquipeutcontenir
L
d'autres objets. C'est souvent le cas de ce que l'on décrit récursivement, mais pas
toujours, nous le verrons plus tard.
edeuxièmepointcommunestqueladéfinitionimpliquequ'ilestpossiblequel'objetne
L
contienne rien. Une poupée russe contient souvent une autre poupée, mais pas
toujours. Un répertoire peut contenir d'autresrépertoires,maispeutaussiêtrevide,ou
necontenirquedesfichiers.Onpourraitbiensûrdéfinirunepoupéerussequicontient
toujoursuneautrepoupéerusse,maisonauraitalorsuneinfinitédepoupées,cequine
peutexisterdanslemonderéeletn'estqu'uneidéeabstraite.Cepointestcommunàla
plupart des définitions récursives et on la retrouvera dans toutes celles que nous
définirons.
ans le cas des fonctions, la récursivités'exprimeratoutsimplementsouslaformede
D
fonctions qui s'appellent elles-mêmes. Nous verrons comment cela fonctionne en
pratique, et à quoi cela peut servir.
16-Fonctions récursives
Note : codes disponibles uniquement en C.
Voyons un premier exemple de fonction récursive, et d'un programme qui l'utilise :
#include <stdio.h>
void
debutFin(
int
nbAffichages)
{
printf
(
"
début %d\n"
, nbAffichages);
if
(nbAffichages > 1)
debutFin(nbAffichages - 1);
printf
(
"
fin %d\n"
, nbAffichages);
}
int
main()
{
debutFin(3);
return
0;
}
En exécutant ce programme, on obtient l'affichage suivant :
début 3
début 2
début 1
fin 1
fin 2
fin 3
eprogrammeaffichetrois"début"et"fin"imbriquéslesunsdanslesautres.Regardons
L
endétaillesdifférentesétapesdel'exécution.Onamisenavantlastructureimbriquée
des différents appels :
E
● xécution de la fonction main()
● Appel de debutFin(3)
○ Affichage de "début 3"
○ (3 > 1) est vrai -> appel de debutFin(2)
■ Affichage de "début 2"
■ (2 > 1) est vrai -> appel de debutFin(1)
■ Affichage de "début 1"
■ (1 > 1) est faux
■ Affichage de "fin 1"
■ Affichage de "fin 2"
○ Affichage de "fin 3"
● Retour de l'appel à main()
ans cet exemple, on passe en paramètre à la fonction le nombre d'appels récursifs
D
imbriqués que l'on souhaite exécuter. Ce nombre est diminué de 1 à chaque appel :
pour afficher 3 fois "début" et "fin", on affiche "début", puisonappellelafonctionpour
afficher 2 fois "début" et "fin", puis on affiche "fin".
Que se passerait-il si l'on n'avait pas ce paramètre, comme dans l'exemple suivant :
void
debutFin()
{
printf
(
"
début\n"
);
debutFin();
printf
(
"
fin\n"
);
}
orsdesonappel,lafonctiondebutFin()afficherait"début",puiss'appelleraitelle-même,
L
doncafficheraitdébut,puiss'appelleraitelle-même,donc...celan'auraitpasdefin,età
aucun moment, le mot fin ne serait affiché.
e la même manière qu'une poupée russe,pourêtreunobjetconcret,doitpouvoirne
D
pas toujours contenir d'autrepoupéerusse,unefonctionrécursivenedoitpastoujours
se rappeler, sinon elle ne se terminera jamais. On peut ainsi définir la règle suivante :
ne fonction récursive doit toujours comporter une condition de findesappels,
U
pour ne pas avoir une exécution infinie.
oyonsmaintenantcequisepassesiaulieud'avoirunseulappel,lafonctionrécursive
V
se rappelle elle-même deux fois de suite :
void
debutFin(
int
nbAffichages)
{
printf
(
"
début %d\n"
, nbAffichages);
if
(nbAffichages > 1)
{
debutFin(nbAffichages - 1);
debutFin(nbAffichages - 1);
}
printf
(
"
fin %d\n"
, nbAffichages);
}
L'affichage du programme est alors le suivant :
début 3
début 2
début 1
fin 1
début 1
fin 1
fin 2
début 2
début 1
fin 1
début 1
fin 1
fin 2
fin 3
En ajoutant des indentations, on voit plus nettement ce qui se passe :
début 3
début 2
début 1
fin 1
début 1
fin 1
fin 2
début 2
début 1
fin 1
début 1
fin 1
fin 2
fin 3
'appel de la fonction la rappelle deux fois, et chacun de ces appels la rappelle
L
également deux fois.
nefonctionfactoriellepeutêtreimplémentéesoitdemanièreitérativeavecuneboucle,
U
soit récursivement en appelant la fonction sur N-1 , chaque méthode ayant ses
avantages et inconvénients en termes de performance et de lisibilité.L’itératifestplus
rapideetconsommemoinsdemémoire,tandisquelerécursifestplusélégantmaispeut
poserproblèmesilenombred’appelsesttropélevé.Unprogrammeitératifbasésurune
boucle peut être converti en récursif en identifiant le cas de base et en décomposant
l’actionenétapessuccessives,commeillustréavecl'affichaged’unelignedecaractères
en remplaçant la boucle par des appels récursifs successifs.
n programme contenant deux boucles imbriquées peut être transformé en version
U
récursiveenappliquantlarécursivitéd'abordsurlaboucleprincipale,puissurlaboucle
interne.Oncommenceparremplacerlaboucledeslignesparunappelrécursif,puison
applique le même principe à la boucle des colonnes pour supprimer totalement les
boucles. Cela permet de comprendre que dessiner un rectangle de Nlignes et
M
colonnes revient à afficher un caractère, compléter la ligne avec
M-1caractères, puis
dessiner N-1lignes. Bienquecetteapprochesoitpluscomplexe,l’habitudepermetde
choisir plus facilement entre une solution itérative ou récursive selon le contexte.
16-Introduction à la complexité en temps des algorithmes
rouverunalgorithmequirésoutunproblème,c'esttrouverunesuccessiond'opérations
T
qui permet de fournir une solution de ce problème. Ce n'est pas toujours une chose
facile,maiscequipeutêtreencoreplusdifficileetsurtoutbienplusintéressant,c'estde
trouver un algorithme qui fournit cette solution rapidement.
vecladescriptiondechacundesproblèmesproposéssurcesite,onvousfournitune
A
limitedetemps:laduréemaximaleautoriséed'exécutiondevotreprogramme.Sivotre
code ne fournit pas sa réponse dans cette limite pour un test donné, ce test est
considérécommeétantunéchec,mêmesiavecplusdetemps,votreprogrammeaurait
pu fournir une réponse juste. Toute la difficulté est donc de faire en sorte que votre
programme soit suffisamment rapide.
e but de ce cours et de la série d'exercices qui l'accompagne est de vous montrer
L
pourquoi certains algorithmes sont plus rapides que d'autres, et surtout de vous
apprendreàdéterminerapproximativementlavitessed'unalgorithmeavantmêmedele
tester,grâceàunoutildontnousvousprésentonslesprincipesdebase:lecalculdela
complexité en tempsd'un algorithme.
ecourscontientdesexemplesenlangagesC++etCaml,maisiln'estpasnécessaire
C
de connaître l'un de ces deux langages pour pouvoir le suivre.
Temps d'exécution d'un programme
i vous n'avez jamais fait d'algorithmique, vous avez probablement écritdenombreux
S
programmes sans jamais vous occuper de leur vitesse d'exécution. Certains de vos
programmes contenaient peut-être parfois des boucles infinies et ne se terminaient
jamais, mais pour le reste, ils fonctionnaient probablement toujours assez rapidement.
Prenons pour commencer l'algorithme suivant :
Lire un entier A
Calculer A * A, et Stocker le résultat dans B
Calculer B * 5 + 3, et Stocker le résultat dans C
Afficher C
i vous écrivez le programme correspondant dans le langage de votre choix, puis
S
l'exécutez, le résultat sera affiché immédiatement après que l'utilisateur ait entré un
entier. Vous pourriez ajouter des centaines d'autres lignes de calcul dumêmetype,le
résultat arriverait toujours immédiatement : une machine récente est en effet capable
d'exécuter plusieurs dizaines de millions de telles instructions en moins d'une seconde.
xercice:essayezd'écrireunprogrammequimetsuffisammentdetempsàs'exécuter
E
pour que le résultat ne soit pas immédiat. Attention : le programme doit être actif
pendant toute son exécution, il ne s'agit pas d'appeler unefonctiondulangagequine
fait qu'attendre un temps donné.
Solution :
emoyenleplussimpledefairetravaillerlamachinesuffisammentlongtempspourque
L
le programme ne se termine pas immédiatement, consiste àluidemanderdecompter
jusqu'à une valeur très élevée, par exemple cent millions :
Pour compteur allant de 1 à 100*1000*1000
ne rien faire
xercice:Ecrivezceprogrammedanslelangagedevotrechoix,ettestez-lesurnotre
E
serveur. Si votre programme prend plus d'un centième de seconde à s'exécuter, le
temps d'exécution sera affiché.
estezalorsavecdifférentesvaleurslimitespourlecompteur,observezcommentévolue
T
cetempsd'exécutionenfonctiondecettevaleur,etessayezd'endéduireunerègle.La
limitedetempsétantfixéeàuneseconde,vousaurezuneerreurdetype"Dépassement
de la limite de temps", si vous allez au delà de cette durée.
Solution :
Voici une version C++ de ce programme :
#include <stdio.h>
int
main()
{
int
N, increment, compteur;
scanf
(
"
%d%d"
, &N, &increment);
for
(compteur = 1; compteur <= N; compteur += increment)
;
printf
(
"
%d\n"
, compteur);
return
0;
}
Version Caml :
let
n =
read_int
()
in
let
increment =
read_int
()
in
let
total =
ref
0
in
for
compteur =
1
to
n
do
total := !total + increment
done
;
print_int
!total
our éviter que le compilateur ne remarque quelabouclenefaitriend'utile,etqu'elle
P
peutêtreremplacéeparunesimpleinstruction compteur N,onfaitlireauprogramme
=
lavaleurdeN,etlavaleurdel'incrément,surl'entréestandard.Ildevientalorsbienplus
difficile d'optimiser la boucle, et celle-ci est entièrement exécutée. On utilisera
systématiquement 1 comme valeur de l'incrément, dans nos tests.
ur notre serveur, au moment de l'écriture de ces lignes, les temps d'exécution de la
S
version C++ en fonction deNsont les suivants :
temps d'exécution
N
en secondes
100000000 0.08
200000000 0.16
300000000 0.25
400000000 0.33
500000000 0.41
600000000 0.50
700000000 0.58
800000000 0.66
900000000 0.75
10000000000.83
partir de ces chiffres,onpeutainsiestimerqueletempsd'exécutionduprogramme,
A
sur cette machine, est égal à N* 8*10-10. La machineexécutedoncenviron1.2milliard
d'itérations par seconde.
e tempsd'exécutionestproportionnelàlavaleurdeN,doncproportionnelaunombre
L
d'itérations de la boucle.
Si vous le souhaitez, vous pouvez aussi tester directement chez vous :
● E n C/C++, utilisez la fonction clock()définie dans
time.h , qui renvoie un
nombre de ticks d'horloge processeur. Divisez par la constante
CLOCKS_PER_SEC pour obtenir une valeur en secondes. Appelez cette
fonction au début et à la fin de votre programme, et affichez la différence pour
connaître le temps écoulé. Attention : sous Windows, la précision est assez
faible.
● En Caml, vous pouvez appeler :
print_float ([Link]());
ette instruction affichera le temps écoulé depuis le début du programme.
C
Utilisez le compilateur ocamloptpour générer du codenatif, et avoir des
résultats raisonnables.
Sous Unix, quel que soit le langage, utilisez
● timeavec en paramètre votre
programme exécutable. Vous verrez alors trois temps s'afficher, celui qui vous
intéresse est le temps " ".
user
ans cetexemple,onn'afaitquecompter.Quesepasse-t-ilsienplusdecompter,on
D
effectue un autre calcul, par exemple additionner toutes les valeurs par lesquelles on
passe :
N = 100*1000*1000
total = 0
Pour compteur allant de 1 à N
total = total + compteur
Afficher total
xercice : testez le temps d'exécution d'un programme basé sur cet algorithme, et
E
comparez les résultats aux précédents.
emarque:sivousutilisezunentiersur32bitspourstockerletotal,lavaleurn'aurapas
R
tropdesenscarlacapacitéesttrèsvitedépassée.Celan'acependantpasd'importance
ici, nous nous intéressons uniquement au temps d'exécution.
Le source C++ correspondant est :
#include <stdio.h>
int
main()
{
int
N, increment, compteur;
scanf
(
"
%d%d"
, &N, &increment);
int
total = 0;
for
(compteur = 1; compteur <= N; compteur += increment)
total++;
printf
(
"
%d\n"
, total);
return
0;
}
Version Caml :
let
n =
read_int
()
in
let
increment =
ref
read_int
()
in
let
total =
ref
0
in
for
compteur =
1
to
n
do
incr
increment;
total := !total + !increment
done
;
print_int
!total
Voici les résultats pour la version C++, sur notre serveur :
temps d'exécution temps d'exécution
N en secondes en secondes
algorithme précédent nouvel algorithme
100000000 0.08 0.11
200000000 0.16 0.22
300000000 0.25 0.33
400000000 0.33 0.44
500000000 0.41 0.55
600000000 0.50 0.66
700000000 0.58 0.77
800000000 0.66 0.88
900000000 0.75 0.99
10000000000.83 limite dépassée : > à 1
nvoitqueletempsd'exécutionestpassédeN* 8*10-10 àN*11*10-10,pourcenouveau
O
programme.
npassantdeuneàdeuxinstructionsdanslecorpsdelaboucle,letempsd'exécution
E
n'a augmenté que de 25% environ.
Temps d'exécution d'une instruction
our bien comprendre ce qui se passeexactement,lemeilleurmoyenestderegarder
P
en détail ce que le microprocesseur va exécuter à chaque boucle. On peut pour cela
utiliser une option qui permet de voir le code assembleur généré par le compilateur.
Pour gcccommepour ocamlopt ,ils'agitdel'option .Notreserveurétantunpentium
-S
4, il s'agit donc d'assembleur x86.
oicil'extraitcorrespondantàlaboucle,avecdescommentairespourchaqueinstruction
V
(rassurez-vous,onnevapasvousdemanderd'apprendrel'assembleur).Lacommande
complèteutiliséedanslecasduC++est:
gccboucle.c -S -O2,quigénèreunfichier
boucle.s.L'option-O2indiqueleniveaud'optimisation,quiestceluiutilisépardéfautsur
notre serveur.
// label L5
.L5:
// ajoute le contenu du registre eax, au registre edx
addl
%eax, %edx
// incrémente de 1 le contenu du registre eax
incl
%eax
// compare le contenu de eax à la valeur 100000000
cmpl
$100000000, %eax
/
/ saute
au
label
L5
si
eax
était
inférieur
ou
égal
à
la
valeur
jle
.L5
n voit ici que la boucle contient quatre instructions du langage machine, dont une
O
correspondant à notre instruction " total = total + compteur ".
npourraitendéduirequel'augmentationdevraitêtrede33%,etnon25%,maissil'on
O
regardelecodegénérépourlaboucledupremierprogramme,onvoitquec'estpireque
cela, la boucle ne contenait que deux instructions :
.L5:
// Décrémente le contenu du registre eax
decl
%eax
// saute au label L5, si on est passé en dessous de zéro
jns
.L5
ans lecasdupremierprogramme,lecompilateuradétectéqu'ilétaitplusefficacede
D
compter dans l'autre sens (partir de 100 millions, et descendre jusqu'à 0) ! Cela ne
correspond pas à ce que l'on avait écrit. Le programme fonctionne cependant
correctement, car le compilateur va en fait appeler printf en lui passant la valeur N
directement, et non la valeur du compteur. Le compilateur, lorsque les options
d'optimisationsontactivées(etc'estcequenoussouhaitons),peutdoncfaireuncertain
ombre de manipulations sur notre programme lors de la transformation en code
n
exécutable, ce qui ne facilite pas la prédiction du temps d'exécution.
ilaboucleexécutéeparlemicroprocesseurfaitdeuxinstructionsdanslepremiercas,
S
et quatre dans l'autre, pourquoiletempsd'exécutionn'augmentequede25pourcent,
aulieudedoubler?Laréponseesttoutesimple:lestempsd'exécutiondesdifférentes
instructions du micro-processeur ne sont pas tous les mêmes.
orsquel'onparledelafréquenced'unmicroprocesseur,onfaitréférenceaunombrede
L
cycles qu'il est capable d'exécuter en une seconde. Un microprocesseur ayant une
fréquence de 1Ghz peut ainsi exécuter un milliard de cycles par seconde. A chaque
cycle,leprocesseurexécuteuneétapedel'exécutiond'uneinstruction,parexemple:la
lire en mémoire, ouladécoder,écrirelerésultat,etc.Lesprocesseursactuelspeuvent
manipuler plusieurs instructions en même temps, donc exécuter lors du même cycle,
une étape de chacune des instructionsqu'ilestentraindetraiter(parexemple,ilpeut
lire en mémoire l'instruction suivante à la même étape que l'écriture du résultat de
l'instruction courante).
Il faut toujours plusieurs cyclesprocesseurspourexécuterentièrementuneinstruction,
mais sur un certain nombre d'instructions consécutives, dont une partie del'exécution
est faite en parallèle, le temps moyen d'exécution d'une instruction peut être bien
inférieur, et ne faire qu'un cycle, parfois même moins, mais parfois bienplus,selonle
type d'instructions.
révoir précisément le temps que va prendre un programme est en fait très difficile :
P
d'une part compter le nombre d'instructions ne suffit pas, car différentes instructions
demandent un temps différent, d'autre-part, le compilateur peut transformer
radicalement notre programme, ce qui fait que nous ne pouvons même pasprévoirle
nombre exact d'instructions exécutées. En pratique, le temps d'exécution des
instructions dépend de nombreux facteurs, et on ne peut donner que des
approximations
our se faire une idée des temps d'exécutionsdedifférentstypesd'instruction,leplus
P
simple reste donc l'expérimentation.
xercice : écrivez des programmes permettant d'estimer le temps d'exécution d'une
E
addition, puis d'une multiplication, d'une division, d'un modulo, d'une lecture et d'une
écritureenmémoire(dansuntableau).Evaluezlestempsd'exécutiondechacundeces
programmes.
Solution :
ourpouvoirmesurerletempsd'exécutiond'uncertaintyped'instructionuniquement,on
p
peutfaireuneboucleoùàchaqueitérationdecetteboucle,onfaituncertainnombrede
foiscetteopération.Letempsconsacréàlaboucleelle-mêmedevientalorsnégligeable
devantletempsconsacréàl'instructionelle-même.Ainsi,pourtesterlamultiplication,on
pourra écrire :
#include <stdio.h>;
int
main()
{
const
int
N = 10*1000*1000;
int
total = 1;
int
compteur;
for
(compteur = 1; compteur <= N; compteur++)
{
total = total * compteur;
total = total * compteur;
total = total * compteur;
total = total * compteur;
total = total * compteur;
total = total * compteur;
total = total * compteur;
total = total * compteur;
total = total * compteur;
total = total * compteur;
}
printf
(
"
%d\n"
, total);
return
0;
}
Version Caml correspondante
let
n =
10
*
1000
*
1
000
in
let
total =
ref
1
in
for
compteur =
1
to
n
do
total := !total * compteur;
total := !total * compteur;
total := !total * compteur;
total := !total * compteur;
total := !total * compteur;
total := !total * compteur;
total := !total * compteur;
total := !total * compteur;
total := !total * compteur;
total := !total * compteur;
done
;
print_int
!total
ur une machine à 1Ghz, le programme C++ s'exécute en environ 1 seconde, cequi
S
montre qu'une multiplication prend de l'ordre de 10 cycles à s'exécuter. Onpeutdonc
exécuter 100 millions de multiplications par seconde. Vous pouvez appliquerlemême
principe pour les autres opérations, en remplaçant " total = total * compteur " par :
t
● otal = total / compteur;pour tester la division
● total = total % compteur;pour tester le modulo
● int index = compteur % 100000;au début, puis
total = tab[index];pour tester la lecture en mémoire(où tab est un tableau
de 100000 entiers).
● tab[index] = compteur;pour tester l'écriture en mémoire.
aitescesdifférentstestschezvous,etn'hésitezpasàenimaginerd'autrespourvous
F
familiariseraveclestempsd'exécution.Rappelez-vousquelesrèglesquevouspouvez
en tirer ne sont que des approximations, beaucoup de facteurs peuvent influencer le
résultat.
e manière générale, lorsque le corps de la boucle contient entre 10 et 20
D
instructions,onpourraestimerenpremièreapproximationqu'onpeuteffectuerde
l'ordre de 10 millions d'itérations de cette boucle en une seconde, toujours sur
une machine à 1Ghz.
Notion de complexité
il'onnepeutpascalculerprécisémentletempsd'exécutiond'unprogramme,onpeut
S
cependantsavoircommentilvaévoluerenfonctiondesdonnées:dansnotreexemple,
onsaitqueletempsd'exécutionestproportionnelàlavaleurdeN,cequiestdéjàune
information très utile. Si on multiplie N par 10, le temps d'exécution sera également
multiplié par 10.
renons un autre exemple : plutôt que de compter jusqu'à 100 millions,comptonsdix
P
mille fois de suite jusqu'à dix mille :
N = 10*1000
total = 0
Pour compteur1 allant de 1 à N
Pour compteur2 allant de 1 à N
total = total + 1
Afficher total
n va donc compter jusqu'à 10 000 avec le compteur 1, et pour chaque itération, on
O
compte jusqu'à 10 000 avec le compteur 2.
xercice : déterminez la valeur affichée par l'algorithme, ainsi qu'une estimation du
E
temps d'exécution de ce programme une fois écrit dans le langage de votre choix.
Testez ensuite ce programme, et comparez le résultat à votre prédiction.
Solution :
abouclesurlecompteur1vaêtreexécutée10000fois,etàchaquefois,labouclesur
L
lecompteur2seraexécutée10000foiségalement.Onauradoncautotal100millions
d'exécutions du corps de la boucle interne, donctotalseraincrémenté100millionsde
fois et le résultat affiché sera 100000000. On peut estimer que le temps sera
comparableàunprogrammequicomptesimplementjusqu'à100millions,doncenviron
0.11 seconde sur notre machine à 1Ghz. Voici le programme C++ correspondant :
#include <stdio.h>
int
main()
{
const
int
N = 10*1000;
int
total = 0;
for
(int
compteur1 = 1; compteur1 <= N; compteur1++)
for
(int
compteur2 = 1; compteur2 <= N; compteur2++)
total++;
printf
(
"
%d\n"
, total);
return
0;
}
Version Caml correspondante :
let
n =
10
*
1000
in
let
total =
ref
0
in
for
compteur1 =
1
to
n
do
for
compteur2 =
1
to
n
do
total := !total +
1
done
done
;
print_int
!total
n test confirme que le programme (la version C++) affiche la valeur 100 millions, et
U
s'exécute en 0.11 seconde, comme prévu.
uestion:sil'onmultipliepar2lavaleurdeN,quelseralenouveautempsd'exécution
Q
?
éponse : on effectue 20000 fois la boucle externe, et à chaque fois, 20000 fois la
R
boucleinterne,soit400millions.Onadoncmultipliépar4lenombred'itérations,doncle
tempsserade0.44secondeenviron.Untestdonneuneduréede0.45seconde,cequi
confirme notre prédiction.
,ouN2 .Sil'onmultiplie
etempsd'exécutionn'esticiplusproportionnelàN,maisàN* N
L
Npar10,onmultiplieraainsiletempsd'exécutionpar100.Sionfaitcettefoisunessai
avecN=1milliard,onaurauntempsd'exécutiondel'ordrede11milliardsdesecondes,
c'est à dire de l'ordre de 350 ans. Inutile donc de tester avant de continuer.
éterminer que le temps d'exécution denotrealgorithmeestproportionnelàN2 estce
D
quel'onappelledéterminerlacomplexitéentempsdecetalgorithme,cettecomplexité
étant dans ce cas O(N2) . Nous verrons plus tard ce que signifie précisément cette
notation O(N2 ), qui se lit "Grand O de N carré", considérez simplement que cela veut
dire "temps d'exécution à peu près proportionnel à ...". Cette notiondecomplexitén'a
rien à voir avec le fait que le programme soit compliqué ou non, et n'est qu'une
indication sur le temps que prendra l'algorithme à s'exécuter. On dira souvent "cet
algorithme est en O(N2 ) ", ou même pour simplifier "cet algorithme est en N2 ". Nous
verrons également qu'il existe une complexité en mémoire, qui donneuneindication
de la quantité de mémoire utilisée par un programme.
a complexité d'un algorithme est la partie du calcul desontempsd'exécutionquiest
L
indépendante des détails d'implémentation, du langage utilisé, du compilateur, du
microprocesseur, des options d'optimisation, etc. Elle permet donc de comparer la
vitesse de deux algorithmes, sanssepréoccuperdesconsidérationsd'implémentation.
Pour une valeur suffisamment grande de N, un algorithme de complexité O(N) sera
toujours bien plus rapide qu'un algorithme de complexité O(N2 ) , et ce quel quesoitle
langage, ou le micro-processeur utilisé.
xercice : déterminez la complexité de l'algorithme suivant, etdonnezuneestimation
E
de son temps d'exécution siNvaut 1000
total = 0
Pour compteur1 allant de 1 à N
Pour compteur2 allant de 1 à N
Pour compteur3 allant de 1 à N
total = total + 1
éponse : nous avons trois boucles imbriquées,chacuneallantjusqu'àN,soitN* N
R *N
3
exécutionsdelabouclelaplusinterne,doncunecomplexitédeO(N ).SiNvaut1000,
nous aurons donc 1 milliard d'exécutions de la boucle la plus interne, donc un temps
d'exécution d'environ 1.1 seconde une fois programmé en C++, comme décrit plus haut.
Revenons maintenant à notre premier algorithme, mais en le modifiant très légèrement :
Pour compteur1 allant de 1 à N + 1
ne rien faire
uelle est la complexité en temps d'un tel algorithme ? Vous avez peut-être enviede
Q
répondreO(N+ 1)?EnfaitondiratoujoursquelacomplexitéestdeO(N) ,carletemps
d'exécution est toujours "à peu près proportionnel à N" . Dès que la valeur de N est
suffisamment grande, ajouter 1 devient négligeable, donc onl'ignore.Cecivautquela
valeurajoutéesoit1outouteautrevaleurconstante:sil'onfaitallerlecompteurjusqu'à
N+1milliard,le1milliarddeviendranégligeabledèsqueNdépassequelquesdizaines
demilliards.Quandoncalculeunecomplexité,considèretoujourscequisepassepour
des valeurs "suffisamment grandes" des variables dont dépend le programme.
Que diriez-vous maintenant de la complexité de l'exemple suivant :
total = 0
Pour compteur1 allant de 1 à N
Pour compteur2 allant de 1 à N
total = total + 1
Pour compteur3 allant de 1 à N
total = total + 1
éponse:laboucleinternedelapremièrepartievas'exécuterN2 fois,etlabouclede
R
la deuxième partie vas'exécuterNfois.Onpourraitdoncpenserquelacomplexitéest
en O(N2 + N) , mais ici encore, pour une valeur suffisamment grande de N, N devient
négligeableparrapportàN2 , etletempsd'exécutionestàpeuprèsproportionnelàN2.
La complexité de l'algorithme est donc de O(N2 ).
elonlemêmeprincipe,unalgorithmecontenantuneboucledeN/2itérationsauraune
S
complexitédeO(N),etunalgorithmecontenantN3 +2*N2 itérationsauraunecomplexité
de O(N3 ).
Complexité en fonction de plusieurs variables
ans tous nos exemples précédents, le temps d'exécution de nos algorithmes ne
D
dépendait que d'une variable : N. Ce n'est pas toujours le cas, prenons par exemple
l'exemple suivant :
total = 0
Pour compteur1 allant de 1 à N
Pour compteur2 allant de 1 à P
total = total + 1
Dans ce cas, on a au totalN* Pitérations, ce quidonne donc une complexité de O(N*P
).
Exercice :quelle est la complexité de l'algorithmesuivant :
total = 0
Pour compteur1 allant de 1 à N * 2
Pour compteur2 allant de 1 à N
total = total + 1
Pour compteur3 allant de 1 à P
total = total + 1
Pour compteur4 allant de 1 à 10
total = total + 1
éponse:lenombretotald'itérationsestde2*N2 +P+10.Apartird'unecertainevaleur
R
de N ou de P, 10 devient négligeable,etn'estdoncpasconsidérépourlacomplexité.
De même,laconstantemultiplicative2n'estpasconservée.Onpourraitavoirenviede
dire que pour une certaine valeur de N, P devient négligeable devant N2 . On nepeut
cependantfaireaucunesuppositionsurlavaleurdeP,quipeutêtrebienplusgrandque
N2 dans certains cas. On conserve doncPdans la complexitéobtenue : O(N2 +P).
Prenons un nouvel exemple :
total = 0
donnees est un tableau de N valeurs entières
Pour compteur1 allant de 1 à N
valeur = donnee[compteur1]
Pour compteur2 allant de 1 à valeur
total = total + 1
Exercice :Quelle est la complexité de cet algorithme?
éponse : le nombre d'itérations dépend cettefoisducontenudechacunedescases
R
dutableau.Lenombredecasesdutableauétantdéfiniparunevariable,onnepeutpas
simplementlisteruneparunetoutescesvaleursdanslecalculdelacomplexité.Leseul
moyen est ici de définir une nouvelle variable P, représentant la valeur maximale
pouvantêtrestockéedansletableau.Unefoiscettevariabledéfinie,lacomplexitépeut
alors être définie comme O(N* P
) .
n pourrait dire que cette complexité n'est pas forcément la bonne : supposons que
O
touteslesvaleursdutableausoienttoujourstrèspetites,parexempleinférieuresà100,
saufl'uned'entreelles,quipeutprendredesvaleursjusqu'àplusieursmilliards.Dansce
cas, le temps de calcul n'est pas du tout proportionnel à N* P
, mais simplement
proportionnel àP, ce qui contredit notre complexitéde O(N*P ).
otrecomplexiténedéfinitenfaitpasqueletempsdecalculseratoujoursproportionnel
N
à N* P
, mais qu'il est possible, avec certaines données, qu'elle atteigne un temps de
calcul correspondant à cette règle deproportionnalité.Onparleainsidecomplexitéen
tempsenpirecas:letempsd'exécutionlepluslongqu'ilsoitpossibled'avoirpourdes
valeurs de NetPdonnées,estproportionnelàN* P .Ilexisteaussiunecomplexitédite
en cas moyen, dont nous verrons la signification plus tard.Lacomplexitéenpirecas
est celle qui nous intéressera le plus souvent.
iensûr,l'exempledécritplushautpeutseréécriredemanièrebeaucoupplusefficace,
B
pour un même résultat :
total = 0
donnees est un tableau de N valeurs entières
Pour compteur1 allant de 1 à N
total = total + donnee[compteur1]
ettenouvelleversionnecontientplusqu'uneboucledeNitérations,ils'agitdoncd'un
C
algorithme de complexité O(N) . Nous avons donc deux algorithmes qui effectuent la
mêmetâche,maisavecunecomplexitédifférente.Nouspouvonssanshésiterdireque
laversionenO(N) estbienplusrapidequelaversionenO(N*P
),etcesansjamaisavoir
estimé le temps d'exécution réel de l'implémentation de ces deux algorithmes. Quels
quesoientlesdétailsd'implémentation,lelangageutilisé,oulecompilateur,etc.onsait
déjàquepourdesvaleurssuffisammentélevéesdePetN,ledeuxièmealgorithmesera
plusrapidequelepremier.Cetypedecomparaisonsestl'objectifprincipaldelanotion
decomplexité:permettredecomparerlavitessededifférentsalgorithmespourlemême
problème.
Conclusion
ous avons vu que le temps d'exécution d'un programme dépendait de nombreuses
N
choses, principalement :
● u type et de la fréquence du microprocesseur utilisé.
D
● Du langage utilisé et du compilateur choisi, ainsi que de ses réglages.
● Des données d'entrée
● De la complexité en temps de l'algorithme
esnombreuxparamètresfontqu'onnepeutobtenirqu'uneapproximationgrossièredu
C
temps d'exécution, pour des valeurs d'entrée données. Le calcul de la complexité en
tempsnousfournitcependantunbonmoyenpourcomparerplusieursalgorithmesentre
eux, avant même de les avoir implémentés et testés.
Pour déterminer la complexité d'un algorithme, plusieurs étapes sont nécessaires :
1. D éterminer de quelles variables le temps de calcul dépend. La complexité sera
exprimée comme une fonction de ces variables.
2. Etablir une première version de la formule, en considérant toutes les boucles. La
complexité d'une boucle est généralement égale à la complexité de l'algorithme
exécuté à l'intérieur de la boucle, multipliée par le nombre d'itérations de la
boucles.
3. Eliminer tout ce qui ne change pas la proportionnalité, ou devient négligeable
pour des valeurs suffisamment grandes des variables : constantes additives,
multiplicatives, etc.
ecalculdelacomplexitéentempsd'unalgorithmeestparfoisbienpluscompliquéque
L
dans les exemples que nous avons vus plus haut. Nous vous proposons quelques
exercicespourvousentraîner,maisunefoisquevousaurezbienassimilélesnotionsde
base, le meilleur moyen d'apprendre à manier ce concept, est de l'utiliser régulièrement.
ésormais, pour tous les problèmes que vous résoudrez sur le site, entraînez vousà
D
calculer la complexité de votre algorithme, avant mêmedel'implémenter.Déduisez-en
une estimation du temps d'exécution de votre programme dans les cas extrêmes, et
vérifiez qu'il est inférieur à la limite de temps du sujet. En général la correction
contiendra une évaluation de la complexité de l'algorithme; vous apprendrez ainsi à
calculerdescomplexitésdetoutessortes,aufuretàmesuredevotreapprentissagede
l'algorithmique.
17-Notation en binaire
orsquenousmanipulonsdesnombres,nouslesécrivonssouslaformed'unesuitede
L
chiffres, où chaque chiffre peut prendre dixvaleurspossibles,de0à9.Lavaleurd'un
nombre à quatre chiffres est alors égale à 1000 (103) fois le premier chiffre, plus 100
(102) fois le deuxième chiffre, plus 10 (101) fois le troisème, plus 1 (100) fois le
quatrième. On multiplie chaque chiffre parlabase(10)puissancelapositionduchiffre
en partant de la droite, et en commençant à 0. C'est ce que l'on appelle la base 10,
puisqu'ellesebasesurdixchiffresdifférents.Laraisonpourlaquellenouscomptonsde
cette manière est en grande partie due au fait que cela nous permet de compter
facilement sur nos 10 doigts.
Le nombre 5432, écrit en base 10, vaut ainsi 5 * 1000 + 4 * 100 + 3 * 10 + 2 * 1.
nordinateurn'ayantpasdedoigts,compterenbase10(ditebasedécimale)neluiest
U
pas particulièrement adapté. La base 2, composée des chiffres 0 et1,l'estparcontre
beaucoup plus. Pour un appareil électrique, on peut en effet considérer deux états
élémentairespossibles:pasdecourant(0),ouducourant(1).C'estdoncenbase2que
la machine manipule tous les nombres. La valeur d'un nombre en base 2, dite base
binaire, se calcule selon le même principe que la valeur d'un nombre en base 10 :la
valeurd'unnombreàquatrechiffres,estde8(23) foislepremierchiffre,plus4(22) fois
le deuxième, plus 2 (21) fois le troisième, plus 1(20) fois le quatrième chiffre.
Common questions
Alimenté par l’IAEn Python, si les entrées utilisateur ne sont pas converties correctement lors des opérations arithmétiques, l'opérateur '+' peut concaténer du texte au lieu de sommer des nombres. Par exemple, si int(input()) est omis et que les valeurs sont traitées comme des chaînes, ces valeurs seront concaténées. Ainsi, le résultat de l'addition de "11" et "22" aboutira à "1122" au lieu de 33 .
La fonction input() en Python permet de demander des informations dynamiques à l'utilisateur, rendant ainsi le programme interactif. Elle est utilisée pour capturer les données saisies par l'utilisateur, comme un nom ou un âge, qui peuvent ensuite être utilisées dans le programme pour adapter son comportement en fonction des entrées fournies . Ceci améliore l'interactivité du programme en transformant les données reçues en actions programmatiques adaptées .
Définir des noms de variables de manière descriptive est crucial car cela permet aux développeurs et à d'autres lecteurs de comprendre facilement ce que représente chaque variable, ce qui rend le code plus lisible et maintenable . Cette pratique aide également au suivi de l'évolution des variables au cours d'un programme, permettant une meilleure compréhension du flux du programme et l'identification rapide de potentielles erreurs .
En Python, les chaînes de caractères sont immuables, ce qui signifie qu'elles ne peuvent pas être modifiées directement. Pour contourner cette limitation, une méthode consiste à convertir la chaîne en un tableau de caractères, modifier les éléments souhaités, puis reconvertir le tableau en une chaîne . Cette approche permet de conserver une flexibilité dans la manipulation des données malgré l'immuabilité inhérente des chaînes .
Pour optimiser le temps d'exécution d'une boucle en Python, il est crucial de minimiser la complexité algorithmique. Par exemple, remplacez une boucle imbriquée O(N^2) par une alternative O(N) si possible, en réduisant les itérations et en privilégiant les opérations vectorisées ou l'utilisation de fonctions adaptées et bien plus optimisées comme réductions intégrées. De plus, en réduisant les accès redondants à la mémoire et en employant des caches locaux, on peut significativement améliorer les performances .
Les règles générales pour le nommage des variables en Python incluent l'interdiction des espaces et l'utilisation des lettres majuscules et minuscules, des chiffres, et du caractère "_" ; le premier caractère ne peut pas être un chiffre, et les mots-clés comme "for" sont interdits pour nommer les variables . Ces règles, en permettant l'utilisation des accents dans les identifiants, accordent une flexibilité qui contribue à choisir des noms clairs et descriptifs, facilitant la compréhension générale des programmes .
Stocker la taille d'un tableau dans une variable peut être source d'erreurs, car cela nécessite une mise à jour manuelle chaque fois que le tableau change, ce qui peut mener à des incohérences. En revanche, l'utilisation de la fonction intégrée len() simplifie la gestion des données en offrant une manière dynamique et toujours à jour de connaître la taille d'un tableau, ce qui réduit le risque d'erreurs et augmente la flexibilité du code .
La complexité temporelle d'un algorithme donne une indication sur la manière dont le temps d'exécution évolue en fonction de la taille des données d'entrée. Un algorithme de complexité O(N) sera toujours plus rapide qu'un algorithme de complexité O(N^2) pour des valeurs de N suffisamment grandes, indépendamment du langage, du compilateur ou du microprocesseur utilisé . La complexité permet donc de prédire les performances relatives de différents algorithmes sur la base de leur asymptote de croissance, indépendamment des détails d'implémentation .
L'utilisation de l'encodage UTF-8 en programmation permet la manipulation universelle de caractères de toutes les langues de manière uniforme . UTF-8 est compatible avec une grande variété de langages modernes comme Python et Java, favorisant une intégration fluide dans des applications multilingues. Toutefois, il n'est pas nativement pris en charge par d'autres langages comme C ou C++, qui nécessitent une conversion explicite vers un format compatible comme ASCII .
En Python, l'utilisation de print() avec les paramètres sep et end permet de définir distinctement les séparateurs entre valeurs et l'achèvement de l'affichage sur une même ligne. Cette fonctionnalité peut être utilisée pour rendre la sortie des données plus lisible et personnalisée, permettant d'éviter des concatenations manuelles et d'améliorer ainsi la clarté et l'esthétisme de l'affichage final .
Vous aimerez peut-être aussi
- Introduction à Python et ses fonctionnalitésPas encore d'évaluationIntroduction à Python et ses fonctionnalités66 pages
- Introduction à Python et ses fonctionnalités100% (1)Introduction à Python et ses fonctionnalités332 pages
- Introduction à la Programmation PythonPas encore d'évaluationIntroduction à la Programmation Python30 pages
- Introduction à la programmation PythonPas encore d'évaluationIntroduction à la programmation Python183 pages
- Introduction à Python et ses ApplicationsPas encore d'évaluationIntroduction à Python et ses Applications12 pages
- Introduction à Python avec exemplesPas encore d'évaluationIntroduction à Python avec exemples33 pages
- Introduction à Python et ses outilsPas encore d'évaluationIntroduction à Python et ses outils32 pages
- Introduction à Python pour l'analyse numériquePas encore d'évaluationIntroduction à Python pour l'analyse numérique15 pages
- Cours Python Complet Detaille FrancaisPas encore d'évaluationCours Python Complet Detaille Francais5 pages
- Cours Informatique OL - Chapitre3 IPEIS 2020Pas encore d'évaluationCours Informatique OL - Chapitre3 IPEIS 202062 pages
- Introduction à Python pour GéostatistiquePas encore d'évaluationIntroduction à Python pour Géostatistique12 pages
- Introduction à la Programmation Objet en PythonPas encore d'évaluationIntroduction à la Programmation Objet en Python55 pages
- Introduction à l'algorithmique en PythonPas encore d'évaluationIntroduction à l'algorithmique en Python3 pages
- Introduction à Python pour le calcul scientifiquePas encore d'évaluationIntroduction à Python pour le calcul scientifique7 pages
- Introduction au langage Python et ses basesPas encore d'évaluationIntroduction au langage Python et ses bases47 pages
- Introduction À La Programmation en PythonPas encore d'évaluationIntroduction À La Programmation en Python11 pages
- Introduction au langage Python en géologiePas encore d'évaluationIntroduction au langage Python en géologie12 pages
- Introduction à Python pour DébutantsPas encore d'évaluationIntroduction à Python pour Débutants4 pages
- Introduction au langage Python 2025Pas encore d'évaluationIntroduction au langage Python 202525 pages
- Introduction à Python pour IA 2024Pas encore d'évaluationIntroduction à Python pour IA 2024248 pages
- Introduction à la programmation PythonPas encore d'évaluationIntroduction à la programmation Python10 pages
- Introduction à Python : Installation et BasesPas encore d'évaluationIntroduction à Python : Installation et Bases16 pages
- Introduction à l'algorithmique en PythonPas encore d'évaluationIntroduction à l'algorithmique en Python59 pages
- Introduction à Python et ses concepts clésPas encore d'évaluationIntroduction à Python et ses concepts clés29 pages
- Introduction à Python pour débutantsPas encore d'évaluationIntroduction à Python pour débutants3 pages
- Sujets et corrigés Brevet Maths 2025Pas encore d'évaluationSujets et corrigés Brevet Maths 2025145 pages
- Exercices de maths 6ème corrigés PDFPas encore d'évaluationExercices de maths 6ème corrigés PDF15 pages
- Exercices Corrigés sur le Cercle 6èmePas encore d'évaluationExercices Corrigés sur le Cercle 6ème24 pages
- Mécanismes de l'évolution : dérive et sélectionPas encore d'évaluationMécanismes de l'évolution : dérive et sélection2 pages
- Modélisation UML des besoins systèmePas encore d'évaluationModélisation UML des besoins système12 pages
- Élection Étudiante et Système de VotePas encore d'évaluationÉlection Étudiante et Système de Vote4 pages
- Développement de services avec JAX-WSPas encore d'évaluationDéveloppement de services avec JAX-WS22 pages
- Théories des systèmes d'exploitationPas encore d'évaluationThéories des systèmes d'exploitation4 pages
- Multifonction couleur A3 bizhub C368Pas encore d'évaluationMultifonction couleur A3 bizhub C3684 pages
- Introduction à l'Algorithmique et ProgrammationPas encore d'évaluationIntroduction à l'Algorithmique et Programmation13 pages
- Balisage HTML côté serveur expliquéPas encore d'évaluationBalisage HTML côté serveur expliqué104 pages
- Bases de l'algorithme en programmationPas encore d'évaluationBases de l'algorithme en programmation25 pages
- Guide Complet sur le Développement WebPas encore d'évaluationGuide Complet sur le Développement Web56 pages
- Exemple de Cahier Des Charges À Télécharger - Word, PDF..100% (3)Exemple de Cahier Des Charges À Télécharger - Word, PDF..5 pages
- Guide sur la librairie standard C++Pas encore d'évaluationGuide sur la librairie standard C++10 pages
- Formation SIG 2024-25 : Projet d'applicationPas encore d'évaluationFormation SIG 2024-25 : Projet d'application5 pages
- Optimisation de la maintenance préventivePas encore d'évaluationOptimisation de la maintenance préventive70 pages
- Ai Automation Client Guide (Darija)Pas encore d'évaluationAi Automation Client Guide (Darija)3 pages
- Planification Informatique 2022-2023Pas encore d'évaluationPlanification Informatique 2022-20234 pages
- Technologies WAN et Protocoles AssociésPas encore d'évaluationTechnologies WAN et Protocoles Associés8 pages