光环大数据培训 递归算法之n阶矩阵行列式求解

 

在数学中，很多数学函数都是由一个公式来表达的，比如 f(x) = 100x; 这个公式可以让我们把长度米转换成长度厘米。 有了这个公式，在程序中敲出一行代码，写出一个函数（function）来计算实在是太简单方便了，就像这样。

 

int convert(int m){    return 100*m;
}

 

我们就写好了一个函数来进行米到厘米的单位换算。

 

但是有的时候，数学函数会以不太标准的形式来定义，比如这个函数，他满足 f(0)=0而且 f(x) = 2f(x-1)+x; 从这个函数定义我们可以得出 f(1)=1;f(2)=3;等等。当一个函数用他自己来定义时就称为这个函数是递归的。

 

通俗地讲，就是从前有个山，山里有个庙，庙里有个老和尚再给小和尚讲故事，讲的是：从前有个山，山里有个庙，庙里有个老和尚再给小和尚讲故事。。。。这就是递归。

 

好了说了这么多你们肯定还是一头雾水，现在来实践一下。

 

 

递归求阶乘

 

刚开始学编程的同学一定会写求阶乘的函数，使用for循环或者while循环都可以，但是递归却完全用不上这两个循环。

 

public static int factorial(int a){    if (a==0 || a==1){        return 1;
    }    return a*factorial(a-1);
}

 

上面的代码就是递归求阶乘的方法，a是需要传入的参数，比如我们要求5的阶乘就传入5这样factorial函数最终的返回值为120；

 

分析这段代码，他的第3行到第五行处理了 基准情况（Base Case），在这个情况下，函数的值可以直接算出而不用求出递归。就像上文提到的函数f(x) = 2f(x-1)+x;如果没有f(0)=0这个事实在数学上没有意义一样。 再编程中，如果没有基准情况也是无意义的。第7行执行的是递归调用。

 

所以所，设计递归算法，需要包含以下两个基本法则：

 

1、基准情形（Base Case），必须总要有某些基准的清醒，在这个情形中，不执行递归就能求解。

 

2、不断推进（Making Progress），对于需要递归求解的情形，递归调用必须总能够朝着一个基准情形推进。这样的话，不断推进到基准情形，到达基准情形的时候递归才会推出，得到返回值。

 

 

 

n阶矩阵行列式的求解

 

有了刚在知识的铺垫，现在我们可以动手写一个程序来用递归计算n阶矩阵的行列式了。

首先来看下二阶矩阵的求法：

 

 

 

也就是说2×2矩阵的元素交叉相乘再想减即可求出行列式。

 

接下来是3阶矩阵：

 

 

 

3×3矩阵求解中，选择任意行或者列，在那一行/列中,移除那个元素所在的行和列比如选择a11，则移除第一行和第一列，这样矩阵就变成了2×2的，再按照刚才的方法求2×2矩阵的行列式即可。之后整个行或列的3个元素进行此类运算后相加就是3×3的行列式。

 

n x n矩阵：

 

n阶矩阵就和3阶矩阵求解的方法一样了，使用3×3求解的方法，比如4阶矩阵，将4阶消除成3阶，然后再变成2阶来算。但是矩阵每上升一个维度，计算量就会扩大很多。

 

 

 

知道了n阶矩阵行列式的计算思路后，就可以开始编写算法了。

 

首先是数据结构设计，我们需要设计一个矩阵类来提供便利，这个类有两个成员，一个二维数组，用来储存矩阵，一个整数，来储存矩阵的行数或列数（行列式必须是方矩阵才可以求解所以行列无所谓）。

 

以下是整个Matrix类的设计：

 

static class Matrix{    private int rowNum=0;    private int[][] array;    //Constructor
    public Matrix(int rowNum){        this.rowNum = rowNum;        array = new int[rowNum][rowNum];
    }    public Matrix(int[][] array){        this.array = array;        this.rowNum = array.length;
    }    int counter = 0; //For add Element

    public void addElement(int a){        array[(counter)/rowNum][counter%rowNum] = a;
        counter++;
    }    //Print the instance itself
    public void printMat(){        for (int i=0;i < rowNum ;i++){            for (int j=0;j < rowNum ;j++){
                 System.out.print(array[i][j]+/t;);
            }
            System.out.println();
        }
    }    //Setter and Getter
    public int getRowNum() {        return rowNum;
    }    public int[][] getArray() {        return array;
    }    public void setArray(int[][] array) {        this.array = array;
    }

}

 

Matrix类中有两个构造方法：传入整数a会初始化一个axa大小的空矩阵，传入一个二维数组的话即可根据二维初始化一个Matrix对象。

 

Matrix类中有一个方法比较特殊：addElement方法，通过不断调用这个函数即可向一个Matrix实例进行有顺序的负值，第一次调用则会更改第第一行第一列位置上的值，第二次调用则会更改第一行第二列上的值，以此类推。

 

接下来就是设计一个MatrixCalculator类的，这个类中的一个成员方法可以求出行列式，我命名他为getDet(); 在计算行列式的时候需要移除元素所在的行和列，生成一个减小了一个维度的矩阵，我们需要编写一个方法来完成这个操作，我命名他为removeRowAndCol()；还有一个方法，由于相加的时候会产生符号的改变，所以需要写一个方法来计算矩阵中一个元素的cofactor，命名为getCofactor。

 

以下就是removeRowAndCol方法的代码：传入需要移除的行和列和一个Matrix对象，函数会返回消除了指定行和列的Matrix对象。

 

public static Matrix removeRowAndCol(int row,int col,Matrix mat){    int matRowNum = mat.getRowNum();    int[][] arr = mat.getArray();

    Matrix matrix = new Matrix(matRowNum-1);    for (int i = 0;i < matRowNum; i++){        for (int j = 0 < matRowNum; j++){                if (i!=row && j!=col) {
                    matrix.addElement(arr[i][j]);
                }
        }
    }

    matrix.printMat();    return matrix;

}

 

以下是getCofactor方法：由于我的算法只会去遍历矩阵第一列来进行求解，所以得到Cofactor的代码就变得简单很多。

 

public static int getCofactor(int colNum){    if (colNum%2 == 0){        return 1;
    }else {        return -1;
    }
}

 

接下来就是核心的递归求解行列式的算法了，先理一下思路，递归算法的两个要素：基准情形，不断推进。

 

对于n阶矩阵什么是基准情形呢？就是矩阵被降为2×2维度的时候，直接返回交叉相乘的差即可，不断推进，如果是一个4阶矩阵，算法会先把4将为3×3矩阵，然后3×3再拆成3个2×2矩阵来达到基准情形来算出答案，就和我们手算行列式时用到的方法一样，手算时候也遵循这一算法。

 

public static int getDet(Matrix targetMatrix){    //Base (Finally reduced to 2 x 2 Matrix)
    if (targetMatrix.rowNum == 2){        int[][] arr = targetMatrix.getArray();        // a*d - b*c
        return arr[0][0]*arr[1][1] - arr[0][1]*arr[1][0];
    }    //MARK- Recursion: to reduce dimension
    int det = 0;    int colNum = targetMatrix.rowNum;    for (int i = 0; < colNum;i++){
        det+= (targetMatrix.getArray()[i][0])*getCofactor(i)*getDet(removeRowAndCol(i,0,targetMatrix));
    }    return det;
}

 

只有不到20行代码，但是却可以解决nxn的矩阵，是不是很神奇，这就是递归的优势，把一个很庞大的问题转化为规模缩小了的同类问题的子问题来求解。n阶矩阵最后被降为若干个2×2矩阵。

 

加上适当的输出语句，来求解一个3阶矩阵行列式试一下：

 

2   1    2 -1   5   21 13 -1  -17Element: 2Cofactor: 1Removing Row 0 Col 0A 2 x 2 Matrix is initialized 
5 21 -1 -17 END State Reached
Det: -64Element: -1Cofactor: -1Removing Row 1 Col 0A 2 x 2 Matrix is initialized 
1 2 -1 -17 END State Reached
Det: -15Element: 13Cofactor: 1Removing Row 2 Col 0A 2 x 2 Matrix is initialized 
1 2 5 21 END State Reached
Det: 11Result: 0

 

但是有一个问题需要注意，就是这个算法的复杂度。

 

算法复杂度

 

这个算法的复杂度为O(n!), 这意味着他的运行速度很慢，随着问题规模的增长，时间会大幅度增长。在我的电脑上，计算3×3到7×7内规模的矩阵，电脑都可以秒算出来，但是如果是一个10×10的矩阵，电脑需要54秒钟，到了11×11时间将会变得更长，下图是这个算法随着问题规模增长对运行时产生影响的曲线。

 

可以看出7×7矩阵需要递归517次，到了10×10需要大约260万次递归运算才能得到结果。可见问题规模增长后时间的开销是十分巨大的。

 

 

　　大数据分析、大数据分析师、大数据培训哪家好、大数据培训靠谱吗、大数据培训排行榜，就选光环大数据！

 

大数据培训、人工智能培训、Python培训、大数据培训机构、大数据培训班、数据分析培训、大数据可视化培训，就选光环大数据！光环大数据，聘请专业的大数据领域知名讲师，确保教学的整体质量与教学水准。讲师团及时掌握时代潮流技术，将前沿技能融入教学中，确保学生所学知识顺应时代所需。通过深入浅出、通俗易懂的教学方式，指导学生更快的掌握技能知识，成就上万个高薪就业学子。 更多问题咨询，欢迎点击------>>>>在线客服！