乐趣区

关于算法:全排列算法及解决数字搭积木问题

如果你是做这道题不会,那么你能够看这道题的解题思路,如果你是不太了解全排列算法,那么你能够通过这个题来了解。

题目形容:

小明最近喜爱搭数字积木。一共有 10 块积木,每个积木上有一个数字,0~9。

搭积木规定:
每个积木放到其它 两个积木的下面 ,并且肯定 比上面的两个积木数字小
最初搭成 4 层的金字塔形,必须用完所有的积木。

上面是两种合格的搭法:

请你计算这样的搭法一共有多少种?

剖析

一共有 10 个数字,要咱们把所有可行的排列形式都求进去,一时没什么思路,索性就全排列了,把所有排列的状况都求进去,而后在把每种状况都判断一下,是不是就能够失去答案了。

所以 全排列 怎么写成了第一大问题了。

全排列

对于这个问题来说,咱们把金字塔当成一个 int 数组,那么就为 全排列这个数组{0,1,2,3,4,5,6,7,8,9}。

太长了,想不明确呀,所以来看比拟少的呗。
对于 {0,1} 全排列,就是把 0 抽出来,1 做全排列,对于{0,1,2}, 就是:

  1. 把 0 抽出来,把 1,2 做全排列,
  2. 把 1 抽出来,把 0,2 做全排列,
  3. 把 2 抽出来,把 0,1 做全排列。
  4. 接下来那不就和下面那个 {0,1} 一样了吗?

这是不是个递归呢? 很显著吧。确实是。

那好咱们定义一个办法,这个办法的作用是,把 list 数组全排列 ,而参数 curr 示意 以后抽出来的那个数,就像下面例子提到的 0 一样。

提出来了之后呢,是不是要把 curr 替换 了,这样就能够把所有在这个地位上的所有状况列出来了,所以应用一个 for 循环,来替换 curr 和前面残余数组的数(就是下面例子的 1,2,3 步骤)。

紧接着定义一个办法,替换两数swap(list,curr,j);,当然你也能够把这个办法间接写到这个函数外面,然而毕竟不美观,不实用。

重点来了:回溯!!!

从这张图中,所谓回溯就是要回到上一没有操作过的状态,再去思考别的状况。就上面这个 A,B,C 他须要回到上一次抽数进去之前的状态。这样他能力去抽另外一个数,全排列下一种状况。所以咱们须要在写一遍swap(list,curr,j);

问题剖析到这了,咱们的代码基本上就能够进去了,所以看下代码,如果看不懂在回到我的剖析,置信你肯定能看懂。

public class Test2 {
    static int sum ;
    public static void main(String[] args) {int list[] = {0,1,2,3,4,5,6,7,8,9};
        allSort(list,0);
        System.out.println(sum);
    }
    // 代表将第 a[m]和 a[n]相替换
    public static void swap(int a[],int m ,int n){int temp = a[m];
        a[m] = a[n];
        a[n] = temp;
    }
    // 调用全排列数组 list,curr 代表以后放在第一个的为第几个数字,比方开始就为数组第 0 个数字
    public static void allSort(int list[],int curr ){
        // 如果以后数组的索引等于数组的长了,就将办法加 1
        if (curr == list.length-1){check(list);
        }else {
            // 数组每一个都要和以后数组的第 curr 个相替换,所以要用个循环
            for (int j = curr; j < list.length; j++){swap(list,curr,j);
                allSort(list,curr+1);
                swap(list,curr,j);
            }
        }
    }
    public static void check(int list[]){if (list[1] < list[0]) return;
        if (list[2] < list[0]) return;
        if (list[3] < list[1]) return;
        if (list[4] < list[1]) return;
        if (list[4] < list[2]) return;
        if (list[5] < list[2]) return;
        if (list[6] < list[3]) return;
        if (list[7] < list[3]) return;
        if (list[7] < list[4]) return;
        if (list[8] < list[4]) return;
        if (list[8] < list[5]) return;
        if (list[9] < list[5]) return;
        sum++;

    }

}

其实这个全排列都能够当成一个模板了,然而还是举荐大家肯定要手敲,本人写代码,写进去了,才是本人的货色。

图片参考:https://blog.csdn.net/Strom72…

退出移动版