題意:給你一顆二叉樹,這是一顆完全二叉樹,給你這棵樹的深度,這棵樹是用來進行小球下落實驗的樹,小球從根節點開始下落,每次進過一個節點,這個節點的狀态就會改變,起初所有的節點的狀态都是關閉的,當一個小球經過的時候那麼就會改變這個節點的狀态。節點的狀态分成兩種,一種是關閉的,當一個節點的狀态是關閉的時候,小球經過它就會向左走,相反的當這個節點的狀态是打開的,那麼這個小球就會向右走,現在給你一棵樹的深度以及落下小球的個數,問你的是最後一個小球落在的葉子的編号是多少。
書中是提供了兩個方法的,其中一個就是通過模拟的方法進行,對每一個小球的下落進行模拟,通過一個标記數組來表示每一個節點的狀态,不斷的記錄小球的落下編号,直到最後一個小球,
還有就是通過找出這樣的下落的規律,其實這樣的下落是有一頂的規律的,當兩個小球下落的時候一定是一個在根節點的左邊一個在右邊,于是或隻要知道這個資料的奇偶性就可以知道最後一個球的下落的過程,進而知道他的下落的位置。每次通過一個節點都是一種重複的過程,可以把每一個節點看成根節點,這樣就像是一個遞歸的過程。隻要下落這棵樹深度那麼多次,就可以得出最後一個小球的編号。
源代碼
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1000+10;
int main()
{
int D,I;
while(scanf("%d%d",&D,&I)==2)
{
int k=1;
for(int i=0;i<D-1;i++)
{
if(I%2)
{
k=2*k;
I=(I+1)/2;
}
else
{
k=2*k+1;
I=I/2;
}
}
printf("%d\n",k);
}
return 0;
}
更加深的了解就是,通過每一次的找出這個小球是第幾次通過這個節點來判斷下一步這個小球是向什麼方向進行下去,通過已知的某個節點的編号是k,那麼這個節點的左孩子的編号就是2k,右孩子的編号就是2k+1.這樣就可以通過計算每一個節點是通過的第幾次來求出最後的一個小球到大的編号是多少。