UVA 679 Dropping Balls(二叉樹模拟)

有一棵二叉樹,最大深度為D,且所有葉子的深度都相同。所有結點從上到下從左到右

編号為1, 2, 3,..., 2 D -1。在結點1處放一個小球,它會往下落。每個内結點上都有一個開關,

初始全部關閉,當每次有小球落到一個開關上時,狀态都會改變。當小球到達一個内結點

時,如果該結點上的開關關閉,則往左走,否則往右走,直到走到葉子結點,如圖6-2所

示。

一些小球從結點1處依次開始下落,最後一個小球将會落到哪裡呢?輸入葉子深度D和

小球個數I,輸出第I個小球最後所在的葉子編号。假設I不超過整棵樹的葉子個數。D≤20。

輸入最多包含1000組資料。

每個小球都會落在根結點上,是以前兩個小球必然是一個在左子樹,一個在右子樹。一

般地,隻需看小球編号的奇偶性,就能知道它是最終在哪棵子樹中。對于那些落入根結點左

子樹的小球來說,隻需知道該小球是第幾個落在根的左子樹裡的,就可以知道它下一步往左

還是往右了。依此類推,直到小球落到葉子上。

如果使用題目中給出的編号I,則當I是奇數時,它是往左走的第(I+1)/2個小球;

當I是偶數時,它是往右走的第I/2個小球。這樣,可以直接模拟最後一個小球的路線:

#include <iostream>
#include <cstring>

using namespace std;

const int maxn=20;
int D,I,s[1<<maxn];
int n;

int main()
{
    while(cin>>n&&n!=-1)
    {
        int k;
        while(n--){
            cin>>D>>I;
            k=1;
            for(int i=0;i<D-1;i++){
                if(I%2){k=k*2;I=(I+1)/2;}
                else {k=k*2+1;I=I/2;}
            }
            cout<<k<<endl;
        }

    }

    return 0;
}      

書上的另一種方法雖然逾時但思想也是比較好的

不難發現,對于一個結點k,其左子結點、右子結點的編号分别是2k和2k+1。這個結論

非常重要,請讀者引起重視。

提示6-11:給定一棵包含2 d 個結點(其中d為樹的高度)的完全二叉樹,如果把結點從

上到下從左到右編号為1,2,3......,則結點k的左右子結點編号分别為2k和2k+1。

這樣,不難寫出如下的模拟程式:

#include <iostream>
#include <cstring>

using namespace std;

const int maxn=20;
int D,I,s[1<<maxn];

int main()
{
    while(cin>>D>>I){
        memset(s,0,sizeof(s));
        int k,n=(1<<D)-1;
        for(int i=0;i<I;i++){
            k=1;
            for(;;){
                s[k]=!s[k];
                k=s[k]?k*2:k*2+1;
                if(k>n) break;

            }
        }
        cout<<k/2<<endl;
    }
    return 0;
}      

轉載于:https://www.cnblogs.com/Fy1999/p/9415319.html