Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 01-10-2014 11:46:01

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 378

[Python] Produit de codes CLE

Bonjour,


Dans le forum Entraide Collège/Lycée, quelqu'un a fait remonter cette discussion à la surface. :
http://www.bibmath.net/forums/viewtopic.php?id=5011
En ayant le temps d'y regarder de plus près, j'ai constaté que le dernier exercice en date posé sur le sujet était loin, très loin d'être rapide à mettre en œuvre.
J'ai donc décidé de créer un programme en Python qui permettra de de résoudre cet exercice ou toute variante avec des nombres différents.
L'informatique, c'est confortable, rapide et sûr (après !)...

Voici le programme :

#!/usr/bin/python
# -*- coding: UTF-8 -*-

def titre():
    print ("        *****************************")
    print ("        **                         **")
    print ("        **  Produit de codes CLE   **")
    print ("        **                         **")
    print ("        *****************************")
    print ()
    print ()
    print ()

def cle(a,l):
    code=[]
    l-=1
    for i, char in enumerate(a):
        if char>"0":
            code.append(l-i)
    return code

   
## Nombres dont on doit trouver le Code CLE ##

nb = [123125256,768648254]

#############################################
titre()
Codes=[]
for n in range(2):
    print("   ## Nombre n°",n+1,"\n")
    code=[]
    a=bin(nb[n])[2:]
    print ("Le nombre "+str(nb[n])+" en base 10")
    long=(14+len(str(nb[n])))//2
    esp=" "*long
    print (esp+"s'écrit")
    print (a+" en base 2")
    print ()
    print ("Son code CLE est donc :")
    l=len(a)
    print(str(nb[n])+"(",end="")
    code=cle(a,l)
    l=len(code)
    Codes.append(code)
    for i, char in enumerate(code):
        print(char,end="")
        if i<l-1:
            print (",",end="")
    print(")"+"\n\n\n")

   
print("+-+ Produit des codes CLE +-+\n")
Prod_codes,Prod, Traite=[],[],[]
for i in Codes[0]:
    for j in Codes[1]:
        Prod_codes.append(i+j)
Prod_codes.sort()
print ("*** BRUT ***")
print ("\n",Prod_codes,"\n")
for a in Prod_codes:
    if a not in Traite:
        Traite.append(a)
        nb_a =Prod_codes.count(a)
        if nb_a==1:
            Prod.append(a)
        else:
            if nb_a%2==1:
                Prod.append(a)
            n_bin=bin(nb_a)[2:]
            lg=len(n_bin)
            code=cle(n_bin,lg)
            for i in code:
                Prod_codes.append(a+i)
    else:
        pass
Prod.sort(reverse=True)
print ("Produit des codes CLE corrigé :")
print(Prod,"\n")
P=0
print ("Le nombre correspondant à ce code CLE est :")
for i in Prod:
    P+=2**i

print (P,"\n")
print ("Vérification :" )
print (nb[0],"*",nb[1],"=",nb[0]*nb[1])

Sortie :

        *****************************
        **                         **
        **  Produit de codes CLE   **
        **                         **
        *****************************



   ## Nombre n° 1

Le nombre 123125256 en base 10
           s'écrit
111010101101011111000001000 en base 2

Son code CLE est donc :
123125256(26,25,24,22,20,18,17,15,13,12,11,10,9,3)



   ## Nombre n° 2

Le nombre 768648254 en base 10
           s'écrit
101101110100001010010000111110 en base 2

Son code CLE est donc :
768648254(29,27,26,24,23,22,20,15,13,10,5,4,3,2,1)



+-+ Produit des codes CLE +-+

*** BRUT ***

 [4, 5, 6, 7, 8, 10, 11, 11, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 33, 33, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 35, 35, 35, 35, 35, 36, 36, 36, 36, 36, 37, 37, 37, 37, 37, 37, 37, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 40, 40, 40, 40, 40, 40, 41, 41, 41, 41, 41, 42, 42, 42, 42, 42, 43, 43, 44, 44, 44, 44, 44, 44, 45, 45, 45, 46, 46, 46, 46, 46, 47, 47, 47, 47, 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 51, 51, 51, 52, 52, 53, 53, 54, 55]

Produit des codes CLE corrigé :
[56, 54, 52, 45, 44, 43, 41, 39, 36, 34, 33, 32, 29, 26, 25, 24, 21, 20, 19, 18, 17, 16, 13, 10, 8, 7, 6, 5, 4]

Le nombre correspondant à ce code CLE est :
94640013047703024

Vérification :
123125256 * 768648254 = 94640013047703024

@+

Dernière modification par yoshi (03-10-2014 08:05:01)


Arx Tarpeia Capitoli proxima...

Hors ligne

#2 02-10-2014 11:38:06

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 378

Re : [Python] Produit de codes CLE

Bien le bonjour,

Quelques explications pour le code ci-dessus.
La première partie :
Conversion de chaque nombre en binaire : ion récupère un String dont les 2 premiers caractères sont 0b, qu'on élimine.
Les 0 et les 1 représentent respectivement [tex]0\times 2^n[/tex] ou [tex]1 \times 2^n[/tex]
Le dernier chiffre à droite représente la puissance 0... donc l = longueur de chaine de -1.
On parcourt chaque caractère de la chaine a avec index i et on stocke l-i si le char n'est pas 0 (fonction Cle)...
On stocke chaque liste_code CLE dans une liste plus grande : Codes.

Etape suivante : produit des clés.
C'est de la distributivité, à ceci près qu'on ajoute les nombres au lieu de les multiplier (ce sont des exposants).
J'ajoute donc chaque élément de la liste 0 à chaque élément de la liste 1 et je stocke la somme dans la liste Prod_Codes...

Tri de la liste Prod_Codes : c'est inutile, maintenant que le programme fonctionne, mais cela m'a facilité le débogage...

Je parcours la liste Prod_codes, du premier élément (a) au dernier, pour chaque élément je compte combien de fois (nb_a) il est présent. .
Je stocke cet élément a dans la liste Traite (= ont été traités) et s'il figure dans cette liste, je passe à l'élément a suivant...
S'il est présent une fois et une seule, je le stocke dans le la liste définitive.
S'il est présent plus d'une fois
   si nb_a est impair (nombre pair + 1), je stocke a dans la liste définitive Prod (il va rester présent une fois)
   je cherche ensuite le code CLE de nb_a puis j'effectue la somme de chaque élément ce code avec a...
   ex : soit 5 nombres 13 présent. On a 5 (2,0) --> [tex]2^2+2^0[/tex] donc on fait 13+0 et 13+2 = 15
         et je rajoute 13 et 15 à la liste_produit brute... Heureusement le 13 est noté comme traité.
         Le problème ne se pose pas avec un nombre pair :
         soit cette une puissance de 2, soit c'est une somme de puissances (autre que 0) de 2...
         Dans les 2 cas, le a disparaît et n'est pas stocké...
Et ainsi de suite, de proche en proche.
On constate que la liste brute n'a pas besoin d'être trié, que ne travaillant pas avec les indices je peux "allonger" cette liste sans dommages.
Enfin, je trie ma liste_produit définitive par ordre décroissant pour affichage, puis je calcule le nombre correspondant à ce code CLE produit en sommant les "puissances" de 2 successives..

Et pour contrôle, j'affiche le produit des 2 nombres donnés au départ...
Je regarderais de nouveau plus tard, pour trouver un moyen de programmer ça plus "proprement".

@+

Dernière modification par yoshi (02-10-2014 12:04:34)


Arx Tarpeia Capitoli proxima...

Hors ligne

#3 02-10-2014 15:05:54

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 378

Re : [Python] Produit de codes CLE

Re,

Deuxième version.
Conception du passage Produit_brut --> Produit_final radicalement différent...
Affichage légèrement modifié...
Sur ce forum, figure un programme que j'avais écrit recensant des méthodes de tris différentes...
Hier, il m'est revenu en mémoire la méthode des "tris par casiers" que j'ai adaptée.
A partir des 2 codes CLES, je cherche l'exposant maximal théorique du Produit brut.
Puis je crée une liste Lst_nb_puiss ayant ce nombre + 10 (pour faire bonne mesure) de zéros.
L'index de chaque emplacement correspondra à l'exposant : le code CLE (5,4,2,1) sera stocké ainsi :
[0, 1, 1, 0, 1, 1] par ordre croissant [tex]2^0 \times 0 + 2^1 \times 1 + 2^2 \times 1 +2^3 \times 0 + 2^4 \times 1+ 2^5 \times 1[/tex]
les  0 signifient qu'aucun 0 ou 3 ne figurent dans le code CLE,
les  1 signifient qu'il y a (un un seul) 2, 4 et 5 dans ce code...
Si dans le produit brut figurait 3 fois le 4, soit CLE (5,4,4,4,2,1), cette configuration serait stockée ainsi
[0, 1, 1, 0, 3, 1] par ordre croissant.
Les éléments visibles représentent le nombre de fois qu'est présent dans le produit brut le nombre ayant pour valeur l'index...
A partir des 2 codes et des éléments i et j de chacun je calcule s = i+j, à chaque fois que cette somme s se représente, j'incrémente de 1 le nombre d'index s...
Un calcul n'est resté là que pour l'affichage : Prod_codes, le produit brut, mais il ne sert pas...
Je parcours Lst_nb_puiss avec index et valeur grâce à enumerate().
Si la valeur vaut 0 ou 1 (nb_a<2), je ne touche à rien
sinon je cherche le code CLE de nb_a.
et je stocke à l'index a la valeur nb_a%2 0 si nb_a est pair et 1 si impair...
Ensuite, je fais les additions entre a et les valeurs i de ce code CLE et si la valeur est non nulle j'ajoute 1 à chaque emplacement d'index a+i...
Le reste est sans surprise.

Mais il me vient à l'esprit qu'on doit pouvoir traiter ça en binaire...
Ce sera pour une prochaine fois...

#!/usr/bin/python
# -*- coding: UTF-8 -*-

def titre():
    print ("        *****************************")
    print ("        **                         **")
    print ("        **  Produit de codes CLE   **")
    print ("        **                         **")
    print ("        *****************************")
    print ()
    print ()
    print ()

def cle(a,l):
    code=[]
    for i, char in enumerate(a):
        if char>"0":
            code.append(l-i-1)
    return code

   
## Nombres dont on doit trouver le Code CLE ##

nb = [123125256,768648254]

#############################################
titre()
Codes=[]
print("            +-+ Recherche des codes CLE +-+\n")
for n in range(2):
    print("   ## Nombre n°",n+1)
    code=[]
    a=bin(nb[n])[2:]
    print ("Le nombre "+str(nb[n])+" en base 10")
    long=(8+len(str(nb[n])))//2
    esp=" "*long
    print (esp+"s'écrit donc")
    print (a+" en base 2")
    print ()
    print ("Son code CLE est :")
    l=len(a)
    print(str(nb[n])+"(",end="")
    code=cle(a,l)
    l=len(code)
    Codes.append(code)
    for i, char in enumerate(code):
        print(char,end="")
        if i<l-1:
            print (",",end="")
    print(")"+"\n\n")
   
print("            +-+ Produit des codes CLE +-+\n")
Prod_codes,Prod, Traite=[],[],[]
fin=max(Codes[0])+max(Codes[1])+10
Lst_nb_puiss=[0]*fin
for i in Codes[0]:
    for j in Codes[1]:
        Lst_nb_puiss[i+j]+=1
        Prod_codes.append(i+j)

Prod_codes.sort(reverse=True)    
print ("    *** BRUT ***")
print (Prod_codes,"\n")
for a,nb_a in enumerate(Lst_nb_puiss):
    if nb_a<2:
        pass
    else:  
        n_bin=bin(nb_a)[2:]
        lg=len(n_bin)
        code=cle(n_bin,lg)
        Lst_nb_puiss[a]= nb_a%2
        for i in code:
            if i>0:
                Lst_nb_puiss[a+i]+=1
           
fin-=1
for a in range(fin,-1,-1):
    nb_a=Lst_nb_puiss[a]
    if nb_a>0:
        Prod.append(a)
       
print ("    *** FINAL ***")
print(Prod,"\n")
P=0
print ("Le nombre correspondant à ce code CLE est :")
for i in Prod:
    P+=2**i

print (P,"\n")
print ("Vérification :" )
print (nb[0],"*",nb[1],"=",nb[0]*nb[1])

Sortie :

        *****************************
        **                         **
        **  Produit de codes CLE   **
        **                         **
        *****************************



            +-+ Recherche des codes CLE +-+

   ## Nombre n° 1
Le nombre 123125256 en base 10
        s'écrit donc
111010101101011111000001000 en base 2

Son code CLE est :
123125256(26,25,24,22,20,18,17,15,13,12,11,10,9,3)


   ## Nombre n° 2
Le nombre 768648254 en base 10
        s'écrit donc
101101110100001010010000111110 en base 2

Son code CLE est :
768648254(29,27,26,24,23,22,20,15,13,10,5,4,3,2,1)


            +-+ Produit des codes CLE +-+

    *** BRUT ***
[55, 54, 53, 53, 52, 52, 51, 51, 51, 50, 50, 49, 49, 49, 49, 48, 48, 48, 48, 47, 47, 47, 47, 46, 46, 46, 46, 46, 45, 45, 45, 44, 44, 44, 44, 44, 44, 43, 43, 42, 42, 42, 42, 42, 41, 41, 41, 41, 41, 40, 40, 40, 40, 40, 40, 39, 39, 39, 39, 39, 39, 39, 38, 38, 38, 38, 38, 38, 37, 37, 37, 37, 37, 37, 37, 36, 36, 36, 36, 36, 35, 35, 35, 35, 35, 35, 35, 35, 34, 34, 34, 34, 33, 33, 33, 33, 33, 33, 32, 32, 32, 32, 32, 32, 31, 31, 31, 31, 30, 30, 30, 30, 30, 30, 30, 29, 29, 29, 29, 29, 28, 28, 28, 28, 28, 28, 27, 27, 27, 27, 27, 27, 27, 26, 26, 26, 26, 26, 26, 25, 25, 25, 25, 25, 25, 25, 24, 24, 24, 24, 23, 23, 23, 23, 23, 23, 22, 22, 22, 22, 22, 21, 21, 21, 21, 20, 20, 20, 20, 19, 19, 19, 19, 18, 18, 18, 18, 17, 17, 17, 16, 16, 16, 16, 16, 15, 15, 15, 15, 14, 14, 14, 14, 14, 13, 13, 13, 13, 13, 12, 12, 12, 11, 11, 10, 8, 7, 6, 5, 4]

    *** FINAL ***
[56, 54, 52, 45, 44, 43, 41, 39, 36, 34, 33, 32, 29, 26, 25, 24, 21, 20, 19, 18, 17, 16, 13, 10, 8, 7, 6, 5, 4]

Le nombre correspondant à ce code CLE est :
94640013047703024

Vérification :
123125256 * 768648254 = 94640013047703024

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de cette opération? 3*3=

Pied de page des forums