## Exercice 2 # Les graphes sont simples. # 2.1 def estDansLaListe(x,L): for u in L: if u == x: return True return False def estDansLaListe_V2(x,L): return x in L # 2.2 def estVoisinDAuMoinsUn(x,L): if not estDansLaListe(x,L): for v in listeVoisins(x): if estDansLaListe(v,L): return True return False # 2.3 def nbVoisinageCommun(G,U,V): nb=0 for x in listeSommets(G): if estVoisinDAuMoinsUn(x,U) and estVoisinDAuMoinsUn(x,V): nb = nb + 1 return nb ### Exercice 3 from PIL.Image import * # 3.1 def miroirVertical(img1, img2): (l,h) = img1.size for x in range(l): for y in range(h): c = Image.getpixel(img1,(x,y)) Image.putpixel(img2,(x,h-1-y),c) # 3.2 def miroirHorizontal(img): (l,h) = img1.size img2 = new("RGB",(l,h)) for x in range(l): for y in range(h): c = Image.getpixel(img1,(x,y)) Image.putpixel(img2,(l-1-x,y),c) return img2 # img1 = open("teapot.png") # img2 = new("RGB",img1.size) # miroirVertical(img1,img2) # Image.show(img2) # Image.show(miroirHorizontal(img1)) ### Exercice 4 # 4.1 # Il y a plusieurs façons de dessiner l'arbre, mais dans tous les cas, l'arbre doit avoir quatre feuilles. # 4.2 # Par définition d'un arbre, son nombre d'arêtes est égal à n-1 (où n est le nombre de sommets). # Par la formule des poignées de main, la somme des degrés des sommets de notre arbre est égale au double du nombre d'arêtes, soit s=2(n-1) # 4.3 # Soit c le nombre de feuilles de l'arbre # L'arbre n'ayant que des sommets de degré 1, 2 et 3, son nombre de sommets vérifie n=a+b+c # La somme des degrés des sommets de cet arbre vaut s=3a+2b+c # La formule de la question précédente nous donne alors : 3a+2b+c=2a+2b+2c-2 # On en conclut donc que c=a+2 (ce qui est cohérent avec notre réponse à la question 1) ### Exercice 5 def facteurImpair(n): while n % 2 == 0: n = n //2 return n def puissanceDiviseur(p, n): v = p while n % v == 0: v = p * v return v // p def puissanceDiviseurBis(p, n): v = 1 while n % p == 0: n = n // p v = p * v return v def decompositionProduitFacteursPremiers(n): p = 2 l = [] while n > 1 : while n > 1 and n % p == 0: n = n // p l = l + [p] p = premierSuivant(p) return l