Demande d aide : Suite logique ?
Olympiades mathématiques, énigmes et défis
-
CaramelDur
- Messages: 7
- Enregistré le: 02 Sep 2017, 17:43
-
par CaramelDur » 02 Sep 2017, 18:00
Bonjour
Je souhaiterais solliciter votre aide a resoudre un petit probleme
Comptant une clef sur 8 caracteres comprenant chiffres et lettres (on va dire tout en majuscule pour simplifier deja !) du type :AX5K3SD1 pour l exemple ..... On a donc (26+10)^8 possibilitées ...
Si par contre je definis qu une clef VALIDE ne doit PAS comprendre 2 caracteres qui se suivent ....
Combien diable obtins-je de possiblitées ?
J ai ecris un petit programme en shell, mais mon processeur ne doit pas être assez puissant car il n arrive a test que 250 clefs (par méthode d incrémentation) par seconde .... je vous laisse compter le nombre de jour nécessaire afin d obtenir ma réponse pour bien vous moquer de moi
Vous remerciant par avance
-
aviateur
- Habitué(e)
- Messages: 3853
- Enregistré le: 19 Fév 2017, 11:59
-
par aviateur » 02 Sep 2017, 18:14
Bonjour
Tu mettras environ 3 siècles. Mais peut-être un peu moins de temps avec un raisonnement, même en ajoutant le temps à corriger le français dans la rédaction.
Par contre je n'ai jamais entendu de parler "shell"
-
Pseuda
- Habitué(e)
- Messages: 3222
- Enregistré le: 08 Avr 2015, 14:44
-
par Pseuda » 02 Sep 2017, 18:14
Bonjour, 1 seconde, 0 possibilités, une clef (valide ou non ) va avoir du mal à ne pas avoir 2 caractères qui se suivent !
-
aviateur
- Habitué(e)
- Messages: 3853
- Enregistré le: 19 Fév 2017, 11:59
-
par aviateur » 02 Sep 2017, 18:18
bien vu @Pseuda. Mais le cerveau a inconsciemment tendance à corriger les fautes dans un texte. J'ai dû comprendre qu'il interdit "2 caractères identiques consécutifs."
-
pascal16
- Membre Légendaire
- Messages: 6663
- Enregistré le: 01 Mar 2017, 14:58
- Localisation: Angoulème : Ville de la BD et du FFA. gare TGV
-
par pascal16 » 02 Sep 2017, 20:49
36*35^7 possibilités ?
-
CaramelDur
- Messages: 7
- Enregistré le: 02 Sep 2017, 17:43
-
par CaramelDur » 02 Sep 2017, 22:06
aviateur a écrit:bien vu @Pseuda. Mais le cerveau a inconsciemment tendance à corriger les fautes dans un texte. J'ai dû comprendre qu'il interdit "2 caractères identiques consécutifs."
C est tout a fait ca.
Une idee ?
-
CaramelDur
- Messages: 7
- Enregistré le: 02 Sep 2017, 17:43
-
par CaramelDur » 02 Sep 2017, 22:21
pascal16 a écrit:36*35^7 possibilités ?
Cela me semble bien plus complexe a résoudre ...
-
CaramelDur
- Messages: 7
- Enregistré le: 02 Sep 2017, 17:43
-
par CaramelDur » 02 Sep 2017, 22:31
aviateur a écrit:Bonjour
Tu mettras environ 3 siècles. Mais peut-être un peu moins de temps avec un raisonnement, même en ajoutant le temps à corriger le français dans la rédaction.
Par contre je n'ai jamais entendu de parler "shell"
Pardon pour les fautes d orthographe
Le shell est un interpreteur de commandes sous linux... a chacun son metier ...
De plus si je me permet de solliciter votre aide c est bel et bien que je n ai pas trouver de reponse a mon interogation, ainsi merci d eviter ce type de message non constructif
Cordialement
-
Pseuda
- Habitué(e)
- Messages: 3222
- Enregistré le: 08 Avr 2015, 14:44
-
par Pseuda » 02 Sep 2017, 22:47
36^8-7*36^7, soit 29*36^7 possibilités
-
beagle
- Habitué(e)
- Messages: 8707
- Enregistré le: 08 Sep 2009, 16:14
-
par beagle » 03 Sep 2017, 10:59
pascal16 a écrit:36*35^7 possibilités ?
+1
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.
-
chan79
- Modérateur
- Messages: 10330
- Enregistré le: 04 Mar 2007, 21:39
-
par chan79 » 03 Sep 2017, 20:16
salut
on peut le voir plus facilement avec moins de caractères (par exemple 5 au lieu de 36, puis 6 au lieu de 36)
-
aviateur
- Habitué(e)
- Messages: 3853
- Enregistré le: 19 Fév 2017, 11:59
-
par aviateur » 03 Sep 2017, 20:44
@Caramel dur
En général mes réponses sont constructives!
J'ai d'ailleurs répondu en partie à ta question puisqu'à priori il semblait que tu ne cherchais que le temps de calcul de ton algorithme
Et puis inciter quelqu'un à formuler ses questions de façon assez claire c'est constructif.
De plus ma réponse n'a rien de déplacé par rapport à la façon dont tu as posé ta question.
Maintenant je peux t'expliquer la réponse de Beagle
soit n=36.
Pour un chiffrage avec un seul caractère n possibilités.
En ajoutant un deuxième caractère n(n-1) (car à chaque cas précédent on exclut une possibilité.)
En ajoutant un troisième caractère n(n-1)(n-1) (par le m^me raisonnement que précédemment)..
Et ainsi de suite pour arriver à la solution de @beagle
-
Pseuda
- Habitué(e)
- Messages: 3222
- Enregistré le: 08 Avr 2015, 14:44
-
par Pseuda » 03 Sep 2017, 23:04
Bonsoir,
Oups, j'ai répondu trop vite (dans ma façon de compter consistant à exclure les chaînes comportant 2 caractères consécutifs, j'ai enlevé plusieurs fois les mêmes chaînes de caractères comportant 3 caractères ou plus consécutifs).
-
aviateur
- Habitué(e)
- Messages: 3853
- Enregistré le: 19 Fév 2017, 11:59
-
par aviateur » 04 Sep 2017, 01:37
@Carameldur
Revenons à l'informatique. Puisque c'est ton métier tu pourras peut être répondre à mon interrogation .
En effet j'ai testé un algorithme pour écrire toutes les clefs possibles et je trouve 14 jours (environ) pour les écrire toutes.
Comparer à tes 319 ans, c'est bien plus rapide (relativement).
Ayant une machine standard j'ai un doute sur le fait que la lenteur d'exécution de ton algorithme vienne de
ton processeur.
La différence de vitesse d'exécution peut alors venir du logiciel shell que tu utilises (mais je ne le connais pas). Où alors de l'écriture de ton algorithme qui ne serait pas économe.
Ma question est donc de savoir d'où vient cette différence de temps? A mon avis c'est une question importante.
-
pascal16
- Membre Légendaire
- Messages: 6663
- Enregistré le: 01 Mar 2017, 14:58
- Localisation: Angoulème : Ville de la BD et du FFA. gare TGV
-
par pascal16 » 04 Sep 2017, 09:25
il y environ mille milliards de clefs possibles, l'algo, l'optimisation et le langage utilisé sont très importants.
Un pc récent gère (programmation multiprocesseurs) vers 10 milliard d'opérations par seconde.
si tu as besoin de 1000 temps processeur par clef, ça te donne 100 000 secondes comme temps de référence, soit dans le 28h de calcul.
Maintenant, un programme qui test si une clef est valide, ça sert à quelque chose.
Un générateur de clef (donc 1 à la fois), ça sert.
Un générateur de clef faciles à mémoriser, c'est ultra cool.
Mais stocker toutes les clefs, ça sert à rien.
Il y a aussi le fait que tu 'testes ' chaque clef, il n'y a rien a tester en faisant des boucles imbriquées
-
Pseuda
- Habitué(e)
- Messages: 3222
- Enregistré le: 08 Avr 2015, 14:44
-
par Pseuda » 04 Sep 2017, 11:10
Bonjour,
Un nouveau défi. Démontrer directement que :
sans utiliser de calculatrice (et sans utiliser les dénombrements précédents).
-
aviateur
- Habitué(e)
- Messages: 3853
- Enregistré le: 19 Fév 2017, 11:59
-
par aviateur » 04 Sep 2017, 11:50
Bonjour
On peut montrer que si
(inégalité de Bernoulli)
Donc
-
Pseuda
- Habitué(e)
- Messages: 3222
- Enregistré le: 08 Avr 2015, 14:44
-
par Pseuda » 04 Sep 2017, 17:51
Bonjour,
Ok ! On doit pouvoir généraliser cette formule avec n (longueur du code) et p (nombres de caractères) quelconques, ce qui ferait un autre défi à démontrer.
J'étais passée par les logarithmes et la concavité de la fonction logarithme :
, donc
, donc
,
,
,
Ainsi
.
Le seul souci est le cas d'égalité, qu'on résout avec
premier avec
et
. Donc
. Mais ta démonstration est plus élégante !
-
fatal_error
- Modérateur
- Messages: 6610
- Enregistré le: 22 Nov 2007, 14:00
-
par fatal_error » 06 Sep 2017, 08:51
hello all,
je vous trouve un peu expéditifs dans la mesure ou le pb ne me semble pas avoir été résolu?
Si on est pointilleux, sur l'alphabet 0-9a-zA-Z, on a (admettons) a qui suit 9, A qui suit z, mais rien qui suit Z.
la vie est une fête
-
CaramelDur
- Messages: 7
- Enregistré le: 02 Sep 2017, 17:43
-
par CaramelDur » 06 Sep 2017, 09:30
aviateur a écrit:@Carameldur
Revenons à l'informatique. Puisque c'est ton métier tu pourras peut être répondre à mon interrogation .
En effet j'ai testé un algorithme pour écrire toutes les clefs possibles et je trouve 14 jours (environ) pour les écrire toutes.
Comparer à tes 319 ans, c'est bien plus rapide (relativement).
Ayant une machine standard j'ai un doute sur le fait que la lenteur d'exécution de ton algorithme vienne de
ton processeur.
La différence de vitesse d'exécution peut alors venir du logiciel shell que tu utilises (mais je ne le connais pas). Où alors de l'écriture de ton algorithme qui ne serait pas économe.
Ma question est donc de savoir d'où vient cette différence de temps? A mon avis c'est une question importante.
Bonjour,
Je genere de facon incrementiel toutes les clefs possibles puis compare le 1er caractere au second, le second au troisieme etc.... j y ajoute un simple compteur de clefs donc definis comme invalide que j affiche a l ecran, alors OK l affichage prends un certain temps mais tout de meme ..... Je vais reecrire le code en C# qui est plus proche du language machine.
Le Shell est (en gros) a Linux ce qu est l invite de commande sous windows (juste pour info)
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 12 invités