พิจารณามีครอบครัวแพทย์และวิศวกรพิเศษ มีกฎบางอย่างอยู่ด้านล่าง −
- ทุกคนมีลูกสองคน
- ลูกคนแรกของวิศวกรคือวิศวกร ลูกคนที่สองคือหมอ
- ลูกคนแรกของหมอเป็นหมอ ลูกคนที่สองเป็นวิศวกร
- แพทย์และวิศวกรทุกรุ่นเริ่มต้นที่วิศวกร
ดังนั้นถ้าอยากได้ผลลัพธ์ระดับ 4 และอันดับ 2 ผลลัพธ์จะเป็นหมอ
ความคิดนั้นง่าย อาชีพของคนขึ้นอยู่กับสองสิ่งต่อไปนี้
- อาชีพของพ่อแม่
- ตำแหน่งของโหนด:เมื่อตำแหน่งของโหนดเป็นเลขคี่ อาชีพของโหนดจะเหมือนกับโหนดหลัก มิฉะนั้นอาชีพจะแตกต่างจากผู้ปกครอง
เราค้นหาอาชีพของผู้ปกครองซ้ำแล้วซ้ำอีก จากนั้นใช้จุดที่ 2 ด้านบนเพื่อค้นหาอาชีพของโหนดปัจจุบัน
ตัวอย่าง
#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
