juste pour préciser sur le tri rapide. Sa complexité est un O(n*log(n)) non pas en moyenne, mais dans le meilleur des cas, c´est à dire lorsque l´on arrive toujours a repérer un pivot qui se situe exactement au millieu de la liste ( se reporter à la page de godrik pour infrmation sur le fonctionnement). Mais en fait trouver ce pivot demande quasiment de trier la liste.

Donc au final on ne peut pas dire qu´il n´y a pas de tri meilleur qu´en O(n*log(n)) car il n´y en a même pas en O(n*log(n)) ( en pratique). Par contre si on peut faire des supposition sur ce que l´on veut trier alors là on peut faire bien mieux.

Pour ma fonction pair voici ce à quoi je pensait ( par exemple) :

--S2--
bool est_pair(int n)
{
if ( n==0) return true; / /ça on le sait.
else return ! (est_pair(n-1)); / /ça aussi on le sait
}

et on n´a bien utilisé que les deux choses que l´on savait ( 0 est pair et il n´y a pas 2 nombres pairs ou deux nombres impairs consécutif).

un autre exo :

--3--
très simple : écrivez une fonction " efficace" pour calculer x à la puissance n ou n est un entier positif.
par efficace, je veux dire que ça doit être mieux que for ( int i=1;i++<n;p*=x);

http://rafb.net/paste/results/dIlDUg58.html

Mais je crois pas que ça soit " efficace "

Un float???????

bah , je manque de pas mal de bases on dirait , mais bon , j´aprendrais!

c´est pas une histoire de multiplications égyptiennes ce dernier exo?

fracart > Bih je sais même pas ce que c´est ^^

Sinon les ga dans mon paste manque une " }" à la fin

pour l´instant quintoff c´est exactement ce que j´ai dit de pas faire.

pour pas vous embêter disont que x et n sont tout les deux strictement positif ( enfin surtout x est différent de zéro et n est un entier positif).

disont que pour réussir l´élévation à la puissance il faut diviser pour regner... et se servir de l´une des propriété de bases de l´élévation à une puissace donnée.

un float , c quoi?

Lol sonic , c le premier truc qu´on apprend en c++ . .. relit ton bouquin un ´float´ , c une variable qui permet de stocker des nombres décimaux , il y a aussi le ´double´ , qui est plus ´grand´ mais prend plus de mémoire . ..

a!
je savait pas que ca s´appelai comme ca ^^

tu savais pas tout court ouais

bah , quand meme , heuresement qe j c utiliser les int!!!
meme que quand on met signed devant ben je croit que ya les chiffre negatif mais moin de positif

" juste pour préciser sur le tri rapide. Sa complexité est un O(n*log(n)) non pas en moyenne, mais dans le meilleur des cas, c´est à dire lorsque l´on arrive toujours a repérer un pivot qui se situe exactement au millieu de la liste ( se reporter à la page de godrik pour infrmation sur le fonctionnement). Mais en fait trouver ce pivot demande quasiment de trier la liste."

L´algorithme de Quick sort est un tres bon exemple d´algorithme de Last Vegas c´est a dire que le temps de calcul de l´algorithme est incertain. En moyenne il est de O(n log(n)), mais dans le pire des cas il est de O(n^2).
C´est pour cela que je le deconseille toujours

" Donc au final on ne peut pas dire qu´il n´y a pas de tri meilleur qu´en O(n*log(n)) car il n´y en a même pas en O(n*log(n)) ( en pratique). Par contre si on peut faire des supposition sur ce que l´on veut trier alors là on peut faire bien mieux."
Mon dieu qu´est ce qu´il ne faut pas lire!
Bien sur qu´il y a des algorithme de tri en O(n*log(n)). Le tri par tas en est un et le tri fusion en est un autre.
Quand tu dis en pratique j´imagine que tu fait reference a une autre mesure de complexite!
En effet on choisit dans le cadre de l´analyse des algorithme de tri de compter le nombre de comparaison et c´est le nombre de comparaison qui est en O(n*log(n)).
On peut se convaincre de cela en raisonnant sur la hauteur maximal d´un arbre de decision.