ho :o !
Merder un exament de poo… ca me semble parfaitement légitime non ? 
Il a manqué de poo 
>< !!
C’est quoi cet exam’ ?
Programmation Orientée Objet…
Sinon, les gens, vous seriez résoudre ça ? c’est dans les annales d’un concours que j’aimerais passer…
Perso sans trier le tableau je vois pas 
Qu’est-ce qui te dit que tu n’as pas le droit de le trier ^o) ?! Tu le copies et le tries et hop non ?
Ca semble plutôt logique de ne pas la trier pour cet exemple. D’autant qu’avec le tri, il faudra conserver une indirection les indices de départ.
A mon avis, cet algo doit utiliser un truc genre le min & le max. Tu dois aussi pouvoir jouer sur le fait que ce soit des éléments uniques au sein de la liste.
:hello:
mon 1/4h de web au taf
re
la pieuvre > on était page 83… :riva:
Comme ça, ça a pas l’air immédiat, il n’y aurais pas un contexte, un programme de cours auquel ça se rapporte?
pour moi, l’intérêt c’est d’être plus rapide qu’un tri, et donc d’être inférieur à du n.log(n).
l’idée que j’aurais est d’adapter un algo de tri pour ne retenir que le classement du n/2 ème élément:
-en adaptant le qsort: tu choisi un pivot, et tu compte le nombre d’éléments sup et inf, dès que l’un des nombre >= n/2, tu en déduis une borne (min ou max) et le nombre d’éléments inférieurs pour la borne min, supérieure pour la borne max. tu rechoisi un pivot dans l’ensemble dépassant les n/2, mais dans les bornes en cours. tu reboucle avec ce pivot, tant que ce n’est pas le bon nombre
à priori, comme du qsort, ça fait du n² dans le pire des cas, et du nLog(n) en moyenne
- en adaptant le tri par classement (ie: le flashsort), comme ce sont des données numériques (ce qui doit nous guider vers cette méthode):
1ere passe:on calcule le min et le max de tous les éléments,
2ème passe: on découpe par tranche de classement toutes les valeurs possibles du tableau et on calcule le nombre d’élément de chaque tranche.
3èmement, on redécoupe la tranche “médiane” et on reboucle sur le 2) tant que la tranche n’a pas q’un seul éléments.
à adapter pour vérifier les conditions de terminaison, les éléments nule effets de bords.
ce dernier cas termine très rapidement si les données sont bien réparties (conditions du tri par classement), mais doit finir au moins en n² aussi dans le pire des cas.
je pense que le but est plus de créer un algorithme ad-hoc que de réutiliser le tri 
même si un bête tri par fusion garantirait un meilleur temps maximum d’exécution
edit bis:
quoique bon: quand on regarde les articles du wiki, le but est aussi de couper le problème ae algorithmes connus, et en phase de projet, moi je ferais un tri, tout dépend de la réponse qu’attend le concours: de faire 2 lignes de codes avec sort, hyper pas couteuse en temps de développement, ou de se la péter avec un gros algo qui rempli des tableaux et des arbres.
http://en.wikipedia.org/wiki/Algorithm#Algorithm_analysis
nanan moi je suis page 42. :non:
tout est relatif
Aucun contexte et c’est une question sur 5 points sur une épreuve de quatre heures sur 40 points… une demi heure de réflexion donc normalement…
Je sais pas si on est censés fournir une réflexion aussi “poussée”.
Pour ceux qui veulent voir l’épreuve au complet
Merci pour vos réponses en tout cas.
Vous connaissez ça ?
Warning: DOMDocument::save() [function.DOMDocument-save]: output conversion failed due to conv error, bytes 0xE9 0x20 0x64 0x65 in…
Joyeux… t’as pas d’erreurs d’encodages ou de noeuds mal ajoutés ?
Encodage c’est à quel niveau que je dois le modifier?
Car j’ai un fichier inclu lui-même dans un fichier en ISO-8859-1, qui appelle un fichier qui gère mon xlm.
Ce xml est lui même en ISO-8859-1.
J’ai raté un truk ?
Si y a aucun caractère spécial, ça devrait aller… mais dans le doute, j’utilise toujours utf8_encode quand je travaille avec du XML.
Voici tous les caractères qu’il enregistre ! Pas besoin de passer en UTF-8 là ?
ton idée de min et max me dis d’utiliser plutôt un algo de dichotomie avec un min et un max que l’on modifie en parcourant le tableau en une seule fois.
Comment on peut utiliser la dichotomie sur un tableau non trié ? :heink:
Darkcham > passe en UTF-8.
Hum… Je viens de tester, c’est bel et bien les accents qui font bugger, mais en UTF-8 j’obtiens une autre erreur :