#========================================== #= Exercice 1 : fonction mini_maxi = #========================================== def mini_maxi(liste): """ mini_maxi(liste : list)->dict entree : liste contient des nombrs dont on veut connaitre le minimum et le maximum sortie : dict_minmax dictionnaire comportant 2 éléments clés 'minimum' ou 'maximum' et la valeur associée """ # utilisation d'une assertion pour eviter un plantage si la liste est vide assert len(liste) != 0, 'Problème : Liste entrée vide ' dict_minmax = {'maximum':liste[0], 'minimum': liste[0]} #initialisation du dictionnaire totalement arbitraire for val in liste : if val > dict_minmax['maximum'] : dict_minmax['maximum'] = val if val < dict_minmax['minimum'] : dict_minmax['minimum'] = val return dict_minmax L = [1, 2, 15, -3, 25, 10, -6, -5] d = mini_maxi(L) print( d ) #Affiche {'maximum': 25, 'minimum': -6} #========================================== # Exercice 2 : Derivation de polynomes = #========================================== #_________Question 1________ def derivePolynome (liste_Coeff): """ derivePolynome (liste_Coeff : list) -> list entree : liste_Coeff liste des coefficients des monomes par degrés croissants sortie : liste_Coeff_Derivee liste des coefficients des monomes par degrés croissants après dérivation """ liste_Coeff_Derivee=[] if( len (liste_Coeff ) > 1) : for deg in range(1, len(liste_Coeff)) : #debut en 1 pour ne pas gérer le monome de degré 0 liste_Coeff_Derivee.append(liste_Coeff[deg]*deg ) else : #cas du polynome constant ou nul liste_Coeff_Derivee.append(0) return liste_Coeff_Derivee print ( derivePolynome( [2,3,0,0,-5] ) ) # affiche [3, 0, 0, -20] print( derivePolynome( [5,2,0,-4] ) ) # Complexité : # Dans tous les cas, la liste liste_Coeff a pour longueur n+1 (avec n degré du polynome). # => La complexité en espace est donc O(n) # dans tous les cas, on parcourt l'ensemble de la liste pour calculer la dérivée # => La complexité en temps est donc O(n) #_________Question 2________ def derivePolynome_Dict (dict_Poly): """ derivePolynome_Dict (dict_Poly : dict ) -> dict entree : dict_Poly, dictionnaire, coefficients des monomes non nuls sortie : dict_Poly_Derivee, dictionnaire, coefficients des monomes non nuls après dérivation """ dict_Poly_Derivee={} if len (dict_Poly ) == 1 and 0 in dict_Poly : #gestion du polynome nul ou constant dict_Poly_Derivee[0] = 0 else : for deg in dict_Poly : #debut en 1 pour ne pas gérer le monome de degré 0 if deg != 0 : dict_Poly_Derivee[deg -1] = dict_Poly[deg] * deg return dict_Poly_Derivee print ( derivePolynome_Dict( {0 : 2, 1 :3, 4 : -5 } ) ) # affiche {0: 3, 3: -20} print( derivePolynome_Dict( {0:5 , 1:2 , 3 :-4}) ) # Complexité : # La complexite dépend du nombre de monomes non nuls # Dans le pire des cas, avec n+1 monomes non nuls, les complexités en espace et temps dont en O(n) # Dans le meilleur des cas,un nombre de monomes negligeable devant le degré n. DOnc complexité constantes O(1) #========================================== #= Exercice 3 : Quizz = #========================================== #_________Question 1________ # correction_QCM - Avec effet de bord def correction_QCM (reponses_Eleves,reponses_valides): """ correction_QCM (reponses_Eleves : dict ,reponses_valides : dict ) entrées : reponses_Eleves dictionnaire dont les clé sont les numéros des éléves et la valeur un dictionnaire comportant nom, prenom et reponses aux questions reponses_valides dictionnaire qui comporte les bonnes reponses Cette fonction agit en modifiant le contenu du dictionnaire en ajoutant le score dans reponses_Eleves (effet de bord) """ for cleEleve in reponses_Eleves.keys() : # pour chaque élève : clé => cleEleve : numero - # valeur reponses_Eleve => dictionnaire comportant nm, prenom et ensemble des reponses score_Eleve = 0 for cle_ReponsesValide, val_ReponsesValide in reponses_valides.items() : valeurReponseEleve = reponses_Eleves[cleEleve][cle_ReponsesValide] if valeurReponseEleve != '' : if valeurReponseEleve != val_ReponsesValide : # réponse invalide (mais différente de la chaine vide : non reponse =>score =0) score_Eleve -= 1 else : # réponse valide score_Eleve += 3 # Une fois toutes les clés du fichier de reponse traitées, on ajoute au dictionnaire le score de chaque élève reponses_Eleves[cleEleve]['Score'] = score_Eleve # ajout de la clé Score pour l'eleve avec sa valeur score calculée # correction_QCM_sansEB - Sans effet de bord def correction_QCM_sansEB (reponses_Eleves,reponses_valides): """ correction_QCM_sansEB (reponses_Eleves : dict ,reponses_valides : dict ) -> dict entrées : reponses_Eleves dictionnaire dont les clé sont les numéros des éléves et la valeur un dictionnaire comportant nom, prenom et reponses aux questions reponses_valides dictionnaire qui comporte les bonnes reponses sorties : resultats_Eleves dictionnaire comportant reponse des élèves et score final """ import copy resultats_Eleves = copy.deepcopy(reponses_Eleves) #copie profonde obligatoire => modification du "sous-dictionnaire" # Rq : en lecture on peut travailler sur l'un ou l'autre des dictionnaires eleve (peu importe : ils contiennent les memes valeurs) for cleEleve in reponses_Eleves.keys() : # pour chaque élève : clé => cleEleve : numero - # valeur reponses_Eleve => dictionnaire comportant nm, prenom et ensemble des reponses score_Eleve = 0 for cle_ReponsesValide, val_ReponsesValide in reponses_valides.items() : valeurReponseEleve = reponses_Eleves[cleEleve][cle_ReponsesValide] if valeurReponseEleve != '' : if valeurReponseEleve != val_ReponsesValide : # réponse invalide (mais différente de la chaine vide : non reponse =>score =0) score_Eleve -= 1 else : # réponse valide score_Eleve += 3 # Une fois toutes les clés du fichier de reponse traitées, on ajoute au dictionnaire le score de chaque élève resultats_Eleves[cleEleve]['Score'] = score_Eleve return resultats_Eleves #_________Question 2________ def generation_dictionnairesv1(fichier) : """ generation_dictionnaires(fichier : str) -> dict, dict entree : fichier correspond au nom du fichier eventuellement prefixe par son chemin sortie : dictionnaire reponses_Eleves qui correspond au dictionnaire des reponses des eleves dictionnaire reponses_valides qui correspond au dictionnaire des bonnes reponses """ #initialisation des dictionnaires reponses_valides = {} fic = open(fichier,'r') ligne1 = (fic.readline()).strip() liste1 = ligne1.split(',') # liste des valeurs de la 1e ligne print("===",liste1) ligne2 = (fic.readline()).strip() liste2 = ligne2.split(',') # liste des valeurs de la 21e ligne print(liste2) for i in range(3,len(liste1) ) : reponses_valides[liste1[i]] = liste2[i] reponses_Eleves = {} reponses = fic.readlines() # reponses des élèves for ligne in reponses : l = ligne.strip() lesreponses = l.split(',') cleELeve = lesreponses[0] dictResEleve={} k=3 dictResEleve['Nom'] = lesreponses[1] dictResEleve['Prenom'] = lesreponses[1] for cle in reponses_valides : dictResEleve[cle] = lesreponses[k] k=k+1 reponses_Eleves[cleELeve] = dictResEleve fic.close() return reponses_Eleves, reponses_valides fichier = 'C:\\Users\\eclermont\\CPGE IPT\\EC\\ITC_S3_2_1_Dictionnaires\\test.csv' print ( generation_dictionnairesv1(fichier)) # en utilisant le module csv import csv def generation_dictionnaires(fichier) : """ generation_dictionnaires(fichier : str) -> dict, dict entree : fichier correspond au nom du fichier eventuellement prefixe par son chemin sortie : dictionnaire reponses_Eleves qui correspond au dictionnaire des reponses des eleves dictionnaire reponses_valides qui correspond au dictionnaire des bonnes reponses manipulation du fichier avec le module csv """ reader = csv.DictReader(open(fichier)) #initialisation des dictionnaires reponses_Eleves = {} reponses_valides = {} cpt = 1 # mise en place d'un compteur pour gérer les bonnes reponses for row in reader: key = row.pop('Numero') # affectation de la clé avec la valeur de la colonne Numero #if key in result: # au cas ou il y ait des doublons : pas le cas ici # implement your duplicate row handling here # pass if( cpt ==1 ) : # gestion de la ligne de réponses => Genération du dictionnaire reponses_valides =row print(reponses_valides) del reponses_valides['Nom'] del reponses_valides['Prenom'] # Les 2 instructions précedentes ne sont pas forcément nécessaires mais elle permettent d'éliminer Nom et Prenom #{'Nom': 'reponse', 'Prenom': 'reponse', 'Q1': 'a', 'Q2': 'c', 'Q3': 'd', 'Q4': 'e', 'Q5': 'b', 'Q6': 'c'} # devient #{ 'Q1': 'a', 'Q2': 'c', 'Q3': 'd', 'Q4': 'e', 'Q5': 'b', 'Q6': 'c'} cpt+=1 else : # gestion des resultats des eleves reponses_Eleves[key] = row return reponses_Eleves, reponses_valides fichier = 'C:\\Users\\eclermont\\CPGE IPT\\EC\\ITC_S3_2_1_Dictionnaires\\test.csv' res_Eleves, res_reponses_valides = generation_dictionnaires(fichier) print( res_Eleves, ' \n ===', res_reponses_valides ) #print( correction_QCM_sansEB(res_Eleves , res_reponses_valides)) correction_QCM (res_Eleves , res_reponses_valides) #print( res_Eleves ) #==================================================================== #= Exercice 5 :Anagrammes = #==================================================================== def determine_nb_occurences(mot): ''' determine_nb_occurences(mot : str) -> dict entree : mot, chaine de caracteres dont on veut connaitre le nb d occurences sortie : dict_occurences le dictionnaire dict_occurences comportant les couples caractere, nb d'occurrences ''' dict_occurences = {} for car in mot : if( car in dict_occurences ): dict_occurences[car] = dict_occurences[car] + 1 else : dict_occurences[car] = 1 return dict_occurences def sont_anagrammes_v1( mot1, mot2) : ''' sont_anagrammes_v1( mot1 : str, mot2 : str) : -> bool entree : mot1 et mot2, chaines de caracteres que l on veut comparer pour savoir si ce sont des anagrammes sortie : sontAnagrammes, booleen qui vaut True si mot1 et mot2 sont des anagrammes, False sinon ''' sontAnagrammes = False if len(mot1) == len(mot2) : #inutile de tester si ce sont des anagrammes si la longueur des mots est differente mot1 = mot1.upper() mot2 = mot2.upper() dicomot1 = determine_nb_occurences(mot1) dicomot2 = determine_nb_occurences(mot2) if dicomot1 == dicomot2 : sontAnagrammes = True return sontAnagrammes print( sont_anagrammes_v1( "caba", "baba") ) print( sont_anagrammes_v1( "bbaa", "baba") ) def sont_anagrammes_v2( mot1, mot2) : ''' sont_anagrammes_v2( mot1 : str, mot2 : str) : -> bool entree : mot1 et mot2, chaines de caracteres que l on veut comparer pour savoir si ce sont des anagrammes sortie : sontAnagrammes, booleen qui vaut True si mot1 et mot2 sont des anagrammes, False sinon ''' sontAnagrammes = False if len(mot1) == len(mot2) : dicomot1 = determine_nb_occurences(mot1) dicomot2 = determine_nb_occurences(mot2) if( len(dicomot1) == len(dicomot2) ) : #inutile de tester si les longueurs des dictionnaires sont différentes sontAnagrammes = True for cle, val in dicomot1.items() : if not (cle in dicomot2 and val == dicomot2[cle] ): del dicomot2[cle] else : break return sontAnagrammes print( sont_anagrammes_v2( "caba", "baba") ) print( sont_anagrammes_v2( "bbaa", "baba") ) def sont_anagrammes_v2( mot1, mot2) : ''' sont_anagrammes_v1( mot1 : str, mot2 : str) : -> bool entree : mot1 et mot2, chaines de caracteres que l on veut comparer pour savoir si ce sont des anagrammes sortie : sontAnagrammes, booleen qui vaut True si mot1 et mot2 sont des anagrammes, False sinon ''' sontAnagrammes = False mot1 = mot1.upper() mot2 = mot2.upper() if len(mot1) == len(mot2) : dicomot1 = determine_nb_occurences(mot1) for lettre in mot2 : if lettre in dicomot1 and dicomot1[lettre]>0 : dicomot1[lettre] = dicomot1[lettre] -1 else : return False return True print( sont_anagrammes_v2( "abba", "baba") ) print( sont_anagrammes_v2( "abac", "baba") ) def genere_Anagrammes ( base, dico_occurrences, listeAnagrammes, nbLettres ): ''' genere_Anagrammes ( base : str, dico_occurrences: dict, listeAnagrammes : list, nbLettres : int ): entrees: base, chaine pour laquelle on veut déterminer la liste des anagrammes : dico_occurrences: dict, dictionnaire d occurences ??? : listeAnagrammes, list : nbLettres, int ''' if nbLettres == 0: # if base not in listeAnagrammes : #eviter les eventuels doublons ? print(base) listeAnagrammes.append(base) else: for car in dico_occurrences.keys(): if dico_occurrences[car] > 0: dico_occurrences[car] -= 1 # retrait d'une occurrence du caractere car pour la recursivité. On aurait pu passer par une copie du dictionnaire genere_Anagrammes (base+car, dico_occurrences, listeAnagrammes, nbLettres-1) dico_occurrences[car] += 1 # on remet le caractere d'une occurrence pour le traitement des autres caracteres def anagrammes(mot): #dico_occurrences = dict([(l, mot.count(l)) for l in set(mot)]) # interet set??? dico_occurrences = determine_nb_occurences(mot) print(dico_occurrences) listeAnagrammes = list() genere_Anagrammes ('', dico_occurrences, listeAnagrammes, len(mot)) return listeAnagrammes #mot = input("Entrez le mot dont vous cherchez les anagrammes") #print( anagrammes (mot) ) #==================================================================== #= Exercice 6 : Compression/Decompression LZ278 = #==================================================================== def compressionLZ78( texte ): n=len(texte) indice = 0 code ='' dico ={'':0} while indice < n : ch='' while indice decompression dico_inverse = {v: k for k, v in dico.items()} texte ='' if( code[-1] == '|' ): code = code[0:-1] #retrait du dernier | les_codes = code.split('|') #decoupage des différents codes for elt in les_codes : E = elt.split(',') debut= dico_inverse[ int(E[0].strip()) ] texte += debut + E[1] return texte res,dico = compressionLZ78( "abracadabrarabarabaran" ) print ("***",res, "===",dico) res = decompressionLZ78( res,dico ) print (res) print ('test hash',res.__hash__)