從一道簡(jiǎn)單題談程序設(shè)計(jì)的思維
題目
Stick
Problem
Anthony has collected a large amount of sticks for manufacturing chopsticks. In order to simplify his job, he wants to fetch two equal-length sticks for machining at a time. After checking it over, Anthony finds that it is always possible that only one stick is left at last, because of the odd number of sticks and some other unknown reasons. For example, Anthony may have three sticks with length 1, 2, and 1 respectively. He fetches the first and the third for machinning, and leaves the second one at last. Your task is to report the length of the last stick.
Input
The input file will consist of several cases.
Each case will be presented by an integer n (1 <= n <= 100, and n is odd) at first. Following that, n positive integers will be given, one in a line. These numbers indicate the length of the sticks collected by Anthony.
The input is ended by n = 0.
Output
For each case, output an integer in a line, which is the length of the last stick.
Sample Output
2
題目分析
題意是對(duì)于給定的n（n為奇數(shù)）根木棒，其中有n - 1根是可以按長(zhǎng)度配對(duì)的，找出按長(zhǎng)度配對(duì)后剩余的一根木棒。
下面給出這題的幾種解法：
（1）對(duì)于每根木棒，都搜索與其匹配的另一根木棒，時(shí)間復(fù)雜度為O(n2)；
（2）先將木棒按其長(zhǎng)度排序，然后依次掃描各相鄰木棒是否匹配，時(shí)間復(fù)雜度為O(nlogn)；
（3）對(duì)于任意的x，都滿足如下公式：x Xor 0 = x， x Xor x = 0。而且異或操作是滿足交換律和結(jié)合律的，因此所有配對(duì)的木棒異或后結(jié)果為0，因此將所有木棒的長(zhǎng)度異或后得到的結(jié)果即為不成對(duì)的那根木棒的長(zhǎng)度，時(shí)間復(fù)雜度為O(n)。
思考題
（1）有長(zhǎng)度為1到n共n根木棒，現(xiàn)從中拿走某一根，再放入一根任意長(zhǎng)度的木棒。順次輸入這n根木棒的長(zhǎng)度，求拿走與放入木棒的長(zhǎng)度分別是多少？
（2）有n根木棒，其中有多于一半的木棒其長(zhǎng)度相等，順次輸入所有木棒的長(zhǎng)度，求出這些長(zhǎng)度相等的木棒的長(zhǎng)度是多少？
參考資料
郭嵩山、張子臻、王磊、湯振東著 國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽例題解（五） 電子工業(yè)出版社