BASE PY 1 : boucles for

1. Les entiers de 0 à 11
Exercice de code : Afficher les entiers de 0 à 11
2. Les entiers de 10 à 21
Exercice de code : Afficher les entiers de 10 à 21
Aide
3. faire une somme
Exercice de code : Afficher la somme des entiers de 1 à 101
Ecrivez ci-dessous un code qui calcule la somme 1 + 2 + 3 + ..... + 101 et l'affiche à la fin (il faut ici utiliser un accumulateur, cf ci-dessus)
4. affichage décroissant
Exercice de code : Afficher les entiers 97, 91, 85, 79
Ecrivez un code qui affiche les entiers 97, 91, 85, 79 (en utilisant la boucle For i in range) Aide

retour sur les exercices 2 et 4
Il existe des façon plus astucieuses de réaliser les boucles dans certains cas. Par exemple, pour l'exercice 2 : afficher les entiers de 10 à 21, on pouvais écrire :
Exemple
for i in range(start,stop) : la boucle début avec i=start et stoppe avec i=stop-1
mais :
for i in range(10,4) : commençant à 10 et finissant à 3, cette boucle ne sera pas exécutée !
Cependant... il est possible de faire aussi des boucles décroissantes. A l'exercice 4 on demandait d'afficher les entiers 97, 91, 85, 79. Cela est réalisé par :
Exemple
Le troisième nombre, ici -6, est le pas.
for i in range(start,stop,pas) : la boucle débute avec i=start i augmente de pas à chaque itération. On arrete quand on atteint ou dépasse stop.
ainsi:
for i in range(10,14,3) : commençant à 10, puis 13 et on stoppe là, la valeur suivante serait 16 dépasse 13
for i in range(10,4,-3) : commençant à 10, puis 7 et on stoppe là, la valeur suivante serait 4 atteint la limite 4
Exercice de code : Lucky Sevens
Ecrire un programme, uyilisant une for boucle for avec un pas de 10, pour afficher tous les nombre à 2 chiffres terminant par 7.

La table de 9
Exemple
Voici un code qui affiche la table de 9
C'est assez ennuyeux de devoir répéter 10 fois quasiment la même ligne... Complète le code ci-dessous qui fait la même chose avec une boucle
Exercice de code : Afficher la table de 9
Complète le code ci-dessous pour afficher la table de 9 de 0*9=9 jusqu'à 10*9=90.
Exercice de code : Afficher la table de 8
Quand tu as validé l'exercice précédent, recopie le ici et modifie le pour afficher la table de 8

les carrés parfaits
Exercice de code : Les carrés
Ecrivez un code qui affiche les carrés des entiers de 1 à 12 (c'est à dire: 1, 4, 9, 16, .... 144 )
Dans cette première version tu dois utiliser une boucle for commençant à 0
Exercice de code : Les carrés
Ecrivez un code qui affiche les carrés des entiers de 1 à 12 (c'est à dire: 1, 4, 9, 16, .... 144 )
Dans cette seconde version tu dois utiliser une boucle for commençant à 1

S1-2 les variables

Des erreurs fréquentes

Si vous demandez à Python d'utiliser une variable qui n'est pas définie, vous obtenez une erreur.

NameError

Exemple : Une variable non définie

Comme vous pouvez le constater, nous obtenons un message d'erreur disant  NameError: name 'trouble' is not defined. Quelquefois, de telles erreurs sont dues à des erreurs de frappes : si vous définissez une variable adresse=32, et ensuite print(adrese), le même type d'erreur est généré.

SyntaxError

Un autre type d'erreur fréquent est généré quand vous écrivez une instruction qui n'a pas de sens pour python.

Par exemple, si vous inversez le sens de l'instruction =.

Exemple : SyntaxError: can't assign to literal
Cherchez l'erreur...

La première ligne est bien mais la deuxième génère une erreur : Python pense que la deuxième ligne 4 = x essaye de changer la valeur de 4 mais vous n'êtes autorisé qu'à changer la valeur d'une variable, et 4 n'est pas une variable. Si A = B et B = A représentent la même chose en mathématiques, ce n'est pas le cas en programmation.

Autre exemple, si vous omettez quelques chose, par exemple, une parenthèse :

Exemple : SyntaxError:
Cherchez l'erreur...
L'instruction print(x) est incomplète, il manque la parenthèse fermante. L'interpréteur Python cherche la parenthèse manquante et constate l'erreur seulement quand il passe à la ligne suivante. Pour cette raison, il indique l'erreur à la ligne juste en dessous et non pas à l'endroit ou la parenthèse manque.

IndentationError

Exercice de code : IndentationError: unexpected indent
Exécutez ce code et corrigez le pour qu'il s'exécute sans erreur...

On s'attendrait que le programme affiche 5, mais il génère une erreur. Examinons-la. Il faudra d'ailleurs prendre l'habitude de décrypter les messages d'erreur pour pouvoir comprendre l'erreur commise. Corrigez l'erreur pour que le code s'exécute correctement.

TypeError

Exercice de code : TypeError: ...
Exécutez ce code et corrigez le pour qu'il s'exécute sans erreur...

On s'attendrait que le programme affiche 0.5, mais il génère une erreur.

Lisez bien l'erreur et comprenez la :

TypeError: unsupported operand type(s) for /: 'str' and 'int'
Littéralement : Erreur de type : les types des opérandes pour la division ne sont pas supportés : str et int.

En clair : vous effectuez la division d'une chaine par un entier, cela n'a pas de sens et n'est pas supporté par l'interpréteur.

Exercices

Ceci est un échauffement pour vous familiariser avec les variables.

Anatomie Python
Exercice de code : L'anatomie Python
Ecrivez un code qui compte les têtes, les épaules, les genoux et les orteils à une fête. Le correcteur va automatiquement définir une variable personnes pour vous, elle contiendra le nombre de personnes à la fête.
Votre code doit définir quatre variables :
  • une appelée tetes
  • une appelée epaules
  • une appelée genoux
  • et une appelée orteils
égales au nombre de têtes, épaules, genoux et orteils à la fête. Votre programme ne doit pas générer de sortie. Cliquez ici pour un indice.

Désordre
Exercice mêlé : Calculette vitesse
Vous assistez à une course cycliste qui monte et descend une colline. Le correcteur automatique définira quatre variables pour vous : distanceMontee et distanceDescente donnent la distance (en km) des deux parties de la course, et tempsMonte et tempsDescente donne le temps (en minutes) du temps pris pour compléter chaque partie de la cours. Ecrivez un programme qui indique la vitesse moyenne (en km/min) pour toute la course.
Cliquez et glissez avec la souris pour réarranger les lignes.
Cliquez ici pour un indice si vous êtes bloqué
  • print(vitesseMoyenne)
  • distanceTotale = distanceMontee + distanceDescente
  • vitesseMoyenne = distanceTotale / tempsTotal
  • tempsTotal = tempsMonte + tempsDescente

programme d'échange

Voici un tout premier algorithme, qui est très fréquemment utilisé. Le problème est d'échanger les contenus de deux variables, nommons les x et y.

Par exemple, initialement on a :

x = 4

y = 3

Et on souhaite modifier l'état pour parvenir à :

x = 3

y = 4

On pourrait songer à écrire que x prend la valeur de y et y prend la valeur de x. C'est ce que fait le code ci-dessous, mais vous allez pouvoir constater que celà ne va pas fonctionner....

Exercice de code : Programme d'échange
Le correcteur va automatiquement définir les variables x et y pour vous, avec des valeurs numériques.

Vous devez modifier le code pour réellement échanger les valeurs :

la valeur de x après que votre code soit exécuté doit être égale à la valeur que y avait avant que votre code s'exécute, et la valeur de y après que votre code s'exécute doit être celle de x avant que votre code s'exécute.

Cliquez sur chaque indice si vous voulez les lire.

T-3.2 Récursivité

Exemples et Exercices

Exemples
Vous savez très bien utiliser une boucle for pour calculer une somme :
  • On initialise la variable somme
  • On itère
  • Dans la boucle on ajoute les éléments
C'est un accumulateur. Exemple :
Exemple : Calculer la sommes des inverse des carrés des entiers de 1 à n

Pour la petite histoire, cette somme tend vers π²/6, cela peut être démontré mais ce n'est pas notre propos.

Il existe une autre façon de calculer cette somme. L'idée est la suivante :

On ajoute (dans somme) 1/n² puis la somme des inverses des carrés des entiers de 1 à n-1.

Mais en fait nous n'allons pas utiliser de variable somme. On va renvoyer le résultat. En fait on peut écrire :

 \sum\limits_{i=1}^n \frac{1}{i^2} = \frac{1}{n^2} + \sum\limits_{i=1}^{n-1} \frac{1}{i^2}

Ce qui, dans le code, ce traduit par :

somme_inverse_carres(n) = 1/n**2 + somme_inverse_carres(n - 1)

Nous allons voir comment programmer cela. L'idée est donc que la fonction sum_inverse_carres s'appelle elle même. On désigne cela par le terme de fonction récursive.

Toutefois, il faut que le processus s'arrête.... Ici on appelle la fonction avec n-1 donc la valeur de l'argument décroit. Jusqu'où ???

En fait, dans tout programmation récursive on doit définir un cas de base, un cas simple où le résultat est trivial, et on peut renvoyer ce résultat sans rappeler la fonction.

Ici le cas de base est n = 1, et la valeur renvoyée dans ce cas est 1.

Exemple : version récursive du code précédent

Exercices

Exercice 1 : somme des entiers de 0 à n

Exercice de code : Somme des entiers de 0 à n
Vous savez programmer cela en itératif avec une boucle for, mais ici vous devez le faire de façon récursive.

COnTRAINTE : vous ne pouvez pas utiliser for ou while dans cet exercice.

Exercice 2 : a^n

Oui... je sais, nous l'avons déjà vu en exemple .... mais saurez vous le refaire ?

Exercice de code : calculer a^n

Il faut toujours penser à vérifier les cas "limites".
Votre fonction renvoie-t-elle le bon résultat pour 0^0?


Indice 
Réponse 

T1.c Listes en compréhension

Listes en compréhension

Une manière originale et très puissante de générer des listes est d'utiliser une liste en compréhension (ou la compréhension de listes). Pour plus de détails, consultez à ce sujet le site de Python et celui de Wikipédia.

Voici quelques exemples.

Nombres pairs compris entre 0 et 30

Exemple : comprégension avec un if

Jeu sur la casse des mots d'une phrase

Exemple : utiliser split, puis upper

Formatage d'une séquence avec 60 caractères par ligne

Exemple d'une séquence constituée de 150 alanines :

Exemple : Formater un chaine

T1.b copier des listes : ATTENTION


Copier une liste


Cette section est particulièrement importante et doit être bien comprise

Exemple : Copier une liste ? ATTENTION !

Vous voyez que la modification de x modifie y aussi ! 
Dans python tutor ( cliquer sur visualiser pour acceder à python tutor) vous pouvez voir que x=y n'a pas dupliqué la liste.

Techniquement, Python utilise des pointeurs (comme dans le langage de programmation C) vers les mêmes objets. Python Tutor l'illustre avec des flèches qui partent des variables x et y et qui pointent vers la même liste. Donc, si on modifie la liste x, la liste y est modifiée de la même manière. Rappelez-vous de ceci dans vos futurs programmes car cela pourrait avoir des effets désastreux !

Pour éviter ce problème, il va falloir créer une copie explicite de la liste initiale. Observez cet exemple :

Exemple : Copier une liste ? ATTENTION !

Si on regarde à nouveau dans Python Tutor (Figure 12), on voit clairement que l'utilisation d'une tranche [:] ou de la fonction list() crée des copies explicites. Chaque flèche pointe vers une liste différente, indépendante des autres

Attention, les deux techniques précédentes ne fonctionnent que pour les listes à une dimension, autrement dit les listes qui ne contiennent pas elles-mêmes d'autres listes.

Exemple : Copier une liste ? ATTENTION !
Exemple : Avec deepcopy

T1.3 Révisions : Algorithmes à connaitre

Algorithmes de tris et dichotomie


Premier algo


fonction algo1(tableau) : 
pour i allant de 0 à longueur(tableau)-2 :
imin=i
pour j allant de i+1 à len(tableau)-1 :
si tableau[j] < tableau[imin] :
imin=j
fin de si
fin de pour
if imin!=i:
tableau[i],tableau[imin]=tableau[imin],tableau[i]
fin de si
renvoyer tableau
Exercice à choix multiple
L'algorithme ci-dessus correspond à ...
Correct !
Exercice de code : ALGO 1
Coder le pseudo code donné au dessus.
Une liste lst sera générée pour vous pour la validation.
Dans la fonction, vous introduirez un comptage du nombre de comparaisons effectuées, qui sera affiché avant de sortir de la fonction (comme indiqué dans le code à compléter ci-dessus)

Deuxième algo


fonction algo2(lst) : 
pour i de 1 à len(lst) - 1 # mémoriser lst[i] dans x x ← lst[i] # décaler vers la droite les éléments de lst[0]..lst[i-1] qui sont plus grands que x en partant de lst[i-1] j ← i tant que j > 0 et lst[j - 1] > x lst[j] ← lst[j - 1] j ← j - 1 fin de tant que # placer x dans le "trou" laissé par le décalage lst[j] ← x renvoyer lst
Exercice à choix multiple
L'algorithme ci-dessus correspond à ...
Correct !
Exercice de code : ALGO 2
Coder le pseudo code donné au dessus.
Une liste lst sera générée pour vous pour la validation.
Dans la fonction, vous introduirez un comptage du nombre de comparaisons effectuées, qui sera affiché avant de sortir de la fonction (comme indiqué dans le code à compléter ci-dessus)

Comment interpréter les nombres de comparaison des algorithmes 2 et 3 ?

Pouvez vous donnez le nombre de comparaisons de l'algo 1 pour une liste de 200 valeurs ?

Pour l'algo2, que pourrait on dire ?

Et quelle est la complexité de l'algo 3 ?


Troisième algo


fonction algo3(x,lst) :
imin=0 imax=len(lst)-1 imilieu=(imin+imax)//2 tant que imin <= imax : si lst[imilieu]>x # on va chercher dans la partie de gauche : imax=imilieu-1 sinon si lst[imilieu] < x : # on va chercher dans la partie de droite: imin=imilieu+1 sinon : # on a trouvé x renvoyer True fin de si imilieu=(imin+imax)//2 fin de tant que renvoyer False
Exercice à choix multiple
L'algorithme ci-dessus correspond à ...
Correct !
Exercice de code : ALGO 3
Coder le pseudo code donné au dessus.
Une liste lst sera générée pour vous pour la validation.
Dans la fonction, vous introduirez un comptage du nombre de comparaisons effectuées, qui sera affiché avant de sortir de la fonction (comme indiqué dans le code à compléter ci-dessus)

S'il vous reste du temps...

Modulo 7

Voici un graphe (nous étudierons les graphes plus en détail bientôt) qui permet de calculer N%7 pour tout nombre entier N :

Ce graphe contient des flèches noires et des flèches bleues. Votre premier travail est de modéliser le graphe avec deux dictionnaires : BLACK et BLUE.

Dans chacun des dictionnaires, les clés sont les valeurs de départ des flèches (noires ou blueues) et les valeurs sont les valeurs d'arrivée.

Par exemple, dans le dictionnaire NOIR, la clé 0 à pour valeur 1.

Ensuite, vous devez implementer l'algorithme de détermination de N%7. Etudions un exemple :


Exercice de code : Graphe Modulo 7

T1.a - Révisions cours : les listes

I Principales méthodes de manipulation des Listes

Nous avons utilisé les listes très fréquemment et nous allons rapidement revoir les principales méthodes associées aux objets de type list.

Comme pour les chaînes de caractères, les listes possèdent de nombreuses méthodes qui leur sont propres et qui peuvent se révéler très pratiques. On rappelle qu'une méthode est une fonction qui agit sur l'objet auquel elle est attachée par un point. Nous étudierons la programmation orientée objet (POO) très prochainement.


AJOUTER : .append et .insert


La méthode .append(), ajoute un élément à la fin d'une liste tandis que La méthode .insert() insère un objet dans une liste avec un indice déterminé :

Exemple : mince ! j ai oublié mon d


LOCALISER, COMPTER : .index et .count


La méthode .count() compte le nombre d'éléments (passés en argument) dans une liste :
La méthode .index() donne la position d'un élément dans une liste.

Exemple : Combien de a dans 'abracadabra' ?


TRIER : .sort et .sorted et aussi reverse


La méthode .sort() trie une liste en laissant les valeurs triées dans cette liste tandis que  .sorted() renvoie une copie de la liste triée

Exemple : trier en place ou pas ?


SUPPRIMER : del remove pop


Exemple : suppression d'élément avec remove
Exemple : suppression d'élément : la fonction del
Exemple : suppression d'élément : la méthode pop

Construction d'une liste par itération

La méthode .append() est très pratique car on peut l'utiliser pour construire une liste au fur et à mesure des itérations d'une boucle.

Pour cela, il est commode de définir préalablement une liste vide de la forme maliste = []. Voici un exemple où une chaîne de caractères est convertie en liste :

Exemple : contruction par itération

La méthode avec list(seq) est certes plus simple, mais il arrive parfois qu'on doive utiliser des boucles tout de même, comme lorsqu'on lit un fichier. On rappelle que l'instruction list(seq) convertit un objet de type chaîne de caractères en un objet de type liste. De même que list(range(10)) convertit un objet de type range en un objet de type list ou encore list(dic.keys()) converti la liste des clés d'un dictionnaire en un objet de type liste.


Appartient : in


Exemple : test d'appartenance

Autres méthodes utiles


Le type liste de python dispose de méthodes supplémentaires par rapport à ce qui précède. Voici toutes les méthodes des objets de type liste :

  • list.extend(iterable)
    Étend la liste en y ajoutant tous les éléments de l'itérable. Équivalent à a[len(a):] = iterable.
  • list.clear()
    Supprime tous les éléments de la liste. Équivalent à del a[:].
  • list.index(x[, start[, end]])
    Renvoie la position du premier élément de la liste dont la valeur égale x (en commençant à compter les positions à partir de zéro). Une exception ValueError est levée si aucun élément n'est trouvé. Les arguments optionnels start et end sont interprétés de la même manière que dans la notation des tranches et sont utilisés pour limiter la recherche à une sous-séquence particulière. L'indice renvoyé est calculé relativement au début de la séquence complète et non relativement à start.

T - 4.2 Listes

Dans cette partie nous utiliserons donc ce jeu de primitives :

listeVide (): renvoie une LISTE vide
estListeVide (l) : renvoie True si l est une LISTE vide, False sinon
cons(x,l) : renvoie une nouvelle LISTE égale à l plus l'élément x ajouté en tête
listeQueue(l) : renvoie la queue de l
listeTete(l) : renvoie la tête de la LISTE

et nous ajouterons une première fonction dérivée des primitives de base :
longueur(l) : renvoie la longueur de la LISTE l

Le type des objet ainsi créés est nommé LISTE

une première implémentation

Exemple : Type abstrait LISTE

Complexité

Exercice à choix multiple : Complexité de la fonction cons :
le nombre d'instructions requis pour cette fonction est :
Correct !
Exercice à choix multiple : Complexité de la fonction longueur :
le nombre d'instructions requis pour cette fonction est :
Correct !

Une seconde implémentation

Bon, il est possible que notre représentation avec les tuples imbriqués ne vous plaise pas beaucoup... non ? En fait ceci n'est qu'une affaire de notation, et n'a pas grande importance. Dans l'exemple ci-dessous, nous allons modifier le constructeur pour changer la représentation de nos LISTE mais nous ne changeons pas les autres primitives (sauf listeQueue de façon marginale), et pas plus la fonction dérivée longueur, et tout fonctionne de façon identique :

Exemple : Type abstrait LISTE version 2

Notez bien que, malgré l'implémentation un peu différente, les appels aux primitives sont strictement identiques (le programme principal est strictement identique, la fonction longueur également).

La représentation est bien la même, nous avons seulement affecté la notation.
Dans la suite, nous utiliserons cette version, qui donne un affichage plus lisible, mais pour autant, ne perdez pas de vue que nos LISTE sont toujours une tête et une queue.

POO - Bilbo et Golum

A vous : programmez le combat

Exercice de code : combat à mort
Modifiez de nouveau le code, cette fois la méthode perdVie doit être écrite de façon à ne jamais renvoyer un nombre de vie négatif. Si le nombre de vie est négatif, nombre de vie sera mis à 0.. Vous devez :
  1. Modifiez perdVie pour ne jamais renvoyer un nombre de vie négatif.
  2. Completer le code de façon à créer 2 personnages ayant 100 vies.
  3. Vous initialiserez une variable attaquant qui vaut 0 ou 1. Si elle est égale à 0, c'est Bilbo qui attaque en premier, sinon c'est Golum. A la fin de chaque attaque, la variable attaquant prendra la valeur 1-attaquant.
  4. A la fin du combat affichez le nombre d'attaques qui ont eu lieu.

T - 4 - Implémenter les graphes

Comme les listes, les piles, et les files, il est important de distinguer le type abstrait de représentation des données, du type implémenté dans le langage.

En Python il n'existe pas de type GRAPHE prédéfini. C'est donc à chacun de l'implémenter avec les outils disponibles dans le langage.

Comme pour les listes il peut exister, selon les auteurs, des différences sur le nombre et la définition des primitives de bases. Nous allons utiliser ici ce jeu de primitives :

  • creerGrapheVide() : retourne un graphe vide
  • estVideGraphe(G) : retourne True si G est un graphe vide
  • ajouterSommet(G,s) : retourne le graphe après ajout du sommet s
  • supprimerSommet(G,s) : retourne le graphe après suppression du sommet s (et tout les arcs rliés à s)
  • existeSommet(G,s) : retourne True si s est un sommet du graphe G
  • Pour un graphe orienté :
    • ajouterArc(G,sd,sa) : retourne le graphe après ajout d'un arc reliant sd à sa (orienté)
    • supprimerArc(G,sd,sa) : retourne le graphe après suppression de l'arc sd->sa
    • existeArc(G,sd,sa) : retourne True si sd->sa est un arc du graphe G
  • Pour un graphe non orienté :
    • ajouterArete(G,sd,sa) : retourne le graphe après ajout d'une arête reliant sd à sa (non-orienté)
    • supprimerArete(G,sd,sa) : retourne le graphe après suppression de l'arête sd->sa
    • existeArete(G,sd,sa) : retourne True si sd->sa est une arête du graphe G

Une première implémentation (d'un graphe orienté) avec un dictionnaire

Comme nous l'avons vu, un graphe peut être représenté par une liste de successeur. Cette représentation peut être implémentée efficacement avec un dictionnaire. Chaque sommet sera donc une clé dictionnaire, et sa valeur sera la liste des sommets sa reliés à s dans le sens s -> sa.

En conséquence, un graphe vide est un dictionnaire vide.

Exemple : implémentation des graphes avec un dictionnaire

Premier exemple d'implémentation d'un graphe, en utilisant une liste de dictionnaire dont les clés sont les sommets et les valeurs les listes de successeurs des sommets.