Discussion :

[schranz]

Bonsoir,

je cherche à résoudre l'algorithme suivant :

Ecrire un algorithme permettant de calculer la somme des entiers impairs naturels
allant de 1 à 9999. Devront être exclus de ce calcul les chiffres finissant par 5.

mais je sèche sur l'écriture de ce dernier. Je vois qu'il faut mettre des conditions mais je n'arrive pas à l'écrire correctement.

Pouvez vous svp me donner les bases pour résoudre ce dernier ?

Merci

[dourouc05]

Tu devras avoir (pour une implémentation naïve) un accumulateur et une boucle. Cette dernière aura un compteur de 1 à 9 999. Si la condition demandée est vérifiée, alors tu ajoutes le nombre courant à l'accumulateur. En gros :

Code python :

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

1
2
3
4
acc = 0
for i in range(1, 9999 + 1): 
  if entier_naturel_impair(i) and se_finit_par_5(i): 
    acc += i

Pour cette dernière partie, j'aurais tendance à utiliser un modulo : si le reste de la division par 5 est nul, c'est que le dernier chiffre est 0 ou 5 ; par 10, s'il est nul, c'est que ce dernier chiffre est 0. Tu peux aussi remplacer cette deuxième partie par la condition d'imparité.

[Flodelarab]

Bonjour,

On peut déjà faire sauter la condition sur l'imparité:

Code :

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

1
2
3
4
5
acc = 0
for i in range(0, 500): 
  j=2*i+1
  if not (se_finit_par_5(j)): 
    acc += j

[BufferBob]

salut,

si on commence à pousser un chouillat le truc, les nombres impairs qui ne finissent pas par 5 finissent tous par 1,3,7 ou 9
partant de là :

Code :

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

1
2
3
r = 0
for i in range(0,10000,10): # tous les entiers de 0 inclus à 10000 exclus avec un pas de 10
  r += (i * 4) + 1 + 3 + 7 + 9

[kolodz]

Si on part par là :
On peux utiliser un dérivé de Sn=1+2+...+n = n*(n+1)/2

http://fr.wikipedia.org/wiki/1_%2B_2..._%2B_%E2%8B%AF

Sachant que 1+9999 =10 000 et 3+9997 =10 000
Pour n =10 000
On a 2 000 paires dont a : 2 000*10 000 = 20 000 000
Car 4 nombre sur 10 est un élément d'une paire. Une paire à deux éléments et on va jusqu'à 10000.

A noter que la formule fonction pour ton nombre finissant par 0.
sommeVoulu = (n/5)*n
Sinon il faut utiliser le n de la dizaine du dessous et ajouter le reste.
On est en O(1) à la place de O(n) !

Cordialement,
Patrick Kolodziejczyk.

[Flodelarab]

On peux utiliser un dérivé de Sn=1+2+...+n = n*(n+1)/2

Amusant de rappeler cette formule au lieu de rappeler que la somme des impaires est un carré.
1² = 1 = 1 (1 nombre)
2² = 4 = 1+3 (2 nombres)
3² = 9 = 1+3+5 (3 nombres)
4² = 16 = 1+3+5+7 (4 nombres)
etc...
5000²=25 000 000=1+3+...+9999 (5000 nombres)

Les nombres finissant par 5 sont de la forme 5*(1+2i) pour i allant de 0 à 999.
Donc 1000 nombres !
5*1000² = 5 000 000

Au final, l'algorithme doit trouver 20 millions.