Discussion :

[yaya125]

Bonsoir
ce problème au dessus pour moi je pense qu'il s'agit de montrer qu'à chaque étape de ton algorithme, on a l'égalité « A = B×Q + R » qui est vérifiée. On procède par récurrence.
À la toute fin de l'algorithme, on a donc bien toujours A = B×Q + R, avec R plus petit que B, ce qui est la définition de la division euclidienne.mais j'ai pas réussi a donner la bonne réponse et de rédiger j'espère que vous pouviez m'aider merci a tous le monde
1)

Montrer que la séquence suivante (non optimale) calcule bien le résultat de la division(justifier votre réponse):

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
B<-c
R<-a
E<-a
Q<-0
Tant que R >=B faire
    R<-R-B
    E<-E-R
    Q<-Q+1
    E<-E+R
fintq

Remarque on suppose que a et c sont positifs

[tnariel]

Salut,

Concernant ton problème voici une ébauche de solution.
Divisons le problème en 2 cas :

1er Cas : a < c (=> On passe pas dans la boucle)
------------------------------------------------

D'après l'initialisation de tes variables, nous avons :
BxQ+R = c.0 + a = a, avec a < c. Donc Q est bien le quotient
de la division de a par B et R=a en est le reste.

2ème Cas : a >= c (=> On passe au moins une fois dans la boucle)
----------------------------------------------------------------

Soit i un entier > 0 qui représente le nombre de passage dans la
boucle.

Soit v une de tes variables (B, R, E, Q etc ...), on appelle v(i-1)
la valeur de v avant le i-ième passage dans la boucle.

Pour i = 1 on a :

B(0) = c
R(0) = a
Q(0) = 0

Après le premier passage dans la boucle les variables subissent des
modifications (voir ton pseudocode). On se retrouve en sortie avec :

B(1) = B(0) = c
R(1) = R(0) - B(0) = a - c
Q(1) = Q(0) + 1 = 1

On constate que :
B(1)*Q(1)+R(1) = c.1 + a - c = a.

Il semble qu'après i passages dans la boucle nous ayont donc
les égalités : (*)
B(i) = B(i-1) = ... = B(0) = c
R(i) = R(i-1) - B(i-1) = a - i.c
Q(i) = Q(i-1) + 1 = i

pour le rang i+1 on a :
B(i) = B(i-1) = ... = B(0) = c
R(i) = R(i-1) - B(i-1) = a - i.c
Q(i) = Q(i-1) + 1 = i

et après le passage dans la boucle en a :
B(i+1) = B(i) = c
R(i+1) = R(i) - B(i) = a - i.c - c = a - (i+1).c
Q(i+1) = Q(i) + 1 = i + 1

Les relations de récurrence constatées dans (*) sont donc bien vérifiées,
ce qui implique que l'on connaît l'état de chacune des variables après
chaque passage dans la boucle.

En plus, on constate que la valeur de R décroit après chaque passage,
alors que celle de B reste constante ce qui implique la boucle "se termine".

On peut alors conclure que si i est le nombre de passages dans la boucle
avant la terminaison de celle ci, on a les valeurs :
B(i) = B(i-1) = ... = B(0) = c
R(i) = R(i-1) - B(i-1) = a - i.c
Q(i) = Q(i-1) + 1 = i


On constate que :

B(i)xQ(i) + R(i) = c.i - a - i.c = a,
donc on retrouve l'égalité a = B(i)xQ(i) + R(i), avec R(i) < B(i)
car la boucle est terminée après i itérations.

Donc Q est bien le quotient
de la division de a par B et R en est le reste.