C++で解く：特別な家系における職業判定アルゴリズム

問題の概要

医師とエンジニアからなる特別な家系を考えてみましょう。この家系には、以下のようなルールが存在します。

• 全員が必ず2人の子どもを持ちます
• エンジニアの第1子はエンジニア、第2子は医師になります
• 医師の第1子は医師、第2子はエンジニアになります
• すべての世代は必ずエンジニアから始まります

例えば、レベル4・位置2の人物の職業を求めた場合、答えは「医師（Doctor）」となります。

解法のアイデア

ある人物の職業は、次の2つの要素によって決定されます。

• 親の職業
• ノードの位置：位置が奇数の場合、その人物の職業は親と同じになります。偶数の場合は、親とは異なる職業になります。

この性質を利用すると、まず再帰的に親の職業を求め、その結果に位置の偶奇に応じたルールを適用することで、現在のノードの職業を効率よく導き出せます。なお、位置 pos のノードの親は (pos + 1) / 2 の位置に存在するため、再帰呼び出しのたびに位置は半分になっていきます。

C++による実装例

#include<iostream>
using namespace std;
char getProfession(int level, int pos) {
   if (level == 1)
   return 'E';
   if (getProfession(level-1, (pos+1)/2) == 'D')
   return (pos%2)? 'D' : 'E';
   return (pos%2)? 'E' : 'D';
}
int main(void) {
   int level = 4, pos = 2;
   cout << "The profession is: ";
   if(getProfession(level, pos) == 'E'){
      cout << "Engineer";
   } else {
      cout << "Doctor" ;
   }
}

実行結果

The profession is: Doctor

処理の流れの解説

このプログラムでは、関数 getProfession が再帰的に動作します。

1. レベル1に到達した時点で「E（エンジニア）」を返します。これは「すべての世代はエンジニアから始まる」というルールに対応しています。
2. それ以外の場合は、親の位置 (pos + 1) / 2 を引数として自分自身を呼び出し、親の職業を取得します。
3. 親の職業が「D（医師）」であれば、現在の位置が奇数なら「D」、偶数なら「E」を返します。
4. 親の職業が「E（エンジニア）」であれば、現在の位置が奇数なら「E」、偶数なら「D」を返します。

このアルゴリズムの計算量は再帰の深さに依存し、O(log pos) 程度で非常に効率的です。大きなレベルや位置に対しても高速に職業を判定できる点が魅力です。