『今週の問題』第190回　解答

◆東京都　ぽこぺん さんからの解答

●perlによるプログラム

#! /usr/bin/perl

$n = shift(@ARGV);
$printMax = 200;
$workingMax = 2 * $n * $printMax;

@f = ();
@p = ();

for($r = 1; $r <= $n; $r++){
    $f[$r*$n] = ($r <= int(($n+2)/2)) ? $r : $n - $r + 2;
    if($r == 1){
$p[$r*$n] = "C";
    } elsif($r == $n){
$p[$r*$n] = "C*";
    } else {
$p[$r*$n] = ($r <= int(($n+2)/2)) ? "C" . ("+" x ($r - 1)) : "C*" . ("-" x ($n - $r));
    }
}

for($k = 2; $k*$n*$n <= $workingMax; $k++){
    $f[$k*$n*$n] = $f[$k*$n] + 1;
    $p[$k*$n*$n] = $p[$k*$n] . "*";

    $i = ($k - 1)*$n*$n;
    $g[$i] = $f[$i];
    $q[$i] = $p[$i];
    for($i += $n; $i < $k*$n*$n; $i += $n){
$g[$i] = $g[$i - $n] + 1;
$q[$i] = $q[$i - $n] . "+";
    }

    $j = $k*$n*$n;
    $h[$j] = $f[$j];
    $r[$j] = $p[$j];
    for($j -= $n; $j > ($k - 1)*$n*$n; $j -= $n){
$h[$j] = $h[$j + $n] + 1;
$r[$j] = $r[$j + $n] . "-";
    }

    for($i = ($k - 1)*$n*$n + $n; $i < $k*$n*$n; $i += $n){
$f[$i] = ($g[$i] <= $h[$i]) ? $g[$i] : $h[$i];
$p[$i] = ($g[$i] <= $h[$i]) ? $q[$i] : $r[$i];
    }
}

for($r = 1; $r < $n; $r++){
    for($k = 0; $n*($k*$n+$r) <= $workingMax; $k++){
$g[$k*$n+$r] = $f[$n*($k*$n+$r)] + 1;
$q[$k*$n+$r] = $p[$n*($k*$n+$r)] . "/";
    }
    $f[$r] = $g[$r];
    $p[$r] = $q[$r];
    for($k = 1; $k*$n+$r <= $workingMax; $k++){
$f[$k*$n+$r] = ($f[($k-1)*$n+$r] + 1 <= $g[$k*$n+$r]) ? $f[($k-1)*$n+$r] + 1 : $g[$k*$n+$r];
$p[$k*$n+$r] = ($f[($k-1)*$n+$r] + 1 <= $g[$k*$n+$r]) ? $p[($k-1)*$n+$r] . "+" : $q[$k*$n+$r];
    }
    for($k = 1; $k*$n+$r <= $workingMax; $k++){
if($f[($k-1)*$n+$r] > $f[$k*$n+$r] + 1){
    $i = 0;
    while($f[($k-1-$i)*$n+$r] > $f[($k-$i)*$n+$r] + 1){
$f[($k-1-$i)*$n+$r] = $f[($k-$i)*$n+$r] + 1;
$p[($k-1-$i)*$n+$r] = $p[($k-$i)*$n+$r] . "-";
$i++;
    }
}
    }
}

&prList;

sub prList {
    local($i, $j);

    for($i = 1; $i <= $printMax; $i += $n){
printf("[%3d:%3d]", $i + $n - 1, $f[$i + $n - 1]);
printf("\t%s", &prOper($n, $p[$i + $n - 1]));
for($j = $i; $j < $i + $n - 1; $j++){
    printf("\t[%3d:%3d]", $j, $f[$j]);
    printf("\t%s", &prOper($n, $p[$j]));
}
printf("\n");
    }
}

sub prOper {
    local($num, $oper) = @_;
    local($i, $str);

    $str = "";
    for($i = 0; $i < length($oper); $i++){
$str .= substr($oper, $i, 1) . $num;
    }
    return $str . "=";
}

　◆ 問題へもどる

　◆ 今週の問題へ

数学の部屋へもどる