Calculer le plus petit commun diviseur (avec la récursivité)

Bonsoir,

Et en français clair, ça donne quoi ?
Si tu pouvais nous donner un exemple d'entrées et de sorties, ça
éclairerait pas mal de lanternes dont la mienne.

@+
FxM

Bonjour,
Quelqu'un peut-il me dire comment déterminer avec un
algorithme le plus petit commun diviseur entre deux nombres
(si possible en utilisant la récursivité)

D'avance merci,

Jean-michel

Bonjour,
Quelqu'un peut-il me dire comment déterminer avec un
algorithme le plus petit commun diviseur entre deux nombres
(si possible en utilisant la récursivité)

D'avance merci,

Jean-michel

Bonsoir,

Alt-f11 puis Insertion | module. Y copier ce qui suit :
'==== d'ici === Public Function ppcd2(inp1, inp2)
Dim decomp As String
Dim tag As Boolean
Dim a As Double
Dim fin As Double
decomp = ""
tag = False: fin = 1E+308
debut:
If inp1 < inp2 Then bout = inp1 Else bout = inp2
If fin > Sqr(bout) Then fin = Sqr(bout)
For a = 2 To fin
If ((inp1 / a) = Int(inp1 / a)) And _
((inp2 / a) = Int(inp2 / a)) Then
inp1 = inp1 / a: inp2 = inp2 / a
decomp = decomp & "*" & a
tag = True
Exit For
End If
Next a
If tag = True Then tag = False: GoTo debut
decomp = decomp & "*" & inp
If Left(decomp, 1) = "*" Then decomp = Right(decomp, Len(decomp) - 1)
If Right(decomp, 1) = "*" Then decomp = Left(decomp, Len(decomp) - 1)
If decomp = "" Then decomp = "--"
ppcd2 = decomp
End Function

'==== jusque là ===
Usage :
Avec tes deux nombres dans deux cellules (disons A1 & A2).
=ppcd2(A1;A2)
validation par enter.

A1y8, A2v0 -> résultat = 2*19
A1i7, A2‰5 -> résultat = --
A1B2, A26 -> résultat = 2

@+
FxM

Bonsour(®),
????
au final c'est l'algorithme ou le résultat qui t'interesse ?
pour l'algorithme notre Matheux canadien pourra t'aider
si c'est le résultat uniquement alors voir l'aide en ligne :

PGCD
Voir aussi

Renvoie le plus grand commun diviseur de plusieurs nombres entiers. Le plus
grand commun diviseur est le nombre entier le plus grand qui puisse diviser
nombre1 et nombre2 sans qu'il y ait de reste.

Si cette fonction n'est pas disponible et renvoie l'erreur #NOM ?, installez
et chargez la macro complémentaire Utilitaire d'analyse.

Procédure

1.. Dans le menu Outils, cliquez sur Macros complémentaires.
2.. Dans la liste Macros complémentaires disponibles, activez la case à
cocher Utilitaire d'analyse, puis cliquez sur OK.
3.. Si nécessaire, suivez les instructions fournies par le programme
d'installation.
Syntaxe

PGCD(nombre1;nombre2;...)

nombre1,nombre2, ... représentent 1 à 29 valeurs. Si une valeur n'est pas un
nombre entier, elle est tronquée à sa partie entière.

Notes

a.. Si un argument n'est pas numérique, PGCD renvoie la valeur d'erreur
#VALEUR!
b.. Si un argument est inférieur à zéro, PGCD renvoie la valeur d'erreur
#NOMBRE!
c.. L'unité (1) est le diviseur pour toutes les valeurs.
d.. Un nombre premier n'admet pas d'autre diviseur que lui-même et l'unité
(1).
@+

Jean-mi wrote:

Bonjour,
Quelqu'un peut-il me dire comment déterminer avec un
algorithme le plus petit commun diviseur entre deux nombres
(si possible en utilisant la récursivité)

D'avance merci,

Jean-michel

begin 666 blueup.gif
M1TE&.#EA#@`*`,03```°``_Z6E[KVZJFFXPPHC]#.]@<`W]_A0`Z@8`
MXI65_]#0_QT5VR0=VXN+_YJ:_[>W_________P``````````````````````
M`````````````````````````"'Y! $``!,`+ `````.``H```4K8(%,9&F2
H0&.<+! =`VL"4J (,LH$04+D@ ?/!US8<$ (+(=RK)@3$904`@`[````
`
end

Salut,

La fonction existante =PPCM(Nombre1;Nombre2) ne te convient-elle pas ?
Il faut que l'utilitaire d'analyse soit coché dans OutilsMacros
complémentaires pour que ça fonctionne.


Sinon, tu as aussi cette macro, qui calcule en fait le PGCD mais qui
retrouve ensuite le PPCM selon la formule :
PGCD(a,b)*PPCM(a,b) = a*b

Function ppcm2(a As Integer, b As Integer)
Dim c, d, e As Integer
d = a
e = b
If e > d Then
c = e
e = d
d = c
End If
While e <> 0
c = d
d = e
e = -Int(c / d) * d + c
Wend
ppcm2 = a * b / d
End Function


A+
--
Nicolas B.

Bonjour,
Quelqu'un peut-il me dire comment déterminer avec un
algorithme le plus petit commun diviseur entre deux nombres
(si possible en utilisant la récursivité)

D'avance merci,

Jean-michel

-----Message d'origine-----
Bonsoir,

Et en français clair, ça donne quoi ?
Si tu pouvais nous donner un exemple d'entrées et de
sorties, ça

éclairerait pas mal de lanternes dont la mienne.

@+
FxM

Bonjour,
Quelqu'un peut-il me dire comment déterminer avec un
algorithme le plus petit commun diviseur entre deux
nombres

(si possible en utilisant la récursivité)

D'avance merci,

Jean-michel
.Bonjour,

En réponse à ta question, je tiens d'abord à m'excuser des

informations peu claires que j'ai
données.
Mon but est de bien comprendre le problème de la
récursivité à partir d'un exemple simple, ce
qui a été le cas avec factorielle.
Je souhaiterais comprendre aussi le deuxième exemple du
cours Internet dans VBA Excel.

FONCTION Min(ENTREE nombre_1, nombre_2)
DEBUT
SI (nombre_1 < nombre_2)
ALORS
Min = nombre_1
SINON
Min = nombre_2
FINSI
FIN

FONCTION MaxMoinsMin(ENTREE nombre_1, nombre_2)
DEBUT
SI ( nombre_1 < nombre_2)
ALORS
MaxMoinsMin = nombre_2 - nombre_1
SINON
MaxMoinsMin = nombre_1 - nombre_2
FINSI
FIN

FONCTION Pgcd(ENTREE nombre_1, nombre_2)
DEBUT
SI (nombre_1 = nombre_2)
ALORS
Pgcd = nombre_1
SINON
Pgcd = Pgcd(Min(nombre_1, nombre_2),
MaxMoinsMin(nombre_1, nombre_2)
FINSI
FIN

Il y a deux fonctions Min et MaxMoinsMin, et une fonction
principale de nom Pgcd qui utilise
le Pgcd des deux nombres_paramètres.

Je ne suis malheureusement pas arrivé à comprendre comment
fonctionne la fonction Pgcd qui
fonctionne par récursivité.
Je suis partiellement autodidacte et n'ai pas de profs
sous la main.
Quelqu'un peut-il m'aider à comprendre?

D'avance merci,
Jean-michel

Salut,

Dis FxM, tu pourrais expliquer un peu ta fonction, s'il te plaît :-)
Je comprends pas trop, et j'ai l'impression d'être complètement à côté de la
plaque avec ma macro...


A+
--
Nicolas B.

Bonjour,
Quelqu'un peut-il me dire comment déterminer avec un
algorithme le plus petit commun diviseur entre deux nombres
(si possible en utilisant la récursivité)

D'avance merci,

Jean-michel

Bonsoir,

Alt-f11 puis Insertion | module. Y copier ce qui suit :
'==== d'ici === > Public Function ppcd2(inp1, inp2)
Dim decomp As String
Dim tag As Boolean
Dim a As Double
Dim fin As Double
decomp = ""
tag = False: fin = 1E+308
debut:
If inp1 < inp2 Then bout = inp1 Else bout = inp2
If fin > Sqr(bout) Then fin = Sqr(bout)
For a = 2 To fin
If ((inp1 / a) = Int(inp1 / a)) And _
((inp2 / a) = Int(inp2 / a)) Then
inp1 = inp1 / a: inp2 = inp2 / a
decomp = decomp & "*" & a
tag = True
Exit For
End If
Next a
If tag = True Then tag = False: GoTo debut
decomp = decomp & "*" & inp
If Left(decomp, 1) = "*" Then decomp = Right(decomp, Len(decomp) -
1) If Right(decomp, 1) = "*" Then decomp = Left(decomp, Len(decomp)
- 1) If decomp = "" Then decomp = "--"
ppcd2 = decomp
End Function

'==== jusque là === >
Usage :
Avec tes deux nombres dans deux cellules (disons A1 & A2).
=ppcd2(A1;A2)
validation par enter.

A1y8, A2v0 -> résultat = 2*19
A1i7, A2‰5 -> résultat = --
A1B2, A26 -> résultat = 2

@+
FxM