11

問題

定義

  • 各要素を一度しか使用しない要素からこの数体系で自然数を書き込むことができる場合、自然数Nを数体系の数集合の書き込み可能数(WN) と定義しましょう。「書かれた」のより厳密な定義: - ここでは連結を意味します。ここに画像の説明を入力MUここに画像の説明を入力CONCAT
  • 自然数が andの WN 数であり、andの CAN数である場合、自然数を数値システムの記号セットの連続到達可能数N(CAN)として定義しましょう(別の定義は、すべての数がおよび)の WN 。より厳密:ここに画像の説明を入力MUMN-1UMNUM0 .. NUMここに画像の説明を入力

問題

自然数の集合があるとしましょうS: ここに画像の説明を入力(ゼロを自然数として扱っています) と自然数M, M>1. U問題は、与えられたとの最大 CAN (MCAN) を見つけることMです。指定されたセットU には重複が含まれる可能性がありますが、各重複は複数回使用できませんでした (つまり、U{x, y, y, z} が含まれている場合、それぞれyが 0 回または 1 回y使用される可能性があるため、0..合計2回）。数値システムでもU有効であることが期待されます(つまりM、シンボルを含むことはできず、if のいずれのメンバーにも含めることはできません)。そして、当然のことながら、 のメンバーは数値であり、記号ではありません(したがって、89M=8UM11M=10) - そうでなければ、問題は簡単です。

私のアプローチ

現在の番号がCANであるかどうかを単純にチェックする単純なアルゴリズムを考えています。

  1. 0WN が指定されているUかMどうかを確認します。2 に進む: これで完了です。MCAN は null です
  2. 1WN が指定されているUかMどうかを確認します。3 に進む: これで完了です。MCAN は次のとおりです。0
  3. ...

したがって、このアルゴリズムはこのすべてのシーケンスを構築しようとしています。この部分は改善できないと思いますが、できるのでしょうか？ここで、number が WN かどうかを確認する方法を説明します。これはある種の「総当たり攻撃」でもあります。私はPHP関数でM=10（実際、文字列を扱っているので、他のものは問題ではありません）それを認識しています：M

//$mNumber is our N, $rgNumbers is our U
function isWriteable($mNumber, $rgNumbers)
{
   if(in_array((string)$mNumber, $rgNumbers=array_map('strval', $rgNumbers), true))
   {
      return true;
   }
   for($i=1; $i<=strlen((string)$mNumber); $i++)
   {
      foreach($rgKeys = array_keys(array_filter($rgNumbers, function($sX) use ($mNumber, $i)
      {
         return $sX==substr((string)$mNumber, 0, $i);
      })) as $iKey)
      {
         $rgTemp = $rgNumbers;
         unset($rgTemp[$iKey]);
         if(isWriteable(substr((string)$mNumber, $i), $rgTemp))
         {
            return true;
         }
      }
   }
   return false;
}

-つまり、一部を試してから、残りの部分が再帰で記述できるかどうかを確認します。書き込めない場合は、 の次のメンバーを試していますU。ここは改善点だと思います。

仕様

ご覧のとおり、アルゴリズムは前にすべての数値を構築しN、それらが WN であるかどうかを確認しようとしています。しかし、唯一の問題は、MCAN を見つけることです。つまり、問題は次のとおりです。

  • ここでは建設的なアルゴリズムが過剰である可能性がありますか? はいの場合、他にどのようなオプションを使用できますか?
  • Unumber が指定されたandの WN であるかどうかを判断するより迅速な方法はありMますか? (前のポイントに肯定的な答えがある場合、このポイントは意味をなさない可能性があり、前にすべての数値を構築してチェックするわけではありませんN)。

サンプル

U = {4, 1, 5, 2, 0}
M = 10

次に、MCAN = 2 (3 に到達できませんでした)

U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11}
M = 10

次に、MCAN = 21 (合計で 2 つのシンボル22がないため、以前のすべてに到達できます)。2

4

3 に答える 3

2

私が行った再帰手順は次のとおりです。

  1. 数字の文字列がアルファベットで利用できる場合は、使用済みとしてマークし、すぐに戻ります
  2. 数字列の長さが 1 の場合、失敗を返します
  3. 文字列を 2 つに分割し、それぞれの部分を試してください

これは私のコードです:

$u = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11];

echo ncan($u), "\n"; // 21

// the functions

function satisfy($n, array $u)
{
        if (!empty($u[$n])) { // step 1
                --$u[$n];
                return $u;
        } elseif (strlen($n) == 1) { // step 2
                return false;
        }

        // step 3
        for ($i = 1; $i < strlen($n); ++$i) {
                $u2 = satisfy(substr($n, 0, $i), $u);
                if ($u2 && satisfy(substr($n, $i), $u2)) {
                        return true;
                }
        }

        return false;
}

function is_can($n, $u)
{
        return satisfy($n, $u) !== false;
}

function ncan($u)
{
        $umap = array_reduce($u, function(&$result, $item) {
                @$result[$item]++;
                return $result;
        }, []);
        $i = -1;

        while (is_can($i + 1, $umap)) {
                ++$i;
        }

        return $i;
}
于 2013-09-21T01:58:25.390 に答える
2

0からまでの桁数の桁数をハッシュしm-1ます。それより大きい数値mは、1 つの繰り返し数字で構成されます。

MCAN はdigit、特定の数字のすべての組み合わせをdigit count構築できない最小のもの (たとえば、X000、X00X、X0XX、XX0X、XXX0、XXXX)、または(digit count - 1)ゼロの場合 (たとえば、4 つのすべての組み合わせ) によって制限されます。数字、組み合わせは 3 つのゼロにのみ必要です。ゼロ カウントがゼロの場合、MCAN はヌルです)。桁数は昇順で評価されます。

例:

1. MCAN (10, {4, 1, 5, 2, 0})
   3 is the smallest digit for which a digit-count of one cannot be constructed.
   MCAN = 2

2. MCAN (10, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11})
   2 is the smallest digit for which a digit-count of two cannot be constructed.
   MCAN = 21

3. (from Alma Do Mundo's comment below) MCAN (2, {0,0,0,1,1,1})
   1 is the smallest digit for which all combinations for a digit-count of four
   cannot be constructed.
   MCAN = 1110

4. (example from No One in Particular's answer) 
   MCAN (2, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1111,11111111})
   1 is the smallest digit for which all combinations for a digit-count of five
   cannot be constructed.
   MCAN = 10101
于 2013-09-20T13:30:04.747 に答える