プログラミング学習記録【12日目】

朝6時からバイトに駆り出され、夕方頃開放されたと思ったらそのまま飲み会に連行、日付が変わっても飲まされるというハプニングがあり、その御蔭で昨日は頭が痛すぎて、光る画面を見ることができず、ずっと寝ていて更新できなかった。2日連続勉強できなくてショック。

2.05. 再帰関数

繰り返し処理を行う方法の一つ。
ある関数の中で同じ関数を呼び出すことを再帰と呼ぶ。
関数の知識が重要なので確認しておくと良い。
煩雑なので例題をもとに理解を深めていく。

N個の組織からなるA社で報告書の提出をおこなう。
0番目の組織以外のN-1個の組織には必ず1つ親組織が存在し、子組織は複数になることもある。
親組織は子組織の報告書が揃ってから、自身の報告書を加えて、親組織に伝達する。伝達に係る時間は1分で、報告書はすでに用意されており、伝達以外にかかる時間はないものとする。
ある時点で末端の子組織が一斉に報告書の伝達を開始したとき、トップの組織に報告書が伝達されるのは何分後かを出力するプログラムを作成する。
サンプルプログラムは以下の通り。

   #include <bits/stdc++.h>
   using namespace std;
    
   // x番の組織について、子組織からの報告書が揃った時刻を返す
   // childrenは組織の関係を表す2次元配列(参照渡し)
   int complete_time(vector<vector<int>> &children, int x) {
     // (ここに追記して再帰関数を実装する)
   }
    
   // これ以降の行は変更しなくてよい
    
   int main() {
     int N;
     cin >> N;
    
     vector<int> p(N);  // 各組織の親組織を示す配列
     p.at(0) = -1;  // 0番組織の親組織は存在しないので-1を入れておく
     for (int i = 1; i < N; i++) {
       cin >> p.at(i);
     }
    
     // 組織の関係から2次元配列を作る
     vector<vector<int>> children(N);  // ある組織の子組織の番号一覧  // N×0の二次元配列
     for (int i = 1; i < N; i++) {
       int parent = p.at(i);  // i番の親組織の番号
       children.at(parent).push_back(i);  // parentの子組織一覧にi番を追加
     }
    
     // 0番の組織の元に報告書が揃う時刻を求める
     cout << complete_time(children, 0) << endl;
   }

入力は次のように行われる。

N
p1 p2 … pN-1

なお、piは親組織がi番目の組織であることを示す。0番目の組織はトップの組織であり、それ以上に親組織がないことに注意する。

ベースケース、再帰ステップを考えていく。
仮にx番目の組織について注目するとする。このときほしいのはその組織の伝達に係る時間であり、すべて組織の伝達時間の中から最大の伝達時間が今回求めたいものとなる。
今回ベースケースとなるのは、子組織がない組織(末端の組織)となる。
main文から関数complete_timeに渡されるのはchildrenという変数で、これはある親組織に所属する子組織の一覧を示しているので、この配列が0になるものをベースケースとすれば良い。つまりこうなる。

children.at(x).size() == 0

このとき再帰関数が終われば良い。
ループして次に渡す値はその組織に報告書が揃う時間なのでその情報を
この組織に報告書が揃う時間は0(自身のものを上に伝達するだけ)なのでreturnで0を返す。
再帰ステップだが、子組織から伝達された報告書に自身の報告書を足して親組織に伝達する、とあったので、子組織の数を知りたいなら単純に+1すればよい。さらにこの時間が伝達にかかる最大の時間かどうかを判断し、更新する作業もループする。これをプログラムに落とし込んでいく。

int pass_time = complete_time(children, y) + 1;
max_time = max(max_time, pass_time);

で、これらをうまいことcomplete_timeという関数にパッケージングしたのがこちら。

int complete_time(vector<vector<int>> &children, int x)
{

 if (children.at(x).size() == 0) //子組織が1つもない場合=伝達時間は0分
 {
   return 0;
 }

 int max_time = 0; // 伝達にかかった時間の最大
 for (int y : children.at(x))
 {

   int pass_time = complete_time(children, y) + 1;
   //→pass_time=子組織から来た報告書に自分の組織の分を合わせて伝達する時間 = 自身を含めた、自身の組織に連なる子組織や孫組織…といった組織の数

   max_time = max(max_time, pass_time);
   //pass_timeと今までのmax_timeを比較して、大きい方を次のmax_timeとして次のループへ
 }
 return max_time;
}

特段提出するところはなかったので自分の環境で答え合わせ。
入力:

6
0 0 1 1 4

出力

3

大丈夫そう。

EX20.報告書の枚数

先程の例題と同じ会社で、報告書の枚数を確認する。
各子組織が親組織に渡す報告書の枚数、並びにトップの組織が社長に提出する報告書の枚数を出力するプログラムを作る。サンプルプログラムは以下の通り。

   #include <bits/stdc++.h>
   using namespace std;
    
   // x番の組織が親組織に提出する枚数を返す
   // childrenは組織の関係を表す2次元配列(参照渡し)
   int count_report_num(vector<vector<int>> &children, int x) {
     // (ここに追記して再帰関数を実装する)
   }
    
   // これ以降の行は変更しなくてよい
    
   int main() {
     int N;
     cin >> N;
    
     vector<int> p(N);  // 各組織の親組織を示す配列
     p.at(0) = -1;  // 0番組織の親組織は存在しないので-1を入れておく
     for (int i = 1; i < N; i++) {
       cin >> p.at(i);
     }
    
     // 組織の関係から2次元配列を作る
     vector<vector<int>> children(N);  // ある組織の子組織の番号一覧
     for (int i = 1; i < N; i++) {
       int parent = p.at(i);  // i番の親組織の番号
       children.at(parent).push_back(i);  // parentの子組織一覧にi番を追加
     }
    
     // 各組織について、答えを出力
     for (int i = 0; i < N; i++) {
       cout << count_report_num(children, i) << endl;
     }
   }

やることは先程と同様再帰関数の導入。
ベースケースは子会社がない末端の子会社について、先程と同様に考えると、もともと持っている報告書は1枚なので、

  if (children.at(x).size() == 0) //子組織が1つもない場合=伝達する報告書は0枚
 {
   return 1;
 }

再帰ステップについて、ループしているのは
･子会社から受け取った報告書に自身の分+1をし、返り値とする
の1点のみである。むしろ変数の名前を考えるほうが難しい。

for (int y : children.at(x)) //yは子組織の数になる
 {
   total += count_report_num(children, y); //x系列の子組織分足す
 }
total += 1;
return total;

以上をうまいことまとめて実装したのがこちら。

#include <bits/stdc++.h>
using namespace std;

// x番の組織が親組織に提出する枚数を返す
// childrenは組織の関係を表す2次元配列(参照渡し)
int count_report_num(vector<vector<int>> &children, int x)
{
 if (children.at(x).size() == 0) //子組織がない会社は持っている報告書1枚
 {
   return 1;
 }

 int total = 0;
 for (int y : children.at(x)) //yは子組織の数になる
 {
   total += count_report_num(children, y); //x系列の子組織分足す
 }
 total += 1; //自身の組織分+1する
 return total;
}
// これ以降の行は変更しなくてよい

int main()
{
 int N;
 cin >> N;

 vector<int> p(N); // 各組織の親組織を示す配列
 p.at(0) = -1;     // 0番組織の親組織は存在しないので-1を入れておく
 for (int i = 1; i < N; i++)
 {
   cin >> p.at(i);
 }

 // 組織の関係から2次元配列を作る
 vector<vector<int>> children(N); // ある組織の子組織の番号一覧
 for (int i = 1; i < N; i++)
 {
   int parent = p.at(i);             // i番の親組織の番号
   children.at(parent).push_back(i); // parentの子組織一覧にi番を追加
 }

 // 各組織について、答えを出力
 for (int i = 0; i < N; i++)
 {
   cout << count_report_num(children, i) << endl;
 }
}

提出。

段々と問題も噛みごたえのあるものになってきた。
気を抜かず精進していきたい。
明日は朝から予定がないので、遅れている分を取り返そうと思う。