[Debutant] Attribuer une cote

13 réponses

Timour

31/01/2004 à 14:57

Bonjour,
j'amerais que vous attribuiez une cote à ma fonction qui calcule tous
les diviseurs d'un nombre.
Merci

int main()
{
using namespace std ;
int a, x ;
cout << "Entrez le nombre à calculer : " ;
cin >> a ;
for ( int x = a ; x != 0; x-- )
{
if ( a % x == 0 )
{
cout << x << "\n" ;
}
}
return 0;
}

3 réponses

1 2

Jean-Marc Bourguet

01/02/2004 à 11:15

"Godot" writes:

"Fabien LE LEZ" a écrit dans le message de
news:
On Sat, 31 Jan 2004 19:50:02 +0000 (UTC),
(Marc Espie) wrote:

for (int x = 1; x * x <= a; ++x) {

Ne serait-ce pas plus efficace de calculer la racine carrée une seule
fois au début ?

Un compilateur moderne est capable d'optimiser ça non ?

Il peut changer le calcul du carré en une addition en gardant une
variable de plus. La technique est connue depuis relativement
longtemps (le Dragon book qui n'est pas particulièrement prolixe en ce
qui concerne les optimisations en parle; je ne sais plus s'il
l'applique aux carrés ou simplement aux multiplications par un
invariant dans la boucle).

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Vincent Lascaux

01/02/2004 à 22:36

Eh bien, il suffit de mettre les diviseurs dans un tableau, et
d'afficher le tableau à la fin, après l'avoir trié.

Ou de faire deux fois la boucle. C'est completement pas satisfaisant
intellectuellement, mais je me demande quel impact ca a sur la performance :

int racine = std::sqrt(a);

for(int x=1; x <= racine; ++x)
if(a%x == 0)
std::cout << x << "n";

for(int x=racine-1; x > 0; --x)
if(a%x == 0)
std::cout << a/x << "n";

--
Vincent

espie

03/02/2004 à 02:58

In article ,
Fabien LE LEZ wrote:

On Sat, 31 Jan 2004 21:33:51 +0000, Timour
wrote:

Oui c'est vrai que votre fonction est plus rapide mais l'ordre dans
lequel sont affichés les diviseurs n'est pas très présentatif..

Eh bien, il suffit de mettre les diviseurs dans un tableau, et
d'afficher le tableau à la fin, après l'avoir trié.

C'est pas efficace, on se reprend du O(sqrt(n) log n)

Plutot afficher les petits diviseurs, pousser les grands dans une pile,
et depiler apres la premiere boucle.

1 2

[Debutant] Attribuer une cote

3 réponses

Veuillez sélectionner un problème