Exercice : Trouver le nombre de divisions nécessaires

Bonjour à tous et à toutes,

Depuis hier je bute sur un exercice d'algorithmique en Java, mais plus dans son implémentation que dans la compréhension de l'exercice.
En effet, je voudrais écrire un programme permettant de compter le nombre de divisions nécessaires pour obtenir un reste inférieur ou égal à 2.

Sachant que pour une division euclidienne nous avons l'équation suivante :

Code:

---

n = 2*q1 + r1

---

avec n un entier naturel non nul, q1 le quotient et r1 le reste (r1 < q1)

Code:

---

1 2 3 4 5 6 7 8 9

Considérons la succession d’opérations suivante : n = 2*q1 + r1 q1 = 2*q2 + r2 q2 = 2*q3 + r3 q3 = 2*q4 + r4 q4 = 2*q5 + r5 On poursuit cette série d’opération jusqu’à ce que le reste obtenu soit inférieur ou égal à 2

---

Par exemple si l'on divise 80844 par 2 on obtient 5 divisions avec (un reste nul puisque que 80844 est un nombre pair)
1 division par 2 pour le nombre 8
1 division par 2 pour le nombre 0
1 division par 2 pour le nombre 8
1 division par 2 pour le nombre 4
1 division par 2 pour le nombre 4

Voici le code que j'ai commencé à élaborer :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

public class Exercise6 { public static int countNumberOfDivisionNecessity(int n) { int remainder = 0; int quotient =0; int counter = 0;   while(remainder <= 2){ quotient =n/2; remainder = n%2; n = 2*quotient + remainder;   System.out.println(counter);   } return 0; } public static void main(String[] args) { countNumberOfDivisionNecessity(80844); // 5 divisions   }

---

Merci d'avance.
Transact

Salut,

Pour commencer :

Citation:

---

Envoyé par transact

...un programme permettant de compter le nombre de divisions nécessaires pour obtenir un reste inférieur ou égal à 2.

Par exemple si l'on divise 80844 par 2 on obtient 5 divisions avec (un reste nul puisque que 80844 est un nombre pair)
1 division par 2 pour le nombre 8
1 division par 2 pour le nombre 0
1 division par 2 pour le nombre 8
1 division par 2 pour le nombre 4
1 division par 2 pour le nombre 4

---

Comme tu le remarques justement le reste d'une division par 2 d'un nombre pair est 0. On doit compter le nombre de divisions nécessaires pour obtenir un reste inférieur ou égal à 2. 0 est inférieur ou égal à 2. Donc on s'arrête dès la première division (on n'en fera donc pas 5).

1. while(remainder <= 2){ signifie tant que le reste est inférieur ou égal à 2, et non pas comme ça devrait, jusqu'à ce que le reste soit inférieur ou égal à 2 (ou tant que le reste est supérieur à 2). Comme on ne peut tester le reste qu'après l'avoir calculé, on devrait faire un do/while plutôt qu'un while.
   On devrait avoir donc :
   
   Code:

   ---

   1 2 3

   do { /*...*/ } while( remainder>2 );

   ---

2. A chaque nouvelle itération, d'après
   
   Citation:

   ---

   n = 2*q1 + r1
   q1 = 2*q2 + r2
   q2 = 2*q3 + r3
   q3 = 2*q4 + r4
   q4 = 2*q5 + r5

   ---

   on refait le calcul sur le quotient trouvé précedemment, donc on devrait avoir, en fin d'itération, pour préparer la suivante, n=quotient;
3. ensuite le compteur doit être incrémenté à chaque itération et sa valeur doit être retournée à l'appelant (là, tu retournes 0)
4. A chaque itération, avant de faire n=quotient;, tu peux afficher un résultat intermédiaire :

Par ailleurs, je ne suis pas mathématicien et mes souvenirs de cours de math ne sont plus très clairs, mais il me semble que

• tout entier pair n peut s'écrire n = 2×q où q est un entier, ou encore n = 2×q + 0
• tout entier impair n peut s'écrire n = 2×q + 1 où q est un entier

Donc, il me semble que le nombre de divisions nécessaires pour obtenir un reste inférieur ou égal à 2 est (0 et 1 étant tous les deux inférieurs à 2) :

• 1 pour un nombre pair
• 1 pour un nombre impair
• soit toujours 1

Merci encore pour tes éclaircissements joel.drigo, je dois aller en salle cours ... je te tiens au courant de l'avancé de mon travail dès que je serai disponible.
Bonne journée.

Voici le code :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public class Exercise6 { public static int countNumberOfDivisionNecessity(int n) { int remainder = 0; int quotient = n/2; int counter = 0;   do { n = 2*quotient + remainder; System.out.println(n); n = quotient; System.out.println(n); counter++; System.out.println("Number of division is : " + counter); } while(remainder > 2); return 0; } public static void main(String[] args) { countNumberOfDivisionNecessity(8144);   } }

---

Effectivement après plusieurs tests sur des valeurs différentes (pair, impair) le résultat est toujours 1.

Merci encore.
Transact