Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Devoir 1 : Algorithmes, base de donn´ ees & coding Professeur : Hayat Zouiten h

Devoir 1 : Algorithmes, base de donn´ ees & coding Professeur : Hayat Zouiten hayat.zouiten@um6p.ma Tous les exercices de ce devoir doivent ˆ etre r´ esolus en utilisant le langage de programmation Python. Le ﬁchier contenant vos r´ eponses doit ˆ etre sous la forme d’un ﬁchier source Jupyter Notebook (.ipynb) et vous devez l’envoyer ` a mon adresse mail. La date limite pour soumettre ce devoir est le lundi 12 avril avant minuit. Exercice 1 : Nombre pairs et impairs ´ Ecrire une fonction trie(classeur, entier) qui permet de ranger un nombre entrer au clavier soit dans la liste ”pairs” ou ”impairs” du dictionnaire classeur selon la parit´ e de l’entier. Indication: Le dictionnaire classeur contiendra deux cl´ es, une ”paire” dont la valeur est une liste d’entiers pairs et l’autre ”impaire” dont la valeur est ´ egalement une liste d’entiers impairs saisis par l’utilisateur. Votre dictionnaire doit ˆ etre d´ eclar´ e avant la fonction. Exercice 2 : Triangle de Pascal 1. ´ Ecrire une fonction fact(n) qui retourne la factorielle d’un entier donn´ e en argument. Exemple: pour n= 5 on a : 5!=120 2. ´ Ecrire une fonction binome( n, k) pour calculer Ck n = n! k! × (n −k)! 3. ´ Ecrire une fonction print pascal(n) pour afﬁcher un triangle de Pascal de n lignes. Indication: • Les r´ esultats renvoy´ es par cette fonction se pr´ esenteront sous la forme d’une liste, comme le montre l’exemple ci-dessous : 4. ´ Ecrire la fonction principale (programme principale) pour lire n puis afﬁcher un triangle de Pascal de n lignes. Vous pouvez r´ ep´ eter la lecture et l’afﬁchage dans une boucle. 1 Exercice 3 : Jeux du plus ou du moins 1. ´ Ecrire un programme mettant en œuvre le jeu suivant : Le premier utilisateur saisi un entier que le second doit deviner. Pour cela, il a le droit ` a autant de tentatives qu’il souhaite. A chaque ´ echec, le programme lui indique si l’entier chercher est plus grand ou plus petit que sa proposition. Exemple : ≫Entrer le nombre myst` ere par le premier utilisateur ? 35 ≫Devinez le nombre myst` ere ? 30 30 est trop petit ! ≫Devinez le nombre myst` ere ? 40 40 est trop grand ! ≫Devinez le nombre myst` ere ? 35 F´ elicitations, le nombre myst` ere est bien 35!!! Am´ elioration du programme: 2. Ajouter un score indiquer ` a l’utilisateur en combien de coups il a trouv´ e le nombre myst` ere. Exercice 4 : Liste La liste suivante repr´ esenta les notes d’une classe : note = {15.25, 14, 20, 14.75, 14.66, 8.5, 13.7, 10.5, 11.25, 13.33, 9.75, 17.87, 19.25, 18.5, 12.45} 1. Combien d’´ etudiants y a-t-il dans cette classe ? 2. Afﬁcher la bonne note de la classe ? 3. Afﬁcher l’indice de la bonne note de la classe ? 4. Afﬁcher la pire note de la classe ? 5. Afﬁcher l’indice de la pire note de la classe ? 6. Afﬁcher la liste des notes du plus grand au plus petit ? 7. Renverser et afﬁcher la liste pr´ ec´ edente ? 8. Compter et afﬁcher le nombre d’´ etudiants qui ont obtenu la moyenne dans cette classe ? Exercice 5 : Distance de Hamming • La distance de Hamming entre deux mots est une notion utilis´ ee dans de nombreux do- maines (t´ el´ ecommunications, traitement du signal, · · · ). Elle est d´ eﬁnie, pour deux mots de mˆ eme longueur, comme le nombre de positions ou les deux mots ont un caract` ere diff´ erent. • ´ Ecrire une fonction hamming qui calcule la distance de Hamming entre deux mots lorsqu’ils ont la mˆ eme longueur, et qui renvoie -1 sinon. 2 Exemple: • hamming(”aaba”, ”aaha”) renvoie 1. • hamming(”poire”, ”pomme”) renvoie 2. • hamming(”stylo”, ”bouteille”) renvoie -1. Exercice (Optionnel avec bonus) : R´ ecursivit´ e et jeu de Tours de Hano¨ ı Le jeu des Tours de Hano¨ ı est comme suit : On a 3 piquets en face de soi, num´ erot´ es 1, 2 et 3 de la gauche vers la droite, et n rondelles de tailles toutes diff´ erentes entourant le piquet 1, formant un cˆ one avec la plus grosse en bas et la plus petite en haut. On veut amener toutes les rondelles du piquet 1 au piquet 3 en ne prenant qu’une seule rondelle ` a la fois, et en s’arrangeant pour qu’` a tout moment il n’y ait jamais une rondelle sous une plus grosse. Un raisonnement par r´ ecurrence permet de trouver la solution en quelques lignes. ´ Ecrire un programme en Python pour r´ esoudre ce probl` eme. Figure 1: Illustration de la r´ esolution du jeu des tours de Hano¨ ı pour n = 3 3 uploads/s3/ devoir-1-algorithmes-1.pdf