3

PHPでは、与えられた

  • 最終的な文字列の長さ
  • 使用できる文字の範囲
  • 最小連続繰り返し回数可能

これらの基準に適合する一致の数をどのように計算できますか?
より良い絵を描くために…</p> 

$range = array('a','b','c');
$length = 2; // looking for 2 digit results
$minRep = 2; // with >=2 consecutive characters
// aa,bb,cc = 3 possibilities

別のもの：

$range = array('a','b','c');
$length = 3; // looking for 3 digit results
$minRep = 2; // with >=2 consecutive characters
// aaa,aab,aac,baa,caa
// bbb,bba,bbc,abb,cbb
// ccc,cca,ccb,acc,bcc
// 5 + 5 + 5 = 15 possibilities
// note that combos like aa,bb,cc are not included
// because their length is smaller than $length

最後の一つ：

$range = array('a','b','c');
$length = 3; // looking for 3 digit results
$minRep = 3; // with >=3 consecutive characters
// aaa,bbb,ccc = 3 possibilities

したがって、基本的に、2番目の例では、3番目の基準により、たとえばaabの[aa]bがキャッチされました。これは、 aが複数回連続して繰り返されたためです。一方、[ a]b[a]は、それらの aが別々であるため一致しません。.

言うまでもなく、どの変数も静的ではありません。

4

3 に答える 3

1

これを数学で処理するのが最善だと思います。

$range = array('a','b','c');
$length = 3; // looking for 3 digit results
$minRep = 2; // with >=2 consecutive characters

$rangeLength = count($range);
$count = (pow($rangeLength,$length-$minRep+1) * ($length-$minRep+1)) - ($rangeLength * ($length-$minRep)); // is the result

これで、$count は 3 つの状況で真の結果を得ています。しかし、それは一般的な式ではない可能性があり、改善する必要があります。

それを説明してみてください：

pow($rangeLength,$length-$minRep+1)

この場合、繰り返し文字は 1 つとして数えます。たとえば、あなたが与えた2番目の例では、aabでaaは1文字だと思います。なぜなら、2 人のキャラクターが一緒に変化する必要があるからです。xy のような文字が 2 つあるとします。したがって、文字 a、b、および c の両方に同じ可能性があります。つまり、2 つの文字 ($length-$minRep+1) に対して 3 ($rangeLength) の値が可能です。したがって、3^2=9 は 2 番目の例で考えられる状況です。

計算すると、9 は yx ではなく xy だけです。このために、xy の長さ ($length-$minRep+1) を乗算します。そして、18人です。

結果を計算したように見えるかもしれませんが、計算には繰り返しがあります。xy => aaa および yx => aaa という状況は想定していませんでした。このために、繰り返し結果を計算して減算します

- ($rangeLength * ($length-$minRep))

この後、結果が得られます。説明の冒頭で述べたように、この式は改善する必要があるかもしれません。

于 2012-08-21T00:02:40.047 に答える
1

とった。すべてはleonbloy @mathexchange.comの功績によるものです。

/* The main function computes the number of words that do NOT contain
 * a character repetition of length $minRep (or more). */
function countStrings($rangeLength, $length, $minRep, &$results = array())
{
  if (!isset($results[$length]))
  {
    $b = 0;

    if ($length < $minRep)
      $b = pow($rangeLength, $length);
    else
    {
      for ($i = 1; $i < $minRep; $i++)
        $b += countStrings($rangeLength, $length - $i, $minRep, $results);
      $b *= $rangeLength - 1;
    }

    $results[$length] = $b;
  }

  return $results[$length];
}

/* This one answers directly the question. */
function printNumStringsRep($rangeLength, $length, $minRep)
{
  $n = (pow($rangeLength, $length) 
            - countStrings($rangeLength, $length, $minRep));
  echo  "Size of alphabet : $rangeLength<br/>"
        . "Size of string : $length<br/>"
        . "Minimal repetition : $minRep<br/>"
        . "<strong>Number of words : $n</strong>";
}

/* Prints :
 * 
   Size of alphabet : 3
   Size of string : 3
   Minimal repetition : 2
   Number of words : 15
 *
 */
printNumStringsRep(3, 3, 2);
于 2012-08-22T10:11:17.440 に答える