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
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
A voir également:
- Probleme en algorithme
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Code ascii algorithme - Guide
- Ecrire un algorithme qui permet de resoudre ax²+bx+c=0 - Forum Programmation
- Le codage optimisé proposé ci-dessous a été obtenu en appliquant l'algorithme du codage de huffman sur un texte. lucia a codé un mot en utilisant ce codage optimisé. elle a obtenu : 010011011000111 ✓ - Forum Programmation
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
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
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
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
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.
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
2 févr. 2009 à 10:34
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,
2 févr. 2009 à 10:51
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?