正しい文(クイズ) in PHP DouKaku?

「この文は0が□個，1が□個，...，9が□個あります」
が正しくなるように□を埋めてください．数値は10進数とします．
一般のn(<=16で可)進数でも解いてみてください．

たとえば2進数なら
「この文は0が11個，1が100個あります」
となります．

とりあえず乱暴な方法だけど2進から16進まで一つずつ答えを得た。

この文は0が11個,1が100個あります。
この文は0が1個,1が11個,2が2個あります。
この文は0が1個,1が11個,2が2個,3が1個あります。
...
この文は0が1個,1が11個,2が2個,3が1個,4が1個,5が1個,6が1個,7が1個,8が1個,9が1個あります。
...
この文は0が1個,1が11個,2が2個,3が1個,4が1個,5が1個,6が1個,7が1個,8が1個,9が1個,aが1個,bが1個,cが1個,dが1個,eが1個,fが1個あります。

<?php
for($n=2;$n<=16;++$n)
{    $str="";
    do{
        $a=count_chars($str);
        $b=array();
        for($i=0;$i<$n;++$i)
        {    $c=base_convert($i,10,$n);
            $b[]="${c}が".base_convert($a[ord($c)],10,$n)."個";
        }
        $str0=$str;
        $str=implode(",",$b);
    }while($str!=$str0);
    echo "この文は${str}あります。\n";
}
?>

全探索バージョン。
直前のお題"自然数の分割"のプログラムを応用して
「数字の数は2n～2n+2 (2進は例外)」という条件で探索範囲を限定。
2進から16進まで探索してCore2Duo 1.2GHzで 29秒

2進:
この文は0が11個,1が100個あります。
3進:
この文は0が10個,1が10個,2が2個あります。
この文は0が1個,1が11個,2が2個あります。
この文は0が2個,1が2個,2が10個あります。
...
10進:
この文は0が1個,1が11個,2が2個,3が1個,4が1個,5が1個,6が1個,7が1個,8が1個,9が1個あります。
この文は0が1個,1が7個,2が3個,3が2個,4が1個,5が1個,6が1個,7が2個,8が1個,9が1個あります。
...
16進:
この文は0が1個,1が11個,2が2個,3が1個,4が1個,5が1個,6が1個,7が1個,8が1個,9が1個,aが1個,bが1個,cが1個,dが1個,eが1個,fが1個あります。
この文は0が1個,1がd個,2が3個,3が2個,4が1個,5が1個,6が1個,7が1個,8が1個,9が1個,aが1個,bが1個,cが1個,dが2個,eが1個,fが1個あります。
28.799607992172sec

<?php
function cmp(&$a1,&$a2)
{
    foreach($a2 as $k=>$v)
        if($a1[ord(base_convert($k,10,36))]!=$v)
            return false;
    return true;
}
function judge($a,$n)
{
    $b=array();
    for($i=0;$i<$n;++$i)
    {    $c=base_convert($i,10,$n);
        $b[]="${c}が".base_convert($a[$i],10,$n)."個";
    }
    $str=implode(",",$b);
    $a1=count_chars($str);
    if(cmp($a1,$a))
        echo "この文は${str}あります。\n";
}

function part($a,$n,$c,$s1,$s2,$m)
{
    if(!$c)
    {    $m1=min($m-$s1,$s2+1);
        for($i=$n*2-$s1;$i<=$m1;++$i)
        {    $a[$c]=$i;
            judge($a,$n);
        }
    }
    else
    {    $m1=min($m-$s1,$s2/$c+1);
        for($i=1;$i<=$m1;++$i)
        {    $a[$c]=$i;
            part($a,$n,$c-1,$s1+$i,$s2-$c*($i-1),$m);
        }
    }
}

$t=microtime(true);

for($n=2;$n<=16;++$n)
{    echo "${n}進:\n";
    $m=max($n*2+2,10);
    part(array(),$n,$n-1,0,$m,$m);
}

echo microtime(true)-$t,"sec\n";
?>

数字の出現回数の合計と(数字x(出現回数-1))の積分の関係で縛りを追加したら
#4376と同条件で4.1秒ほどになりました。

リストは変更していないcmp()とjudge()省略。

<?php
function part($a,$n,$c,$s1,$s2,$m)
{
    if(!$c)
    {    for($i=$s2-$s1;$i<=min($m-$s1,$m-$s2+1);$i+=$n-1)
            if($i>=$n*2-$s1)
            {    $a[$c]=$i;
                judge($a,$n);
            }
    }
    else
    {    $m1=min($m-$s1,($m-$s2)/$c+1);
        for($i=1;$i<=$m1;++$i)
        {    $a[$c]=$i;
            part($a,$n,$c-1,$s1+$i,$s2+$c*($i-1),$m);
        }
    }
}

$t=microtime(true);

for($n=2;$n<=16;++$n)
{    echo "${n}進:\n";
    $m=max($n*2+2,10);
    part(array(),$n,$n-1,0,0,$m);
}

echo microtime(true)-$t,"sec\n";
?>

DouKaku?

正しい文(クイズ)

Posted feedbacks - PHP

Index

Feed

Other

Link

Pathtraq