【PHPで解いてみた】2章 C++入門 AtCoder Programming Guide for beginners (APG4b)

2.01.ループの書き方と範囲for文

　キーポイント

• パターンがあるプログラムを見つけたらループ文を使う。
• 配列の要素にはループを用いてアクセスする。
• ループ分の使い分け
  • for文：カウンタによって繰り返す回数を管理したいとき
  • while文：上記以外

気付き・学び

• 改行コードが含まれていることを念頭においてプラグラムを組む必要がある。

EX16 - 隣り合う同じ値を探す

<?php
    $Ai = trim(fgets(STDIN));

    $Ai_list = explode(" ",$Ai);

    $flag = false;

    for($i=0;$i<count($Ai_list)-1;$i++){
        if($Ai_list[$i] == $Ai_list[$i+1]){
            echo "YES\n";
            $flag = true;
            break;
        }
    }

    if(!$flag){
        echo "NO\n";
    }

2.02.多重ループ

キーポイント

• 内側のループでbreakを書くと、内側のループは抜けれるが外側のループは抜けれない。
• 多重ループを１度に抜ける時はフラグ変数を用いる。

EX17 - 果物屋さんでお買い物

<?php
    fscanf(STDIN,"%d %d", $n,$s);

    $Ai_list = explode(" ",trim(fgets(STDIN)));
    $Pi_list = explode(" ",trim(fgets(STDIN)));

    $count = 0;

    for($i=0;$i<count($Ai_list);$i++){
        for($j=0;$j<count($Pi_list);$j++){
            if($Ai_list[$i]+$Pi_list[$j] == $s){
                $count ++;
            }
        }
    }

    echo $count."\n";

2.03.多次元配列

キーポイント

• 2次元配列は、２次元の表を扱うときに用いる。
• 2次元配列は、「１次元配列の配列」で表す。
• ２次元配列を構成する１次元配列の要素数が要素ごとに異なる配列をジャグ配列という。
• 多次元配列は、「N-1次元配列の配列」とかんがえる。

気付き・学び

• forを用いる時はインデックス変数の値とループ条件でミスが起こりやすいので注意する。
• 2次元配列を作成したいとき、２重配列内でfor文を用いるときはbreakを用いる。そうしなければ、２次元配列にはならない。

EX18.ゲーム大会

<?php
fscanf(STDIN,"%d %d", $n,$m);



$games = array();

if($m == 0){
    echo "-";
}else {

    for ($t = 0; $t < $m; $t++) {
        fscanf(STDIN, "%d %d", $a, $b);
        $games[] = [$a, $b];
    }

    for ($i = 1; $i <= $n; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            for ($k = 0; $k < count($games); $k++) {
                if ($i == $games[$k][0] && $j == $games[$k][1]) {
                    if ($j == $n) {
                        echo "o";
                    } else {
                        echo "o ";
                    }
                    break;
                } elseif ($i == $games[$k][1] && $j == $games[$k][0]) {
                    if ($j == $n) {
                        echo "x";
                    } else {
                        echo "x ";
                    }
                    break;
                } elseif ($k == count($games) - 1) {
                    if ($j == $n) {
                        echo "-";
                    } else {
                        echo "- ";
                    }
                }
            }
        }
        echo "\n";
    }

}

2.04.参照

キーポイント

• 参照渡しとは変数の参照先（メモリアドレス）をコピーすること。
• 参照は、関数で変数を複数返したいときに使える

気付き・学び

• 今回のEXでは、３つの変数情報を返したい関数だったが、参照を使うことでシンプルな関数で３つの変数を返せることを実感できた。

EX19 - 九九の採点

<?php
$A_list = array();
for($i=0;$i<9;$i++){
    $A_list[$i] = explode(" ",trim(fgets(STDIN)));
}


$correct_count = 0;
$wrong_count = 0;
function saiten(&$A,&$correct_count,&$wrong_count){
    for($m=1;$m<=9;$m++){
        for($n=1;$n<=9;$n++){
            if($m*$n == $A[$m-1][$n-1]){
                $correct_count++;
            }else{
                $A[$m-1][$n-1]=$m*$n;
                $wrong_count++;
            }
        }
    }
}

saiten($A_list,$correct_count,$wrong_count);

for($t=0;$t<9;$t++){
    for($s=0;$s<9;$s++){
        if($s==8){
            echo $A_list[$t][$s];
        }else{
            echo $A_list[$t][$s]." ";
        }
    }
    echo "\n";
}


echo $correct_count."\n";
echo $wrong_count."\n";

2.05.再帰関数

キーポイント

• 「ある関数の中で同じ関数を呼び出す」ことを再帰呼び出しという。
• 再帰呼び出しを行わずに完了できる処理をベースケースといい、ベースケースが再帰の終了ポイント。
• 再帰呼出しを行い、その結果を用いて行う処理のことを再帰ステップという、このステップが再帰を起こす。
• 再帰関数のイメージは、再帰的に再起関数を呼び出して深くもぐり、下まで到達したのちに、返り値を複数回返すことで上っていくイメージ。
• 再起関数を作るとき、同じ意味を持つ関数を再起関数内で呼び出す。この時、呼び出した関数のアルゴリズムまで考えず、この関数はこういう処理をしてこの値を返してくれるんだと定義することでわかりやすく関数を作れる。

EX20 - 報告書の枚数

<?php
  function calc_report($par, $children, &$reports) {
    if(count($children[$par])==0){
        return $reports[$par]=1;
    }
    $send_reports = 1;
    foreach($children[$par] as $child){
        $send_reports += calc_report($child,$children,$reports);
    }
    return $reports[$par] = $send_reports;
  }


  function main() {
    fscanf(STDIN, "%d", $n);
    $p = explode(" ",trim(fgets(STDIN)));

    # 組織図を隣接リストで持つ
    $children;
    for ($i=0; $i<$n-1; $i++) {
      $parent = $p[$i];
      $children[$parent][] = $i+1;
    }

    $reports = array(); # それぞれの組織が提出するレポートの数

    for ($i=0; $i<$n; $i++) $reports[] = -1;
    calc_report(0, $children, $reports); # 0番目の組織から計算していく

    for ($i=0; $i<$n; $i++) {
      echo $reports[$i] . "\n";
    }

  }

  main()
?>

2.0.6 計算量

EX21は与えられたコードから１つの関数呼び出しをコメントアウトするだけなので、PHPへの書き換えは割愛します。

キーポイント

• コンピュータの記憶領域(メモリ)は有限であり、プログラムで変数を使用した分だけメモリを消費する
• プログラムの実行時間: 時間計算量　、メモリ使用量:空間計算量。これらは時間計算量はオーダーで表される。
• オーダー記法では O(N)と表されます。