プログラミング | 帰宅部所属

子供が小学６年生で、算数で数列を学んでいます。課題で次のような問題が出されました。

ある地域内で、複数の道路が互いに一箇所だけ交差するとして、各交差点に交通整理の警察官を配置した場合の必要人数を求めよ

図に示すと次のようなものです。

	道路が１本、交差点なし
	道路が２本、交差点ひとつ
	道路が３本、交差点３つ
	道路が４本、交差点６つ
	道路が５本、交差点１０個

つまり道路の本数を n、お巡りさんの必要人数を Kn　と置いたとき、次の漸化式で表現することができます。

$K_n=K_{n-1}+n-1$ (ただし $n > 0, K_0=0$ )

この手の問題はプログラムを作ることで、道路が数え切れないほどたくさんあっても一瞬に答えを出せることを教えようと、子供に PHPで作ってみな、といってみたものの少々難しかったようです。
アルゴリズムの部分だけ示すと下記のようなコードとなります。

$n = $_GET['numroads'];
printf("<p>Number of roads = </p>", $n);
$Kn = 0;
for ($i = 0; $i < $n; $i++)
{
	$Kn += $i;
}
printf("<p>Number of policemen = %d</p>", $Kn);

numroads にはフォームからユーザに入力してもらった道路の本数が格納されています。

実際に作ってみたフォームがこちらです。お粗末さまでした。