Disons que je souhaite trouver tous les ensembles de 5 numéros à simple chiffre et non répétitif qui ajoutent jusqu'à 30 ... je finirais avec [9,8,7,5,1], [9, 8,7,4,2,2] [9,8,6,4,3], [9,8,6,5,2], [9,7,6,5,3] et [8,7 , 6,5,4]. Chacun de ces ensembles contient 5 chiffres non répétés qui ajoutent jusqu'à 30, la somme donnée.
Toute aide serait grandement appréciée. Même juste un point de départ pour que je puisse utiliser serait génial.
Je suis venu avec une méthode, qui semble être une longue façon d'y aller: obtenez tous les nombres à 5 chiffres uniques (12345, 12346, 12347, etc.), additionnez les chiffres et voyez s'il est égal à la étant donné somme (par exemple 30). Si tel est le cas, ajoutez-le à la liste des ensembles de correspondance possibles.
Je le fais pour un projet personnel, qui m'aidera à résoudre des énigmes kakuro sans résoudre le tout à la fois. Ouais, ça peut être tricher, mais c'est ... ce n'est pas si mauvais ...: P
8 Réponses :
Je sais qu'il y a des algorithmes pour cela, et ils seront probablement fournis par d'autres personnes, mais voici une simplification rapide que vous pouvez faire: recherchez tous les ensembles de 4 chiffres simples qui ajoutent jusqu'à 21-29 (je suppose que Vous ne comptez pas 0 comme un chiffre) et simplement éliminer ceux pour lesquels 30- (la somme) est l'un des chiffres.
Si je voulais essayer quelque chose de plus rapide, je penserais à partir de 45678 et à changer progressivement cela en ajoutant 1 à un chiffre et en soustrayant 1 d'un autre chiffre. Je ne sais pas à quel point cela fonctionnerait bien à la fin, cependant.
Je suppose qu'une approche serait de trouver un ensemble de correspondance, puis d'ajouter / soustraire des chiffres symétriquement pour trouver d'autres ensembles.
Une approche naïf serait d'incrémenter une variable de 12345 jusqu'à 98765 et pour le sélectionner uniquement s'il a des chiffres uniques et une somme des chiffres est 30 < / code>:
J'ai rationalisé votre exemple, Unicornaddict: ideone.com/cuaah Je pense en fait que c'est la bonne voie . Tout ce que j'ai besoin de faire est de me débarrasser des doublons (comme 15789 et 15798, qui contiennent les mêmes chiffres) en triant les chiffres et en vérifiant le tableau de tri pour voir s'il a été renvoyé précédemment.
Bam: ideone.com/y91zx fonctionne parfaitement, merci principalement à votre réponse, Unicornaddict! Merci beaucoup! Tous dans moins de 20 lignes, aussi. :RÉ
Faire le array_sum d'abord dans le conditionnel est probablement plus rapide, compte tenu de la création d'une matrice unique.
Bonne idée! Cela ne devrait pas faire des opérations coûteuses qu'il n'a pas besoin de faire. Merci!
Itération de 56789 ne serait-il pas suffisant? Je crois que tous les chiffres ci-dessus 56789 seront une permutation d'un nombre inférieur à 56789. Cela devrait couper la longueur de l'itération en deux. De plus, je pense que l'état de fin de la boucle de la boucle doit être i $ i <= , pas $ i << / code>, vous voudrez être sûr de tester le numéro de fin.
function sumOfDigits($num) {
$str = "{$num}";
$sum = 0;
for ($i=0;$i<strlen($str);$i++) {
$sum += (int)substr($str, $i, 1);
}
return $sum;
}
function hasDuplicateDigits($num) {
$str = "{$num}";
$pieces = array();
for ($i=0;$i<strlen($str);$i++) {
$pieces[] = substr($str, $i, 1);
}
return (count(array_unique($pieces)) != strlen($str));
}
// if you prefer the opposite function
function hasAllUniqueDigits($num) {
return (!hasDuplicateDigits($num));
}
$numbers = range(10000, 99999);
foreach ($numbers as $num) {
if ( !hasDuplicateDigits($num) && (sumOfDigits($num) == 30)) {
print $num . "\n";
}
}
Certains d'entre eux sont intégrés à PHP si je traquis des tableaux. Voir Ideone.com/cuaah pour plus d'informations. Merci de votre réponse! Comme je ne connaissais pas la fonction de gamme (), cela vous aidera. :RÉ
Ceci est probablement suffisamment rapide:
<?php
$digitCount = 5;
$sum = 30;
function getAnswer($b)
{
$a = "";
$i = 1;
while ($b)
{
if ($b & 1) $a .= "$i ";
$b >>= 1;
++$i;
}
return $a;
}
for ($b = 0; $b < 512; ++$b)
{
$v = 0;
$c = 0;
$i = 1;
$s = $b;
while ($s)
{
if ($s & 1)
{
if (++$c > $digitCount) continue 2;
$v += $i;
}
$s >>= 1;
++$i;
}
if ($c == $digitCount && $v == $sum)
{
echo getAnswer($b)."\n";
}
}
?>
Utilisation du code de combinaisons de ici
[15] => 12345 [16] => 12346 [17] => 12347 12356 [18] => 12348 12357 12456 [19] => 12349 12358 12367 12457 13456 [20] => 12359 12368 12458 12467 13457 23456 [21] => 12369 12378 12459 12468 12567 13458 13467 23457 [22] => 12379 12469 12478 12568 13459 13468 13567 23458 23467 [23] => 12389 12479 12569 12578 13469 13478 13568 14567 23459 23468 23567 [24] => 12489 12579 12678 13479 13569 13578 14568 23469 23478 23568 24567 [25] => 12589 12679 13489 13579 13678 14569 14578 23479 23569 23578 24568 34567 [26] => 12689 13589 13679 14579 14678 23489 23579 23678 24569 24578 34568 [27] => 12789 13689 14589 14679 15678 23589 23679 24579 24678 34569 34578 [28] => 13789 14689 15679 23689 24589 24679 25678 34579 34678 [29] => 14789 15689 23789 24689 25679 34589 34679 35678 [30] => 15789 24789 25689 34689 35679 45678 [31] => 16789 25789 34789 35689 45679 [32] => 26789 35789 45689 [33] => 36789 45789 [34] => 46789 [35] => 56789
Je crois que cela est connu sous le nom de problème du sous-ensemble:
Écrivons F (30,5,1) pour la réponse à votre problème. Le 30 indique la somme souhaitée, le 5 indique le nombre de chiffres qui doivent ajouter à la somme souhaitée et le 1 indique le chiffre minimal acceptable. Dans ce formulaire, vous pouvez résoudre le problème de manière récursive. Par exemple,
f (30,5, b) = somme (i = 1..9) f (30-i, 4, i + 1)
Nous sommes effectivement épuisants sur la valeur la plus basse que je produisait dans la combinaison que vous recherchez.
Si vous pensez plus avec précaution sur la valeur maximale possible de I (elle ne peut pas être trop grande puisqu'il s'agit du minimum des chiffres) et ajoutez quelques conditions de sauvetage appropriées, vous aurez une solution très rapide.
La somme d'impression des nombres forment un tableau de n chiffres sans chiffres en double. Par example INPUT: [100, 213, 414, 555, 62, 321]
sortie: 596 (c'est-à-dire 213 + 62 + 321)
Votre réponse pourrait être améliorée avec des informations justificatives supplémentaires. S'il vous plaît Modifier Pour ajouter des détails supplémentaires, tels que les citations ou la documentation, de sorte que d'autres puissent confirmer que votre réponse est correcte. Vous pouvez trouver plus d'informations sur la façon d'écrire de bonnes réponses dans le centre d'aide .