Discussion :

[pera12]

bonjour a tous!
j'essaie de resoudre un exercice en scheme sur la fonction pgcd-ter:

On propose enfin d’implanter un algorithme de calcul du pgcd par dichotomie basé sur les équations suivantes :
– pgcd(m;n) = 2* pgcd(m/2;n/2), si m et n sont pairs ;
– pgcd(m;n) = pgcd(m/2;n), si m est pair et n impair.
Bien entendu, les équations
On pourra traiter le cas où m est impair et n pair en remarquant que
– pgcd(m;n) = pgcd(n;m)
Enfin, pour le cas où ni m, ni n ne sont pairs, on utilisera le fait qu’alors la différence entre m et n est paire (pensez que dans ce cas, il faut soustraire le plus petit au plus grand).
Donnez une définition de la fonction pgcd-ter qui implante le calcul du pgcd par dichotomie.

Franchement je vois pas par où commencer,je vois meme pas qu'est qu'une dichotomie!
Si quelqu'un pouvait m'aider ca serait gentil de sa part. Merci d'avance!!

[So.Ta]

Premièrement, pour savoir ce qu'est une recherche par dichotomie je ne peux que te conseiller d'aller voir la page wikipédia correspondante qui est assez claire à ce sujet.

Deuxièmement, tu commences en divisant ce que tu dois savoir sur les nombres entrés en vérifiant la parité d'une seule des deux variables. En gros, à l'aide de deux conditions tu vérifies si m est pair ou impair (par exemple) et puis tu vérifies si la parité de n.
Schéma :
.....................................-> n est pair alors ...
..............-> m est pair |.-> n est impair alors ....
m et n |
..............-> m est impair |.-> n est pair alors ...
.........................................-> n est impair alors ...

Enfin, c'est comme ça que je structurais le problème.

[pera12]

Merci de m'avoir repondu! j'ai structuré ma definition par des conditions:if.
mais je ne trouve pas d'alternance pour ma definition.
(if:condition consequence alternance)

[So.Ta]

L'alternance n'est pas obligatoire, tu peux avoir comme structure :

Code :

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

 (if condition consequence)