Discussion :

[farized]

Bonjour,

SVP, Est ce qu'il y a quelqu'un qui maîtrise l'algorithme? pour m'aider à trouver une solution à cet exercice:

Écrire l'algorithme qui fait la somme des nombres suivants:

s=1+2+4+8+....+N

Merci d'avance.

[droggo]

Qia,

La réponse est dans la question.

De plus, personne n'est ici pour faire tes exercices à ta place, donc montre-nous ce que tu as déjà fait, et explique-nous ce qui te bloque.

[farized]

ok, merci.
vous maîtrisez algorithme?
c’était un sujet d’examen , je veux connaitre la solution ..

[prgasp77]

Bonjour farized,
merci de tenir compte de ce qu'a dit droggo ; il s'agit là de la « philosophie » de developpez.com.

Pour t'aider,

• lorsque l'on parle de la discipline, on parle « d'algorithmie » ; lorsque l'on parle d'un cas particulier, alors là on parle d'algorithme ;
• faire la somme des premiers éléments d'une suite est souvent un problème proposant une solution algébrique plutôt qu'une solution algorithmique ;
• ici, j'imagine que tu cherches à calculer ; tes cours de mathématiques du lycée devraient te venir en aide (ou google « somme des premiers éléments d'une suite géométrique »).

Si malgré tout, pour l'exercice, tu devais résoudre le problème en proposant un algorithme ... quels sont les outils dont tu disposes ? Une boucle peut-être ?

[disedorgue]

Bonjour,

Cette question me rappel une anecdote concernant Carl Friedrich Gauss qui enfant (7 ans je crois) avait résolu un problème similaire:
1+2+3+4+...+100=?
Tandis que les autres élèves faisaient les différentes sommes, Gauss écrivit le résultat presque instantanément en trouvant et utilisant la formule:
1+2+3+...+n=n(n+1)/2

Après l'anecdote, pour le problème:
1+2+4+8+...+N=(2*N)-1

semble fonctionner.

Cordialement.

[sologne]

Bonjour,

il s'agit en effet de la somme des termes d'une suite géométrique.
Somme(q^k,k=0,k=p) = (1-q^(p+1))/(1-q)
dans ton cas :
1+2+4+8+....+N = Somme(2^k,k=0,k=p) = (1-2^(p+1))/(1-2) = 2^(p+1)-1

Donc si tu imagines une toute petite interactivité avec l'utilisateur, du style : "Entrez le N" et tu retournes la somme, la seule difficulté est de lier le N au p.

Pour cela on pose :

N=2^p <=>
ln(N) = ln(2^p) = pln(2) <=>
p = ln(N)/ln(2)

Si N est bien une puissance de 2 alors p sera un entier à coup sûr.

Ensuite tu n'as plus qu'à appliquer la formule de calcul .

Concrètement et sans contrôle de cohérence sur la saisie utilisateur :

Code :

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

1
2
3
4
5
 
Saisir N;
p = ln(N)/ln(2);
S = 2^(p+1)-1;
Afficher S;

Il s'agit seulement du cœur le l'algo, ensuite il faut affiner, déclarer les variables, leur type, placer un petit controle de cohérence sur la saisie utilisateur, etc ...

Bon courage

[disedorgue]

On peut se passer de chercher p en utilisant la formule que je donne précédemment (sauf si elle fausse ):
1+2+4+8...+N=(2*N)-1 (forme plus informatique, mathématiquement, on l'écrirait 2N-1)
Ce qui donne comme algo:

Code :

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

1
2
3
Saisir N;
S=(2N)-1;
Afficher S;

Cordialement.

[pseudocode]

On peut se passer de chercher p en utilisant la formule que je donne précédemment (sauf si elle fausse )

Elle n'est pas fausse. Un petit passage en binaire rend la chose plus visuelle

1+2+4+8 = 15 = 16-1

  00001 (1)
+ 00010 (2)
+ 00100 (4) 
+ 01000 (8)
-------
= 01111 (15)

= 10000 (16) - 1

[disedorgue]

On peut même généraliser sur les suites du même type:
Par exemple, si on considère la suite suivante:
1+A(2^0)+A(2^1)+A(2^2)+A(2^3)...+A(2^P)=2(A(2^P))-(A-1)

En remplaçant A par 2 et A(2^P) par N, on aurait:
1+2(1)+2(2)+2(4)+2(8)...+N=1+2+4+8+16...+N=2(N)-(2-1)=(2*N)-1

En remplaçant A par 3 et A(2^P) par N, on aurait:
1+3(1)+3(2)+3(4)+3(8)...+N=1+3+6+12+24...+N=2(N)-(3-1)=(2*N)-2

Etc...