安徽省年度“达内杯”程序设计大赛解题报告(doc 19页)

安徽省年度“达内杯”程序设计大赛解题报告内容提要：
B-转换二叉树：
首先根据先序序列和中序序列建立二叉树，然后按要求先序遍历一遍二叉树即可。当然，由于建树过程实际也是在先序遍历二叉树，所以可以不用实际建树，只是模拟那个过程，然后再过程中输出即可。建树过程简单的说就是以先序序列定根节点，以中序序列和和根节点定左右子树。
C-取石子：
首先给出必胜结论，只要n != 2^x，则先手必胜。证明：假设n = 12，将它转换为二进制则为'1100'。先手第一次取只需把二进制中从低位数起第一个'1'取走即可。在这个例子中，先手留给后手石子数的二进制为'1000'。这样后手能取的石子数的二进制范围为'0001'-'0100'，无论后手怎么取，它都不可能把所有数字都取完，而且取了之后剩下的石子数的二进制后3位肯定有一个'1'。先手只需再次将从低位数起的第一个'1'取走即可重复上述过程直至游戏结束。而如果先手第一次面对的石子数是2^x个，由于他第一次不能把石子都取完，所以他无论如何取都会把上述必胜状态留给对手。

..............................