同個(gè)人網(wǎng)站 https://www.serendipper-x.cn/，歡迎訪問 ！

問題描述：
有一顆二叉樹，最大深度為D，且所有葉子的深度都相同。所有結(jié)點(diǎn)從上到下從左到右編號為 1，2，3，… ，2^D - 1。在結(jié)點(diǎn)1處放一個(gè)小球，它會(huì)往下落。每個(gè)內(nèi)結(jié)點(diǎn)上都有一個(gè)開關(guān)，初始全部關(guān)閉，當(dāng)每次由小球落到一個(gè)開關(guān)上時(shí)，狀態(tài)都會(huì)改變。當(dāng)小球到達(dá)一個(gè)內(nèi)結(jié)點(diǎn)時(shí)，如果該結(jié)點(diǎn)上的開關(guān)關(guān)閉，則往左走，否則往右走，直到走到葉子結(jié)點(diǎn)，如圖所示。

一些小球從結(jié)點(diǎn)1處下落，最后一個(gè)小球?qū)?huì)落到哪里呢？輸入葉子深度 D 和小球個(gè)數(shù) I，輸出第 I 個(gè)小球最后所在的葉子編號。假設(shè) I 不超過整棵樹的葉子個(gè)數(shù)，D ≤ 20。

tips:
給定一顆包含2^d個(gè)結(jié)點(diǎn)（其中d為樹的高度）的完全二叉樹，如果把結(jié)點(diǎn)從上到下從左到右編號為1，2，3……，則結(jié)點(diǎn)k的左右子結(jié)點(diǎn)編號分別為2k 和 2k+1。

Python:

while True:try:D, I = list(map(int, input().split()))n = (1<<D) - 1 # n是最大結(jié)點(diǎn)編號s = [False for _ in range (1<<20)] # 初始值都為假for i in range (I):k = 1while True:s[k] = ~s[k] # 狀態(tài)改變if s[k] == 0:k = 2 * k + 1else:k = 2 * kif k > n: # 出界breakprint (k//2) # 出界之前的葉子編號except:break

C:

#include<cstdio> #include<cstring>const int maxd = 20; int main() {int D, I;while(scanf("%d%d", &D, &I) == 2) {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;}}printf("%d\n", k/2);}return 0; }

如果使用題目中給的編號 I，則當(dāng) I 是奇數(shù)時(shí)，它是往左走的的第（I+1）/ 2個(gè)小球；當(dāng) I 是偶數(shù)時(shí)，它是往右走的第 I/2 個(gè)小球。這樣，可以直接模擬最后一個(gè)小球的路線：

while(scanf("%d%d", &D, &I) == 2) {int 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 /= 2;}printf("%d\n", k)} } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的算法竞赛入门经典 例题6-6 小球下落（python、C）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。