Il y a quelques années, un ami à moi m'avait conçu un algo me permettant sur la base de 3 données (somme à obtenir, liste de chiffres, et nombre de chiffres à prendre), un script me permettant de calculer toutes les additions possibles avec le nombre de chiffres ciblé et la somme donnée.
Cela donnait ceci.
<?php
if($_POST['submit'])
{
set_time_limit(0);
extract($_POST);
if(!empty($Somme) && !empty($nombre_el) && !empty($liste_nombres))
{
/** nombre a trouver **/
$n = $Somme;
/** nombre d'element de la liste a utiliser **/
$it = $nombre_el;
/** liste des éléments -- elle prend tout, même des negatifs, même 0, elle l'utilise **/
//$nums = array(1,2,8,7,3,-1,24, 44, 12,0,4,2,7,5,3,13,14,15,16,3);
$nums = $liste_nombres;
$total = 0;
/**
* on vire les doublons (evite d'avoir deux fois le même résultat avec parametre different utilisé)
* on trie en ordre ascendant, c'est plus jolie à l'affichage
*/
$nums = array_unique($nums);
rsort($nums);
/**
* si on l'appel mal, pas la peine de continuer
*/
if (count($nums) < $it || $it <= 0 || $n <= 0) {
die('Not enough number or some other stupid errors');
}
/**
* tableau qui va contenir les positions dans les differents elements
* (position du nombre 1, du nombre 2, etc ...)
*/
$my_pos = array();
/** on met les positions par defaut: les premiers hciffres qui sortent **/
for ($i = 0; $i < $it; $i++) {
array_push($my_pos, $i);
}
/**
* boucle principale, s'execute tant que la première position (le premier element)
* n'a pas parcourue toute la la liste
*/
while ($my_pos[0] < count($nums)) {
$bak_pos = $my_pos; /** copie de nos positions pour les restaurer **/
/**
* on fait tourner le dernier nombre et uniquement lui (si 3 element, resultat de la
* forme x + y + z, on fait tourner z) de sa valeur atcuelle a la derniere de la
* liste
*
* a chaque passage, on remplie notre liste de numeros actuelle, et on regarde si le
* resultat convient
*/
while ($my_pos[count($my_pos) - 1] < count($nums)) {
$t_nums = array();
/** pour chaque element qu'on a positionné, et qui n'est pas encore dans la liste **/
for ($i = 0; $i < count($my_pos) && (array_search($nums[$my_pos[$i]], $t_nums) === false); $i++) {
array_push($t_nums, $nums[$my_pos[$i]]);
}
if (count($t_nums) == $it /** au cas où on a zappé un chiffre avec le array_search au dessus **/
&& array_sum($t_nums) == $n) {
echo implode(' + ', $t_nums).'<br />'; /** on a un resultat valide **/
$total++;
}
$my_pos[count($my_pos) - 1]++;
}
/**
* on remonte en marche arrière jusqu'au dernier qui n'a pas atteint la fin, et on
* l'increment. D'abord y, puis x donc.
*
* après ça on restaure ceux suivant a leur etat d'origine.
* (si on trouve x en etat non final, on l'increment et on replace x et y a leur position
* d'origine)
*/
for ($i = (count($my_pos) - 1); $i >= 0; $i--) {
/** si on a déjà tout changé (premier element en position finale) on sort a terminé **/
if ($i == 0 && $my_pos[$i] == (count($nums) - 1)) {
break 2;
}
if ($my_pos[$i] < (count($nums) - 1)) { /** on est pas en position finale **/
$my_pos[$i]++;
for ($j = ($i + 1); $j < count($my_pos); $j++) { /** on restaure tout les suivants **/
$my_pos[$j] = $bak_pos[$j - 1] + 1;
}
break;
}
}
}
/**
* Les choses qu'on peut améliorer:
*
* - Je calcul beaucoup trop de choses là. A chaque fois que je reset mes chiffres, je les remet
* a leur positions d'origine, même si elle est dépassée. Par exemple (1,2,3,4,5), trouver 10 en
* trois chiffres, je remet toujours le 2eme element sur le chiffre "2", même si le premier y est
* (alors que je devrais le placer sur 3, puis sur 4 quand le premier est sur 3, etc ..)
* - Je bouge tout les elements jusqu'à la fin. Dans le même exemple qu'au dessus, je bouge toujours
* l'element 2 jusqu'à la fin jusque sur le 5, alors qu'il peut s'arreter au 4 (l'element deux n'aura
* jamais 5, ce sera forcement l'element 3 ...)
* - Vitesse: les array_search, array_sum et autre ça va bien 5 minutes poru la demo mais un buffer dynamique
* c'est quand même vingt fois plus rapide.
* - plein d'autres trucs mais je vais aller me pieuter
*/
}
else
{
echo 'Tous les champs ne sont pas remplis !!';
}
}
?>
Le script me convenait parfaitement mais j'ai un paramètre de plus à rajouter et je ne suis plus en contact avec la personne depuis quelques temps maintenant...
Quelqu'un pourrait il se pencher dessus svp (pas tous les jours que l'on a un peu d'algo à résoudre, ca peut être un ptit défi personnel :lala:)
Actuellement, il m'autorise seulement une fois le même nombre, je ne peux donc pas faire pour obtenir 15 avec 3 chiffres (5 + 5 + 5), j'aimerai avoir cette possibilité, j'ai testé de modifier mais mis à part une boucle me gelant le pc j'ai rien obtenu de concret...
MERCI d'avance.
)