ntro.ca

        • Contrats de classe
        • Liens utiles
        • Calendrier
        • Calendrier groupe 2
        • Calendrier groupes 1, 3
        • Structure du cours
        • Évaluations
        • Matériel à se procurer
        • Les profs
          • Marc-Olivier Tremblay
          • Mathieu Bergeron
        • Module 1.1: installation + trier des cartes
        • Module 1.2: rappels POO
        • Module 1.3: tableau d'objets
        • Examen 1
        • Module 2.1: données JSON
        • Module 2.2: données en Java
        • Module 2.3: récursivité
        • Examen 2
        • Module 3.1: structure générique
        • Module 3.2: efficacité (1)
        • Module 3.3: efficacité (2)
        • Examen 3
        • Module 4.1: liste naïve
        • Module 4.2: liste par tableau
        • Module 4.3: liste chaînée
        • Examen 4
        • Module 5.1: mappage naïf
        • Module 5.2: mappage par hachage
        • Module 5.3: mappage par arbre
        • Examen 5
        • Équipes
          • Horaire groupe 1
          • Horaire groupe 2
          • Horaire groupe 3
          • Groupe 1
          • Groupe 2
          • Groupe 3
        • Projets vedettes 2022
        • Projets vedettes 2023
        • Projets vedettes 2024
        • Projets vedettes 2025
        • Survol
        • Structure
        • Calendrier
        • Calendrier des séances
        • Évaluations
        • Exemples de jeu
        • Exemples de pages
        • Réponses à vos questions
        • Module 1: créer le projet
        • Module 2: concevoir l'application
        • Module 3: vues NtroFx
        • Module 4: modèle et navigation
        • Module 5: ajouter le dorsal, modifier le modèle
        • Module 7: améliorer l'affichage
        • Module 8: jeu en 2d
        • Module 9: client/serveur
        • Module 10: plusieurs instances du même modèle
        • TP1
        • Examen 1
        • TP2
        • Examen 2
        • Projet de fin de session
        • Calendrier
        • Structure du cours
        • Évaluations
        • Contrat de classe
        • Le prof
        • 01: Windows et Word
          • Astuces et raccourcis
        • 02: Word
        • 03: Word
          • Exercice Word: insertion d'éléments spéciaux
          • Exercice Word: tableaux
        • 04: Word
          • Exercice Word: références
          • TP01: Word (15%)
        • 05: PowerPoint
          • TP02: PowerPoint (10%)
        • 06: Examen Word (20%)
        • 07: Excel
        • 08: Excel
        • 09: Excel
          • TP03: Excel (15%)
        • 10: Excel
        • 11: Examen Excel (20%)
        • 12: Access
        • 13: Access
        • 14: Access
        • 15: Examen Access
      • Sondage H2023 (dept. info)
      • Vision H2023 (dept. info)
      • P1) exercices interactifs de lecture
      • P2) transition Excel vers Python
        • Atelier 2: un exemple
      • Jquery
      • Jquery Ui
      • Point de vue sur l'IA
    Théorie 2.3: Fibonacci
    • Théorie 2.3: Fibonacci
      • Définition
      • Nombre d’or
      • Modéliser la suite de Fibonnaci
      • Pour calculer la réponse et le nombre d’or
      • Construire le graphe d’objets récursivement
      • Construire le graphe d’objets dynamiquement

    Théorie 2.3: Fibonacci #

    Définition #

    1. Voici le début de la suite de Fibonacci

      0 1 1 2 3 5 8 13 21 34 55 89 144 ...
      
    2. La définition mathématique est récursive

      \( F_0 = 0\\~\\ F_1 = 1\\~\\ F_n = F_{n-1} + F_{n-2}\\~\\ \)
    3. Autrement dit:

      • 0 et 1 sont deux cas spéciaux

      • sinon le prochain nombre de la suite est toujours l’addition deux nombres précédents

    Nombre d’or #

    1. La suite de Fibonacci est utilisée pour calculer le nombre d’or, soit environs 1.618

      • (le nombre d’or est reconnu, entre autres choses, comme une proportion hauteur/largeur agréable à l’oeil)
    2. Comme pour π, on peut le calculer le nombre d’or avec autant que précision que désiré

      • (c-à-d avec autant de chiffres après le point que désiré)
    3. Pour calculer un approximation du nombre d’or on fait tout simplement:

      \( \text{nombre d'or} \approx \dfrac{F_{n}}{F_{n-1}} \text{~~~pour~~~} n\geq 2 \)
    4. Plus on prend un n élevé, plus la précision est bonne

    5. Autrement dit, le nombre d’or est à peu près égal à:

      • un nombre de la suite de Fibonacci, divisé par le nombre qui le précède

      • (plus on prend un nombre loin dans la suite, plus l’approximation est bonne)

    Modéliser la suite de Fibonnaci #

    1. Pour modéliser la suite en Java, on va créer une structure de données récursive
    1. Pour n = 0, on a le graphe d’objets suivant

    2. Pour n = 1, on a le graphe d’objets suivant

    3. Pour n = 2, on a le graphe d’objets suivant

      • NOTE: la suite se lit de droite à gauche
    4. Pour n = 3, on a le graphe d’objets suivant

    5. Et ainsi de suite…

    Il existe une modélisation plus simple. Chut, ne le dis pas! C’est la question bonus de l’atelier 2.3.

    Pour calculer la réponse et le nombre d’or #

    1. Calculer la réponse pour n >= 2 est simple

      reponse = moinsUn.getReponse() + moinsDeux.getReponse();
      
    2. Même chose pour le nombre d’or

      nombreOr = Double.valueOf(reponse) / Double.valueOf(moinsUn.getReponse());
      
    3. Le défi est qu’il faut d’abord construire le graphe d’objet

    Construire le graphe d’objets récursivement #

    1. Avec des appels récursifs, on va construire d’abord, puis calculer

      • on crée d’abord l’objet n, puis n-1, et ainsi de suite jusqu’à l’objet 0
    2. Pour le cas n >= 2, voici comment procéder

      • créer un nouvel objet MonFibonacci et le mémoriser dans moinsUn

      • enregistrer que le n de ce moinsUn est n-1 (le n courant moins 1)

      • créer le reste du graphe récursivement en appelant moinsUn.construireGrapheRecursivement()

      • enregister que le moinsDeux courant est moinsUn.getMoinsUn() (le moinsUn du moinsUn courant)

      • calculer la réponse courante à partir des réponses de moinsUn et moinsDeux

    3. L’appel récursif est plus proche de la définition mathématique

      • (pour calculer la réponse en n, il faut d’abord calculer la réponse en n-1)
    4. L’inconvénient est qu’on peut déborder la pile d’appel

      Exception in thread "main" java.lang.StackOverflowError
          at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
          at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
          at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
          at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
          at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
          at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
          at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
          at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
          at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
          at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
          at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
          at ca.ntro.cards.fibonacci.solution.MonFibonacci.construireGrapheRecursivement(MonFibonacci.java:31)
          ...
      
      • RAPPEL: le code n’est pas bogué, mais limité par la mémoire attribuée à la pile d’appel

    Construire le graphe d’objets dynamiquement #

    1. En programmation dynamique, on calcule en même temps qu’on construit

      • on crée d’abord l’objet 0, puis 1, et ainsi de suite jusqu’à l’objet n
    2. L’idée est qu’on fait une boucle pour créer le graphe d’objets

      • on crée une nouvelleTete

      • le moinsUn de la nouvelleTete est l’ancienne tete

      • le moinsDeux de la nouvelleTete est le moinsUn de l’ancienne tete

      • c-à-d on insère la nouvelleTete à gauche, et on «pousse» les objets existants vers la droite

    3. Pour le cas n >= 2, voici comment procéder

      • pour chaque i allant de 2 à n (inclusivement)

        • créer un nouvel objet MonFibonacci pour représenter la nouvelleTete

        • enregistrer que le n de la nouvelleTete est i

        • enregistrer que le moinsUn de la nouvelleTete est la tete courante

        • enregistrer que le moinsDeux de la nouvelleTete est le moinsUn de la tete courante

        • enregistrer que tete pointe maintenant vers la nouvelleTete

        • calculer la réponse pour tete

    4. Le calcul dynamique est moins intuitif (et moins proche de la définition mathématique), mais

      • on a éliminé l’appel récursif, alors on ne peut plus déborder la pile d’appel
    Creative Commons License Creative Commons Attribution Creative Commons ShareAlike
    • Théorie 2.3: Fibonacci
      • Définition
      • Nombre d’or
      • Modéliser la suite de Fibonnaci
      • Pour calculer la réponse et le nombre d’or
      • Construire le graphe d’objets récursivement
      • Construire le graphe d’objets dynamiquement