Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 10-10-2016 13:20:20

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3263

vhanger un nombre

Bonjour à tous.

A combien d'échanges entre chiffres voisins (par exemple ...12... --->...21...) doit on procéder pour passer du 1er nombre suivant au 2ème nombre suivant ?

1738250439674693522047619814376099540
4977627055940117836238494393504612069

Le résultat exact est bien sûr demandé, mais ce n'est pas le plus important: La méthode l'est davantage, pour la généralisation qu'elle permet.

Tout ça à la main, bien entendu.

Bon amusement.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 10-10-2016 15:31:41

Agid1915
Passionné de Prise2Tete
Enigmes résolues : 0
Messages : 50

changer un nombrr

[HS]J`avais travaille sur ce probleme avec un carre (n*n). Le but etait cryptographique. Les nombres des 0 et des 1. Cle symetrique sous forme algorithmique. Les 2 personnes possedent le meme algorithme de "permutation".
L`algorithme permet de "melanger" et de reconstruire le message original.

Ce probleme est infiniment interessant.
Si apres manipulation d`une suite connue U(n) et complexe moyennant quelques parametres on peut retrouver une autre suite que l`on peut genere moyennant une formule explicite on touche la jackpot en matiere de "compression"
Formule explicite + quelques parametres et on reconstitue une suite determinee.

 #3 - 10-10-2016 19:41:25

Sydre
Professionnel de Prise2Tete
Enigmes résolues : 15
Messages : 183

Changer un noombre

On procède par tri par insertion.
Cet algorithme est de complexité [latex]O(n^2)[/latex] en moyenne donc je vote pour une réponse proche de [latex]37^2=1369[/latex] lol

EDIT : Après application je trouve [latex]187[/latex] roll

 #4 - 10-10-2016 19:48:19

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3263

Changer un nmobre

@ Sydre : il n'y a pas que Wikipédia dans la vie....

Je me doute bien que, poser une telle question en aveugle, c'est un risque d'avoir des réponses connues par les mathématiciens- informaticiens.

Pour l'instant, c'est encore calme....

 #5 - 10-10-2016 20:06:18

kossi_tg
Professionnel de Prise2Tete
Enigmes résolues : 18
Messages : 303
Lieu: Montargis

Chagner un nombre

Il faut procéder à 151 échanges.

Comment y arriver?

Etape 0: Prendre E=0, n=1;
Etape 1: Prendre le nième chiffre de b, notons ce chiffre x;
Etape 2: Compter le nombre de chiffres avant la première apparition de x dans a (notons ce nombre k),
Etape 3: Ajouter k à E;
Etape 4: Supprimer x de a;
Etape 5: Augmenter n d'une unité;
Etape 6: Si b est vide alors E est le nombre d'échanges, sinon retourner à l'étape 1.

Ma méthode résout le problème, mais est ce le nombre minimum? Je ne saurai l'affirmer.

.

 #6 - 10-10-2016 20:40:17

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 465

chznger un nombre

Bonsoir,
En optant pour une méthode simple (pas forcément optimale), en amenant successivement chaque nombre à sa place, je trouve 151.

 #7 - 10-10-2016 20:55:33

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 241

changer yn nombre

Bonjour, supposons dans un premier temps que tout les chiffres soient distants.
Prenons l'exemple 946375182->123456789
On compte le nombre de chiffres supérieurs à un chiffre donné situé à sa droite, et ce pour chaque chiffres.
Ici, 1 va devoir passer au dessus de 946375, 2 au dessus de 9463758
3 va devoir passer au dessus 946
4 va devoir passer au dessus de 9
5 va devoir passer au dessus de 967
...
On obtient au final un certain nombre n de chiffres à "passer"
Chaque transposition augmente ou diminue n de 1:
Si on passe un grand au dessus d'un petit (79->97), la valeur de 7 augmente de un, mais pas celle de 9.
Inversement, un petit au dessus d'un grand diminue la valeur de 1.
Si l'on procède dans l'ordre (placer le 1, puis le 2...), la valeur de n diminue de 1 à chaque fois (le 1 ne peut passer qu'au dessus de valeurs plus grandes, le 2 aussi, à part 1, mais il est déjà au bout, et ainsi de suite)

Si l'on place les chiffres l'un après l'autre, il n'y a pas de mouvements supplémentaires, chaque mouvement "trie" le nombre, c'est le principe du tri par insertion.

Dans le cas où les chiffres peuvent être identiques, il faut associer chaque chiffre à un chiffre unique, deux chiffres identiques mais à deux endroits différents du mot étant associer à un nouveau chiffre distinct l'un de l'autre. On peut alors appliquer notre procédé précédent.
Il faut donc trouver quel "étiquetage" donne une valeur de n la plus petite possible. La réponse est intuitive, il suffit de le faire dans l'ordre:
Par exemple, pour 1232143 -> 1122334
On ré-étiquette le deuxième nombre 1234567.
Le premier sera donc étiqueté 1354276.
On voit bien que proposer un autre étiquetage donnera une valeur de n plus élevée, car pour toutes les instances du chiffre k, le chiffre k ne sautera que pour les valeurs strictement inférieures à k dans le cas proposé ici, mais devra sauter au dessus de valeurs égales à k dans les autres cas. (A noter que changer l'étiquetage entre les valeurs de k ne change pas les valeur associées aux autres chiffres)

Application:
Dans notre, si on étiquette le deuxième nombre 1|2|3|...|37, on trouve pour le premier la permutation 14|3|18|17|6|9|8|1|21|2|5|4|12|19|11|26|10|20|34|13|23|7|32|15|24|22|33|25|28|16|36|30|27|37|29|31|35.
La somme des sauts donne:
1+1+3+3+4+7+8+7+8+4+1+6+8+2+8+2+15+1+9+3+5+1+4+3+14+4+6+6+5+2=151 ce qui nous donne 151 transpositions à effectuer afin de modifier notre nombre (sauf erreur de calcul)

 #8 - 11-10-2016 08:24:24

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3263

changer un nomnre

@kossi-tg, Enigmatus, Caduk: vous avez tous la bonne réponse, bravo !

@kossi_tg: Ta méthode de calcul semble efficace, mais par manque de clarté (b ? a ? ) je ne peux pas pour l'instant valider. Preuve qu'on ne peut pas faire mieux? 
@Enigmatus: Reste à prouver qu'on ne peut pas faire mieux.
@Caduk : C'est de la même façon que j'ai calculé, et par là même tu donnes aussi la preuve qu'on ne peut pas faire mieux.

 #9 - 11-10-2016 08:26:30

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3263

cjanger un nombre

@ tous : il existe une preuve assez expéditive, comme les aime Vasimolo, qui montre qu'on ne peut pas faire moins d'échanges que le nécessaire.

 #10 - 13-10-2016 17:02:41

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3263

Changer un noombre

Le temps est maintenant écoulé, et pour ces 3 bonnes réponses, encore un bravo aux auteurs.

Comme promis, la preuve courte (et visuelle) de l'optimisation du nombre d'échanges:

On écrit le nombre Départ en haut d'une page et le nombre Arrivée en bas de page. On trace un segment entre chaque paire de chiffres identiques, l'un en haut, l'autre en bas.
Le nombre d'échanges est égal au nombre de croisements entre les segments !

En effet, on montre facilement:
1) Le final est quand il n'y a plus de croisement.
2) Il existe toujours au moins un croisement entre 2 chiffres voisins du haut (donc aptes au décroisement par échange)
3) Un échange entre 2 chiffres voisins correspond à un unique décroisement.

La seule précaution à prendre est, au moment des tracés, de ne pas croiser 2 paires de chiffres identiques.

La démarche de kossi_tg est remarquable pour la façon efficace de calculer le nombre d'échanges. En réalité, c'est comme s'il avait construit ses 2 nombres chiffre après chiffre, l'un des nombres étant construit en ajoutant chaque chiffre à une extrêmité (toujours la même).

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete