Développeur du ( a +/- b ) ^ n

Soyez le premier à donner votre avis sur cette source.

Vue 2 764 fois - Téléchargée 230 fois

Description

Choisissez N et le signe dans la parenthèse
L'algorithme, que j'ai cherché en cours de maths (au moins ca occupe... et ca évite de dormir ) developpe de facon formel ... il n'utilise pas la méthode traditionnelle des Cnp, mais je dirai qu'en fait on pourrai retrovuer cet algo a partir du Cnp.

Cependant cet algo a quelques avantages par rapport à la méthode classique :

Il est RAPIDE:

La ou les factoriels utilise beaucoup de multiplication pour chaque terme, ma méthode en utilise seulement 4 :
un + un - un * un / (dans l'ordre d'execution je crois)

Il est PRECIS :

Avec le calcul des factoriels vous pouvez très vite dépasser la porté du type d'entier que vous utilisez avant de diviser par les autres factoriels...
Cette méthode utilise un entier qui ne devient jamais plus grand au cours des calcul (entre deux opérateurs le résultat est momentanement stocké ) que la valeur du coeff du milieu multiplier par (n/2). C'est une valeur aproximative ... j'ai jamais vraiment pris le temps de la calculer...

Enfin bref regardez le calcul... vous comprendrez (enfin j'espère :p )

Source / Exemple :


Dans le zip ...

Conclusion :


Pas de bug ( mais on sait jamais si vous en aver un fates le moi savoir ... )

Si vous ne vouler pas que le developpement saute des ligne, supprimer la premiere ligne SOUS la boucle For ...Next
Valaaaaaa !!!!

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
224
Date d'inscription
mercredi 21 avril 2004
Statut
Membre
Dernière intervention
29 mars 2009

La complexité (en mémoire comme en temps) est faible car on ne fait que des additions et tu dois savoir que cette opération est TRES peu coûteuse en temps (j'ai fait un algorithme de calcul sur des grands entiers et additioner deux nombrs de 10 000 chiffres est pour ainsi dire presqu'immédiat).

Pour ton algorithme, tu as raison je ne l'ai pas lu mais par contre je lis énormément de document sur le calcul formel et pour ce type de développement, la méthode que j'ai citée est considérer comme bonne (par des spécialistes donc un peu d'humilité de ta part serait bien venue), même si son intérêt est nulle.

Pour ton raisonnement, c'est évident mon "garçon" car : C(p) C(n;p)
n! / p! (n-p)!
n! / [p×(p-1)! (n- p+1)! / (n-p+1)]
n! / [p-1)! (n- p+1)!] × (n-p+1)/p
C(n;p-1) × (n-p+1)/p
C(p-1) × (n-p+1)/p

Au passage, tu fais une division et donc il faut sortir des entiers naturels à moins de programmer une division euclidienne.

Après avoir trouvée cette formule tu pourras maintenant la démontrer. De plus ton algorithme va être gourmand en temps pour des grands entiers. En effet, le coût d'un algorithme ne se mesure pas en simple nombre d'opérations arithmétiques : l'usage est de compter le nombre d'addition/soustraction/comparaison car ces opérations sont considérées de coût négligeable en temps.

PS : ma remarque était sans agressivité donc soit un peu zen et n'oublie pas que les livres sont faits pour être lus à moins que tu veuilles réinventer toutes les math. mais là je te souhaite bon courage. Vous êtes un peu agressif sur ce site c'est halucinant.

PS Bis : si tu as besoin d'info, n'hésites pas.
Messages postés
367
Date d'inscription
lundi 1 avril 2002
Statut
Membre
Dernière intervention
11 février 2010

J'ai oublié de préciser que je ne dois pas être le premier à avoir trouvé cette formule ...
Si kkun lui connait un nom, je suis preneur ... :-)
Bon coding all !
Messages postés
367
Date d'inscription
lundi 1 avril 2002
Statut
Membre
Dernière intervention
11 février 2010

Il ne m'en avait pas parlé , mais ca ne veut pas dire que je ne la connaissait pas ! Bien sur que oui je la connais :) !

Cependant avant de me prodiguer des conseils tu ferais mieux de regarder l'algo plus en détails :

EXPLICATIONS :

Examinons comment la méthode classique fonctionne pour un degré n = 5 par exemple.
Déterminons donc le triangle de pascal qui va nous permettre d'obtenir les coefficients du developpement :

puissance (p) 0 1 2 3 4 5 6 ...

n = 0 : 01
n = 1 : 01 01 00 00 ...
n = 2 : 01 02 01
n = 3 : 01 03 03 01
n = 4 : 01 04 06 04 01
n = 5 : 01 05 10 10 05 01

Il faut savoir que C(0,0) = 1 et que les autre valeurs se calculent en effectuant la somme des deux valeurs situées immédiatement au dessus à gauche (et quand il en manque une, on considère qu'elle est egale à zero)
Exemple C(3, 1) = 01 + 02
C(3, 2) = 02 + 01

Ce qui revient à écrire la relation : C(n,p) = C(n-1,p-1) + C(n-1,p)

On a donc : (a + b) ^ 5 = 1*(a^5) + 5*(a^4) b + 10*(a^3)(b^2) + 10*(a^2)(b^3) + 10*a(b^4) + 1*(b^5)

Avec cette méthode, chaque valeur C(n, p) [ avec n > 1 et p quelconque ] recquiert de connaitre C(n-1, p-1) ET C(n-1, p) => la formule récursive est pas top top question complexité !
Pour calculer le 06 par exemple il faut connaitre 03 et 03 qui doivent connaitre elle même 01 02 et 02 01 ...
pour un 'n' "très" grand on recalcules tout le triangle ( 03 03 ; 01 02 01; 01 01 01 00) qui a pour origine le nombre que tu cherche et qui "monte" vers le haut... PLUS encore les valeurs du triangle maximal strictement inclut dans ce triangle ( 02 ; 01 01 qui sont calculé deux fois par la récursivité) .... etc ... Bref
Pour une ligne n = 50 .. l'algo classique c'est de la m...
D'ou mon idée de chercher si il n'existait pas une relation (qui existe toujours ;) ), entre C(n,p) et C(n, p-1) ! ... pour me simplifier la vie pendant les controles ou pour les exos, plutôt que d'avoir à redessiner un triangle complet (bien qu'il n'atteignait jamais plus de 5 lignes en général mais au moins j'épatais la gallerie ;p)

Et cette solution existe, je l'ai trouvé (clairement pas en 5 minute :-) puisqu'a tatons, en terminal on ne dispose pas trop d'outils !) !! C'est une suite numérique qui prend un parametre 'n' (dans l'enssemble N, qui représente le degré de développement que l'on souhaite faire ) et qui calcul la valeur de C(n,p) en fonction de p.
La voici :

On fixe C(0) = 01
et C(p) = C(p-1) * (n - p + 1) / p

Exemple pour n = 5
C(0) = 1 (par def)
C(1) 1 * (5 - 1 + 1) / 1
5
C(2) 5 * (5 - 2 + 1) / 2
5 * 4 / 2
= 10
C(3) 10 * (5 - 3 + 1) / 3
10 * 3 / 3
= 10
C(4) 10 * (5 - 4 + 1) / 4
10 * 2 / 4
= 5
C(5) 5 * (5 - 5 + 1) / 5
5 * 1 / 5
= 1
C(6) 1 * (5 - 6 + 1) / 6
1 * (0)/ 6
= 0

Pour tout p>=6 C(p) = 0;
Ce qui est pratique c'est qu'il n'est pas necessaire d'utiliser de variable de boucle, il suffit de vérifier que la dernière valeur n'est pas égale à 0 (ce que jen'ai aps fait dans mon code )
En se débrouillant pour que la multiplication se produise en dernière, on atteint ainsi la valeur maximale capable d'être calculée de manière simple avec des type de données classique (Integer, int, Entier, etc) !
J'espère que ceux qui n'avait pas compris trouveront cette explication claire :) !

CCL : Cet algo est plus beau, permet d'atteindre des valeurs sans perte de précision, et est carrément plus rapide ! :-)
En effet il est en o(n) alors que le classique est en o(2^n) (à cause des triangles imbriqués les uns dans les autres) Le gain est extraordinaire !!!
Mais l'application de cette formule est de toute manière très limitée.
Messages postés
224
Date d'inscription
mercredi 21 avril 2004
Statut
Membre
Dernière intervention
29 mars 2009

C(n;p) := n! / (n-p)! p!

C(n;p) + C(n;p+1) = C(n+1;p+1) est la formule qui donne le triangle de Pascal. On peut faire les calculs à l'aide d'un simple appel récursif.

(a+b)^n = Somme(k=0 à n ; C(n;k) a^k b^(n-k) )



(a+b)^1 = a + b

(a+b)^2 = a^2 + 2 ab + b^2
avec 2 = 1 + 1

(a+b)^3 = a^3 + 3 a^2 b + 3 a b^2 + b^2
avec 3 1 + 2 puis 3 2 + 1

(a+b)^3 = a^4 + 4 a^3 b + 6 a^2 b^2 + 4 a b^3 + b^4
avec 4 1 + 3 puis 6 3 + 3 et 4 = 3 + 1

...

Ecoutes ton prof à l'avenir ou mieux poses lui la question.
Messages postés
367
Date d'inscription
lundi 1 avril 2002
Statut
Membre
Dernière intervention
11 février 2010

Euh non, il m'en avait pas parlé :-/
Afficher les 8 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.