安徽省年度“達內杯”程序設計大賽解題報告(doc 19頁)

安徽省年度“達內杯”程序設計大賽解題報告內容提要：
B-轉換二叉樹：
首先根據先序序列和中序序列建立二叉樹，然後按要求先序遍曆一遍二叉樹即可。當然，由於建樹過程實際也是在先序遍曆二叉樹，所以可以不用實際建樹，隻是模擬那個過程，然後再過程中輸出即可。建樹過程簡單的說就是以先序序列定根節點，以中序序列和和根節點定左右子樹。
C-取石子：
首先給出必勝結論，隻要n != 2^x，則先手必勝。證明：假設n = 12，將它轉換為二進製則為'1100'。先手第一次取隻需把二進製中從低位數起第一個'1'取走即可。在這個例子中，先手留給後手石子數的二進製為'1000'。這樣後手能取的石子數的二進製範圍為'0001'-'0100'，無論後手怎麼取，它都不可能把所有數字都取完，而且取了之後剩下的石子數的二進製後3位肯定有一個'1'。先手隻需再次將從低位數起的第一個'1'取走即可重複上述過程直至遊戲結束。而如果先手第一次麵對的石子數是2^x個，由於他第一次不能把石子都取完，所以他無論如何取都會把上述必勝狀態留給對手。

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