Le triangle de Pascal en C#

[invitedd654e81]

Bonsoir, j'essaye en ce moment de comprendre comment faire pour générer le triangle de Pascal sur Visual Studio C# mais je n'y arrive pas vraiment.
Donc voici mon programme (attention je suis un débutant donc vous pourriez être choqués) :

           
 for (int i = 0; i <= 19; i +=1) {               
                for (int w = (i+1); w <= 19; w += 1) {
                    Console.WriteLine(i + " " +  w + " " + i);
                }
            }

Donc voilà, pour les 2 premières lignes ça va, mais ensuite ça dégringole. Mais je pense que si vous me filiez le truc je pourrais y arriver (sans me donner la réponse trop facilement hein)

Merci d'avance pour votre aide
-----

[invitea0ecda6e]

Perso en essayant ton code j'ai:

0 1 0
0 2 0
...
0 19 0
1 2 1
...

Ce qui parait tout à fait logique à la vue de ton code.
La 2eme ligne te parait correcte ?

Est-ce que tu peux essayer d'écrire concrètement ce que tu veux obtenir en résultat ?

[invitedd654e81]

Comme résultat je veux obtenir les 19 premières lignes du triangle de Pascal (d'où le i <= 19) et pour la deuxième ligne je me suis trompé c'était avec un autre essai, d'ailleurs je le poste parce qu'il avait l'air meilleur :

            
for (int i = 1; i <= 19; i += 1) {
                Console.WriteLine((i-1) + " " + i + " " + (i-1));
            }

Pour être plus précis, je veux que les 0 n'apparaissent pas (pour ma première ligne par exemple je voudrais les faire disparaître) et que le triangle soit aligné à gauche avec un espace de 4 entre chaque nombre le long d'une ligne. Donc on aurait au final un triangle rectangle qui décrit les 19 premières lignes du triangle de Pascal.

[invitea0ecda6e]

Ton code est forcement faux puisque tu n'écris les nombres qu'en fonction du numero de ligne...

Un algo trouvé sur wikipedia (trop facile me direz vous):

n ← 10    (* n est inférieur ou égal à la taille X utilisée dans le tableau c *)
c[0][0] ← 1

pour i de 1 à n faire
     c[i][0] ← 1
     pour j de 1 à i faire
          c[i][j] ← c[i-1][j-1] + c[i-1][j]
     finpour
     c[i][i] ← 1
finpour

A toi de jouer, j'espère que je ne donne pas la réponse trop facilement

[A voir en vidéo sur Futura]

[invitea0ecda6e]

Au fait, ça pourra aussi t'aider: http://forums.futura-sciences.com/pr...de-pascal.html

[invitedd654e81]

Oui je l'avais déjà vu cet algorithme de Wikipédia mais il n'est pas dans mon langage et mon professeur avait mentionné l'utilisation de tableau à une dimension (j'ai essayé de faire ça et je me retrouve au même point). Le tout devrait se faire en 10 lignes incluant les tabulations (Ma classe n'a pas été graciée de la correction du prof non plus, bien que le sujet se retrouve à l'examen). En regardant le topic en java je comprends que les programmeurs utilisent les tableaux, mais ceux-ci ne fonctionnent pas de la même manière sur C# :S J'essaye en ce moment de comprendre ce qu'ils écrivent (Je suppose que System.out.print est semblable au ConsoleWriteLine de C# ?) mais le "t[i][j]" et compagnie c'est du chinois pour moi.

Je continue à bosser là dessus en attendant du renfort

[Jack]

mais le "t[i][j]" et compagnie c'est du chinois pour moi

A priori, il suffit de remplacer la notation java t[i][j] par la notation C# t[i,j] pour les tableaux à 2 dimensons.

A+

[invite4492c379]

Hello Youssef,
En espérant que le problème sur l'autre fil est résolu, pourrais-tu me donner une formule qui calcule le coefficient (écrivons le c[n][p]) de la ligne n à la colonne p ?

[invitedd654e81]

Hein ? Non, je n'ai pas vu les tableaux à 2 dimensions encore, on en est qu'aux tableaux à 1-D. Je préfère en rester aux notions que j'ai vues car c'est ce qui va se trouver à mon examen.

[invite4492c379]

Peux te me donner une formule qui donne le coefficient de la ligne n à la colonne p ?
Je te demande ça car c'est à partir de cette formule que tu vas pouvoir construire un programme qui fonctionne.
Faire du copier coller ne t'apprendra rien. Il faut déjà maitriser les bases ... boucles, conditionnelles, bloc d'instructions, fonctions, variables et paramètres ... mais avant tout ça il faut comprendre comment on passe de c(n,p)=.... à un algo puis à un programme.
Ce genre d'exercice est classique à plusieurs niveau.

[invitedd654e81]

Nous on a pas ça (pas encore en tout cas) mais un ami vient de m'envoyer une soluce et il y a déjà pas mal de trucs qu'on avait pas vu en classe dedans. Je maîtrise tout ce qui va jusqu'aux tableaux 1-D, après le coefficient ligne-colonne j'ai jamais vu donc c'est pour après (et il n'est pas nécessaire de l'employer pour que le programme fonctionne):

public static void AfficherTriangleDePascal(int nbLignes){
            if (nbLignes < 1 || nbLignes >= 21 ) 
                Environment.Exit(1); // Erreur: On termine le programme.
            Console.WriteLine("Voici les {0} premières lignes du Triangle de Pascal", nbLignes);            
            int[] ligne = new int[20];  
            ligne[0] = 1;
            for(int i = 1 ; i <= nbLignes ; i += 1) {
                for(int j = 0; j < i ; j += 1) Console.Write("{0,6}", ligne[j]);
                Console.WriteLine();
                for(int j = i; j > 0 ; j--) ligne[j] += ligne[j-1];
            } // fin for
            Console.WriteLine();
        } // fin méthode AfficherTriangleDePascal(int)

Donc voila, en fait il fallait utiliser une fonction de lignes à laquelle je n'avait pas du tout pensé. Est-ce que quelqu'un pourrait m'expliquer la ligne que j'ai mise en gras souligné s.v.p ?

[Jack]

Les nouveaux coefficients sont calculés à partir des anciens, à savoir que chaque nouveau coefficient est égal à la somme du coefficient de même rang et de celui de rang immédiatement inférieur (c'est le principe du triangle de Pascal).
On est obligé de calculer les nouveaux coefficients de droite à gauche afin de ne pas écraser les anciens au cours du calcul.

Je te conseille de prendre une feuille de papier un crayon et une gomme, et d'écrire l'évolution des variables et des données du tableau au fur et à mesure de l'exécution du programme, ligne par ligne donc.

A+

[invitedd654e81]

for(int j = i; j > 0 ; j--) ligne[j] += ligne[j-1];
qu'est-ce que cela veut dire ?
quelqu'un peut m'expliquer cette ligne s.v.p ? Je sais comment fonctionne le triangle de Pascal en maths, inutile de compliquer les choses.

[invite4492c379]

OK. Ce n'est pas pour compliquer les choses, mais comment veux-tu écrire un algo et à défaut un programme qui calcule les coefficients binomiaux si tu ne sais pas ce que c'est.

Le triangle de pascal est :

p 0     1     2     3     4     5

n
0 1
1 1     1
2 1     2     1
3 1     3     3     1
4 1     4     6     4     1
5 1     5    10    10     5      1
...

Les coef à calculer sont ceux en gras. On les nomme généralement c(n,p) où n est la ligne et p la colonne.
Une définition simple est :


Cela signifie que pour calculer un coef tu ajoutes celui qui est au-dessus de lui et celui qui est en haut à gauche de lui. Par exemple c(4,3)=c(3,2) + c(3,3) = 1 (au-dessus) + 3 (au-dessus à gauche).

Plusieurs remaques :
1. ça commence toujours par un 1
2. ça finit toujours par un 1
3. c'est symétrique c(n,p)=c(n,n-p)
4. pour calculer la ligne n tu n'as besoin que de connaître les valeurs de la ligne n-1
5. la ligne n contient n+1 coefficients

Imaginons maintenant que tu disposes d'un tableau L qui contient les n+1 valeurs des coef de la ligne n du triangle. Tu veux construire un tableau L' qui va contenir les n+2 coef de la ligne n+1.

Tu peux faire :

L'[0]=1 // remarque 1
pour i de 1 à n+1
  L'[i]=L[i] (au-dessus) + L[i-1] (au-dessus à gauche) // par définition
L'[n+2] = 1 // remarque 2

Ensuite tu peux essayer d'optimiser (ce qu'a fait ton ami) en considérant que tu n'as pas forcément besoin d'un second tableau mais que tu peux réécrire dans le même tableau. Mais si dans l'algo tu remplaces L' directement par L tu vas écraser des valeurs dont tu auras besoin. Prenons un exemple, tu as la ligne 2 et tu veux calculer la 3 :

L = {1,2,1}
L[0]=1, L={1,2,1}
L[1]=L[0]+L[1] = 1+2 = 3, L={1,3,1}
L[2]=L[1]+L[2] = 1+3 erreur car on aurait du utiliser l'ancienne valeur de L[1]
Une astuce consiste simplement à parcourir le tableau à partir de la fin :
L={1,2,1}
L[3]=1,L={1,2,1,1} // remarque 2
L[2]=L[1]+L[2]=2+1=3, L={1,2,3,1}
L[1]=L[0]+L[1]=1+2=3, L={1,3,3,1}
L[0]=1,L={1,3,3,1}

Et voilà

C'est exactement ce que fait la boucle de ton ami. Il parcourt la tableau à l'envers et ajoute à la cellule courante la précédente.

Le += est un opérateur affectation. Si tu rencontres a+=b, cela signifie la même chose que a=a+b (il y a aussi -=, *=, /=, %=, ...)

Une optimisation supplémentaire pourrait-être de considérer la remarque 3 ...
Tous les tableaux en C# ont une dimension, pour des tableaux d'ordre supérieurs on utilise des tableaux de tableaux.

[invitedd654e81]

for(int j = i; j > 0 ; j--) ligne[j] += ligne[j-1];
Il faut que je repose la question : Que veut dire cette ligne ? JUSTE cette ligne, rien d'autre. J'ai déjà compris ce que le programme faisait et comment.
Je veux juste comprendre cette ligne : for(int j = i; j > 0 ; j--) ligne[j] += ligne[j-1]; pour être capable de reproduire quelque chose de semblable.

pourquoi changer la valeur de j=0 en j=i ? Pourquoi j>0 et que se passerait-il si on mettait >= 0 par exemple ? ligne[j] += ligne[ j-1] signifie que j'ajoute la ligne précédant j à la ligne j, mais pourquoi est-ce qu'on additionne des lignes alors qu'on veut juste additionner des coefficients ?

Photon tu as écris ceci :

L = {1,2,1}
L[0]=1, L={1,2,1}
L[1]=L[0]+L[1] = 1+2 = 3, L={1,3,1}
L[2]=L[1]+L[2] = 1+3 erreur car on aurait du utiliser l'ancienne valeur de L[1]

Je ne comprends pas comment tu fais pour additionner tes lignes, je n'ai pas encore vu ça en cours donc peux-tu m'expliquer comment ça marche s.t.p ? L[0] = 1 j'ai compris ça veut dire que la valeur sur la première ligne est 1, mais ensuite tu mets L = {1,2,1} (La troisième ligne du triangle de Pascal) Mais d'où ça sort ? Et c'est quoi L tout seul ? (sans les [] avec un nombre dedans). Et pour L[1]=L[0]+L[1] = 1+2 = 3, L={1,3,1} c'est quoi {1,3,1} ? C'est même pas sur le triangle ça non ? et c'est quoi l'ancienne valeur de L[1] ? L[1] ça reste toujours 2 pourquoi est-ce que sa valeur changerait ? Et enfin comment est-ce que 1+2 = 3 devient ensuite L = {1,3,1} ?

[invite4492c379]

for(int j = i; j > 0 ; j--) ligne[j] += ligne[j-1];
Il faut que je repose la question : Que veut dire cette ligne ? JUSTE cette ligne, rien d'autre. J'ai déjà compris ce que le programme faisait et comment.
Je veux juste comprendre cette ligne : for(int j = i; j > 0 ; j--) ligne[j] += ligne[j-1]; pour être capable de reproduire quelque chose de semblable.

Comme je te l'ai dit :

C'est exactement ce que fait la boucle de ton ami. Il parcourt la tableau à l'envers et ajoute à la cellule courante la précédente.

Le += est un opérateur affectation. Si tu rencontres a+=b, cela signifie la même chose que a=a+b (il y a aussi -=, *=, /=, %=, ...)

pourquoi changer la valeur de j=0 en j=i ? Pourquoi j>0 et que se passerait-il si on mettait >= 0 par exemple ? ligne[j] += ligne[ j-1] signifie que j'ajoute la ligne précédant j à la ligne j, mais pourquoi est-ce qu'on additionne des lignes alors qu'on veut juste additionner des coefficients ?

Ligne est un tableau unidimensionnel, Ligne[j] est le coefficient à la colonne j de la ligne courante. Tu trouves cela en consultant le code de ton ami :

int[] ligne = new int[20];

ligne est de type tableau d'entiers (int[]) et pointe sur un espace mémoire qui pourra contenir 20 éléments (new int[20])

Photon tu as écris ceci :

L = {1,2,1}
L[0]=1, L={1,2,1}
L[1]=L[0]+L[1] = 1+2 = 3, L={1,3,1}
L[2]=L[1]+L[2] = 1+3 erreur car on aurait du utiliser l'ancienne valeur de L[1]

Je ne comprends pas comment tu fais pour additionner tes lignes, je n'ai pas encore vu ça en cours donc peux-tu m'expliquer comment ça marche s.t.p ? L[0] = 1 j'ai compris ça veut dire que la valeur sur la première ligne est 1, mais ensuite tu mets L = {1,2,1} (La troisième ligne du triangle de Pascal) Mais d'où ça sort ? Et c'est quoi L tout seul ? (sans les [] avec un nombre dedans). Et pour L[1]=L[0]+L[1] = 1+2 = 3, L={1,3,1} c'est quoi {1,3,1} ? C'est même pas sur le triangle ça non ? et c'est quoi l'ancienne valeur de L[1] ? L[1] ça reste toujours 2 pourquoi est-ce que sa valeur changerait ? Et enfin comment est-ce que 1+2 = 3 devient ensuite L = {1,3,1} ?

Je n´additionne jamais aucune ligne, le L={1,2,1} représente le contenu du tableau après la modification qui vient juste avant. Cela s'appelle une trace. C'est une démonstration que «ça plante si on parcourt le tableau du début à la fin» mais que «ça marche si on parcourt le tableau de la fin au début».

Si je peux essayer de te donner un conseil ... n'essaye pas de comprendre le code de ton ami (surtout qu'il y a une optimisation). Essaye déjà :

1. de construire un triangle à la main pour bien comprendre comment ça marche
2. ensuite regarde bien comment tu fais pour passer d'une ligne à une autre ... note ce que tu fais

Et au lieu d'essayer de comprendre un code optimisé que tu n'as pas écrit, essaye d'écrire ton propre code.
Je pense, àmha, qu'il est plus important de comprendre comment on passe de la définition mathématique au programme que d'essayer de comprendre l'astuce de ton ami.

[Jack]

pourquoi changer la valeur de j=0 en j=i ?

c'est pour calculer les coefficients de la gauche vers la droite, comme dit précédemment.

pourquoi changer la valeur de j=0 en j=i ? Pourquoi j>0 et que se passerait-il si on mettait >= 0 par exemple ? ligne[j] += ligne[ j-1] signifie que j'ajoute la ligne précédant j à la ligne j, mais pourquoi est-ce qu'on additionne des lignes alors qu'on veut juste additionner des coefficients ?

Comme je l'ai exprimé précédemment également, il suffit de faire l'effort de prendre du papier et un crayon. Mais comme tu le veux pas ...

[invitedd654e81]

Je n´additionne jamais aucune ligne, le L={1,2,1} représente le contenu du tableau après la modification qui vient juste avant. Cela s'appelle une trace. C'est une démonstration que «ça plante si on parcourt le tableau du début à la fin» mais que «ça marche si on parcourt le tableau de la fin au début».

Si je peux essayer de te donner un conseil ... n'essaye pas de comprendre le code de ton ami (surtout qu'il y a une optimisation). Essaye déjà :

1. de construire un triangle à la main pour bien comprendre comment ça marche
2. ensuite regarde bien comment tu fais pour passer d'une ligne à une autre ... note ce que tu fais

Et au lieu d'essayer de comprendre un code optimisé que tu n'as pas écrit, essaye d'écrire ton propre code.
Je pense, àmha, qu'il est plus important de comprendre comment on passe de la définition mathématique au programme que d'essayer de comprendre l'astuce de ton ami.

Ah ok voilà je pense avoir compris l'embrouille c'est que dans le code c'était écrit ligne[x] donc je pensais que ça désignait toute la ligne au lieu du coefficient de cette ligne. Je n'aurais pas pu écrire le code moi-même si on utilise des notions auxquelles je n'ai pas encore été introduit et le code c'est pas mon ami qui l'a fait, il l'a juste trouvé sur le net :P (Et ça je pense que mon prof en est conscient et qu'il voulait juste nous faire baver)
Je vois en général comment ça fonctionne, ça m'embrouille un peu l'histoire de la ligne du troisième for mais on a pas vu ces trucs en classe encore alors c'est pas grave.
Et Jack je sais comment fonctionne le triangle de Pascal, ma question c'était sur comment le faire sur C#, j'ai la version papier déjà.

Merci pour votre aide

[Jack]

Et Jack je sais comment fonctionne le triangle de Pascal, ma question c'était sur comment le faire sur C#, j'ai la version papier déjà.

Je te crois sur parole. Ce que je voulais juste dire, c'est que pour comprendre le fonctionnement d'une partie d'un programme, il faut parfois le faire manuellement pour voir comment évoluent les variables. C'est très formateur.
Après, lorsqu'on a compris l'algorithme, on peut le reproduire avec n'importe quel langage "classique".

Bonne chance pour la suite.

A+