Les solutions proposées par les candidats pour le qcm 2011

Cette mauvaise foi =p
Les gens rageant, ça existe, un point c'est tout !
Je confirme les dires de pole4. (J'hésite à me pencher sur son algo cependant, je risque pas de ne pas le comprendre si je ne le regarde pas :-°)

Piotr: Il suffit de voir son classement sur france ioi pour comprendre que c'est pas un petit rigolo \^\^

Edit: Rah, je commence à avoir des remords d'avoir seché tout les cours d'algebres l'annee derniere (enfin... tout les cours)

Paul est bien en Terminale S, c'est juste un passionné spécial :p
Par contre il a raté la sélection au stage animath d'aout (auquel il ne pouvait de toute façon pas participer vu qu'il partait aux IOI), et il ne s'est pas ré-intéressé à des choses dans le genre depuis (=pas d'IMO).

@Paul, passe à autre chose maintenant :p

« Sinon j'suis intéressé par l'algo de Pole... »
... Je ne le suis plus.
« Et surtout par son raisonnement et son explication de l'algo, vu que l'algo tout seul je ne le comprendrais pas xD »
Ah ah ah, comme j'étais drôle en ce temps-là !

Je me considère matheux, dans le sens où je fais spé maths et que j'aime assez la matière. Mais non, à ce point, non, ce n'est pas humain. :(

Gilbert s'est mis à la programmation après avoir vu Paul sur France 3 à ce qu'il paraît.

Tout est dit ;-)
@ Paul => clap clap clap

Tu pourrais penser aux pauvres mortels que nous sommes ?
Franchement ton algorithme a l'air intéressant, mais peut (pas ?) de gens arrive à le comprendre : pourrais-tu écrire une explication "avec les mains" ? (et des maths quand même)

Il y a un exemple à la fin.
Que ne comprenez-vous pas dans celui-ci ?

L'exemple est parfaitement compréhensible puisque ce n'est là qu'une application de l'algo que tu as expliqué, mais après... l'algo l'est beaucoup moins...

Ben moi même l'exemple, je ne l'ai pas compris! Mais bon disons que c'est un peu hard comme initiation aux matrices !

Je relance le sujet sur un post un peu ancien de jaloyan qui disait qu'il a codé l'exercice 4 en "modulo 3" de quoi s'agit il et a quoi ca sert ? J'ai regardé sur internet mais je n'ai rien trouvé.

Le modulo c'est le reste de la division euclidienne, Modulo 3 de 4 c'est 1 et Modulo 3 de 2 c'est 2...

Il s'en est servit pour savoir si après X application une case était blanche ou noir ...

Non, il s'en est servi pour économiser de la mémoire, en utilisant le fait qu'une ligne se déduit des 2 précédentes, et ça permet d'avoir un tableau de 3 lignes au lieu de 100. Et pour accéder à la bonne ligne, on fait un truc du type tableau[i%3], d'où le modulo 3.

merci @uguste je viens de comprendre, c'est pas bête en tout cas.

Ah, les balayages de tableaux... (nostalgie)

J'en connais un qui est encore plus nostalgique (son pseudo commence comme le tien ;) ).

Beuh c'est mechant??!!
Karatsuba: n\^log2(3)
Tu confonds avec Strassen: n\^log2(7)

Oui désolé c'est une erreur d'inattention, je voulais dire 3 bien sur.

@Pole4, ok t'es qu'un Terminale alors on te pardonne mais sérieusement, t'as déjà écris une vraie preuve dans ta vie ? Parce que là c'est juste illisible ... I have no idea what you’re talking about… so here’s a bunny with a pancake on its head .
En plus tu fais quand même beaucoup d'affirmations gratuites dans ta "preuve" :
- « Une multiplication classique de polynôme se fait O(n²/log n), que l'on peut accélérer facilement en O(n²/log² n). », les « algos classiques » c'est Karatsuba en n\^(log_2(7 ou 3, il parait :p)) et c'est mieux que tes trucs et la FFT est encore mieux.
- « On dérive en fonction de K : MM(n)-n³/log n/K² », tu *dérives* ? un grand O ?
C'est surement des petites erreurs d'inattention mais à cause d'elles on n'y comprend rien.

Finalement, ton code c'est une escroquerie, moi j'y vois juste un pivot (mais je le reconnais bien codé avec des xor) et d'ailleurs la complexité que tu annonces a l'air fausse (d'où vient le M(n) ?).

Sur un plan plus personnel, j'espère que tu te plairas bien en prépa, que tu pourras y utiliser correctement ces théorèmes et dans deux ans (trois?) qui sait ? une ENS ;) ?

Ah ben avec ce code c'est tout de suite plus compréhensible.
Merci ;)

C'est celui que tu as envoyé pour la séléction?

C'est un des 17, oui.
Un avec 2n multiplications bourrines :
http://pastebin.com/20yaupUg