Discussion :

[gilles81]

salut.
Je ne comprend pas pourquoi cet algorithme:

Code :

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

1
2
3
4
5
6
7
static long f (long n){
long t = 0;
for (long i=1; i<=n; i=i*2){
t = t + i;
}
return t;
}

donne

Code :

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

une suite allant de zéro à deux puissance log2(n)

. Je pense qu'elle devrait plutôt aller de

Code :

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

zéro à deux puissance n.

merci

[Jean Dumoncel]

Salut,

je suis d'accord avec toi, telle que tu la présente, c'est même la somme des termes d'une suite géométrique de premier terme 1 et de raison 2 (ou de terme général 2^k)

[vincent69]

A cause de ça :

Code :

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

for (long i=1; i<=n; i=i*2)

[Jean Dumoncel]

A cause de ça :

Code :

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

for (long i=1; i<=n; i=i*2)

Et ??

je ne vois vraiment pas ou le log2 intervient...
pour aller plus loin on peut aussi calculer directement le résultat (somme des n premiers termes d'une suite géométrique) : 2^(n+1)-1

[Ulmo]

C'est la différence entre :

Code :

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

1
2
for (long i=1; i<=n; i=i*2)
    t = t + i;

et

Code :

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

1
2
for (long i=1; i<=n; i=i+1)
    t = t + 2^i;

Et ??

je ne vois vraiment pas ou le log2 intervient...
pour aller plus loin on peut aussi calculer directement le résultat (somme des n premiers termes d'une suite géométrique) : 2^(n+1)-1

Cherche la valeur finale de i. Elle fait intervenir log2(n).

[Jean Dumoncel]

Ah, oui, autant pour moi, je n'avais pas fait gaffe au rapport entre la condition d'arrêt et la façon d'incrémenter... dsl d'avoir un peu pourri le fil

[gilles81]

merci, c'est assez clair maintenant