Résumé du cours : La programmation et la récursivité

Sujet : Bac 2021, Exercice 2

Introduction

• Exercice sur la programmation (en général) et la récursivité (en particulier).
• Travail sur un tableau de dimensions n lignes et p colonnes.
• Les lignes et colonnes sont numérotées respectivement de 0 à n-1 et 0 à p-1.
• Repérage de la case en haut à gauche par (0, 0) et celle en bas à droite par (n-1, p-1).

Déplacement et Chemin

• Déplacements autorisés : vers la droite et vers le bas (pas de déplacement en diagonale).
• La somme d’un chemin est la somme des entiers situés sur ce chemin.
• Objectif : déterminer la somme maximale pour tous les chemins possibles allant de (0, 0) à (n-1, p-1).

Mise en Place

Q1-1 : Déplacements vers le bas

• Question : Pour aller de (0, 0) à (2, 3) avec 3 déplacements vers la droite, combien de déplacements vers le bas ?
• Réponse : 2 déplacements vers le bas.

Q1-2 : Longueur des chemins

• Question : Justifier que tous les chemins de (0, 0) à (2, 3) ont une longueur égale à 6.
• Réponse :
  • 3 déplacements vers la droite + 2 vers le bas + 1 case de départ.
  • Total : 3+2+1 = 6.

Q2 : Déterminer la somme maximale

• Étape 1 : Lister tous les chemins possibles de (0, 0) à (2, 3).
• Étape 2 : Calculer la somme des valeurs sur chaque chemin.
• Exemple de chemins :
  1. (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,3)
  2. (0,0) -> (0,1) -> (1,1) -> (1,2) -> (2,2) -> (2,3)
  3. etc.
• Somme maximale trouvée : 16 pour le chemin (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (2,3).