Inscription / Connexion Nouveau Sujet
Niveau seconde
Partager :

algorithme et PGCD

Posté par
claraadr
18-05-17 à 17:35

Bonjour,

j'ai un DM de maths à faire ( avant ce week-end ), un exercice porte sur le PGCD, voici l'énoncé :

• Avec la structure " pour " et " tant que ", écrire un algorithme qui permet d'obtenir le PGCD de deux nombres.
- on fera l'algorithme des différences et l'algorithme d'Euclide.

Pour Euclide, je sais qu'il faut diviser le plus grand nombre(a) par le plus petit(b), puis diviser ensuite le plus petit (b)( du début ), le diviser par le reste que l'on trouve lors d'une division euclidienne, tant que le reste est supérieur à zéro

Pour celui des différences, il me semble qu'il faut faire le plus grand nombre (a) moins le plus petit(b), puis le plus petit du début(b) moins la différence trouvée.


Je ne vois pas du tout comment faire ces deux algorithme sachant que le professeur nous a donné une feuille non-remplie sur la structure " pour " et la structure " tant que "

Merci d'avance,

Posté par
barbubabytoman
re : algorithme et PGCD 18-05-17 à 17:37

Bonjour, as-tu déjà fait des algorithmes avant cela ? (pour savoir si par exemple tu sais ce qu'est une variable, et un "si alors")

Posté par
claraadr
re : algorithme et PGCD 18-05-17 à 17:41

Bonjour, oui j'en ai déjà fait

Posté par
barbubabytoman
re : algorithme et PGCD 18-05-17 à 17:50

Très bien, cela nous facilitera la tâche.

Je vais illustrer ce qu'est une boucle à l'aide d'un exemple.
Imaginons que tu fasses ton algorithme sur un ordinateur, avec un écran qui peut afficher des choses. Tu veux afficher 1000 fois "Bonjour tout le monde."

Tu as deux options qui s'offrent à toi:
* soit ton algorithme c'est
- afficher "Bonjour tout le monde."
- afficher "Bonjour tout le monde."
- afficher "Bonjour tout le monde."
- afficher "Bonjour tout le monde."
.....
- afficher "Bonjour tout le monde."

et ce 1000 fois

*soit tu fais preuve d'un peu plus d'ingéniosité, et tu fais appel aux boucles.
Ici, une boucle "pour" est plus adapté: ce que l'on va faire, c'est prendre une variable, par exemple, notons là "compteur", qui va compter combien de fois on fait les choses.
Et on fait l'instruction

- pour compteur variant de 1 à 1000
   - afficher "Bonjour tout le monde".
- fin pour

Ainsi, ce qui est entre "pour compteur blablbla" et "fin pour" sera répété 1000 fois.

Est-ce que jusqu'ici tu comprends ?

Posté par
claraadr
re : algorithme et PGCD 18-05-17 à 17:56

Oui, pour l'instant je comprends.
à voir avec la suite parce que pour le moment, je ne vois pas comment on va utiliser " les boucles " pour résoudre cet algo...!

Posté par
barbubabytoman
re : algorithme et PGCD 18-05-17 à 18:07

Nous allons y venir petit à petit, pas de soucis.

Maintenant, parlons la boucle "Tant que".
Là encore, le but est de répéter quelque chose autant de fois que l'on veut.
L'intérêt de celle-ci, c'est que ça durera tant qu'une condition sera vérifiée.

Par exemple, "tant qu'il pleut, je garde mon parapluie".
La condition qui est vérifiée ici, c'est "il pleut".
Ce qui est répété, c'est "je garde mon parapluie".

Grossièrement, on pourrait y écrire comme cela:
- Tant que IL PLEUT Faire
    - je garde mon parapluie
- Fin Tant que

Imaginons  à présent que par exemple, tu veuilles faire 5+2+2+2+2+2+...+2 jusqu'à dépasser 1000, à l'aide d'un algorithme, et qu'on sache à la fin combien on a ajouté de 2.

On va là encore utiliser une variable: notons là "somme".
Au début, elle vaudra 5 car on aura pas encore ajouté de 2.
Puis on va utiliser une variable "compte", qui comptera combien de 2 on a ajouté.
Au début, elle vaudra 0 car on aura pas encore ajouté de 2.

Ainsi, note algorithme pourrait ressembler à cela:

- mettre SOMME à 5
- mettre COMPTE à 0
- Tant que COMPTE < 1000 Faire:
       - SOMME = SOMME + 2
       - COMPTE = COMPTE + 1
- Fin Tant que

Est-ce que tu comprends jusque là ?

Posté par
claraadr
re : algorithme et PGCD 18-05-17 à 18:22

Pour le moment, vous ne m'avez pas perdu.

Posté par
barbubabytoman
re : algorithme et PGCD 18-05-17 à 18:34

Maintenant, nous avons toutes les clés en main pour réussir l'algorithme d'Euclide.

Reprenons depuis le début: on prend deux nombres a et b dont on veut connaître le pgcd.

Pour cela, on commence par effectuer la division euclidien du plus grand par le plus petit: on va supposer que a est plus grand que b.
La division euclidienne de a par b s'écrit a=qb + r.

Puis on fait la division euclidienne de b par r.
On obtient b=qr + r'.

On recommence avec r et r', et ainsi de suite jusqu'à ce que le reste vaille 0.

Il nous faut donc effectuer ces divisions euclidiennes successives.
Donc on doit obtenir le quotient et le reste.

Si tu as deux entiers a et b, est-ce que tu sais comment obtenir le quotient de la division euclidien de a par b ?

Posté par
claraadr
re : algorithme et PGCD 18-05-17 à 18:41

Je ne sais pas si je réponds à votre question mes par exemple :

50 et 3
50:3 = 1 + ( reste ) 2
3:2 = 1 + ( reste ) 1
2:1 = 2 + 0

c'est ça?

Posté par
carpediem
re : algorithme et PGCD 18-05-17 à 19:16

salut

Citation :
Pour celui des différences, il me semble qu'il faut faire le plus grand nombre (a) moins le plus petit(b), puis le plus petit du début(b) moins la différence trouvée.
il serait bien de savoir !!!

prenons a = 50 et b = 15

écris toute les étapes :

avec la division euclidienne
avec des soustractions successives

Posté par
claraadr
re : algorithme et PGCD 18-05-17 à 19:36

a=50 et b=15

Euclide :
50:15= 3 + 5
15:5= 3 + 0
le pgcd est 5

soustractions :
50-15 = 35
35-15 = 20
20-15 = 5
15-5 = 10
10-5 = 5
5-5 = 0
idem

carpediem @ 18-05-2017 à 19:16

salut

Citation :
Pour celui des différences, il me semble qu'il faut faire le plus grand nombre (a) moins le plus petit(b), puis le plus petit du début(b) moins la différence trouvée.
il serait bien de savoir !!!

prenons a = 50 et b = 15

écris toute les étapes :

avec la division euclidienne
avec des soustractions successives
carpediem @ 18-05-2017 à 19:16

salut

Citation :
Pour celui des différences, il me semble qu'il faut faire le plus grand nombre (a) moins le plus petit(b), puis le plus petit du début(b) moins la différence trouvée.
il serait bien de savoir !!!

prenons a = 50 et b = 15

écris toute les étapes :

avec la division euclidienne
avec des soustractions successives
a=50 et b=15

Euclide :
50:15= 3 + 5
15:5= 3 + 0
le pgcd est 5

soustractions :
50-15 = 35
35-15 = 20
20-15 = 5
15-5 = 10
10-5 = 5
5-5 = 0
idem

Posté par
claraadr
re : algorithme et PGCD 18-05-17 à 19:36

( petit bug de ma part, excusez- moi )

Posté par
carpediem
re : algorithme et PGCD 18-05-17 à 20:05

Citation :
Euclide :
50:15= 3 + 5
15:5= 3 + 0
le pgcd est 5

ceci ne veut strictement rien dire et c'est du grand n'importe quoi en terminale spé !!!

50 = 15 * 3 + 5
15 = 5 * 3 + 0

sont les divisions euclidiennes de 50 par 15 et de 15 par 5


bon ben maintenant il est aisé d'écrire un algorithme dans les deux cas ...

Posté par
claraadr
re : algorithme et PGCD 18-05-17 à 20:25

J'ai du mal en maths, je pense que vous pouvez comprendre..
C'est d'ailleurs pour ça que j'ai ouvert ce topic, car je n'arrive pas à faire l'algo.
( ps : je suis en seconde )

Je n'arrive pas à voir comment on peut faire un algorithme à partir de ça.

Posté par
mathafou Moderateur
re : algorithme et PGCD 18-05-17 à 21:17

Bonjour,

bon reprenons
après les explications détaillées et exemples par barbubabytoman tu devrais avoir compris que

une boucle permet de répéter des opérations un certain nombre de fois

la boucle "pour" permet de les répéter un nombre de fois connu à l'avance
la boucle "tant que" un nombre de fois inconnu, mais de s'arrêter sur une certaine condition, de boucler tant que (mots français) une certaine condition est vraie

ici on a bien exactement ce genre de cas : il faut répéter des divisions ou répéter des soustractions un certain nombre de fois

et ce nombre de fois on ne le connait pas à l'avance

avec l'algorithme d'Euclide on doit faire ça tant que le reste n'est pas nul
le PGCD étant le dernier reste non nul

l'algorithme prendra donc la structure générale :

tant que le reste n'est pas nul
effectuer une division euclidienne
remplacer dividende et diviseur par diviseur et reste
afficher le reste précédent, c'est à dire le diviseur actuel

cet algorithme pose un problème : la première fois on n'a pas encore calculé de reste !!
on est donc incapable de savoir s'il faut faire ou pas la boucle car on est incapable de savoir si oui ou non "reste" = 0

qu'à cela ne tienne, on décale tout d'un cran et on fait :

tant que diviseur n'est pas nul
effectuer une division euclidienne
remplacer dividende et diviseur par diviseur et reste
afficher le dividende

dès qu'on a fait une première fois la boucle, le nouveau diviseur est l'ancien reste et tout est fait exactement comme on veut :
à la fin le dernier dividende sera le PGCD (le dernier reste non nul)

essaie de continuer sur ces bases.

Posté par
claraadr
re : algorithme et PGCD 19-05-17 à 17:23

Je n'arrive pas à programmer l'algorithme, voici un exemple que je fais :
Variable : a;b type nombres

Afficher « le plus grand nombre »
Lire a
Afficher « le plus petit nombre »
Lire b
( donc là deja ça me pose problème car je ne vois pas comment dire que la variable a doit être supérieure à la variable b, pour ensuite faire la division )

Et après je ne sais pas quoi faire, qui doit prendre quelle valeur, et ce que je dois écrire dans la partie " tant que ".
Également, comme le reste change à chaque fois, je ne vois pas comment l'afficher..
Je ne sais pas si c'est clair, mais autant vous dire que je suis complètement perdue.

Posté par
mathafou Moderateur
re : algorithme et PGCD 19-05-17 à 18:54

le division euclidienne de 3 par 7 donne un quotient de 0 et un reste de 3
ou est le problème ?
3 = 7*0 + 3 le reste est bien entre 0 et 7 non, c'est bien une division euclidienne
le coup suivant je prend le diviseur et le reste
qui sont 7 et 3 et je diviserais 7 par 3 :
7 = 3*2 + 1
etc
donc je décide de diviser a par b, que a soit plus grand ou plus petit je m'en fiche

a s'appelle le dividende (ce que l'on divise)
b le diviseur
et cela va me donner un quotient que je vais appeler q et un reste que je vais appeler r
la division euclidienne c'est chercher q et r avec 0 ≤ r < b tels que
a = bq + r

que a soit > ou < b

maintenant tu tombes en fait dans l'écueil de "je veux me précipiter sur ma machine écrire tout de suite du code

et bien non on ne travaille pas comme ça, c'est la gamelle assurée.
on construit petit à petit un algorithme
en langage français naturel et ordinaire et formules de maths, pas en Algobox ou va savoir quoi
ça ce n'est pas un algorithme c'est un programme
ne pas confondre.
en détaillant par étape la structure de cet algorithme et en détaillant les opérations (mathématiques) qu'il y a à faire de façon de plus en plus précise et détaillée étape par étape


traduisons mot à mot ce que j'ai dit

entrer a et b (c'est fait)
tant que le diviseur est non nul

se traduit par : tant que b ≠0
je ne vois vraiment pas ce qui te bloque la dedans
dans la partie tant que on effectue la division euclidienne de a par b ce qui donne q et r
laissons les détails de côté pour l'instant (c'est comme ça qu'on peut avancer, pas en restant bloqué dés qu'il y a une difficulté)

entrée a et b
tant que b ≠ 0
calculer q et r tels que a = b*q + r et 0 ≤ r < b // effectuer la division euclidienne
mettre b dans a et mettre r dans b // pour recommencer avec comme dividende l'ancien diviseur et comme diviseur l'ancien reste
fin tantque
afficher a // c'est bien ce que j'avais dit afficher le dividende actuel, le dividende c'est a

on n'a absolument pas besoin d'afficher tous les restes qu'on trouve
seulement le dernier non nul
et c'est bien celui là, la valeur du dividende quand je suis amené à essayer de diviser par 0, ce que je n'effectue pas puisque je suis sorti de la boucle
c'est ce que l'on a analysé avant
ici on ne fait que traduire cette analyse de façon simplement plus précise, pas réinventer autre chose.

ne pas confondre une variable et son contenu
la variable c'est par exemple "a" écrite "a" tout du long, une sorte de "boite" dans laquelle je vais mettre des choses
et son contenu, sa valeur, c'est ce qu'on met successivement dedans au fur et à mesure.
ce qui se trouvait avant quand je met autre chose dedans est perdu.
et seul moi je connais la signification de ce que j'ai décidé de mettre dedans.
avoir cela présent à l'esprit est fondamental.

comme je penses que tu t'impatientes bien trop pour agir sainement dans cette construction patiente d'un algorithme étape par étape intéressons nous maintenant à la partie qui est au coeur du problème (et qui à tort te bloque)

étant donnés a et b comment calculer le quotient et le reste de la division de a par b
pour répondre à cette question c'est comme toujours : il faut se poser la question fondamentale :
comment je fais réellement pour calculer la division de 7 par 3, comment je fais réellement pour obtenir le quotient 2 et le rest 1

tant que je n'ai pas répondu sincèrement à cette question, toute écriture de code ou d'algorithme est vaine et vouée à l'échec.
il faut déja savoir quelles opérations mathématiques je fais pour faire ça.
à la main

une façon de faire est de faire une division brutale de 7 par 3 ce qui me donne 2,66666666666666...
qui est composé d'une partie entière 2 et d'une partie décimale ou fractionnaire 0,6666666....

je cherche le quotient entier, "euclidien". qu'est ce que je prends ?

mathématiquement cela va s'écrire
quotient= partie entière de a/b
soit ici q = partie entière de a/b

comment maintenant obtenir le reste ?
à partir de la définition pardi !
a = b*q + r je connais a, je connais b, je connais q
donc r = a - b*q

et voila enfin mon algorithme complètement analysé

entrer a et b
tant que b ≠0
q <--- partie entière de a/b
r <--- a - b*q
a <--- b
b <--- r
fin tant que
afficher a

il n'y a plus rien à détailler là dedans tout est fait, il ne reste plus au besoin que à traduire cela (mot à mot) dans le langage de son choix
par exemple Algobox, ou une calculette quelconque, ou en C etc
(rappel ne pas confondre algorithme, ce que l'on vient de faire, et traduction en un programme dans un langage donné.cet traduction qui va nécessiter de se pencher sur la doc de Algobox ou de la calculette etc pour par exemple savoir comment on écrit "la partie entière de"
voire même, parce que après tout q ne sert à rien, s'il existe une fonction qui donne directement le reste, va savoir...

Posté par
mathafou Moderateur
re : algorithme et PGCD 19-05-17 à 18:59

* 2,333333...
(ça ne change rien au principe, mais tant qu'à faire autant mettre des valeurs correctes

Posté par
claraadr
re : algorithme et PGCD 20-05-17 à 11:41

Merci beaucoup, je vais essayer de refaire tout ça sur papier étape par étape, puis une fois que j'aurai compris, j'essaierai sur algobox.
Je reviens vers vous si j'ai un soucis, merci



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !