數據結構考研分類復習真題 第五章 答案[32]

　　[題目分析] 因為數組中存放的是從到N的自然數原程序運行後數組元素A[i](<=i<=N)中存放的是A[]到A[i]中比原A[i]小的數據元素的個數易見A[N]+就是原A[N]的值(假定是j<=j<=N)設一元素值為的輔助數組flag采用累加確定一個值後flag中相應元素置零下面程序段將A還原成原來的A:

　　VAR flag:ARRAY[N] OF integer;
　　FOR i:= TO N DO flag[i]:=;   //賦初值
　　FOR i:=N DOWNTO DO
　　BEGIN sum:=; j:=; found:=false;
　　WHILE j<=N AND NOT found DO
　　BEGIN sum:=sum+flag[j];
　　IF sum=A[i]+ THEN BEGIN flag[j]:=; found:=true; END;
　　END;
　　A[i]:=j;
　　END;

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23041.html