07 Fonctions Recursives Aut 2012

  • Published on
    18-Oct-2015

  • View
    32

  • Download
    0

Transcript

  • 11

    Programmation en C++ sous LinuxMaster MSI, Automne 2012

    Prof Abdelaziz Bouroumi

    07. Fonctions rcursives

    Prof. Abdelaziz Bouroumia.bouroumi@gmail.com

    20/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumi

    2

    07. Fonctions rcursives

    07. Fonctions rcursives20/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumi

  • 233

    Rcursivit

    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 fonction

    qui sappelle elle-mme

    07. Fonctions rcursives

    qui 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/2013

    44

    Exemples simples

    1.// fact(n)=1*2**(n-1)*nunsigned long fact(unsigned short n) {unsigned long fact(unsigned short n) {return n

  • 35

    Autre exemple classique

    http://fr.wikipedia.org/wiki/Tours_de_Hano

    Si n=1 dplacer le disque directement de A C;i {

    A B C

    07. Fonctions rcursivesC++ sous Linux, Master MSI, 2013 A. Bouroumi

    Sinon {dplacer n-1 disques de A B;dplacer le disque restant de A C;dplacer les n-1 disques de B C;

    }20/01/2013

    6

    Cas de 3 disques (7 dplacements)

    07. Fonctions rcursivesC++ sous Linux, Master MSI, 2013 A. Bouroumi20/01/2013

  • 47

    4 disques (au moins 15 dplacements)

    h // iki di / iki/I T f H i 4 if

    07. Fonctions rcursivesC++ sous Linux, Master MSI, 2013 A. Bouroumi

    http://commons.wikimedia.org/wiki/Image:Tower_of_Hanoi_4.gif

    20/01/2013

    8

    Fonctionnement des appels rcursifs

    cout

  • 599

    Rcursivit 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 d

    07. Fonctions rcursives

    la lisibilit et llgance du code, lefficacit, la facilit de maintenance.

    20/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumi

    1010

    Exemple 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);cout

  • 61111

    Mauvaise rcursivit

    // testFibo.cpp (Janvier 2013)#include "masterTools.hpp" unsigned n;int main(int argc, char* argv[]) {// Programme paramtrif(argc!=2) {cout

  • 71313

    Complexit 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 la

    07. Fonctions rcursives

    ncessite 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. Bouroumi

    1414

    Complexit de la fonction fibo

    Equation de rcurrence: La redondance des traitements suggre une

    )1()2()( += nTnTnTgg

    complexit exponentielle. En posant , lquation devient: Do:

    nnT =)( 12 += nnn 012 =

    + 51

    07. Fonctions rcursives

    ==

    =+=

    )(2

    51

    )(or d' nombre 2

    51

    2

    1

    20/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumi

  • 81515

    Solution de lquation de rcurrence

    , avecnn BAnT 21)( += =+= 0)0( BAT 1BA

    =+=+

    0)1(0)0(

    21 BATBAT

    5== BA

    nnnnT 6.12

    512

    515

    1)(

    +=

    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 sicles

    20/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumi

    1616

    Programmation 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. Bouroumi

    unsigned int t[n]; t[0]=0; t[1]=1;for(int i=2;i

  • 91717

    Exercice

    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. Bouroumi

    1818

    Exemple des tours de Hano

    Hanoi(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. Bouroumi

    cinTnT ii )12()(2)( +=ccTnT nn += 11 2)1(2)(

    )2()12()( nn OcnT ==

  • 10

    19

    Autre mthode de rsolution

    07. Fonctions rcursives20/01/2013 C++ sous Linux, Master MSI, 2013 A. Bouroumi

    2020

    Exercices

    1. 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 rcursives

    3. 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