~ Algorithme ~

[Lostounet]

Bonsoir,

Dans le cadre d'un exercice de TP, je cherche à écrire un algorithme permettant d'effectuer la division euclidienne de deux nombres a et b sur Algobox.
Contrainte: On ne peut utiliser que l'addition/soustraction.

J'ai écrit un algorithme, mais qui n'aboutit pas... J'arrive bien à déceler l'erreur, mais je n'arrive pas à la corriger. L'erreur est dans la partie rouge... Merci de m'aider

Code: Tout sélectionner

ALGOBOX : SANSTITRE
CODE DE L'ALGORITHME :
1 VARIABLES
2 a EST_DU_TYPE NOMBRE
3 b EST_DU_TYPE NOMBRE
4 x EST_DU_TYPE NOMBRE
5 i EST_DU_TYPE NOMBRE
6 v EST_DU_TYPE NOMBRE
7 q EST_DU_TYPE NOMBRE
8 DEBUT_ALGORITHME
9 LIRE a
10 LIRE b
11 SI (b == 0) ALORS
12 DEBUT_SI
13 AFFICHER "On ne divise pas par 0"
14 FIN_SI
15 SINON
16 DEBUT_SINON
17 x PREND_LA_VALEUR a-b
18 TANT_QUE (x>b) FAIRE
19 DEBUT_TANT_QUE
20 x PREND_LA_VALEUR x-b
21 FIN_TANT_QUE
22 AFFICHER x
23 v PREND_LA_VALEUR a-x[COLOR=Red]
24 i PREND_LA_VALEUR 1
25 POUR i ALLANT_DE 1 A 100
26 DEBUT_POUR
27 TANT_QUE (v-b*i>0) FAIRE
28 DEBUT_TANT_QUE
29 POUR i ALLANT_DE 1 A 100
30 DEBUT_POUR
31 TANT_QUE (v-b*i>0) FAIRE
32 DEBUT_TANT_QUE
33 q PREND_LA_VALEUR v-b*i
34 FIN_TANT_QUE
35 FIN_POUR
36 FIN_TANT_QUE
37 AFFICHER i
38 FIN_POUR[/COLOR]
39 FIN_SINON
40 FIN_ALGORITHME


[Nightmare]

Hello,

bien qu'ayant fait du Maple, mes souvenirs sont un peu loin, mais je pense qu'on doit pouvoir écrire un truc du style

if a-b > b
then a:=a-b

[XENSECP]

Qu'est-censé représenter v et i en fait ? Parce que tout ça se fait en une boucle ^^

[Lostounet]

Bonsoir Night,

Tu veux dire pour le reste de la division euclidienne si j'ai bien compris?
Le problème vient surtout du quotient... :s

Modif: Yo Xen,
J'ai conçu "i" comme un compteur... Et v c'est le dividende moins le reste.
Le reste de la division euclidienne de 102 par 25 est 2, donc ici v = 102 - 2 = 100

Et de ce 100, je veux enlever "i" fois 25 jusqu'à trouver 0...?

[Nightmare]

Pour le quotient moi je m'en tirerai en introduisant une nouvelle variable qui augmente de 1 à chaque fois qu'on boucle.

Donc en gros, ça donnerait :

initialisation k=0
if a-b > b
then a:=a-b and k:=k+1

et à la fin on met un print a pour le reste et un print k pour le quotient. A confirmer et étayer par expert en algo.

[Skullkid]

Salut, je ne connais pas exactement la syntaxe (bon elle se devine assez bien...) de ce langage qui m'a l'air positivement atroce, mais quelques remarques :

Déjà tu as répété les lignes 25 à 28, tu as deux boucles POUR qui font varier le même indice, et tu as un FIN_POUR qui est après un affichage, alors qu'on s'attend logiquement à ce que ton programme n'affiche que deux choses : le quotient et le reste. Plus important, tu dis ne pas avoir le droit d'utiliser la multiplication, pourtant il me semble que tu t'en sers à la ligne 27, par exemple. De plus, tu fais varier ton i de 1 à 100. Pourquoi ? Ton i a bien vocation à contenir le quotient de la division in fine, n'est-ce pas ?

Enfin, ne crois-tu pas que dans toute première boucle TANT_QUE, tu puisses calculer le quotient et le reste en même temps ?

Y a aussi quelques effets de bord mal gérés sur lesquels on pourra pinailler après.

[Lostounet]

@Night: Le problème, c'est que je ne comprends pas la syntaxe que tu emploies, je débute en algorithmique :/

Salut, je ne connais pas exactement la syntaxe (bon elle se devine assez bien...) de ce langage qui m'a l'air positivement atroce, mais quelques remarques :

Déjà tu as répété les lignes 25 à 28, tu as deux boucles POUR qui font varier le même indice, et tu as un FIN_POUR qui est après un affichage, alors qu'on s'attend logiquement à ce que ton programme n'affiche que deux choses : le quotient et le reste. Plus important, tu dis ne pas avoir le droit d'utiliser la multiplication, pourtant il me semble que tu t'en sers à la ligne 27, par exemple. De plus, tu fais varier ton i de 1 à 100. Pourquoi ? Ton i a bien vocation à contenir le quotient de la division in fine, n'est-ce pas ?

Enfin, ne crois-tu pas que dans toute première boucle TANT_QUE, tu puisses calculer le quotient et le reste en même temps ?

Y a aussi quelques effets de bord mal gérés sur lesquels on pourra pinailler après.

A la ligne 27, je ne considère pas cela comme une "multiplication" mais plutôt comme une "soustraction successive" que j'ai simplifié par ce produit: J'aurais pu mettre - b - b - b - b "i fois" mais y'a pas vraiment moyen de le faire avec ce logiciel, je ne sais pas faire autrement.
Le Fin_Pour n'affiche rien, il y a une option "Afficher variable" dont je me sers à la ligne 22 par exemple.
Je peux faire varier mon i de 1 à 100, de 1 à 200 000 au max (capacité du logiciel d'après ce que j'ai compris) cela importe peu puisque je veux qu'il s'arrête à i = 4 pour la division de 102 par 25.

C'est vraiment lassant, ça fait plusieurs heures que je change et rechange les boucles, les variables sans intérêt. Je vais bientôt jeter l'éponge.

[XENSECP]

Je suis d'accord avec l'idée de Nightmare (j'en avais parlé vite fait dans mon message précédent).

Si tu veux on peut revoir en "langage algobox" cette simple boucle qui détermine reste et quotient ? :)

[Nightmare]

Le problème, c'est que je ne comprends pas la syntaxe que tu emploies, je débute en algorithmique :/

Qu'est-ce que tu ne comprends pas particulièrement? Si c'est le := , cela veut dire qu'on affecte une nouvelle valeur à la variable.

[Lostounet]

Je suis d'accord avec l'idée de Nightmare (j'en avais parlé vite fait dans mon message précédent).

Si tu veux on peut revoir en "langage algobox" cette simple boucle qui détermine reste et quotient ?

Ce serait trop simple: il y a déjà une fonction "reste de la division" et je peux facilement trouver la partie entière de a/b, si c'est ce dont tu veux parler?

Sauf que j'ai pas le droit...

[Nightmare]

Bon voici le programme complet que j'écrirais :

blabla de procédure
x:=a
y:=b
k:=0

tant que x > y
faire x:=x-y et k:=k+1
fin tant que
print "reste=x et quotient = k"
fin

[Lostounet]

Bon voici le programme complet que j'écrirais :

J'ai essayé d'adapter, mais il y a une grosse différence dans la syntaxe, je n'arrive justement pas à incorporer cette histoire de quotient, l'équivalent du "k" dans mon algorithme.
Désolé de t'embêter :triste:

[Nightmare]

J'ai justement essayé d'utiliser la même syntaxe que toi, à part le := mais ça, je crois pas me tromper en me disant que c'est un des premiers trucs à savoir écrire en algorithmique.

Qu'est-ce que tu ne comprends pas avec le coup du quotient?

Le quotient, ça va être le nombre de soustraction qu'on a besoin de faire avant que le programme s'arrête. Il augmente donc de 1 à chaque fois que le programme boucle et refait une soustraction. C'est pour ça que j'ai demandé à mon programme de transformer k en k+1 à chaque fois qu'il boucle. (sachant qu'on pose bien sûr k=0 au début)

Quand il aura fini de boucler, le dernier k obtenu sera le quotient, que je lui demande de m'afficher.

[Lostounet]

Merci beaucoup à tous !!
Grâce à vos conseils, j'ai pu perfectionner mon algorithme.

Code: Tout sélectionner

VARIABLES
2 a EST_DU_TYPE NOMBRE
3 b EST_DU_TYPE NOMBRE
4 x EST_DU_TYPE NOMBRE
5 k EST_DU_TYPE NOMBRE
6 DEBUT_ALGORITHME
7 AFFICHER "Saisir deux nombres a et b tels que a le dividende et b le diviseur !"
8 LIRE a
9 LIRE b
10 SI (b == 0) ALORS
11 DEBUT_SI
12 AFFICHER "On ne divise pas par 0"
13 FIN_SI
14 SINON
15 DEBUT_SINON
16 x PREND_LA_VALEUR a-b
17 k PREND_LA_VALEUR 1
18 TANT_QUE (x>=b) FAIRE
19 DEBUT_TANT_QUE
20 x PREND_LA_VALEUR x-b
21 k PREND_LA_VALEUR k+1
22 FIN_TANT_QUE
23 AFFICHER "On a donc:"
24 AFFICHER "Reste = "
25 AFFICHER x
26 AFFICHER "Et quotient = "
27 AFFICHER k
28 FIN_SINON

[Skullkid]

A la ligne 27, je ne considère pas cela comme une "multiplication" mais plutôt comme une "soustraction successive" que j'ai simplifié par ce produit: J'aurais pu mettre - b - b - b - b "i fois" mais y'a pas vraiment moyen de le faire avec ce logiciel, je ne sais pas faire autrement.

Étant donné que tu ne manipules que des entiers, toute multiplication est une "addition successive". Soit tu as le droit de l'utiliser, soit tu n'as pas le droit. Il n'y a en effet aucun moyen d'écrire directement "b + ... + b k fois", c'est à ça que servent les boucles.

Le Fin_Pour n'affiche rien, il y a une option "Afficher variable" dont je me sers à la ligne 22 par exemple.

Oui, mais ton AFFICHER était dans la boucle POUR, donc il aurait été appelé autant de fois que la boucle aurait fait de tours, donc au final, ton programme aurait souvent affiché plus de 2 résultats.

Je peux faire varier mon i de 1 à 100, de 1 à 200 000 au max (capacité du logiciel d'après ce que j'ai compris) cela importe peu puisque je veux qu'il s'arrête à i = 4 pour la division de 102 par 25.

Oui, mais si tu veux diviser 100000 par 2, ton programme ne marcherait pas. Si le logiciel est limité à des nombres entre 1 et 200000, alors ton programme doit être capable de diviser n'importe quel couple de nombres entre 1 et 200000. Typiquement, quand on ne sait pas quand arrêter une boucle POUR (dont le nombre d'itérations est fixé à l'avance), c'est qu'il faut probablement tenter d'utiliser une boucle TANT QUE (dont le nombre d'itérations n'est pas fixé à l'avance).

Bref, ton dernier programme est beaucoup mieux, mais il y a encore un problème, un de ces effets de bord dont je parlais plus tôt. Que renvoie ton programme si a = 1 et b = 2 ? Est-ce le résultat attendu ?