首页 > 代码库 > S-Trees UVA 712
S-Trees UVA 712
说说:
先来说一下题意,题意感觉挺难描述的。有如下这样一棵树:
每一层都有一个变量描述,如左树,从根节点到倒数第二层为x1,x2,x3,而右树为x3,x1,x2,这在开始的时候会给定的。然后题目也会给你从左到右叶子节点所代表的数值,只可能是0或1.最后,会给你一串01数字,代表的是x1,x2,x3...的数值。相当于告诉你从树的根到叶子节点行走的路径。比如右树,从根到倒数第二层的变量依次为x3,x1,x2,如果题目给你它们的值为110(这是按顺序的,即x1=1,x2=1,x3=0)。那么我们的行走路径为(0代表进入左子树,1反之)左,右,右,即如图所示。
我的解法是先用一个数字标记变量的所在的层数。那样通过这个数组的间接操作,我们就能找到每一层的变量的值了。然后其实我们可以将树的叶子节点从做到右编号,将所有叶子保存在一个字符数组中。接着初始一个变量ans为0,若进入左子树,仅将ans右移一位,反之,则ans右移一位且+1。最后我们到达叶子节点后,ans保存的就是叶子所在的序号,输出结果即可。可能描述地不太清楚,看代码也许会更明白一点^_^
源代码:
#include <stdio.h> #define MAX 7+5 int main(){ int order[MAX];//保存每层的变量序号 char terminal[1000],x[3],test[MAX]; int n,m,T=1,i,ans; // freopen("data","r",stdin); while(scanf("%d",&n)&&n){ for(i=0;i<n;i++){ scanf("%s",x); order[i]=x[1]-'1'; } scanf("%s",terminal);//叶子节点 scanf("%d",&m); printf("S-Tree #%d:\n",T++); while(m--){ scanf("%s",test); ans=0; for(i=0;i<n;i++)//通过每层变量的序号,找到该变量并判断 if(test[order[i]]=='0')//进入左子树 ans=ans<<1; else ans=(ans<<1)+1;//进入右子树 putchar(terminal[ans]); } printf("\n\n"); } return 0; }
S-Trees UVA 712
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。