NYOJ63小猴子下落

NYOJ63小猴子下落

小猴子下落

描述

有一顆二叉樹，最大深度為D,且所有葉子的深度都相同。所有結點從左到右從上到下的編號為1,2,3，·····，2的D次方減1。在結點1處放一個小猴子，它會往下跑。每個內結點上都有一個開關，初始全部關閉，當每次有小猴子跑到一個開關上時，它的狀態都會改變，當到達一個內結點時，如果開關關閉，小猴子往左走，否則往右走，直到走到葉子結點。

一些小猴子從結點1處開始往下跑，最後一個小猴兒會跑到哪裡呢？

輸入

輸入二叉樹葉子的深度D,和小猴子數目I，假設I不超過整棵樹的葉子個數，D<=20.最終以 0 0 結尾

輸出

輸出第I個小猴子所在的葉子編號。

樣例輸入

4 2
3 4
0 0

樣例輸出

12
7

# include 
# include 
# define TRUE 1
int i;
int fact(int i, int n,int *a)
{
	if (2*i > n && 2*i +1 > n)
	{
		return i;
	}
	else
	{
		if (a[i] == 0 )
		{
			a[i] = 1;
			i = 2*i;
		}
		else
		{
			a[i] = 0;
			i = 2*i +1;
		}
		fact(i,n, a);
	}
}
int main(void)
{
	int n,m,s;
	while (scanf("%d%d", &n,&m) && (n != 0 || m != 0))
	{
		int a[100000] = {0};
		while (m--)
		{
			s = fact(1,pow(2,n) - 1,a);
		}
		printf("%d\n", s);
	}
	return 0;
}

本人不才，只想到用遞歸解題，看下面大神的代碼

#include02.using namespace std;03. 04.int main()05.{06.int d,i,k;07.while(cin>>d>>i && (d+i) !=0)08.{09.k=1;10.for (int j=0;j11.if(i%2) {k=k*2;i=(i+1)/2;}12.else {k=k*2+1;i /=2;}13.cout<14. 15.}16.}

復制去Google翻譯翻譯結果