resolution d'équation x0*x1...=K

[invite99e93d4e]

Bonsoir,
Un ami m'a donné un défi que j'aimerai bien résoudre mais qui me pose problème même après certaine recherches d'où la sollicitude de votre aide(en espérant que la question ne vous semble pas trop stupide de la part d'un lycée:

Le but est de trouver un mot de maximum 40 caractères ou moins qui sont traduit en nombre grâce à la table ASCII(le mot ne contient pas de majuscules mais peut contenir des espaces et autres caractères spéciaux qui sont eux aussi vu comme des caractères traduit en un nombre).
Donc chaque caractère est associé à un nombre grâce à la table ASCII : par exemple le caractère 'a' se traduit par 97.
On sait aussi que la multiplication de tous ces nombres dont chaqu'un représente un caractère doit être égal à K(où K est un réel connu)
(par exemple si le mot fait 40 caractère,soit le maximum, on aurait u₀ * u₁ *...*u₃₉=K où u_i est un nombre qui représente un caractère)
existe t-il des méthodes permettant de connaître ces caractères ou est ce que c'est plus du type "on va essayer toutes les combiaison"^^?

merci d'avance pour vos futur réponses
-----

[invite99e93d4e]

un lien pour la table ASCII(wikipedia)

[g_h]

Si on se restreint à la table ASCII standard (pas la table "étendue") tu as donc tous les nombres entre 0 et 127;

Je pense que pour résoudre ce problème il faut étudier la décomposition de K en produit de nombre premiers (pas forcément distincts) :

Si l'un des est supérieur ou égal à 128, tu peux déjà dire que l'équation ne peut pas avoir de solution.

En suite il faut étudier la possibilité de grouper ces facteurs de sorte à transformer l'expression en produit de n nombres inférieurs ou égaux à 127 ( donc)

Un algorithme "basique" serait :
soit x[40] un tableau de nombres initialisé à 1, .... 1
i = 1
j=1

tant que i <= 40 et j <= k
tant que j <= k et x[i]*p_j < 128
x[i] <- x[i]*p_j
j <- j+1
fin tant que
i <- i+1
fin tant que

en éliminant les 1 qui restent dans x, tu obtiens une suite de caractères qui rentrent bien dans la table ascii standard (sauf si i a dépassé 40)

Après cet algorithme n'assure pas de trouver la solution (le cas ou i dépasse 40), même si elle existe, car cela peut à priori dépendre de l'ordre choisi pour les p_j. C'est peut-être là que ça devient tendu, faut-il essayer tous les ordres possibles, je ne sais pas, j'ai rien qui me vient à l'esprit

[invitea0b22930]

Il n'est pas difficile de factoriser K avec des nombres susceptibles de représenter des caractères. Il n'est pas difficile non plus de comparer les résultats obtenus avec les mots d'un dictionnaire si le dictionnaire est organisé en arbre.
Le problème majeur est le suivant:
Il faut tester a priori toutes les permutations possibles, et pour un mot de 40 caractères ....
Voici un exemple simple en langage python de programme qui factorise et traduit, sans permuter ni rechercher dans un dictionnaire.

# -*- coding: utf-8 -*-
codes=[97+i for i in range(0,26)] #les codes des lettres minuscules

def test(n):
    """retourne le premier diviseur de n dans codes s'il y en a-retourne 0 sinon"""
    for i in codes:
        if n%i==0:
            return i
    return 0

def facto(n):
    """fonction récursive retournant la décomposition de n en produits de facteurs simples dans codes"""
    if test(n)==0:
        return [] #aucun diviseur trouvé
    else: #dans le cas contraire
        i=test(n) #prendre le diviseur trouvé
        L=facto(n/i) #appel récursif
        return [i]+L

def mot(L):
    """reconstitue un mot à partir d'une liste de codes"""
    if L==[]:
        return ""
    else:
        return chr(L[0])+mot(L[1:])


print mot(facto(103691448)) #va afficher 'abel'

[A voir en vidéo sur Futura]

[invitea0b22930]

En y réfléchissant bien (enfin mieux...), l'ensemble des lettres ayant été détecté, il n'est pas nécessaire de générer toutes les permutations de celles-ci. Il suffit de détecter, dans le dictionnaire à structure arborescente, les mots qui contiennent ces lettres. C'est un problème de bien moins grande complexité, du point de vue du temps de calcul.

[invite99e93d4e]

ça fait longtemp que je n'est pas vu de programme python mais il m'en reste de bon souvenir aparement
merci à vous deux pour ces réponses.

[g_h]

Si on prend tous les caractères de 0 à 127, il y a un souci : si je prends le nombre 15, je peux le décomposer en 3*5 et en 15, donc 2 mots possible (à l'ordre près)

Ramenons la limite de 40 caractères à quelque chose de plus petit, comme 3, pour bien voir le problème.
Notre tableau codes vaut [0, 1, ..., 127]
Prenons K = 216 = 6*6*6 = 3*2*3*2*3*2

Ton algorithme, AbouAntoun, va renvoyer la liste [2,2,2,3,3,3], ce qui est au dela de la limite de 3 caractères.
Car ici il faudrait renvoyer [6,6,6], ou [18, 2, 6], ou [18, 1, 12] et encore plein d'autres possibilités.
Mais tout ça pour dire qu'en général, c'est un vrai problème que d'essayer de remplir une liste de taille limitée (<= 40) avec des facteurs eux aussi de taille limitée (<= 127), et qu'une résolution complète du problème doit faire intervenir pas mal d'arithmétique pas forcément élémentaire. Dans mon exemple, on n'a pas de mal à trouver plein de listes qui marchent bien, mais ça devient beaucoup plus complexe quand les facteurs deviennent grands, et la liste grande.

[invitea0b22930]

Ton algorithme, AbouAntoun, va renvoyer la liste [2,2,2,3,3,3], ce qui est au dela de la limite de 3 caractères.

Non, parce que je commence à 97. donc je ne peux avoir que des décompositions 'simples' (le produit de deux codes de minuscules n'est pas le code d'une minuscule).

[g_h]

Non, parce que je commence à 97. donc je ne peux avoir que des décompositions 'simples' (le produit de deux codes de minuscules n'est pas le code d'une minuscule).

Oui oui je suis d'accord, c'est bien pour ça que j'ai dit :

Si on prend tous les caractères de 0 à 127, il y a un souci

car à là base le problème ne se limitait pas aux lettres