Augmenter la rapidité de calcul d'un programme.

[Résolu]
Signaler
Messages postés
12
Date d'inscription
samedi 24 avril 2004
Statut
Membre
Dernière intervention
14 décembre 2005
-
Messages postés
12
Date d'inscription
samedi 24 avril 2004
Statut
Membre
Dernière intervention
14 décembre 2005
-
Bonjour,

En essayant de dévelloper un exercice du concours prologin, je me suis heurté à un problème que je n'arrive pas à résoudre.

L'exercice est le suivant : http://www.prologin.org/training/site/sujet.php?epreuve=4&sujet_id=2



Mon problème vient du fait que lorsque j'augmente le chiffre n, le
temps de calcul augmente aussi jusqu'à atteindre la limite autorisée
(0,125secondes). Je vois pas d'autres solutions que de changer
l'algorithme mais j'en vois pas trop d'autres :| ... si quelqu'un peut
m'éclairer, Merci.



Voilà mon code :



#include



using namespace std;



int main(int argcs, char* szarg)

{



int nLong;

cin >> nLong;




if (nLong > 100000 || nLong
< 2)


return 0;







int* nElem = new int[nLong];

int max = 0, snd;






for (int i = 0; i < nLong; i++)



{











cin >> nElem[i];












if (nElem[i] >= max)




{




snd = max;




max = nElem[i];




}//if














else
if (nElem[i] > snd)





snd = nElem[i];




}//for



delete[] nElem;


cout

2 réponses

Messages postés
546
Date d'inscription
mardi 26 novembre 2002
Statut
Membre
Dernière intervention
4 mai 2007
1
Ton algo est largement assez rapide pour passer le test ( ou plutot le teste est assez large pour que ton algo passe )
Ton erreur vient du fait que tu traites le probleme pendant que tu recuperes les entrées et ca peut donc poser des problemes .
J'ai corrigé ton algo et il passe sans probleme :

#include <stdio.h>
int nb;
int tab[100000];

int second()
{
int first =0; int snd 0 , max 0;

int i;
for(i = 0;i<nb;i++)
{

if (tab[i] >= max)
{
snd = max;
max = tab[i];
}//if
else if ( tab[i] > snd)
snd = tab[i];

}

return snd;

}

int main()
{
int i;
scanf("%d",&nb);

for(i = 0;i < nb ; i++)
scanf("%d",&tab[i]);

printf("%d\n",second());

return 0;
}
Messages postés
12
Date d'inscription
samedi 24 avril 2004
Statut
Membre
Dernière intervention
14 décembre 2005

Salut, merci de ta réponse. En effet ton code fonctionne et passe le test sans problèmes. Par contre j'en ai refais un avec les fonctions C++ à l'image du tien et il ne fonctionne pas, du moins il n'est pas assez rapide. Dois-je en conclure que le CPP est potentiellement plus lent que le C ?

Voilà mon code :

#include


using namespace std;


int nElem[100000];
int nLong;


int second()
{ int snd 0, max 0;

for (int i = 0; i < nLong; i++)
{
if (nElem[i] >= max)
{
snd = max;
max = nElem[i];
}
else if (nElem[i] > snd)
snd = nElem[i];
}

return snd;

}


int main(void)
{

cin >> nLong;

for (int i = 0; i < nLong; i++)
cin >> nElem[i];

cout << second();

return 0;

}