Série d’exercices N°2 Programmation Python

Exercice 1. Écrire un programme qui permet de saisir le nom de l'utilisateur et d’afficher "Bonjour", suivi de ce nom. Exercice 2. Ecrire un programme qui permet de saisir un entier tant que la valeur entrée ne peut être convertie en entier. (Indication : utiliser la méthode isdigit() qui permet de vérifier si une chaîne contient que des caractères chiffres ou non) Exercice 3. Ecrire un programme qui calcule la somme des chiffres d’un entier positif. Exercice 4. Ecrire un programme qu’affiche n tel que n soit le premier entier qui vérifie 2n > k. Ce programme lit l’entrée k au clavier. On précise qu’en langage Python, 2**n signifie 2 à la puissance n. Exercice 5. On considère deux listes d’entiers. La première est inférieure à la seconde si l’une des deux conditions suivantes est vérifiée :

– les n premiers nombres sont égaux mais la première liste ne contient que n éléments tandis que la seconde est plus longue

– les n premiers nombres sont égaux mais que le n + 1ème de la première liste est inférieur au n + 1ème de la seconde liste

Par conséquent, si l est la longueur de la liste la plus courte, comparer ces deux listes d’entiers revient à parcourir tous les indices depuis 0 jusqu’à l exclu et à s’arrêter sur la première différence qui détermine le résultat. S’il n’y pas de différence, alors la liste la plus courte est la première. Il faut écrire une fonction compare_liste(p, q) qui implémente cet algorithme. Exercice 6. Ecrire un programme qui calcule l’élément u13 de la suite définie par :

u1= 1 u2= 2 n > 2; un = un-1 + un-2

Exercice 7. fonctions et procédures On désire créer un glossaire des mots techniques d’informatique. Pour cela on utilisera un une chaîne de caractères Glossaire, dans lequel on stockera les mots techniques. Tous les mots, sauf le dernier, sont suivit par le caractère ‘ :‘. ‘o’ ‘r’ ‘d’ ‘i’ ‘n’ ‘a’ ‘t’ ‘e’ ‘u’ ‘r’ ‘:‘ ‘s’ ‘o’ ‘u’ ‘r’ ‘i’ ‘s’ a) Ecrire la fonction AjoutMot(Glossaire ) qui lit un mot au clavier et l’ajoute au glossaire la nouvelle chaîne doit être retourner. b) Ecrire la fonction NombreMot(Glossaire) qui calcul et retourne le nombre de mots contenu dans la chaîne. c) Ecrire la procédure AfficheListeMot(Glossaire ) qui affiche la liste de tous les mots du glossaire d) Ecrire la fonction dont la signature est : chercheMot(Glossaire , Mot) qui retourne 1 si le mot Mot existe dans le Glossaire et 0 sinon. e) Ecrire la fonction iemeMot(Glossaire , i) qui affiche le ième mot du glossaire s’il existe et affiche : «indice hors limite » sinon. f) Ecrire la fonction existeDoublon(Glossaire) qui cherche l’existence des mots en double. g) Ecrire la fonction supprimeMot(Glossaire) qui supprime un mot du glossaire dont on précisera la position. e) Ecrire une fonction qui permet de créer une liste contenant tous les mots techniques contenant dans le Glossaire GlossaireToListe(Glossaire) f. Plus difficile : écrire une fonction triGlossaire(Glossaire) qui classe tout les mots du glossaire par ordre alphabétique croissant.

Exercice 8

La notation habituelle des expression algébriques, sous forme dite infixe, où les opérateurs +, -, *, / figurant entre leurs 2 opérandes, souffre a priori d’une ambiguïté si l’on n’introduit pas des priorités entres les opérateurs. C’est ainsi que la notation 2+3*4 peut aussi bien désigner 2+(3*4)=14 que (2+3)*4=20.

Des parenthèses ou des règles de priorité sont donc nécessaire pour lever cette ambiguïté. Nous allons étudier ici une autre notation, appelée notation algébrique poste-fixée ou encoure notation polonaise inversée qui ne souffre pas de ces inconvénients. Cette notion est utilisée par certains langages de programmations ou certaines calculatrices.

Exemple

2 3 + sin 4 * 5 6 + -

Son équivalent en notation infixée : (sin(2+3)*4)-(5+6)

Les étapes de son évaluation :

+ opérateur binaire r=2+3 sin un seul paramètre r=sin(r) * opérateur binaire r=r*4 + opérateur binaire s=5+6 - opérateur binaire r=r-s

On suppose dans ce problème une expression algébrique sous forme d’une chaîne de caractère C composée de : 4 opérateurs ‘+’, ‘-‘, ‘*’, ‘/’ des opérandes caractères appartenant à l’ensemble des entiers {exemple "10","231", "2", "1759"} représentant des entiers positifs.

La transformation d’un caractère chiffre ‘0’<=C[i]<’9’ en entier équivalent se fait par la soustraction du caractère ‘0’ de c[i] (ex. ‘1’-‘0’ = 1).

Des étapes de l’évaluation, on remarque que les opérandes de s sont mémorisées puis évaluées par les opérateurs de s suivant le principe LIFO (Last In First Out) implémenté par une structure stack (liste dans notre cas).

Exemple "1 2 +"

(le dernier caractère souligné est le caractère courant)

1 2 + 1 2 + 1 2 +

2 2

1

1

a

1

b

1

a+b

3

On supposant que l’expression s est rédigée correctement selon la notation algébrique poste-fixe.

Ecrire la fonction eval(s) qui donne la valeur de l’expression algébrique C. Solution 1) Nom=input(‘donner votre nom’) print(‘Bonjour’,Nom) 2) N=input(‘donner un entier’) while(N.isdigit()==False) N=input(‘donner un entier’) N=int(N) 3) def somme (n) :

return sum ( [ int (c) for c in str (n) ] )

Cette écriture résumée cache une conversion en chaîne de caractères. Une boucle est inévitable à moins de procéder par récurrence. Commençons par une version plus étendue et qui passe par les chaînes de caractères. Pour cette version, il ne faut pas oublier de faire la conversion inverse, c’est-à-dire celle d’un caractère en nombre. def somme (n) :

l = str (n) # il ne faut pas confondre l=str (n) avec l = "n" s = 0 for c in l : # ou for i in range (0, len (c)) :

s += int (c) # ou s += int (c [i]) return s

Une version numérique maintenant, celle qui utilise l’opération % ou modulo pour obtenir le dernier chiffre def somme (n) :

s = 0 while n > 0 :

s += n % 10 n /= 10 # ici, c’est une division entière, si vous n’êtes pas sûr :

# n = int (n/10) return n Enfin, une autre solution utilisant la récurrence et sans oublier la condition d’arrêt def somme (n) :

if n <= 0 : return 0 else : return (n % 10) + somme ( n / 10 )

4) def fonction_log2 (k) :

n = 0 while 2**n < k :

n += 1 return n

5) Version 1 def compare_liste (p,q) :

i = 0 while i < len (p) and i < len (q) :

if p [i] < q [i] : return -1 # on peut décider elif p [i] > q [i] : return 1 # on peut décider i += 1 # on ne peut pas décider

# fin de la boucle, il faut décider à partir des longueurs des listes if len (p) < len (q) : return -1 elif len (p) > len (q) : return 1 else : return 0

On pourrait également écrire cette fonction avec la fonction cmp qui permet de comparer deux éléments quels qu’ils soient. Version 2 def compare_liste (p,q) :

i = 0 while i < len (p) and i < len (q) :

c = cmp (p [i], q [i]) if c != 0 : return c # on peut décider i += 1 # on ne peut pas décider

# fin de la boucle, il faut décider à partir des longueurs des listes return cmp (len (p), len (q))

6) def Fibonacci (n) :

if n == 2 : return 2 elif n == 1 : return 1 else : return Fibonacci (n-1) + Fibonacci (n-2)

print Fibonacci (13) Cette solution n’est pas très rapide car si Fibonacci (13) va être appelée une fois, Fibonacci (12) une fois aussi, mais Fibonacci (11) va être appelée deux fois... Cette solution implique un grand nombre de calculs inutiles. Après la solution récursive descendante (n décroît), la solution récursive montante (n croît) : version 2 def Fibonacci (fin, n = 2, u1 = 1, u2 = 2) :

if fin == 1 : return u1 elif fin == 2 : return u2 elif n == fin : return u2 u = u1 + u2 return Fibonacci (fin, n+1, u2, u)

print Fibonacci (13) La méthode la plus simple est non récursive mais il ne faut pas se tromper dans les indices : def Fibonacci (n) :

if n == 1 : return 1 u1 = 1 u2 = 2 for i in range (3,n+1) :

u = u1 + u2 # il est impossible de u1 = u2 # résumer ces trois lignes u2 = u # en deux

return u2 print Fibonacci (13) Quelques variantes utilisant les listes def Fibonacci (n) :

if n == 1 : return 1 u = [1,2] for i in range (2,n) :

u.append (u [i-1] + u [i-2]) return u [n-1]

print Fibonacci (12)