# --- Exo 1 # On considère qu'un entier b représente un tableau bits, avec comme # clé de lecture que b[x] vaut True ssi le bit de rang x de b vaut 1. # Ainsi l'entier 26, qui s'écrit en binaire \of{0...011010}, # représente le tableau de booléens [False, True, False, True, True, # False, ..., False], autrement dit l'ensemble {1, 3, 4}. # On peut donc utiliser l'entier 2^x, qui a tous ses bits à \of{0} sauf # le bit de rang \of{x} qui vaut \of{1}, comme révélateur. On calcule # 2^x avec l'opération de décalage 1 << x. Si on fait un ou bit à bit # s | (1 << x), alors on fait passer le bit de rang x de s à 1 (et il # y reste s'il y était déjà). Si en revanche on fait un et à bit (s & # (1 << x)), on obtient soit 2^x si b[x] vaut True, soit 0 sinon. def cree(): return [0] def contient(s, x): assert x>=0 return s[0] & (1 << x) != 0 def ajoute(s, x): assert x>=0 s[0] = s[0] | (1 << x) # --- Exo 2 x = int(input("Entrer un entier:")) while True: try: y = int(input("Entrer un entier non nul:")) z = x / y break except ZeroDivisionError: print("Il faut un nombre entier non nul") # --- Exo 3 # La tranche est créée dans un nouveau tableau de longueur adaptée, où # on place les éléments prélevés à partir de l'indice \of{i}. La # concaténation de même crée dès l'origine un tableau de taille # adaptée. def tranche(t, i, j): n = j - i if n <= 0: return [] else: tab = [None] * n for k in range(n): tab[k] = t[i+k] return tab def concatenation(t1, t2): l1, l2 = len(t1), len(t2) tab = [None] * (l1 + l2) for i in range(l1): tab[i] = t1[i] for i in range(l2): tab[l1 + i] = t2[i] return tab # --- Exo 4 # Le dictionnaire vide n'est rien d'autre qu'un tableau vide. def cree(): return [] # Pour chercher une clé, on passe en revue tous les couples clé-valeur # jusqu'à trouver la clé cherchée ou épuiser le tableau. def cle(d, k): for (kv, v) in d: if kv == k: return True return False def lit(d, k): for (kv, v) in d: if kv == k: return v return None # Pour ajouter une nouvelle association, il faut distinguer le cas où # la clé est déjà présente du cas où elle ne l'est pas. Ici, dans le # premier cas on remplace le couple correspondant par un nouveau # couple, et dans le deuxième cas on ajoute le nouveau couple à la # fin. def ecrit(d, k, v): for i in range(len(d)): if d[i][0] == k: d[i] = (k, v) return d.append((k, v)) # La différence avec les dictionnaires de Python est dans l'opération # de lecture. En Python, essayer d'obtenir la valeur associée à une # clé absente lève une exception KeyError. On peut l'observer ainsi : # d = {} # d['a'] # et écrire une nouvelle version de lit dans laquelle une exception # KeyError est levée si le parcours du tableau termine sans avoir # trouvé la clé cherchée. def lit(d, k): for (kv, v) in d: if kv == k: return v raise KeyError(k) # --- Exo 5 class Ensemble: def __init__(self): self.taille = 0 self.paquets = [[] for _ in range(23)] def contient(self, x): return x in self.paquets[x % 23] def ajoute(self, x): if not self.contient(x): self.taille += 1 self.paquets[x % 23].append(x) def contient_doublon(t): s = Ensemble() for x in t: if s.contient(x): return True s.ajoute(x) return False # --- Exo 6 # On teste la valeur du dénominateur dans le constructeur. Pour le # reste, on applique les règles de calcul et on construit une nouvelle # fraction dans chaque opération arithmétique. class Fraction: def __init__(self, n, d): if d <= 0: raise ValueError(str(d) + \ " n'est pas strictement positif") self.num = n self.denom = d def __str__(self): if self.denom == 1: return str(self.num) return str(self.num) + ' / ' + str(self.denom) def __eq__(self, f): return self.num * f.denom == f.num * self.denom def __lt__(self, f): return self.num * f.denom < f.num * self.denom def __add__(self, f): return Fraction(self.num*f.denom + f.num*self.denom, self.denom * f.denom) def __mul__(self, f): return Fraction(self.num*f.num, self.denom*f.denom) # Comme les fractions ne sont jamais modifiées, il suffit de charger # le constructeur de réduire les arguments qui lui sont fournis. On # peut donc prendre le nouveau constructeur # et une fonction auxiliaire pour calculer le PGCD. def _pgcd(a, b): if b == 0: return a return Fraction._pgcd(b, a % b) def __init__(self, n, d): if d <= 0: raise ValueError(str(d) + \ "n'est pas strictement positif") p = Fraction._pgcd(n, d) self.num = n // p self.denom = d // p # Notez qu'une fois les fractions réduites, il n'est plus nécessaire # de définir une égalité __eq__ dédiée à cette classe, car l'égalité # par défaut composante par composante donne déjà le résultat # souhaité. # Pour tester, grâce aux méthodes spéciales __eq__, __lt__, __add__ et # __mul__ on peut utiliser les notations arithmétiques usuelles. print(Fraction(11, 12)) assert Fraction(1, 2) == Fraction(1, 3) + Fraction(1, 2) * Fraction(1, 3) # --- Exo 7 class Intervalle: """classe pour représenter un intervalle fermé d'extrémités a et b, considéré vide si b < a""" def __init__(self, a, b): self.a = a self.b = b def est_vide(self): return self.b < self.a # La longueur d'un intervalle est donnée par la différence entre les # bornes, avec cas particulier pour l'intervalle vide. def __len__(self): return max(0, self.b-self.a) def __contains__(self, x): return self.a <= x <= self.b # Deux intervalles sont égaux s'ils ont les mêmes bornes, ou s'ils # sont tous deux vides. L'inclusion est déterminée par une comparaison # des indices lorsque les intervalles sont non vides, mais le cas self # vide doit être traité à part. def __eq__(self, i): return self.est_vide() and i.est_vide() \ or self.a == i.a and self.b == i.b def __le__(self, i): return self.est_vide() \ or i.a <= self.a and self.b <= i.b def intersection(i, j): return Intervalle(max(i.a, j.a), min(i.b, j.b)) def union(i, j): return Intervalle(min(i.a, j.a), max(i.b, j.b)) # --- Exo 8 def fact(n): if n == 0: return 1 else: return n * fact(n - 1) # --- Exo 9 def syracuse(u_n): print(u_n) if u_n > 1: if u_n % 2 == 0: syracuse (u_n // 2) else: syracuse (3 * u_n + 1) # --- Exo 10 def serie(n, a, b): if n == 0: return a elif n == 1: return b else: r = 3 * serie(n - 1, a, b) + 2 * serie(n - 2, a, b) + 5 return r # --- Exo 11 def boucle(i,k): if i <= k: print(i) boucle(i+1, k) # --- Exo 12 def pgcd(a, b): if b == 0: return a return pgcd(b, a % b) # --- Exo 13 def nombre_de_chiffres(n): if n <= 9: return 1 else: return 1 + nombre_de_chiffres(n // 10) # --- Exo 14 def nombre_de_bits_1(n): if n == 0: return 0 else: return (n % 2) + nombre_de_bits_1(n // 2) # --- Exo 15 def appartient(v, t, i): if i == len(t): return False else: return t[i] == v or appartient(v, t, i + 1) # --- Exo 16 def hanoi(n,a=1,b=2,c=3): if n > 0: hanoi(n-1,a,c,b) print ("Move ",a," on",c) hanoi(n-1,b,a,c) # --- Exo 17 def C(n,p): if p == 0 or n == p: return 1 else: return C(n - 1, p - 1) + C(n - 1, p) for i in range(10): for j in range(i + 1): print(C(i, j), ' ', end='') print() # --- Exo 18 from turtle import * def koch(n, l): if n == 0: forward(l) else: koch(n - 1, l/3) left(60) koch(n - 1, l/3) right(120) koch(n - 1, l/3) left(60) koch(n - 1, l/3) koch(3,400)