Probleme en algorithme

Fermé
jean-joel - Modifié par baladur13 le 30/12/2014 à 13:34
Apatik Messages postés 5304 Date d'inscription mercredi 28 janvier 2009 Statut Contributeur Dernière intervention 29 mai 2016 - 2 févr. 2009 à 11:04
Bonjour,
jesuis Nom supprimé Modération CCM , etudiant de niveau 1 en Maths. Lors d'un devoir d'info j'ai ete buté à un exo du genre: ecrire un algo qui calcul la racine carrée grecque d'un nombre qui est un carré parfait.
A voir également:

2 réponses

Apatik Messages postés 5304 Date d'inscription mercredi 28 janvier 2009 Statut Contributeur Dernière intervention 29 mai 2016 782
2 févr. 2009 à 09:57
Hum.. carré parfait je vois. Racine carrée grecque par contre...?

Si on pars sur une racine carrée habituelle, tu peux utiliser une approximation:
On te donne le carré parfait A dont tu dois trouver la racine.
Tu compare un nombre aléatoire B² à A. En fonction du résultat tu incrémente ou décrémente B, puis tu recommence.
Tu peux optimiser le programme en faisant varier B par tranche de 5-10-15 par exemple, puis dès que tu as une fourchette, tu réduis la tranche. Tu peux aussi déterminer un ordre de grandeur de B avant de commencer en regardant le longueur de A. Par exemple, si A "mesure" 3 chiffres de long, tu sais que B est compris entre 10 et 32
0
Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009 329
2 févr. 2009 à 10:34
Bonjour,
Idem, je n'ai jamais entendu parler de "racine carrée grecque" (et google non plus apparemment).
Par contre, le meilleur moyen pour trouver la racine carrée, c'est non pas de le faire par tranche de 5-10-20 comme le suggère Apatik, mais de le faire par dichotomie, ce qui t'assure une complexité en O(log(n)), qui est optimale.

Cordialement,
0
jean-joel > Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009
2 févr. 2009 à 10:51
Je te donne un exemple. Pour calculer la racine carrée grecque de 49, on fait:
49-1=48
48-3=45
45-5=40
40-7=33
33-9=24
24-11=13
13-13=0
La racine carrée est le nombre de soustraction effectuée jusqu'à zero; donc 7 dans ce cas. Tu vois un peu?
0
Apatik Messages postés 5304 Date d'inscription mercredi 28 janvier 2009 Statut Contributeur Dernière intervention 29 mai 2016 782
2 févr. 2009 à 11:04
Waouw.. Sympa cette propriété des carré parfaits :)
Bon.. par contre je remarque que le grec donne juste une méthode puisque la racine reste la même. Voila un petit algo simple qui te permet d'obtenir ta racine comme ça.

A = carré_parfait
B = 1
C = 0
while (A != 0)
{
   A = A - B         //tu fais ta soustraction par ton nombre impair
   C = C + 1        //tu incrémente ton compteur, qui te donnera ta racine à la fin
   B = B + 2        //tu incrémente de 2 ton nombre impair pour la soustraction suivante
}

Racine = C

0