南星&北斗 2015-07-12 14:24 采纳率: 0%
浏览 2053
已采纳

排序重构的问题,求解答

令A为一个由N个已特殊排序数组成的数列:A1,A2,…,AN,其中A1=0。令B为N(N-1)/2个数(定义为Dij=Ai-Aj(i>j))组成的数列。例如,A=0,1,5,8,那么D=1,3,4,5,7,8。请完成:
a) 编写程序,根据A构造D;
b) 编写程序,构造与D相对应的某一个数列A,注意A不是唯一的

  • 写回答

3条回答 默认 最新

  • JonsonJiao 2015-07-13 02:11
    关注
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class ArrayDemo {
    
        public static void main(String[] args) {
            Integer[] aArray = new Integer[] { 0, 1, 5, 8 };
    
            // 第一步获取D数组
            System.out.println("根据A计算得到的数组D:");
            Integer[] dArray = getDArray(aArray);
    
            for (int i = 0; i < dArray.length; i++) {
                System.out.println(dArray[i]);
            }
            // 第二步根据D数组反求A数组
            System.out.println("反求得到的数组A:");
            Integer[] _aArray = getAArray(dArray);
            for (int i = 0; i < _aArray.length; i++) {
                System.out.println(_aArray[i]);
            }
        }
    
        /**
         * 构造与D相对应的某一个数列A,注意A不是唯一的
         * 
         * @param dArray
         * @return
         */
        private static Integer[] getAArray(Integer[] dArray) {
            int dLen = dArray.length;
            int aLen = getALen(dLen);
            if (aLen == 0) {
                System.err.println("计算A的数组出错,请确认传入的D数组有效。");
                return null;
            }
    
            // 因为A1必须为0,可以直接确定A1,并设置A最后一个值为D的最后一个值,保证了最大值。同时A2=A1+D1,A3=A2+D2,依次类推,认为D是有序数组,遍历D数组得到中间A的所有数据
            Integer[] aArray = new Integer[aLen];
            aArray[0] = 0;
            aArray[aLen - 1] = dArray[dLen - 1];
            for (int i = 1; i < aLen - 1; i++) {
                aArray[i] = aArray[i - 1] + dArray[i];
            }
            return aArray;
        }
    
        /**
         * 根据传入的D数组的长度求出A数组的长度来,就是解一元二次方程n*n-n=2*dLen,n代表A数组的长度
         * 
         * @param dLen
         * @return
         */
        private static int getALen(int dLen) {
            for (int n = 2; n <= 2 * dLen; n++) {
                if (n * n - n - 2 * dLen == 0) {
                    return n;
                }
            }
            return 0;
        }
    
        /**
         * 令aArray为一个由N个已特殊排序数组成的数列:A1,A2,…,AN,其中A1=0。令D为N(N-1)/2个数(定义为Dij=Ai-Aj(i>j
         * )组成的数列。例如,A=0,1,5,8,那么D=1,3,4,5,7,8
         * 
         * @param aArray
         * @return
         */
        private static Integer[] getDArray(Integer[] aArray) {
            int aLen = aArray.length;
            int dLen = aLen * (aLen - 1) / 2;
            List<Integer> tempList = new ArrayList<Integer>();
            for (int i = 0; i < aArray.length; i++) {
                for (int j = i + 1; j < aArray.length; j++) {
                    if (tempList.size() == dLen) {
                        i = aLen;
                        break;
                    } else {
                        tempList.add(aArray[j] - aArray[i]);
                    }
                }
            }
            Integer[] dArray = tempList.toArray(new Integer[0]);
            Arrays.sort(dArray);
            return dArray;
        }
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

悬赏问题

  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误