L1-071 前世檔案 (20 分)

L1-071 前世檔案 (20 分)

網(wǎng)絡(luò)世界中時(shí)常會遇到這類滑稽的算命小程序，實(shí)現(xiàn)原理很簡單，隨便設(shè)計(jì)幾個(gè)問題，根據(jù)玩家對每個(gè)問題的回答選擇一條判斷樹中的路徑（如下圖所示），結(jié)論就是路徑終點(diǎn)對應(yīng)的那個(gè)結(jié)點(diǎn)。

現(xiàn)在我們把結(jié)論從左到右順序編號，編號從 1 開始。這里假設(shè)回答都是簡單的“是”或“否”，又假設(shè)回答“是”對應(yīng)向左的路徑，回答“否”對應(yīng)向右的路徑。給定玩家的一系列回答，請你返回其得到的結(jié)論的編號。

輸入格式：

輸入第一行給出兩個(gè)正整數(shù)：N（≤30）為玩家做一次測試要回答的問題數(shù)量；M（≤100）為玩家人數(shù)。

隨后 M 行，每行順次給出玩家的 N 個(gè)回答。這里用 y 代表“是”，用 n 代表“否”。

輸出格式：

對每個(gè)玩家，在一行中輸出其對應(yīng)的結(jié)論的編號。

輸入樣例：

3 4
yny
nyy
nyn
yyn

輸出樣例：

3
5
6
2

思路：

有題目可知，最小值為1，即結(jié)論1，最大值是結(jié)論2^N。

當(dāng)為y的時(shí)候，表示是左子樹，因此，原有值不需要改動 。

當(dāng)為n時(shí)，表示在右子樹，此時(shí)需要在原有值的基礎(chǔ)上 加上 當(dāng)前結(jié)點(diǎn)所有的葉節(jié)點(diǎn)的一半 。

代碼：

#include<stdio.h>
#include<string.h>
#include<math.h>
char str[35];
int N,M;
int main()
{
	scanf("%d %d",&N,&M);
	int k = pow(2,N);// 計(jì)算出最大結(jié)論值 
	int i,j,index,n;
	for(i=0;i<M;i++)
	{ 
		index = 1;	//論值賦值為1 
		n = k;		//根節(jié)點(diǎn)置為 k 
		scanf("%s",str);
		for(j=0;j<strlen(str);j++)
		{
			if(str[j]=='n')
				index+=(n/2);
			n/=2;
		}
		printf("%d\n",index);
	}
	return 0;
}