GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.

====== Meilleur parcours dans une grille (variante dynamique) ======

<WRAP box>Il est question ici de l'exercice 2 du {{ .:sujet_0.pdf |sujet 0}} de l'épreuve terminale de NSI. Dans le sujet, on aborde le problème à la façon de la programmation dynamique. Mais, à la dernière question, on implémente en utilisant une récurrence ce qui n'est pas la meilleure façon de faire. On tente ici l'approche dynamique.</WRAP>

<WRAP info>Je reprends les premières questions à l'identique</WRAP>

==== Présentation ====
{{page>.:exercice_2#Présentation&nofooter&noheader}}

==== Question 1 ====
{{page>.:exercice_2#Question 1&nofooter&noheader}}

==== Question 2 ====
{{page>.:exercice_2#Question 2&nofooter&noheader}}

==== Question 3 ====
{{page>.:exercice_2#Question 3&nofooter&noheader}}

==== Question 4 ====
{{page>.:exercice_2#Question 4&nofooter&noheader}}

==== Question 5 ====

<WRAP info>Changement ici : on va utiliser la programmation dynamique au lieu de la récursivité. Le sujet évoque un tableau ''%%T'%%'' qui sert à l'explication mais n'est pas utilisé dans la version récursive. Nous devons maintenant créer ce tableau. Mais nous ne pouvons pas l'appeler ''%%T'%%''... Nous l'appellerons ''T2''.</WRAP>

Écrire une fonction ''%%somme_max(T)%%'' qui :
  - initialise ''T2'' aux mêmes dimensions que ''T'', rempli de ''0'',
  - initialise ''T2[0][0]'',
  - initialise la première ligne de ''T2'',
  - initialise la première colonne de ''T2'',
  - parcours les ''%%T2[i][j]%%'' pour ''%%1 <= i < n%%'' et ''%%1 <= j < p%%'' et les complète,
  - renvoie le contenu de ''%%T2[n-1][p-1]%%''.