Défi Lycée : Informatique et complexité (collège+lycée)

[Kikoo <3 Bieber]

Hello,

Un topic sur de l'algorithmie m'a rappelé ce petit défi (sans doute bien plus facile qu'il n'en a l'air) que je m'étais posé un jour, en tapotant sur mon clavier.

Kikoo <3 Bieber floode sur un forum. Pour ce faire, il tape quelques lettres, qu'il définit comme étant un mot. Il sélectionne ce mot et le copie, par combinaison CTRL+C.
Il compte coller ce mot n fois. Expliquer comment il peut minimiser le nombre de fois qu'il appuie sur le clavier afin de coller n mots.

[Archytas]

Hello,

Un topic sur de l'algorithmie m'a rappelé ce petit défi (sans doute bien plus facile qu'il n'en a l'air) que je m'étais posé un jour, en tapotant sur mon clavier.

En utilisant la souris ! (ok je sors...)

[Kikoo <3 Bieber]

Bien évidemment :) Mais que je sache, sélectionner avec la souris ne compte pas en tant qu'appui sur une touche de clavier. On peut donc (je dirais même "on doit") sélectionner qqchose avec la souris.
Mais quoi ? Et pourquoi ?

[Anonyme]

Bonjour,

En fait tu copies/colles plusieurs fois le mot que tu veux. (Par exemple 10 fois). Ensuite, tu selectionnes tous les copiés/collés que tu as (les 10), et le re-copie/colle. Donc, au final tu ne copies/colles pas qu'une seule fois le mot, mais dix fois ou plus ! :P

Plus serieusement, j'y reflechis un peu ^^
Et au faut, Kikoo, tu me dois toujours un defi hein ! Je n'ai pas oublié ;)

[Archytas]

Bien évidemment Mais que je sache, sélectionner avec la souris ne compte pas en tant qu'appui sur une touche de clavier. On peut donc (je dirais même "on doit") sélectionner qqchose avec la souris.
Mais quoi ? Et pourquoi ?

N'utilisant pas le clavier, on minimise le nombre d'appuis sur le clavier ^^, donc ton défis est finit tu as appuyé 0 fois sur le clavier ! Bref je chipotte sur les termes, je suppose que la réponse que tu attends est de coller deux fois le mot puis de sélectionner les deux mots puis les copier et les coller puis prendre les 4 mots copier et coller puis les 2^n de manière à minimiser le nombre d'opération et à maximiser la vitesse (: (chose qu'avec la souris seulement on ne fait pas) ! C'est ça ?

[Kikoo <3 Bieber]

N'utilisant pas le clavier, on minimise le nombre d'appuis sur le clavier ^^, donc ton défis est finit tu as appuyé 0 fois sur le clavier ! Bref je chipotte sur les termes, je suppose que la réponse que tu attends est de coller deux fois le mot puis de sélectionner les deux mots puis les copier et les coller puis prendre les 4 mots copier et coller puis les 2^n de manière à minimiser le nombre d'opération et à maximiser la vitesse (: (chose qu'avec la souris seulement on ne fait pas) ! C'est ça ?

Ouaip.
Mais je veux une réponse claire : Le nombre d'opérations, la démarche et voir si d'autres méthodes sont plus efficaces. A partir de quel n une méthode devient plus rentable que l'autre par exemple

[Kikoo <3 Bieber]

Saccharine : Je n'ai pas oublié ton défi ! Je vais essayer de trouver quelque chose sur de l'analyse combinatoire :)

[Anonyme]

J'avais donné cette idée avant Archytas, mais mon message est passé inaperçu, tant pis.
Je vous laisse avec votre défi, bonne journée.

[Kikoo <3 Bieber]

J'avais donné cette idée avant Archytas, mais mon message est passé inaperçu, tant pis.
Je vous laisse avec votre défi, bonne journée.

Aha nan ! Pas inaperçu, mais ta méthode est plus gourmande en opération : tu attends de faire 10 copier-collers avant de doubler la quantité. C'est une perte de temps car tu commences une progression linéaire avant de passer à une progression exponentielle. Une simple étude de fonction te montrera que l'autre méthode est plus efficace et ce dès le début !
Ceci dit tu as eu une bonne idée, c'est bien (et je rajouterais que tu es intelligente pour une ES. Je plaisante, et préfère le dire avant de me faire taxer d'idiot :p)

[Archytas]

Si ton n est de la forme alors ma méthode est la plus rapide, tu en colles deux tu les prends tu les colles tu prends le résultat tu le prends et tu le colles etc... Si n different de 2^k tu te ramènes au 2^k le plus proche par valeur inférieure ensuite tu copie n-2^k mots et tu les colles !
Conclusion :
Pour n=2^k copier n mots prend exactement k-1 opérations minimum. (n=1 et 2 exclus)
Pour n différent de 2^k il faut se ramener au 2^k inférieur et tu as k opérations minimum

[Kikoo <3 Bieber]

Si ton n est de la forme alors ma méthode est la plus rapide, tu en colles deux tu les prends tu les colles tu prends le résultat tu le prends et tu le colles etc... Si n different de 2^k tu te ramènes au 2^k le plus proche par valeur inférieure ensuite tu copie n-2^k mots et tu les colles !
Conclusion :
Pour n=2^k copier n mots prend exactement k-1 opérations minimum. (n=1 et 2 exclus)
Pour n différent de 2^k il faut se ramener au 2^k inférieur et tu as k opérations minimum

Ah non Archytas ! Si le compte n'est pas rond il est hors de question de coller mots !
Il va falloir faire un peu d'arithmétique modulaire sur ce coup

[Archytas]

J'avais donné cette idée avant Archytas, mais mon message est passé inaperçu, tant pis.
Je vous laisse avec votre défi, bonne journée.

Mathématiquement cette méthode est moins rapide mais elle est "réellement plus rapide" tu bourrine le coller et tu copie et tu rebourine le coller t'en seras à 200 alors que celui qui utilise la méthode "mathématiquement" efficace sera en train de galérer à copier à la souris ses 2^k termes donc oui elle est moins efficace mathématiquement mais ce serait stupide de pas l'utiliser si le besoin se présente ^^ !

[Zweig]

Bah si , alors on appuie 2 fois sur CTRL+C, on sélectionne le bloc et on le colle une fois. On obtient alors un bloc de 4 mots. Ensuite, on sélectionne ce dernier bloc et on le colle soit fois ou bien fois. Après cette opération, dans le premier cas, on sélectionne un mot déjà collé et on le colle à le fin du bloc, dans le deuxième cas, on sélectionne un bloc de 3 mots et on le colle à la fin du bloc obtenu.
Ensuite, on sélectionne le bloc entier (formé de mots) et on le colle fois. Ensuite, il nous faut former un bloc de mots (qui est un nombre supérieur à ). Il nous faut donc former mots en utilisant la méthode initiale. Puis le bloc de mots est collé fois etc ...

C'est mon idée à froid, reste à voir si le nombre total de collages est bien minimal ...

[Archytas]

Ah non Archytas ! Si le compte n'est pas rond il est hors de question de coller mots !
Il va falloir faire un peu d'arithmétique modulaire sur ce coup

Pardon ?! ça marche parfaitement ! Prenons n=20 tu vas jusqu'à 16 en copier/coller (ce qui prends k+1 opérations (oui excuse moi c'est k+1 et non k-1) puis à 16 tu en copies 20-2^4 et tu les colles et tu as k+2soit 4+2 opérations donc le minimum, non ?

[Kikoo <3 Bieber]

Mathématiquement cette méthode est moins rapide mais elle est "réellement plus rapide" tu bourrine le coller et tu copie et tu rebourine le coller t'en seras à 200 alors que celui qui utilise la méthode "mathématiquement" efficace sera en train de galérer à copier à la souris ses 2^k termes donc oui elle est moins efficace mathématiquement mais ce serait stupide de pas l'utiliser si le besoin se présente ^^ !

Cela rejoint ce que j'ai dit avant. Cette méthode est bien plus rapide au bout d'un certain moment, si n est élevé ou un truc comme ça. Mais il faut que je me mette à brouillonner ceci pour en être sûr !
Et j'ai pas trop le temps :p

Je vais poser un petit défi à Saccharine et après je me pencherai sur mes obligations.

[Zweig]

Mieux : tu programme en 10 lignes un programme qui se charge de copier n fois un texte donné ^^

[Kikoo <3 Bieber]

Pardon ?! ça marche parfaitement ! Prenons n=20 tu vas jusqu'à 16 en copier/coller (ce qui prends k+1 opérations (oui excuse moi c'est k+1 et non k-1) puis à 16 tu en copies 20-2^4 et tu les colles et tu as k+2soit 4+2 opérations donc le minimum, non ?

Tu prends un exemple assez facile là. Tu t'aperçois que le compte est rond.
Par contre, pour un n assez grand et un reste premier assez grand aussi, je me demande ce que cela donne.

PS : je t'avoue ne pas y avoir réfléchi, et de toute manière j'ai pas le temps là. Bonne réflexion

[Archytas]

Tu prends un exemple assez facile là. Tu t'aperçois que le compte est rond.
Par contre, pour un n assez grand et un reste premier assez grand aussi, je me demande ce que cela donne.

PS : je t'avoue ne pas y avoir réfléchi, et de toute manière j'ai pas le temps là. Bonne réflexion

Peut être en effet... enfin logiquement ça me semble faisable pour tout n aussi complexe qu'il soit n=1003 le plus petit k est 9 et 2^9=512 celà prends donc 10 opérations ensuite tu copies/colles 491 mots (à l'oeil c'est pas évident et c'est un nombre premier) et tu as 1003 mots en 11 opérations. A voir si on peut trouver mieux, ça doit être possible mais c'est trop compliqué pour moi après ^^ !

[Anonyme]

(et je rajouterais que tu es intelligente pour une ES. Je plaisante, et préfère le dire avant de me faire taxer d'idiot :p)

Je viens de voir ça. Tu te fous de moi ? Tu insinues en fait que je ne le suis pas, c'est ça ? Ah ben merci.

[Kikoo <3 Bieber]

Je viens de voir ça. Tu te fous de moi ? Tu insinues en fait que je ne le suis pas, c'est ça ? Ah ben merci.

Va falloir t'apprendre le second degré dis-donc Je plai-san-te !