排序重构问题 用C/C++实现

Question

令A为一个由N个已特殊排序数组成的数列：A1 A2 … AN，其中A1=0。令B为N（N-1）/2个数（定义为Bij=Ai-Aj(i>j)）组成的数列。例如，A=0 1 5 8，那么D=1 3 4 5 7 8。请完成：

1. 编写程序，根据A构造D；
   2）编写程序，构造与D相对应的某一个数列A，注意A不是唯一的。

Answer 1

题目应该是笔误了，莫名出现了D，似乎应该是B。那么按B来理解D，思路如下：

1. 用两重循环， i=[N,2], j=[i-1,1], 求出所有Bij， 再按从小到大进行排序，构成数列B。
2. 因为限定了A1=0， 所以B中最大数必然是AN，其他数必然存在成对出现的Bi + Bj = AN。找出N - 2对这样的数，每对取其中一个，再加上0和AN，就能构造出一个备选的数列A。再将备选数列按题设算法构造数列B'。如果B'与B一致，就可以判断当前的备选数列A满足条件。备选数列A的可能性有2^(N-2)种。

以例子中的数据为例，
8 = 1+7 = 3+5.
如果取 1和5,就得到 0 1 5 8. 验证可以推导出 1 3 4 5 7 8. 匹配。
如果取 3 和 7， 就得到 0 3 7 8. 验证可以推导出 1 3 4 5 7 8. 匹配。
如果取1和3， 就得到 0 1 3 8. 验证推导出 1 2 3 5 7 8. 不匹配。
如果取 7 和5 ，就得到 0 5 7 8, 验证推导出 1 2 3 5 7 8. 不匹配。