#### TP n°8: Récursivité #### ################# ### EXEMPLES SIMPLES ### ## Question 1 : Exponentiation def puissance(x,n): """ Calcule x^n """ if n==0: return 1 else: return x*puissance(x,n-1) print(puissance(3,4)) ## Test de la fonction `puissance`; **à exécuter sans éditer** ok=True if puissance(3,0)!=1: ok=False if puissance(2,3)!=8: ok=False if ok: print("Fonction puissance: test réussi!") else: print("Fonction puissance: test échoué!") ## Question 2 : Suite récurrente import math def u(n): """ calcule u_n """ if n==0: return 1 else: return math.sqrt(u(n-1)+3) print(u(100)) print((1+math.sqrt(13))/2) ## Question 3 : Suites adjacentes import math def uv(n): """ calcule u_n et v_n """ if n==0: return (1,10) else: uprec,vprec=uv(n-1) return (math.sqrt(uprec*vprec),(uprec+vprec)/2) print(uv(100)) ## Question 4 : Suite de Fibonacci def fibo1(n): """ calcule fibonacci(n) """ if n==0: return 0 elif n==1: return 1 else: return fibo1(n-1)+fibo1(n-2) print(fibo1(6)) #print(fibo1(20)) # soit a(n) le nombre d'appels pour calculer fibo(n) # le calcul de fibo(n) appelle fibo(n-1) et fibo(n-2) donc a(n)=2+a(n-1)+a(n-2) # en posant b(n)=a(n)+1 on trouve b(n)=b(n-1)+b(n-2) ce qui redonne la suite de Fibonacci # comme a(0)=0 et a(1)=0 on a b(0)=b(1)=1 donc au final b(n)=u_{n+1} # et a(n)=1+u_{n+1} # le comportement asymptotique de cette suite est en phi^n avec phi le nombre d'or # donc très vite le temps de calcul explose, ainsi que la mémoire ## Question 5 def fibo2(n): """ calcule fibonacci(n) et fibonacci(n-1) """ if n==0: return (0,1) else: unm1,un=fibo2(n-1) return (un,un+unm1) print(fibo2(6)) print(fibo2(20)) ### FRACTALES ### ### ÉVALUATION D'UN POLYNÔME ### ## Question 6 : Algorithme de Horner def horner(P:[float],x:float)->float: """ calcule P(x) à partir de la liste des coefficients du polynome """ if len(P)==1: return P[0] else: a0=P.pop() return a0+x*horner(P,x) print(horner([1,2,3],2)) ## Test de la fonction `horner`; **à exécuter sans éditer** ok=True if horner([1,2],1.5)!=3.5: ok=False if horner([1,2,3,2,1],1)!=9: ok=False if ok: print("Fonction horner: test réussi!") else: print("Fonction horner: test échoué!") ### ÉVALUATION D'UNE EXPRESSION NUMÉRIQUE ### ## Question 7 : Préliminaire def index_symbole(chaine,symbole): assert len(symbole)==1, "Le symbole ne doit contenir qu'un seul caractère" for i in range(len(chaine)): if chaine[i]==symbole: return i return -1 print(index_symbole("2*5.2+6.6-2/4","*")) ## Question 8 def decoupe_chaine(chaine,index): return [chaine[0:index],chaine[index+1:len(chaine)]] print(decoupe_chaine("2*5.2+6.6-2/4",1)) ## Question 9 : Évaluation d'une expression sans parenthèses def evalue_expression(expression): if index_symbole(expression,"+")!=-1: e1,e2=decoupe_chaine(expression,index_symbole(expression,"+")) return evalue_expression(e1)+evalue_expression(e2) if index_symbole(expression,"-")!=-1: e1,e2=decoupe_chaine(expression,index_symbole(expression,"-")) return evalue_expression(e1)-evalue_expression(e2) if index_symbole(expression,"*")!=-1: e1,e2=decoupe_chaine(expression,index_symbole(expression,"*")) return evalue_expression(e1)*evalue_expression(e2) if index_symbole(expression,"/")!=-1: e1,e2=decoupe_chaine(expression,index_symbole(expression,"/")) return evalue_expression(e1)/evalue_expression(e2) return float(expression) print(evalue_expression("2*5+4")) # doit renvoyer 14 print(evalue_expression("5/2-1")) # doit renvoyer 1.5 print(evalue_expression("2*5.2+6.6-2/4")) # doit renvoyer 16.5 ## Question 10 : Prise en compte des parenthèses def index_symbole_hors_parentheses(chaine:str,symbole:str)->int: assert len(symbole)==1, "Le symbole ne doit contenir qu'un seul caractère" nbp=0 # nb de parethèses ouvertes for i in range(len(chaine)): if chaine[i]=="(": nbp=nbp+1 if chaine[i]==")": nbp=nbp-1 if nbp<0: raise(ValueError("Parenthèse non ouverte")) if nbp==0 and chaine[i]==symbole: return i if nbp>0: raise(ValueError("Parenthèse non fermée")) return -1 print(index_symbole_hors_parentheses("2*(3-4)-5","-")) # doit renvoyer 7 print(index_symbole_hors_parentheses("2.5*((4+3*2)+4/2.1)+6","+")) # doit renvoyer 19 ## Question 11 : Évaluation d'une expression avec parenthèses def evalue_expression(expression): if expression[0]=="(": if expression[len(expression)-1]==")": return evalue_expression(expression[1:len(expression)-1]) else: raise(ValueError("Problème de parenthèses")) if index_symbole_hors_parentheses(expression,"+")!=-1: e1,e2=decoupe_chaine(expression,index_symbole_hors_parentheses(expression,"+")) return evalue_expression(e1)+evalue_expression(e2) if index_symbole_hors_parentheses(expression,"-")!=-1: e1,e2=decoupe_chaine(expression,index_symbole_hors_parentheses(expression,"-")) return evalue_expression(e1)-evalue_expression(e2) if index_symbole_hors_parentheses(expression,"*")!=-1: e1,e2=decoupe_chaine(expression,index_symbole_hors_parentheses(expression,"*")) return evalue_expression(e1)*evalue_expression(e2) if index_symbole_hors_parentheses(expression,"/")!=-1: e1,e2=decoupe_chaine(expression,index_symbole_hors_parentheses(expression,"/")) return evalue_expression(e1)/evalue_expression(e2) return float(expression) print(evalue_expression("2*(3-4)-5")) # doit renvoyer -7 print(evalue_expression("2.5*((4+3*2)+4/2.1)+6")) # doit renvoyer 35,76... ### LES TOURS DE HANOÏ ### ## Question 12 def piquet_intermediaire(debut:int,fin:int): if debut!=1 and fin!=1: return 1 if debut!=2 and fin!=2: return 2 if debut!=3 and fin!=3: return 3 # remarque: il existe aussi une formule magique: return 6-debut-fin print(piquet_intermediaire(1,3)) ## Question 13 def transporte_hanoi(debut:int,fin:int,nombre:int): if nombre==0: return else: inter=piquet_intermediaire(debut,fin) transporte_hanoi(debut,inter,nombre-1) print("On déplace le disque "+str(nombre)+" du piquet "+str(debut)+" vers "+str(fin)) transporte_hanoi(inter,fin,nombre-1) transporte_hanoi(1,3,5) ## Question 14 # soit N(n) le nombre d'opérations pour déplacer n disques # alors N(1)=1 et N(n+1)=N(n)+1+N(n)=2N(n)+1 # on montre alors facilement que N(n)=2^n-1 ## Question 15 def simule_hanoi(L:[int],debut:int,fin:int,nombre:int): if nombre==0: return else: inter=piquet_intermediaire(debut,fin) simule_hanoi(L,debut,inter,nombre-1) L[fin-1].append(L[debut-1].pop()) print(str(L[0])+(" "*(3*N-len(str(L[0]))))+str(L[1])+(" "*(3*N-len(str(L[1]))))+str(L[2])) simule_hanoi(L,inter,fin,nombre-1) disques=[[1,2,3,4,5],[],[]] # 5 disques sur le piquet 1, 0 ailleurs simule_hanoi(disques,1,3,N)