7

合計が30になる5つの1桁の繰り返しのない数字のすべてのセットを検索したいとします...[9,8,7,5,1]、[9,8,7]になります、4,2]、[9,8,6,4,3]、[9,8,6,5,2]、[9,7,6,5,3]、および[8,7,6、 5,4]。これらの各セットには、5つの繰り返しのない数字が含まれ、合計で30になります。

どんな助けでも大歓迎です。私が使用するための単なる出発点でさえ素晴らしいでしょう。

私は1つの方法を思いつきました。これは、長い道のりのようです。すべての一意の5桁の数字（12345、12346、12347など）を取得し、数字を合計して、指定された合計と等しいかどうかを確認します（例：30）。含まれている場合は、一致する可能性のあるセットのリストに追加します。

私は個人的なプロジェクトのためにこれを行っています。これは、実際にすべてを一度に解決することなく、カックロのパズルを解くのに役立ちます。ええ、それは浮気かもしれませんが、それは...それはそれほど悪くはありません...：P

4

8 に答える 8

2

素朴なアプローチは、変数を から12345までインクリメントし、98765一意の数字があり、数字の合計が である場合にのみ選択することです30。

for($i=12345;$i<98765;$i++) {
    $arr = preg_split('//',strval($i));
    if(count(array_unique($arr)) == count($arr) && array_sum($arr) == 30)
        echo $i."\n";
}

実施例

于 2010-05-04T02:07:05.420 に答える
1

ここから組み合わせコードを使用する

foreach(new Combinations("123456789", 5) as $p)
    $r[array_sum(str_split($p))] .= "$p ";
print_r($r);

結果

[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

かわいくないですか？

于 2010-05-04T09:35:29.793 に答える
1 
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";
    }
}
于 2010-05-04T02:16:34.977 に答える
1

これはおそらく十分に高速です。

<?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";
        }
}

?>
于 2010-05-04T02:55:06.733 に答える
0

これにはアルゴリズムがあり、おそらく他の人から提供されることはわかっていますが、簡単に説明すると、21〜29になる4桁の数字のすべてのセットを探します（あなたが0を数字として数えずに）、30-（合計）が数字の1つであるものを削除します。

もっと早く何かを試したい場合は、45678から始めて、1桁に1を足し、別の桁から1を引くことによって、それを段階的に変更することを考えます。しかし、最終的にどれだけうまくいくかはわかりません。

于 2010-05-04T01:51:56.990 に答える
0

問題の答えを f(30,5,1) と書きましょう。30 は目的の合計を示し、5 は目的の合計に追加する必要がある桁数を示し、1 は最小許容桁数を示します。この形式では、問題を再帰的に解くことができます。例えば、

f(30,5,b) = 合計(i = 1..9) f(30-i,4,i+1)

私たちは、あなたが求める組み合わせで発生する最小値 i を効果的に使い果たしています。i の可能な最大値 (数字の最小値であるため、大きすぎることはありません) についてより慎重に検討し、適切な救済条件を追加すると、非常に迅速な解決策が得られます。

于 2010-10-29T12:10:01.173 に答える
0

これはサブセットサム問題として知られていると思います：

http://mathworld.wolfram.com/SubsetSumProblem.html

于 2010-05-04T13:44:47.530 に答える