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.

[kolodz]

@Flodelarab : Euh... non !
La version dérivé est : (n/5)*n
Comme je l'explique dans mon message précédent.
Et il trouve le bon résultat !

Cordialement,
Patrick Kolodziejczyk.

[ToTo13]

Devront être exclus de ce calcul les chiffres finissant par 5.

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

Devient donc :

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

J'aime bien celui-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

Le même en C/Java/C++ un peu optimisé (évite une multiplication et moins d'additions) :

Code C :

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

1
2
3
4
 
int i, acc = 0 ;
for (i=0 ; i < 10000 ; i+=10)
     acc += (i<<2) + 20 ;

[Flodelarab]

@Flodelarab : Euh... non !

Pourquoi "non" ? C'est juste et non contradictoire.

[schranz]

Merci pour ces échanges , c'est intéressant de voir des approches différentes de chacun.

J'ai oublié de préciser mais je débute dans le pseudo code du coup je comprend pas tout notamment. J'en suis resté a la syntaxe suivante :

Code :

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

1
2
3
4
5
6
 
var A en entier
debut
si
finsi
fin

Pour l'instant la méthode la plus explicite pour moi reste celle la

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

par contre je comprend pas trop bien la dernière ligne , le (i*4) correspond au 4 chiffres impaire présent pour un pas de 10 mais a quoi sert la multiplication dans tout ca ?

[Flodelarab]

C'est le nombre de dizaines. Mais tu ne fais pas l'exercice demandé si tu prends des raccourcis.

[kolodz]

Pourquoi "non" ? C'est juste et non contradictoire.

Ce que tu fait c'est une dérivé et non un dérivé(variante)... Tu joue sur les mots et ce n'est pas le but.

par contre je comprend pas trop bien la dernière ligne , le (i*4) correspond au 4 chiffres impaire présent pour un pas de 10 mais a quoi sert la multiplication dans tout ca ?

Si tu prends le cas de 11 13 17 19 :
Devient :

10+1+10+3+10+7+10+9

Qu'on réarrange :

10+10+10+10+1+3+7+9

Qu'on factorise :

10*4+1+3+7+9

Qu'on généralise :

i*4+1+3+7+9 ou i est le nombre de dizaine (où la partie supérieur à 10)

Mais tu ne fais pas l'exercice demandé si tu prends des raccourcis.

J'avoue ne pas comprendre la logique sous-jacente...

Cordialement,
Patrick Kolodziejczyk.

[arkya4]

Bonsoir,

Pour reprendre et continuer l'idée de Kolodz :

La somme S des nombres de 1 à n est donnée par S = n * (n+1) / 2 = E(1,n) . Nommons là S1.

Donc la somme des nombres pairs de 1 à n est par E(2,(n/2)). Appelons la S2.

La somme des nombres des nombres multiples de 5 de 1 à N est E(5,(n/5)). Appelons la S5.

Il faut penser au multiples de 10 qui sont également pairs et divisibles par 5.

Il suffit alors de créer une fonction qui prend en paramètre un multiplicateur et une limite supérieure et d'appliquer la formule :

S(1,N) - S(2, N) - S(5) + 2*S(10) avec N = 9999

Mes 2 centimes.

[schranz]

je vois que cette algo donne lieu à débat, sans vouloir être exigeant est ce que quelqu’un peut me le l'écrire sous forme de pseudo-code :

Code :

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

1
2
3
4
5
var A en entier
debut
si
finsi
fin

Merci

[kolodz]

Je ne suis pas pour le pseudo code. Voici les deux versions qu'il me semble important de retenir coder en Java :

Code java :

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
package aide.forum.developpez;
 
public class Sum {
 
	/**
         * @param args
         */
	public static void main(String[] args) {
		// On va faire un test des algos jusqu'à n =10 000
		int n = 10000;
		for (int i = 0; i <= n; i++) {
			int sum = sumWithForAlgo(i);
			int result = sumAsO1Algo(i);
			if(sum!= result){
				System.out.println("Erreur ! Itération "+i+" : Résultat version simple "+sum + ", Résultat version rapide " + result);
				System.exit(1);
			}
			System.out.println("Itération "+i+" : Résultat version simple "+sum + ", Résultat version rapide " + result);
		}
	}
 
	private static int sumAsO1Algo(int n) {
		n=n-1; //On retir un car prend le cas où n est non inclut pour être identique à l'autre algo.
		// On veux savoir quel est l'unité final
		int reset = n % 10;
		// Si on est dans le cas où on est divisible par 10, pas besoin de se prendre la tête on applique la formule.
		if (reset == 0 ) {
			return (n / 5) * n;
		} else {
			// Mince ce n'est pas le cas parfait ! On fait une version étendu
			// On va compter ce qui est après le cas parfait ! Et l'ajouter ... C'est pas si long !
			int topPart=0;
			// On veux l'arrondi au dizaine inférieur pour faire les belles additions !
			int arrondi = n/10*10;
			if(reset>=1){
				topPart+=arrondi+1;
			}
			if(reset>=3){
				topPart+=arrondi+3;
			}
			if(reset>=7){
				topPart+=arrondi+7;
			}
			if(reset>=9){
				topPart+=arrondi+9;
			}
			return (arrondi / 5) * arrondi+topPart;
		}
	}
 
	private static int sumWithForAlgo(int n) {
		int toReturn = 0;
		for (int i = 1; i < n; i++) {
			if (i % 10 == 1 || i % 10 == 3 || i % 10 == 7 || i % 10 == 9) {
				toReturn += i;
			}
		}
		return toReturn;
	}
 
}

Résultat:

Itération 0 : Résultat version simple 0, Résultat version rapide 0
Itération 1 : Résultat version simple 0, Résultat version rapide 0
Itération 2 : Résultat version simple 1, Résultat version rapide 1
Itération 3 : Résultat version simple 1, Résultat version rapide 1
Itération 4 : Résultat version simple 4, Résultat version rapide 4
Itération 5 : Résultat version simple 4, Résultat version rapide 4
Itération 6 : Résultat version simple 4, Résultat version rapide 4
Itération 7 : Résultat version simple 4, Résultat version rapide 4
Itération 8 : Résultat version simple 11, Résultat version rapide 11
Itération 9 : Résultat version simple 11, Résultat version rapide 11
Itération 10 : Résultat version simple 20, Résultat version rapide 20
Itération 11 : Résultat version simple 20, Résultat version rapide 20
Itération 12 : Résultat version simple 31, Résultat version rapide 31
Itération 13 : Résultat version simple 31, Résultat version rapide 31
Itération 14 : Résultat version simple 44, Résultat version rapide 44
Itération 15 : Résultat version simple 44, Résultat version rapide 44
Itération 16 : Résultat version simple 44, Résultat version rapide 44
Itération 17 : Résultat version simple 44, Résultat version rapide 44
Itération 18 : Résultat version simple 61, Résultat version rapide 61
...
Itération 9993 : Résultat version simple 19970011, Résultat version rapide 19970011
Itération 9994 : Résultat version simple 19980004, Résultat version rapide 19980004
Itération 9995 : Résultat version simple 19980004, Résultat version rapide 19980004
Itération 9996 : Résultat version simple 19980004, Résultat version rapide 19980004
Itération 9997 : Résultat version simple 19980004, Résultat version rapide 19980004
Itération 9998 : Résultat version simple 19990001, Résultat version rapide 19990001
Itération 9999 : Résultat version simple 19990001, Résultat version rapide 19990001
Itération 10000 : Résultat version simple 20000000, Résultat version rapide 20000000

Pour information le temps d'exécution pour n de 0 à 100000:
sumWithForAlgo : 11 375ms
sumAsO1Algo : 6 ms
C'est le passage de O(n) à O(1) !

Cordialement,
Patrick Kolodziejczyk.

[ToTo13]

Avec le petit morceau de code que je propose :
- 7ms si pas d'affichage
- 370ms si affichage.
Une méthode directe est toujours mieux qu'une boucle.

[kolodz]

Avec le petit morceau de code que je propose :
- 7ms si pas d'affichage
- 370ms si affichage.
Une méthode directe est toujours mieux qu'une boucle.

En réalisant l'ensemble des itérations de n=1 à n = 10000 ?

[ToTo13]

En réalisant l'ensemble des itérations de n=1 à n = 10000 ?

oui.

[Deuzz]

Bonsoir

je vois que cette algo donne lieu à débat, sans vouloir être exigeant est ce que quelqu’un peut me le l'écrire sous forme de pseudo-code :Merci

Comme j'ai pitié (à toi de l'adapter à tes règles d'écriture, si je n'utilise pas les mêmes que toi) :

Code :

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

1
2
3
4
5
6
7
8
9
10
var Total = 0
var Nombre = 1
DEBUT
TANT_QUE Nombre < 10000
SI Nombre MOD(5) <> 0
ALORS Total = Total + Nombre
FINSI
Nombre = Nombre + 2
FINTANT_QUE
FIN

Et si tu veux absolument incrémenter de 1 en 1 au lieu de 2 en 2, change la condition en
SI Nombre MOD(5) <> 0 OU Nombre MOD(2) <> 0

Au besoin : Modulo

Au passage : Algorithme est masculin.

je vois que cette algo

[schranz]

Merci pour vos explicatiosn et aides,

@Deuzz comme je découvre l'algorithme , je préfère par le pseudo que plutôt un langage connu. Mais c'est sympa de me l'avoir écrit .