Modification d'un algo de calculs de somme
Posté : 18 mai 2011, 20:28
Bonjour,
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.
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.
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.
)