หาอาชีพในครอบครัวพิเศษ (Doctor/Engineer) ใน C++

ครอบครัวพิเศษ: ทุกคนมีลูก 2 คน

• Engineer: ลูกคนที่ 1 = Engineer, ลูกคนที่ 2 = Doctor
• Doctor: ลูกคนที่ 1 = Doctor, ลูกคนที่ 2 = Engineer
• รุ่นแรก (Root) เป็น Engineer เสมอ

หาอาชีพที่ Level L, Position P (1-indexed)

ข้อสังเกต

• อาชีพขึ้นอยู่กับ: อาชีพของพาเรนต์ + ตำแหน่ง (Odd/Even)
• ตำแหน่งคี่ (Odd) → อาชีพเหมือนพาเรนต์
• ตำแหน่งคู่ (Even) → อาชีพต่างจากพาเรนต์

ตัวอย่างโค้ด (Recursive)

#include <iostream>
using namespace std;

char getProfession(int level, int pos) {
    if (level == 1) return 'E'; // Root เป็น Engineer

    char parent = getProfession(level - 1, (pos + 1) / 2);

    if (parent == 'D')
        return (pos % 2) ? 'D' : 'E'; // Parent เป็น Doctor
    else
        return (pos % 2) ? 'E' : 'D'; // Parent เป็น Engineer
}

int main() {
    int level = 4, pos = 2;
    cout << "The profession is: ";
    if (getProfession(level, pos) == 'E')
        cout << "Engineer";
    else
        cout << "Doctor";
    return 0;
}

ผลลัพธ์

The profession is: Doctor

วิธี Iterative (Bit Manipulation) - เร็วกว่า

char getProfessionIterative(int level, int pos) {
    // นับจำนวน 1 ใน binary ของ (pos-1)
    int flips = __builtin_popcount(pos - 1);
    // Engineer = 0, Doctor = 1
    // Root = E (0), ทุกครั้งที่ pos เปลี่ยน parity (คู่/คี่) จะ flip
    return (flips % 2 == 0) ? 'E' : 'D';
}

การทำงาน

Level 4, Pos 2: Path = Root(1) → Left(1) → Right(2) → Right(2) = E→E→D→D = Doctor