Votre question

Triangle de pascal

Tags :
  • Visual basic
  • Programmation
Dernière réponse : dans Programmation
14 Septembre 2005 17:00:44

Bonjour tout le monde. Donc j'ai un petit projet qui consiste à calculer une identité puissance n à l'aide du triangle de pascal. Donc j'ai essayé de coder ça mais je ne trouve pas d'algorythme, de méthode pour réaliser ceci.
Est ce que quelqu'un aurait une idée de par où commencer
PS : le langage est le Visual Basic

Je ne veux pas qu'on me fasse le code juste qu'on m'aide à trouver une méthode
Merci

Autres pages sur : triangle pascal

14 Septembre 2005 19:35:52

t'as un lien qui explique ce que c'est que le triangle de pascal ?
a b L Programmation
14 Septembre 2005 19:42:05

tu construis le triangle, c'est une fonction récursive:
u(i, j) = u(i-1, j-1) + u(i, j-1)
i étant la colonne et j la ligne, l'identité étant une ligne.
Contenus similaires
a b L Programmation
14 Septembre 2005 19:47:59

Citation :

bluedylc a écrit :
t'as un lien qui explique ce que c'est que le triangle de pascal ?


11
121
1331
14641
...[/font]
(a+b)²=a²+2ab+b²
(a+b)³=a³+3a²b+3ab²+a³
...
14 Septembre 2005 20:16:52

et tu vois pas comment coder ca ?

Personellement, en ocaml la solution me parait assez évidente (bon le ocaml est fort pour faire ca) mais je pense que c'est pareil en Visual Basic.

Tu fais une matrice, tu remplis le haut, et tu remplis ligne par ligne avec une boucle, en te servant de la ligne du dessus. Tchac Tchac.

Pour m'exercer, voilà un code impératif en ocaml qui fait ca :
  1. let pascal = Array.init nb_lignes (fun ligne -> Array.create (ligne+1) 1) in (* on cree le triangle avec 1 comme valeur par defaut*)
  2.  
  3.  
  4. for ligne = 1 to nb_lignes-1 do
  5. for colonne = 1 to (ligne-1) do
  6. pascal.(ligne).(colonne) <- pascal.(ligne-1).(colonne-1) + pascal.(ligne-1).(colonne) (* on ajoute les deux cases au dessus pour avoir la case *)
  7. done
  8. done;
  9.  
  10. Array.iter (fun tab -> Array.iter print_int tab; print_newline()) pascal;; (* on affiche le résultat *)


la version fonctionnelle devrait suivre.
a b L Programmation
14 Septembre 2005 20:27:59

Citation :

bluedylc a écrit :
et tu vois pas comment coder ca ?

Personellement, en ocaml la solution me parait assez évidente (bon le ocaml est fort pour faire ca) mais je pense que c'est pareil en Visual Basic.

Tu fais une matrice, tu remplis le haut, et tu remplis ligne par ligne avec une boucle, en te servant de la ligne du dessus. Tchac Tchac.

oui et même plus simple sans matrice, 2 lignes suffisent (la ligne en cours de traitement et la ligne précédente)
sinon en ocaml, on peut aussi calculer le résultat directement avec les combinaisons:
u(i,j) = combinaison(j, i) = j! / (i! (j-i)!)
= (j*(j-1)*...*1)/((i*(i-1)*...*1)((j-i)*(j-i-1)*...*1))

14 Septembre 2005 20:58:05

J'avoue que je ne comprend pas ton exemple de combinaisons. ! désigne une factorielle ? Si oui, on dirait que je ne suis pas au courant des rapports entre ce triangle et les factorielles.

Voici cependant une version fonctionnelle "bêta (sans utiliser d'astuces mathématiques tenant des propriétés du triangle non connues de ma part)" (je me suis bien cassé le cul pour la pondre, celle-là) :
  1. let rec pascal = function
  2. 0 -> [[]]
  3. | num_ligne ->
  4. let rec nouvelle_ligne = function
  5. | [1] | [] -> [1]
  6. | tete1::(tete2::_ as queue) ->
  7. (tete1 + tete2) :: (nouvelle_ligne queue)
  8. | _ -> raise Exit (*cas impossible*)
  9. in
  10. let lignes_precedentes = pascal (num_ligne-1) in
  11. (1::(nouvelle_ligne (List.hd lignes_precedentes)))::lignes_precedentes
  12. in
  13.  
  14. List.iter (fun liste -> List.iter print_int liste; print_newline()) (List.rev (pascal (read_int())));;
a b L Programmation
14 Septembre 2005 21:34:46

Le ! est bien la fonction factorielle.
combinaisons et arrangement sont tirés des problas.
le choix de i boules dans une urne qui en contient j.
Le nombre de possibilités si on les tire de façon ordonnée: j*(j-1)*...*(j-i) (une fois qu'on a tiré une boule il y en a une de moins à tirer)
ça c'est le nombre de tirages ordonné, c'est l'arrangement(i,j): j! / (j-i)! puisque (j-i)! = (j-i)*(j-i-1)*...*1

Ensuite si on veut calculer le nombre de tirage sans ordre précis (c'est a dire que toutes les permutation représente en fait le même tirage), il faut enlever toutes les permutations possibles.
Le nombre de permutation c'est parait c'est le choix de n boules parmi n boules dans un ordre précis, soit n*(n-1)*...*1 = n!

donc le nombre tirage de i boules parmi n distinctes sans ordre précis (on les tirent toutes d'un coup) et de j! /((j-i)! i!) et ça ça s'appelle combinaison(i, j)

après il s'avère que c'est la même combinaison pour calculer le triangle de pascal.
Bref tout ça pour dire qu'en ocaml, il y a certainement une fonction qui calcule directement la combinaison :-D
14 Septembre 2005 22:28:05

mais le triangle de pascal est composé de plusieurs (nombreux) nombres. Comment une seule formule (que je comprend mieux maintenant) peut-elle le représenter ?
(et surtout, aurais-tu une explication (de toi, d'un article, etc.) sur le lien entre le nombre de tirages aléatoires sans considérations d'ordre et le 'calcul du triangle de pascal') ?
a b L Programmation
14 Septembre 2005 23:49:17

dans le tableau du triangle de pascal, la valeur situé à la colonne i et à la ligne j correspond à Combinaison (i, j) donc tu boucles sur i et sur j et tu remplis le tableau.

Le rapport, il n'y en a pas vraiment (enfin je pense pas), c'est juste une coïncidence: un même modèle mathématique pour 2 applications différentes.
http://www.mjc-andre.org/pages/amej/glossair/entrees/binome_f.html
15 Septembre 2005 00:23:06

en meme temps, caculer trois factorielles et faire une division, c'est plus lent (beaucoup plus lent) que lire deux cases du même tableau. L'intérêt est donc relativement limité.
a b L Programmation
15 Septembre 2005 00:41:33

pas forcément, car il n'y a pas de remplissage de tableau, en fait ça peut se calculer avec les produits j*(j-1)*..*(j-i) et i(i-1)...1 et une division: i+(j - (j - i))+1 flops soit i + j + 1 flops
le même calcul en récursif (le remplissage partiel du tableau demande 2 additions avec les 2 éléments de la ligne j-1 précédente) soit au total 2^j flops
Un flop étant une opération de base (addition multiplication)

A moins que je me sois trompé, dans un cas c'est linéaire, alors que dans l'autre c'est exponentiel: si i et j sont grand, la méthode des combinaisons est plus rapide.
Même si le produit est légèrement plus lent que l'addition, c'est proportionnel alors que la différence entre les 2 algos est exponentiel (toujours à éviter dans les algos ;-) )
15 Septembre 2005 14:25:56

euh, deux additions par case ca fait du 2*cases additions et pas du 2^cases additions, non ?

Plutot que de parler en flops, pourrais-tu parler la prochaine fois en utilisant la complexite algorithmique (O(n), Theta(n), Omega(n)) je pense que c' est plus comprehensible, car simplifie.
15 Septembre 2005 16:39:37

Huhu merci. effectivement je n'avais jamais travaillé sur le matrice et bien je vais m'y essayé bien le merci.
bluedylc -> je viens de l'apprendre en seconde et je vais essayer de faire un prog pour calculer automatiquement tout le tableau
a b L Programmation
19 Septembre 2005 22:09:13

Citation :

bluedylc a écrit :
euh, deux additions par case ca fait du 2*cases additions et pas du 2^cases additions, non ?

Plutot que de parler en flops, pourrais-tu parler la prochaine fois en utilisant la complexite algorithmique (O(n), Theta(n), Omega(n)) je pense que c' est plus comprehensible, car simplifie.

exact, je me suis trompé, ce n'est pas 2^j mais bien 2 fois le nombre de cases soit environ 2 * 1/2 * (i * j) soit i * j additions.

Là on ne peut pas parler de O(n) puisqu'il y 2 paramètres (ligne et colonne)
si on prend la ligne = colonne, on n'a que n et donc:
le remplissage de la matrice est en n² + O(n)
et avec les calculs des combinaisons pour une seule valeur n + O(n)
Avec la technique du remplissage, on est obligé de calculer les autres valeurs pour en trouver une (c'est là qu'on y gagne).

maintenant si on veut récupérer toutes les valeurs, le tien est de n² + O(n) et celui avec les combinaisons est de n³ + O(n)

Donc en fait le remplissage de la matrice est plus optimisée si l'on recherche plusieurs valeurs, et celui est combinaison l'est plus si l'on ne recherche qu'une seule valeur
Tom's guide dans le monde
  • Allemagne
  • Italie
  • Irlande
  • Royaume Uni
  • Etats Unis
Suivre Tom's Guide
Inscrivez-vous à la Newsletter
  • ajouter à twitter
  • ajouter à facebook
  • ajouter un flux RSS