Discussion :

[anissa01]

Bonjour, je suis débutante et je voudrais savoir si cet algo tient la route svp.

Ecrire un algorithme qui permette de calculer la valeur exacte d'une somme suivante:

S=1-2^1+2^2-2^3+...+2^n avec n=>0.

Vous pourrez utiliser la méthode de raffinage des algorithmes pour exprimer votre résultat.

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
 
// Initialisation des variables
 
Lire(n); 
S<- 1;
i<- 1;
N<- 1;
j<- 0;
 
tant que (i<= n)
	tant que (j<i)
 
//Calcul des puissances (-2)^n
 
		N<- (-2)*N;
		j<- j+1;
		fin tant que
 
//Calcul de la somme
 
	S<- S+N;
	j<- 0;
	N<- 1;
	i<- i+1;
fin tant que
 
afficher (S);

[Zavonen]

Les sommes partielles ne vérifient-elles pas
S_n+1=1-2*S_n ?

[pseudocode]

Les sommes partielles ne vérifient-elles pas
S_n+1=1-2*S_n ?

whooa... joli.

[ellgafsi]

Les sommes partielles ne vérifient-elles pas
S_n+1=1-2*S_n ?

Salut Zavonen, peux-tu m eclairer comment t as trouvé ce résultat? (Démonstration)
Merci

[Zavonen]

Salut Zavonen, peux-tu m eclairer comment t as trouvé ce résultat? (Démonstration)

La vérification, elle est immédiate tu en conviendras.
Comment je l'ai trouvé:
Je suis matheux et j'ai l'habitude de travailler avec des séries entières.
On cherche toujours des relations de récurrence simples (ou multiples) entre ces sommes pour leur évaluation rapide (en général cela correspond à des développements limités de fonctions transcendantes). En résumé donc, l'habitude, la routine, rien de plus.
Cela s'applique aussi aux polynômes voir par exemple ma (courte) page sur l'évaluation et l'exemple d'expressions polynomiales http://gilles.dubois10.free.fr/Bases...valuation.html

[pseudocode]

Moi j'avais la somme des premiers termes d'une suite géométrique de raison -2. Ca necessite une division par 3, c'est donc moins classe que la solution de Zavonen avec seulement une addition et un décalage de bit.

[ellgafsi]

Je suis matheux

Vous etes prof universitaire en mathematiques et informatiques ---> mon respect!

En résumé donc, l'habitude, la routine, rien de plus

----> comment avoir monsieur tout ca pour pouvoir resoudre les problemes algorithmiques avant de les implementer?
example: un probleme X comment savoir si pour le resoudre on utilise un diviser pour reigner, un backtrack, une recursion...
comment savoir si on un besion pour ce probleme X ce struture de donné????
ca me manque toujours, moi je me lance directement dans le codage et compilation jusqu a ce que je resoue le probleme.

[ellgafsi]

Les sommes partielles ne vérifient-elles pas
S_n+1=1-2*S_n ?

Salut monsieur,
Alors selon votre proposition, on peut resoudre le probleme avec une recursion?
(relation S_n <---> S_n+1)
Si oui quelle est la complexité de la solution (j ai du mal a calculer la complexité d un algorithme recursif )

Merci pour l aide!

PS: j ai visité votre site. Vous etiez prof dans des universités arabes.
Vous etiez en Tunisie.
Je suis originaire d une ville du sud tunisien qui s appelle Gafsa (c est 150 Km de Gabes).

[Zavonen]

Je suis originaire d une ville du sud tunisien qui s appelle Gafsa (c est 150 Km de Gabes).

Oui votre pseudo 'Ellgafsi' est pour moi tout à fait clair.
Si vous voulez communiquer sur ce sujet utilisez plutôt les courriers perso parce que ces propos sont en marge de la discussion.
Pour recoller au sujet, il n'y a pas besoin d'appel récursif car il s'agit d'une récursivité 'terminale' pouvant être résolue par une simple itération.

[Zavonen]

Vu les remarques de pseudocode.
OK pour tout
Reste donc à mettre en balance la division par 3 avec les incrémentations à répétition.
Comme le dividande croit très vite, on doit travailler avec des bignums (long long int).
Chaque langage a son truc, Java a un type prédéfini, Python utilise une représentation par listes sans limitation autre que la mémoire disponible, etc. etc. Mais la division par 3 avec ces types de données peut se révéler couteuse, spécialement quand le numérateur est très grand.

[Nebulix]

Puisqu'il s'agit de puissances de 2, un décalage suffit.
Si on veut éviter la division par 3, on peut tout écrire directement en binaire.
s[5]=(10101)-(1010)=1011
s[6]=-(101010-10101)=-10101