7-111 前世档案 (15 分)
网络世界中时常会遇到这类滑稽的算命小程序，实现原理很简单，随便设计几个问题，根据玩家对每个问题的回答选择一条判断树中的路径（如下图所示），结论就是路径终点对应的那个结点。
现在我们把结论从左到右顺序编号，编号从 1 开始。这里假设回答都是简单的“是”或“否”，又假设回答“是”对应向左的路径，回答“否”对应向右的路径。给定玩家的一系列回答，请你返回其得到的结论的编号。
输入格式：
输入第一行给出两个正整数：N（≤30）为玩家做一次测试要回答的问题数量；M（≤100）为玩家人数。
随后 M 行，每行顺次给出玩家的 N 个回答。这里用 y 代表“是”，用 n 代表“否”。
输出格式：
对每个玩家，在一行中输出其对应的结论的编号。
输入样例：
3 4 yny nyy nyn yyn
结尾无空行
输出样例：
3 5 6 2
结尾无空行
#include<iostream> #include<cmath> using namespace std; int main(){ int m,n; cin>>n>>m; string s; for(int i=0;i<m;i++){ int sum=1; cin>>s; for(int j=0;j<n;j++){ if(s[j]=='y') sum+=0; else sum+=pow(2,n-1-j); } cout<<sum<<endl; } return 0; }
/* 有题目可知，最小值为1，即结论1，最大值是结论2^N 当为y的时候，表示是左子树，因此，原有值不需要改动 当为n时，表示在右子树，此时需要在原有值的基础上 加上 当前结点所有的叶节点的一半 */ #include<bits/stdc++.h> using namespace std; char str[35]; int N,M; int main() { scanf("%d %d",&N,&M); int k = pow(2,N); // 计算出最大结论值 int index,n; for(int i=0;i<M;i++){ index = 1; // 每次循环，都要将结论值赋值为1 n = k; // 修改当前结点所拥有的叶节点，这个时候是根节点，所以置为 k scanf("%s",str); for(int j=0;j<strlen(str);j++){ // 遍历输入的字符串 if(str[j]=='n'){ // 若为 n ，则表示需要加上当前结点所拥有的叶节点个数的一半 index += (n/2); } n /= 2; // 每次循环，叶节点的数量都会减半 } printf("%d\n",index); // 输出结果即可 } return 0; }
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e3+10; char s[N]; int n,m; int main() { cin>>n>>m; for(int i=1;i<=m;i++) { cin>>s; int x=1; for(int i=0;s[i];i++) { if(s[i]=='y')x*=2; else x=x*2+1; } int y=pow(2,n)-1;//上一层最后一个节点编号 printf("%d\n",x-y); } return 0; }
