07 Fonctions Recursives Aut 2012

  • Published on
    18-Oct-2015

  • View
    32

  • Download
    0

Transcript

11Programmation en C++ sous LinuxMaster MSI, Automne 2012Prof Abdelaziz Bouroumi07. Fonctions rcursivesProf. Abdelaziz Bouroumia.bouroumi@gmail.com20/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumi207. Fonctions rcursives07. Fonctions rcursives20/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumi233Rcursivit Moyen simple et efficace de programmer, de faon lgante, des tches quon peut successivement diviser en: Une tche quon sait raliser (cas de base), et Une ou plusieurs autres tches qui se dfinissent de la mme faon que la tche initiale. Une fonction rcursive est une fonctionqui sappelle elle-mme07. Fonctions rcursivesqui s appelle elle-mme. Cest un cas particulier dapplication de la technique "diviser pour mieux rgner" surlaquelle repose la PS.C++ sous Linux, Master MSI, 2013 A. Bouroumi20/01/201344Exemples simples1.// fact(n)=1*2**(n-1)*nunsigned long fact(unsigned short n) {unsigned long fact(unsigned short n) {return n35Autre exemple classiquehttp://fr.wikipedia.org/wiki/Tours_de_HanoSi n=1 dplacer le disque directement de A C;i {A B C07. Fonctions rcursivesC++ sous Linux, Master MSI, 2013 A. BouroumiSinon {dplacer n-1 disques de A B;dplacer le disque restant de A C;dplacer les n-1 disques de B C;}20/01/20136Cas de 3 disques (7 dplacements)07. Fonctions rcursivesC++ sous Linux, Master MSI, 2013 A. Bouroumi20/01/2013474 disques (au moins 15 dplacements)h // iki di / iki/I T f H i 4 if07. Fonctions rcursivesC++ sous Linux, Master MSI, 2013 A. Bouroumihttp://commons.wikimedia.org/wiki/Image:Tower_of_Hanoi_4.gif20/01/20138Fonctionnement des appels rcursifscout599Rcursivit et rptitions Thoriquement, tout ce quon peut programmer laide dune structure itrative peut ltre moyennant la rcursivit t i tet inversement. Pratiquement, le choix entre la rcursivit et les structures itratives doit tre fait en se basant sur des critres comme: la complexit spatiale (mmoire) et temporelle (temps dexcution) de lalgorithme, l li ibilit t ll d d07. Fonctions rcursives la lisibilit et llgance du code, lefficacit, la facilit de maintenance.20/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumi1010Exemple des tours de Hano// Hano1, version rcursivevoid Hanoi1(int n, int a, int b, int c){if(n){Hanoi1(n-1 a c b);Hanoi1(n-1,a,c,b);cout61111Mauvaise rcursivit// testFibo.cpp (Janvier 2013)#include "masterTools.hpp" unsigned n;int main(int argc, char* argv[]) {// Programme paramtrif(argc!=2) {cout71313Complexit de la fonction fibo La complexit dun algorithme, ou du code qui limplmente, se mesure par lordre de grandeur du de la fonction T(n) qui traduit la variation du temps dexcution T en fonction de la taille des donnes (ici le nombre n). Dans le cas dalgorithmes rcursifs, ce calcul ncessite deux tapes: ltablissement puis la07. Fonctions rcursivesncessite deux tapes: l tablissement puis la rsolution de lquation de rcurrence qui traduit la faon dont lalgorithme utilise la technique diviser pour rgner. 20/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumi1414Complexit de la fonction fibo Equation de rcurrence: La redondance des traitements suggre une )1()2()( += nTnTnTggcomplexit exponentielle. En posant , lquation devient: Do: nnT =)( 12 += nnn 012 = + 5107. Fonctions rcursives===+=)(251)(or d' nombre 2512120/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumi81515Solution de lquation de rcurrence , avecnn BAnT 21)( += =+= 0)0( BAT 1BA=+=+0)1(0)0(21 BATBAT5== BA nnnnT 6.125125151)( +=07. Fonctions rcursives Combien de temps faudrait-il pour calculer fibo(100) sur une machine qui ralise 109 oprations par seconde? T(100)=1.6100/109/60/60/24/30/12/100=83 sicles20/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumi1616Programmation dynamique Existe-t-il de mthode plus efficace pour calculer fibo(n)? La programmation dynamique est une technique de conception dalgorithmes qui vise sacrifier la mmoire pour gagner en temps dexcution. Pour cela, on mmorise les calculs intermdiaires au lieu de les refaire.unsigned int fibo2(int n) {07. Fonctions rcursives20/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumiunsigned int t[n]; t[0]=0; t[1]=1;for(int i=2;i91717Exercice Ecrire une version de la fonction fibo qui ne conserve en RAM que les deux derniers termes calculs de la suite de Fibonacci. Ecrire un programme de test de cette fonction.07. Fonctions rcursives20/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumi1818Exemple des tours de HanoHanoi(n,a,c,b)=Hanoi(n-1,a,b,c)+Hanoi(1,a,c,b)+Hanoi(n-1,b,c,a) Equation de rcurrence: )1()1(2)( TnTnT +==== ccteOT )1()1(cnTnTcnTnT 3)2(4)()2(2)1( +=+=cnTnTcnTnT 7)3(8)()3(2)2( +=+=cnTnTcnTnT 15)4(16)()4(2)3( +=+=07. Fonctions rcursives Gnralisation: Cas de base: n-i=1 20/01/2013 C++ sous Linux, Master MSI, 2013 A. BouroumicinTnT ii )12()(2)( +=ccTnT nn += 11 2)1(2)()2()12()( nn OcnT ==1019Autre mthode de rsolution07. Fonctions rcursives20/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumi2020Exercices1. En supposant que chaque dplacement lmentaire de disque demande une seconde, combien de temps faut-il pour dplacer 32 disques?2. Calculer le temps qui nous spare de la fin du monde selon la lgende des tours de Hano (lorsque 64 disques seront dplacs de la tour A vers la tour C) en supposant que chaque dplacement demande une seconde.annesanness 08.13812/30/24/60/60/22 3232 ==07. Fonctions rcursives3. Existe-t-il de mthode plus efficace pour rsoudre le problme des tours de Hano?4. Peut-on savoir sil est possible de trouver une mthode plus efficace?20/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumi