Exercice 18

Je ne comprends pas la résolution...si quelqu'un peut m'éclairer...

merchi beaucoup

Un triangle de pascal ressemble à ça :



La case au sommet vaut 1 et la valeur de chaque case vaut la somme de la case du dessus et de la case en haut à gauche, donc à priori on peut écrire :

Code:

if(i == 0 and j == 0):
      res = 1
else:
      res = triangle_pascal(i-1,j) + triangle_pascal(i-1,j-1)

Seulement ça ne suffit pas, car si on demande à ta fonction la valeur d'une case, elle va regarder (entre autres) la case du dessus, puis celle encore au dessus, etc ... et ne va jamais rien trouver, puisque le seul truc qu'on lui a indiqué c'est la case en (0,0)

C'est pour ça qu'on rajoute un ligne de zéros sur la ligne -1 (au dessus du triangle) avec :

Code:

elif((i == (-1)) or (j > i)):
      res = 0

Comme ça la récursion s'arrêtera une fois que la fonction regardera une case à la ligne -1 (elles valent toutes 0)
(Je pense pas que le j > i soit obligatoire, ça stoppe juste la boucle un peu plus tôt et ça demande moins de calculs pour le même résultat)

Benjamin a écrit:

Code:

elif((i == (-1)) or (j > i)):
      res = 0

Comme ça la récursion s'arrêtera une fois que la fonction regardera une case à la ligne -1 (elles valent toutes 0)
(Je pense pas que le j > i soit obligatoire, ça stoppe juste la boucle un peu plus tôt et ça demande moins de calculs pour le même résultat)

je comprends pas pq i==-1 et justement je pense que j>i c'est le plus important vu que ca concerne tout ce quil y a au dessus de la diagonale,...nn?

Chaque fois que la fonction s'appelle elle même, elle regarde à la ligne au dessus, donc pour éviter que la fonction s'appelle à l'infini sans jamais renvoyer de valeur, on lui dit de renvoyer zéro quand elle atteint la ligne -1 (sur le schéma de mon 1er post, c'est la ligne au dessus de la 1re valeur).

Le j > i fera que la fonction renverra 0 si elle passe au dessus de la diagonale. Si on le retire, la fonction remontera encore jusqu'à la ligne -1, qui renverra également 0. (au pire tu peux essayer de le retirer, on verra bien si la fonction marche encore ou pas)

est-ce qu´on pourrait aussi dire i < 0 au lieu de i==(-1) ??