#java#关于我用两种方案解决同一个技术问题产生的奇怪现象（相关搜索：自学java|逆序数）

Question

好的,我本人是大一新生,最近在自学java,进度在石头迷阵这个板块,在完成这个项目之后我发现迷阵会产生无法还原的情况,因此我寻找了各种解决方法,在一个文章那里获得灵感,利用了逆序数的概念,因此我对打乱后的数组进行了逆序数的判断并做出了解决,关于逆序数的结论是这样的:

不将空白块带入逆序数的计算的话,对于四阶拼图，空白块在4、2行（行索引为3、1）时，逆序数为偶数才能保证拼图可还原，空白块在3、1行（行索引为2、0）时，逆序数为奇数才能保证拼图可还原.

因此我写出了下面这些代码:

public void puzzle() {//此方法用于计算逆序数
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data[i].length; j++) {
                if (data[i][j] != 0 && data[i][0] > data[i][1]) {
                    inverse++;
                }
                if (data[i][j] != 0 && data[i][0] > data[i][2]) {
                    inverse++;
                }
                if (data[i][j] != 0 && data[i][0] > data[i][3]) {
                    inverse++;
                }
                if (data[i][j] != 0 && data[i][1] > data[i][2]) {
                    inverse++;
                }
                if (data[i][j] != 0 && data[i][1] > data[i][3]) {
                    inverse++;
                }
                if (data[i][j] != 0 && data[i][2] > data[i][3]) {
                    inverse++;
                }
            }
        }
    }

并且进行了以下处理:

    public void initData() {//此方法用于初始化数据,即打乱二维数组
        Random r = new Random();//创建对象,准备随机数
        for (int i = 0; i < data.length; i++) {//遍历二维数组中的一维数组
            for (int j = 0; j < data[i].length; j++) {//遍历一维数组中的元素
                int x = r.nextInt(4);//创建两个随机索引
                int y = r.nextInt(4);
                int temp = data[i][j];//接下来三步用于交换原数据与随机数据
                data[i][j] = data[x][y];
                data[x][y] = temp;
                if (data[i][j] == 0) {//在此判断元素是否为零号元素
                    row = i;//不在此定义这两个变量是为了使移动业务能使用这两个变量
                    column = j;// 因此在成员变量位置定义出来
                }
            }
        }
        puzzle();//接下来对游戏是否可解进行判断
        if (row == 1 || row == 3) {//当空白块在第2/4行时,若逆序数为奇数则无法还原
            if (inverse / 4 % 2 != 0 && column != 3) {//解决思路为判断空白块是否在第三列,不在的话将其与右边块进行交换
                int temp = data[row][column];
                data[row][column] = data[row][column + 1];
                data[row][column + 1] = temp;
            } else if (inverse / 4 % 2 != 0 && column == 3) {//如果空白快在第三列,则将其与左边方块交换
                int temp = data[row][column];
                data[row][column] = data[row][column - 1];
                data[row][column - 1] = temp;
            }
        } else if (row == 0 || row == 2) {//当空白块在第1/3行时,若逆序数为偶数则无法还原
            if (inverse / 4 % 2 == 0 && column != 3) {//解决思路与上面相同
                int temp = data[row][column];
                data[row][column] = data[row][column + 1];
                data[row][column + 1] = temp;
            } else if (inverse / 4 % 2 == 0 && column == 3) {
                int temp = data[row][column];
                data[row][column] = data[row][column - 1];
                data[row][column - 1] = temp;
            }
        }
        for (int i = 0; i < data.length; i++) {//在这里需要重新定位空白块,否则上面处理完之后定位会失效
            for (int j = 0; j < data[i].length; j++) {
                if (data[i][j] == 0) {//在此判断元素是否为零号元素
                    row = i;//不在此定义这两个变量是为了使移动业务能使用这两个变量
                    column = j;// 因此在成员变量位置定义出来
                }
            }
        }
    }

首先呢,我承认自己代码写的很烂,但我还刚刚起步,请多多见谅,在这之后我又从另一位师兄那里获得灵感,找出了另一种解决方案,也就是改变打乱方块的逻辑:

    public void initData() {//此方法用于初始化数据,即打乱二维数组
        Random random = new Random();//创建对象,准备随机数
        for (int rank = 0; rank <= 100; rank++) {//这是第二种打乱方式
            int r = random.nextInt(4);//创造一个随机数决定空白块的移动方式
            if (r == 0 && column != 0) {//如果r为0且空白块不在最左边则让空白块向左交换
                int temp = data[row][column];
                data[row][column] = data[row][column - 1];
                data[row][column - 1] = temp;
            } else if (r == 1 && row != 0) {//如果r为1且空白块不在最上边则让空白块向上交换
                int temp = data[row][column];
                data[row][column] = data[row - 1][column];
                data[row - 1][column] = temp;
            } else if (r == 2 && column != 3) {//如果r为2且空白块不在最右边则让空白块向右交换
                int temp = data[row][column];
                data[row][column] = data[row][column + 1];
                data[row][column + 1] = temp;
            } else if (r == 3 && row != 3) {//如果r为3且空白块不在最下边则让空白块向下交换
                int temp = data[row][column];
                data[row][column] = data[row + 1][column];
                data[row + 1][column] = temp;
            }
            for (int i = 0; i < data.length; i++) {//每次空白块移动都要重新定位
                for (int j = 0; j < data[i].length; j++) {
                    if (data[i][j] == 0) {
                        row = i;
                        column = j;
                    }
                }
            }
        }
    }

虽然这个方法解决了迷宫不可还原的问题,但是也产生了另一个令我疑惑不解的现象:

那就是虽然这个空白块在第三行,但它的逆序数却是12,按照之前的规律,空白块在1/3行时,其逆序数必须为奇数才可还原,然而12是个偶数而且这个迷宫确实可以还原.

这个现象的发生完全违背了之前的规律,而这样的情况不在少数,先前的规律完全作废了,无论在哪一行,逆序数都有可能出现奇偶的情况,我们无法再依照之前的规律进行判断,我本人对此非常疑惑,因此发布了这个问题,希望能有人进行解答,非常感谢!

Answer 1

【相关推荐】

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7483606
• 你也可以参考下这篇文章：定义一个含有五个元素的数组,并为每个元素赋值,求数组中所有元素的最小值
• 除此之外, 这篇博客: C语言实现八大排序算法详解及其性能之间的中的 我们老师给我们花了100个星星的重要，那就是非常重要，快速排序。名字就很嚣张。。。言归正传，快排采用了分治算法。把大问题，分解成小问题。首先我们先找一个基准值，基准值的寻找法，有很多，这里我先用一个取边上值得方法，找到基准值以后呢拿着这个基准值和所有数组比较，使这个数组中比基准值小的都放左边，比基准值大的都放到右边，然后就把原来数组分成三块，中间基准值，左边都是比它小的，右边都是比它大的。然后这两个数组，继续分，一直分。直到他的终止条件，也就是小数组有序了就停止，那么什么时候有序停止呢？小区间长度为1或者长度为0的时候，就是有序了。所有小数组都有序了，那么就是整个数组有序了。只是原理，那么问题，又来了，怎么放左放右呢？我目前会三种。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

  算法思想

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^