Discussion :

[coyotte507]

Bonjour,

Par exemple, la somme de k=0 à n de k est n*(n+1)/2 = 0.5*n^2+0.5*n.

L'algorithme peut déterminer ces formules pour des k², k³, k^n...

Cependant je vous conseille d'utiliser des structures qui peuvent contenir des fractions, pour éviter les erreurs d'arrondi.

Je précise que je l'algo a été entièrement conçu par moi-même...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
int degré
demander valeur pour degré.
tableau somme[degré+2]
tableau coeffs[degré+1]
 
somme[0] = 0
somme[1] = 1
 
pour i de 2 à degré+1
  somme[i-1]+i^degré -> somme[i]
fin pour
 
pour i de degré+1 à 1
  tableau mouvant = somme
  pour j de i à 1
    pour k de 1 à j
      mouvant[k]-mouvant[k-1] -> mouvant[k-1]
    fin pour
  fin pour
 
  mouvant[0]/factorielle(i) -> coeffs[degré+1-i]
  float C;
  coeffs[degré+1-i] -> C;
 
  pour j de 1 à i
    somme[j-1]-C*(j-1)^i ->somme[j-1]
  fin pour
fin pour
 
pour i de 1 à degré + 1
  afficher coeffs[i-1] & "n^" & degré+2-i
fin pour

voila le code en C:

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int degre;
 
int factorielle(int num)
{
	int ret = 1;
	while (num > 1)
	{
		ret *= num;
		num--;
	}
	return ret;
}
 
int main()
{
	double *somme, *coeffs, *mouvant, C;
	int i, j, k;
	printf("Donnez la puissance du membre à l'intérieur de la somme: ");
	scanf("%d", &degre);
 
	somme = malloc(sizeof(double)*(degre+2));
	coeffs = malloc(sizeof(double)*(degre+1));
	mouvant = malloc(sizeof(double)*(degre+2));
 
	somme[0] = 0;
	somme[1] = 1;
 
	for(i=2; i <= degre+1; i++)
	{
		somme[i] = somme[i-1]+pow(i, degre);
	}
 
	for(i=degre+1; i > 0; i--)
	{
		for(j=0; j < i+1; j++)
		{
			mouvant[j] = somme[j];
		}
 
		for(j=i; j>0; j--)
		{
			for(k=1; k<j+1;k++)
			{
				mouvant[k-1] = mouvant[k]-mouvant[k-1];
			}
		}
 
		coeffs[degre+1-i] = mouvant[0]/factorielle(i);
		C = coeffs[degre+1-i];
 
		for (j = 1; j <= i; j++)
		{
			somme[j-1] = somme[j-1]-C*pow(j-1, i);
		}
	}
 
	for (i = 1; i <= degre +1; i++)
	{
		printf("%lf n**%d ", coeffs[i-1], degre+2-i);
		if (i != degre +1) printf("+ ");
	}
	printf("\n");
 
	return EXIT_SUCCESS;
}

A noter que par exemple pour un degré égal à 10, on commence à voir apparaître 0.000001 au lieu de 0.000000, c'est pour ça qu'il serait judicieux d'utiliser des fractions.

Si vous trouvez ca pas très clair dites-le, peut être qu'il existe aussi d'autres algos plus performants sur internet...

[PRomu@ld]

n*(n+1)/2 = 0.5*n^2+0.5*n.

Soit, mais ta formule n'aide en rien, tu remplace deux multiplications et une addition par deux multiplications un calcul de puissance (ici une multiplication) et une addition.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

somme[j-1]-C*(j-1)^i ->somme[j-1]

Ici, au lieu de calculer une puissance, on pourrait utiliser le schéma de horner.

voila le code en C:

Là ça se complique

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
somme = malloc(sizeof(double)*(degre+2));
	coeffs = malloc(sizeof(double)*(degre+1));
	mouvant = malloc(sizeof(double)*(degre+2));

Vérifie le retour de malloc et n'oublie pas de libérer tes tableaux.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

somme[j-1] = somme[j-1]-C*pow(j-1, i);

Tu es en C, utilises la puissance du langage :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

somme[j-1] -= C*pow(j-1, i);

Il vaut mieux créer sa propre fonction puissance parce que pow est lente et ici, tu ne fait que des puissances entières.

Enfin, pour tes parcours de tableaux, tu prends un indice i égal à 1 pour parcourir ton tableau en utilisant i-1, c'est pas très logique.

Ma question habituelle : est-ce que tu as un exemple d'application de ton algorithme ?

[coyotte507]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Ma question habituelle : est-ce que tu as un exemple d'application de ton algorithme ?

Par exemple tu donnes D = 100, il te sort le polynôme pour calculer 1^100 +2^100+3^100....+n^100. C'est comme si avec maple on faisait sum(k^100, k=1..n).

Enfin, pour tes parcours de tableaux, tu prends un indice i égal à 1 pour parcourir ton tableau en utilisant i-1, c'est pas très logique

Ca vient que j'ai fait mon algo sur ma calculatrice en premier...

Vérifie le retour de malloc et n'oublie pas de libérer tes tableaux

Le code en C est juste pour montrer l'algo. Après ces tableaux sont utilisés jusqu'à la fin du programme donc ca fait pas de fuites mémoires.

Soit, mais ta formule n'aide en rien, tu remplace deux multiplications et une addition par deux multiplications un calcul de puissance (ici une multiplication) et une addition.

Ce n'est pas ce que je fais. Par exemple, pour degre = 2, mon programme trouve 0.5*n² + 0.5*n. Je disais que c'était bien équivalent à la formule qui est (n+1)*n/2. Mais je n'utilise pas cette formule pour trouver 0.5*n² + 0.5*n. Je pars juste du contenu de la variable degre.

Ici, au lieu de calculer une puissance, on pourrait utiliser le schéma de horner.

Je ne sais pas ce que c'est. Mais si il y a des algos plus performants, autant remplacer celui-là par un sur internet. (mais je n'en ai trouvé aucun)

Edit: Un schéma de horner permet de simplifier le calcul d'un polynome, si j'ai bien compris. Or moi, je ne retranche que k*x^n, ce n'est pas vraiment un polynome.