お題（グループ分け）

short

某所でグループ分けのクイズが出ていたので反応してみた。

2人以上のn人を3人グループと2人グループに分け、それぞれのグループ数を出すにはどうしたら良いですか？
なるべく3人グループが多くできるようにし、余りが出ないようにします。分類できないケースはfalseとします。

http://pc11.2ch.net/test/read.cgi/php/1234958956/503

まぁ、普通に考えれば %で余りを出してswitchすればできそう。
それでは面白くないので、3人2人が変化したときでも対応できる関数にし、数学的な処理からループを組んでみた。

<?php
function group($n, $large = 3, $small = 2)
{
    for ($s = 0; $s <= $large; $s++) {
        if (is_int($l = ($n - $small * $s) / $large) && $l >= 0) {
            return array((string) $large => $l, (string) $small => $s);
        }
    }
    return false;
}
//もしくは
function group($n, $large = 3, $small = 2)
{
    for ($s = 0, $tmp = 0; $s <= $n / $small + 1 ,$tmp >=0 ; $s++) {
        if (fmod($tmp = $n - $small * $s, $large) == 0) {
            return array((string) $large => ($tmp / $large),
                         (string) $small => $s);
        }
    }
    return false;
}

PHPで書くと、型の甘さを逆用したようなプログラムが書けてしまう。intの限界とか割り算の結果精度を考えると、近似的に間違った結果が出るけど、ロジック的にはほぼＯＫだと思う。まぁ、そういうのを見過ごすからバグが出るんだけどね。精度的には%とswitchを使った処理の方がマシなような気はする。バグらせることができる最小値の組み合わせを検出できる人もいるんだろうなぁ。ちなみにintの限界は2147483647。
こういう問題のロジック部は、関数型言語だとすっきり書ける。整数問題みたいのは集合が扱える言語がいいよね。そうじゃない場合はさっさと試行して、とりあえず答えを出しておくというのも悪くない。正しいかどうかは気にしない（笑）。
さて、今日はあえて中学生に戻った気分で整数問題。上のお題を中学生の数学に置き換えると下記のようになる。

自然数(0を含む）集合N、{l, s, large ,small} ∈Nに対し、{n : large * x + small * y = n } ∈Nの関係が定義されるとき、最小のy（とxの組み）を探してね

という算数の問題になる。子供たちに教えるときは、3人のグループが3つあると何人になる？と置き換える。分解するとlとlarge、sとsmallの関係はそれらの積がグループ化された人数になる。nl = large * l , ns = large *s　グループを定義する関数関係になる。さらにグループ人数を合計する関数を用いるとnが定義される。グループ人数 = fmat(定員,グループ数)　、合計人数 = fsum(大グループ人数,小グループ人数)　、よって、n= fsum(fmat(large,x),fmat(small,y)) inf y お題の人はnを引数にしていたけれど、n,large,smallに実引数が与えられれば、残るのは n = 3*x + 2*y の1次関数だよね。（昔、BASICで最初に書いたプログラムは2次関数やSinやcosでxを変化させながらyを取得して、ドットを打っていくっていうプログラムだった）グラフ的には、こんな感じ。整数なので不連続な点線になる。nの与え方によっては第1象限に解はない。

集合が扱える言語ならそのまま表現できるが、PHPみたいなもので実装するときは、中学校の数学になり、方程式を解いた結果　x = (n - 2*y)/3 に対して、yを最小の0から試行して最大でもlargeに至るまでに自然数となる解があるかどうかを総当たりで調べるというのが合理的。(large倍したsmallはlargeで割り切れる。よって$sはかならず整数largeを通過することを利用して制約をきつくしているわけだ。ところで、下の方のプログラムは、整数ではない場合も適用できる。たとえば、3.4553という数値を1.2 と0.0001のそれぞれ整数倍に分類することが可能かどうか？とか。）
ちなみに問題が２と３になっているが、これはかなり特殊で小さい方の２以上の自然数であれば、グループ分けが完全にできる。偶数nは２でグループ分けが可能で、奇数nについては、5以上であれば、少なくとも3を引けば偶数になる。組み合わせが3と4ならどうか、5は表現できないが、6以上ならすべて表現可能。このことから、任意の大小に対して、nを十分に大きくすれば連続するn+mに対して解があるような集合を定義したら、その様子をビジュアルに表現することはできるだろうか。もちろん、大小が両方偶数だったときには奇数は表現不可能だから、[n..]にはならないのは当然として。
このお題（改）のように検証対象や与える引数が無限にあるようなプログラムの場合、問題に沿っているかどうかを検証するのは難しくなる。
プログラミングにとって大切なことは、正しさじゃぁなくて、（無論誤りでもないけど）、評価する人にわかるように書けって事かも知れない。
#このプログラムの間違いが既知であれば、反例を示すためのプログラムは書けそう。
お題が変化して、特定の$large,$smallであり、$nの範囲が有限なら、それを確認するプログラムは簡単に書ける。
任意のプログラムを検証可能なプログラムは存在しないことは証明されている。しかし一方で、有限な条件に絞った命題であれば検証可能なプログラムが存在する可能性は否定されていない。