Demande d aide : Suite logique ?

Olympiades mathématiques, énigmes et défis
CaramelDur
Messages: 7
Enregistré le: 02 Sep 2017, 17:43

Demande d aide : Suite logique ?

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 :hehe: :hehe: :hehe:

Vous remerciant par avance



aviateur
Habitué(e)
Messages: 3853
Enregistré le: 19 Fév 2017, 11:59

Re: Demande d aide : Suite logique ?

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. :hehe: :hehe: :hehe:

Par contre je n'ai jamais entendu de parler "shell"

Pseuda
Habitué(e)
Messages: 3222
Enregistré le: 08 Avr 2015, 14:44

Re: Demande d aide : Suite logique ?

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

Re: Demande d aide : Suite logique ?

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

Re: Demande d aide : Suite logique ?

par pascal16 » 02 Sep 2017, 20:49

36*35^7 possibilités ?

CaramelDur
Messages: 7
Enregistré le: 02 Sep 2017, 17:43

Re: Demande d aide : Suite logique ?

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

Re: Demande d aide : Suite logique ?

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

Re: Demande d aide : Suite logique ?

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. :hehe: :hehe: :hehe:

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

Re: Demande d aide : Suite logique ?

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

Re: Demande d aide : Suite logique ?

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.

Avatar de l’utilisateur
chan79
Modérateur
Messages: 10330
Enregistré le: 04 Mar 2007, 21:39

Re: Demande d aide : Suite logique ?

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

Re: Demande d aide : Suite logique ?

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

Re: Demande d aide : Suite logique ?

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

Re: Demande d aide : Suite logique ?

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

Re: Demande d aide : Suite logique ?

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

Re: Demande d aide : Suite logique ?

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

Re: Demande d aide : Suite logique ?

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

Re: Demande d aide : Suite logique ?

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 !

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 6610
Enregistré le: 22 Nov 2007, 14:00

Re: Demande d aide : Suite logique ?

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

Re: Demande d aide : Suite logique ?

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)

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 12 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite