Discussion :

[blenderiste09]

Bonjour,
Avec des amis nous participons au Project Euler. Pour ceux qui ne connaîtraient pas, c'est tout simplement des problèmes mêlant informatique et mathématiques.
Nous en sommes au problème 88 et nous avons bien progressé, cependant nous sommes face à une petite difficulté. Je précise que l'objet de ma question n'est pas d'avoir une réponse toute faite, mais simplement d'avoir une piste ou des conseils.

L'algo que nous avons imaginé comporte cette partie:

Pour un k donné, on génère des listes d'au plus k chiffres dont le produit P doit être k <= P <= 2k
Exemple, pour k = 3 : (6), (5), (4), (3), (3, 2), (2, 2). Il n'est pas forcément obligatoire d'avoir des listes de tailles différentes si cela rend l'algorithme trop compliqué. Les listes peuvent toutes être composées de 3 chiffres en remplissant les chiffres manquants par des 1. Je pourrais par la suite exploiter ces listes avec une fonction supplémentaire.

Le soucis est que je n'arrive pas à trouver un algorithme efficace qui permettrait de générer ces listes. Sur le papier j'ai ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
Pour k = 2:
<div style="margin-left:40px">4 * 4 n'est pas dans les bornes : (4, 4) n'est pas une liste valide
4 * 3 ..
4 * 2 ..
4 * 1 est dans les bornes : (4, 1) est une liste valide
 
3 * 3 ...
...
Au final, (4, 1) (3, 1) (2, 2) (2, 1) sont les listes valides pour k = 2</div>

J'ai l'impression que la solution est plutôt simple, sur papier ça fonctionne, mais je n'arrive pas à généraliser pour n'importe quel k, sachant que ce k doit varier entre 2 et 12 000.

J'ai pensé à utiliser un nombre de k chiffres que j'incrémenterai de 1 à chaque tour de boucle et que je pourrais convertir en caractères individuels. Cela me générerai entre autres les listes dont j'ai besoin, mais aussi des listes qui ne remplissent pas les conditions requises. Le temps d'exécution serait médiocre...


Auriez-vous des conseils ou des pistes à me donner ?
Merci d'avance.

[tatayo]

Bonjour,

Pour un k donné, on génère des listes d'au plus k chiffres dont le produit P doit être k <= P <= 2k
Exemple, pour k = 3 : (3); (3, 2); (2, 2); (2, 2, 2).

Je vois déjà un problème ici, à moins que je n'ai pas compris.
Si je prends le dernier exemple, le produit vaut 8 (2*2*2), alors qu'il doit être compris entre 3 et 6 (3 et 2*3).

Tatayo.

[blenderiste09]

Effectivement, j'ai fait une erreur. C'est corrigé, merci

[tbc92]

Prenons k = 100 pour l'exemple.
On va considérer que la solution (28,3) et la solution (3,28) sont considérées comme 2 solutions différentes, on les veut toutes les 2.
On va considérer aussi que le nombre 1 est exclu de l'étude. Les solutions (3,1,28) ou (3,28,1) ou (1,1,1,3,1,1,1,1,28,1,1,1,1,1,1,1,1) ne nous intéressent pas ; Ces 3 solutions se résument à (3,28).

Du coup, je te propose de chercher toutes les solutions avec un seul nombre (si k=100, il y en a 199, chacun des nombres entre 2 et 200).
Puis à partir de ce listing, chercher toutes les solutions avec 2 nombres.
Puis à partir des solutions avec 2 nombres, chercher toutes les solutions avec 3 nombres... etc etc ...
Pour k=100, des solutions avec 7 nombres, il y en a peu : (2,2,2,2,2,2,2), (2,2,2,2,2,2,3), (2,2,2,2,2,3,2) et les autres permutations avec 6 fois le nombre 2, et 1 fois le nombre 3.

Ici, je recherche toutes les combinaisons dont le produit est inférieur ou égal à 2*k ; je ne prend pas la contrainte k<=P
Comme ça, je peux réutiliser les combinaisons avec n éléments pour chercher les combinaisons avec n+1 éléments.

A partir de ce recensement, afficher uniquement les combinaisons qui vérifient en plus la condition k<=P, c'est simple.

Même pour k=12000, on va avoir des listes de longueur très raisonnable ; pour k=12000, ln(24000)/ln(2) = 14.55, et donc on aura au max 14 nombres dans notre listes (2*2*2*2 ... répété 15 fois, ça fait plus que 24000)

Ici, une piste, c'est la récursivité (faire une procédure qui s'appelle elle-même)

[Flodelarab]

Bonjour

Pour ouvrir tes horizons, je propose le contraire.

1. Considère 2 sacs. Un sac de solutions à creuser, et un sac de solutions finies.
2. Tu prends une solution à creuser ...
3. ... si la quantité max de nombres n'est pas atteinte ...
4. tu rajoutes un nombre.
5. Si le résultat est supérieur à 2*k, tu bazardes la solution à creuser.
6. Si le résultat est entre k et 2*k, tu mets une version dans le sac des solutions et une version dans le sac des solutions à creuser.
7. Si le résultat est inférieur à k, tu mets cette version dans le sac des solutions à creuser.
8. Quand tu n'as plus rien à creuser, c'est fini, et tu as toutes tes solutions dans le sac des solutions.
9. Sinon (plus de places), tu bazardes la solution et tu reviens à l'étape 2.

[Nebulix]

Chacun de tes produits pourra s'écrire 2^x2*3^x3*5^x5*7^x7. Les nombres premiers de plus d'un chiffre sont exclus.Les facteurs 2^2 et 3^2 peuvent aussi s'écrire 4 et 9, 2^3 peut s'écrire de 4*2,2*4 ou 8.
Il faut faire une quadruple boucle où x2 varie de 0 à trunc(ln(k)/ln(2)) (13 si k=12000), x3 de 0 à trunc( ( ln(k)-x2*ln(2)) /ln(3)), etc