Ex3-23 親兄弟問題
« 問題描述：
給定n 個整數(shù)0 1 1 , , , n- a a a 組成的序列。序列中元素i a 的親兄弟元素k a 定義為：
min{ | } k i j n j j i a = a a ³ a
< <
。
親兄弟問題要求給定序列中每個元素的親兄弟元素的位置。元素i a 的親兄弟元素為k a
時，稱k 為元素i a 的親兄弟元素的位置。當(dāng)元素i a 沒有親兄弟元素時，約定其親兄弟元素
的位置為-1。
例如，當(dāng)n=10，整數(shù)序列為6，1，4，3，6，2，4，7，3，5 時，相應(yīng)的親兄弟元素位
置序列為：4，2，4，4，7，6，7，-1，9，-1。
« 編程任務(wù)：
對于給定的n個整數(shù)0 1 1 , , , n- a a a 組成的序列，試用抽象數(shù)據(jù)類型棧，設(shè)計一個O(n)
時間算法，計算相應(yīng)的親兄弟元素位置序列。
« 數(shù)據(jù)輸入：
由文件input.txt提供輸入數(shù)據(jù)。文件的第1 行有1 個正整數(shù)n，表示給定給n個整數(shù)。
第2 行是0 1 1 , , , n- a a a 。
« 結(jié)果輸出:
程序運行結(jié)束時，將計算出的與給定序列相應(yīng)的親兄弟元素位置序列輸出到output.txt
中。
輸入文件示例 輸出文件示例
input.txt
10
4 2 4 4 7 6 7 -1 9 -1
output.txt
6 1 4 3 6 2 4 7 3 5
標簽：
61516
laquo
min
序列
上傳時間：
2013-12-17
上傳用戶：shizhanincc
