[UVA] 11615 - Family Tree
| B. Family Tree |
“Importantfamilies are like potatoes.
The best parts are underground.”
Francis Bacon
Context
A family tree is a chart representing family relationships in a conventionaltree structure. The more detailed family trees used in medicine, genealogy, and socialwork are known as genograms. Several genealogical numbering systems have beenwidely adopted for presenting family trees. Some of them are ascendingnumbering systems.
Ahnentafel, also known as the Eytzinger Method, Sosa Method, and Sosa-StradonitzMethod, allows for the numbering of ancestors beginning with a descendant. This systemallows one to derive an ancestor's number without compiling the list, and allows one toderive an ancestor's relationship based on their numbers.
The number of a person's father is the double of his own number, and the number of aperson's mother is the double of his own plus one. For instance, if the number of JohnSmith is 10, his father is 20, and his mother is 21.
The first 15 numbers, identifying individuals in 4 generations, are as follows:
(First Generation) 1 Subject(Second Generation) 2 Father 3 Mother(Third Generation) 4 Father's father 5 Father's mother 6 Mother's father 7 Mother's mother(Fourth Generation) 8 Father's father's father 9 Father's father's mother10 Father's mother's father11 Father's mother's mother12 Mother's father's father13 Mother's father's mother14 Mother's mother's father15 Mother's mother's mother
It is possible (and usual) that two or more individuals are the same, and so are theancestors.
Complete binary tree for four generations
The Problem
We have built our complete family tree, including until the N-th generation.But we have found out that two of our ancestors are brothers (they have the same parents).
We want to know the amount of different people of our family tree (including us).
The Input
The first line of the input contains an integer T indicating the number oftest cases. For each test case, there is a line with three positive integer numbers N,A and B, separated by blanks, (4<=N<=20),where N is the number of generations, and A and B are brotherswith the same parents.
The Output
For each test case, the output shouldconsist of one integer indicating the amount of different people of our family tree(including us).
Sample Input
34 4 124 4 65 2 3
Sample Output
151317
題目給定一個族譜，那麼假設有兩個人是兄弟姊妹關係，那麼族譜會重覆某一個部分，
也就是說，他們之上的父母親關係會重覆，求這張族譜真正有多少不同人。
由於族譜只有給 n 層，那麼求一個高度最低的去扣。
#include <stdio.h>
int getLevel(int a) {//get high bit
int i, j;
for(i = 0; i < 31; i++)
if((a>>i)&1)
j = i;
return j;
}
int main() {
int testcase;
int n, a, b, la, lb;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d %d", &n, &a, &b);
la = getLevel(a);
lb = getLevel(b);
int ret = (1<<n)-1, same;
if(la > lb)
same = (1<<(n-la))-1;
else
same = (1<<(n-lb))-1;
printf("%d\n", ret-same+1);
}
return 0;
}