专栏首页机器学习入门挑战程序竞赛系列(43):4.1矩阵 高斯消元

挑战程序竞赛系列(43):4.1矩阵 高斯消元

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/77747706

挑战程序竞赛系列(43):4.1矩阵 高斯消元

详细代码可以fork下Github上leetcode项目,不定期更新。

练习题如下:

POJ 2345: Central heating

知识点:高斯消元法,关于高斯消元法可以参考博文:

博文1: http://www.cppblog.com/menjitianya/archive/2014/06/08/207226.html

博文2: http://www.hankcs.com/program/algorithm/poj-2345-heating-central.html

我的理解: 它的核心在于消元,体现在迭代的过程当中,具体如下,依次遍历每一行,意味着消元消到了第i个变量,此时把后续行和第i个变量有关的全部消去,这样一来,第i+1行的所有变量数减一。

那么自然地,遍历到最后一行时,只剩一个变量,自然就出解了,接着把这个解慢慢往前回代,就能得到所有解。

此题思路:先将输入处理为01矩阵。题目用例中,如果第i个人管理第j个阀门,则记matrix[j][i] = 1,否则为0。然后目标是让所有闸门都开,也就是B向量都为1。

接着:把消元相减看成异或,乘法看成与运算,over。

代码如下:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main{

    String INPUT = "./data/judge/201708/P2345.txt";

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    static final int MAX_N = 255;
    int[][] matrix = new int[MAX_N][MAX_N];

    void solve() {
        while (more()){
            int n = ni();
            for (int i = 0; i < n; ++i){
                int j = ni();
                while (j != -1){
                    j--;
                    matrix[j][i] = 1;
                    matrix[j][n] = 1;
                    j = ni();
                }
            }
            int[] ans = gauss(matrix, n);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < ans.length; ++i){
                if (ans[i] == 1){
                    sb.append(" " + (i + 1));
                }
            }
            out.println(sb.deleteCharAt(0).toString());
        }
    }

    /*******************高斯消元法*********************/
    public int[] gauss(int[][] matrix, int n){
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i){

            int row = i;
            for (int j = i; j < n; ++j){
                if (matrix[j][i] > matrix[row][i]){
                    row = j;
                }
            }

            swap(matrix, i, row);

            for (int j = i + 1; j < n; ++j){
                if (matrix[j][i] == 1){
                    for (int k = i; k <= n; ++k){
                        matrix[j][k] ^= matrix[i][k];
                    }
                }
            }
        }

        for (int i = n - 1; i >= 0; --i){
            ans[i] = matrix[i][n];
            for (int j = i - 1; j >= 0; --j){
                matrix[j][n] ^= (ans[i] & matrix[j][i]);
            }
        }

        return ans;
    }

    public void swap(int[][] matrix, int i, int j){
        int n = matrix[0].length;
        for (int col = 0; col < n; ++col){
            int tmp = matrix[i][col];
            matrix[i][col] = matrix[j][col];
            matrix[j][col] = tmp;
        }
    }

    FastScanner in;
    PrintWriter out;

    void run() throws IOException {
        boolean oj;
        try {
            oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
        } catch (Exception e) {
            oj = System.getProperty("ONLINE_JUDGE") != null;
        }

        InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
        in = new FastScanner(is);
        out = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if (!oj){
            System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
        }
    }

    public boolean more(){
        return in.hasNext();
    }

    public int ni(){
        return in.nextInt();
    }

    public long nl(){
        return in.nextLong();
    }

    public double nd(){
        return in.nextDouble();
    }

    public String ns(){
        return in.nextString();
    }

    public char nc(){
        return in.nextChar();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        boolean hasNext;

        public FastScanner(InputStream is) throws IOException {
            br = new BufferedReader(new InputStreamReader(is));
            hasNext = true;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    hasNext = false;
                    return "##";
                }
            }
            return st.nextToken();
        }

        String next = null;
        public boolean hasNext(){
            next = nextToken();
            return hasNext;
        }

        public int nextInt() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Integer.parseInt(more);
        }

        public long nextLong() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Long.parseLong(more);
        }

        public double nextDouble() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Double.parseDouble(more);
        }

        public String nextString(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more;
        }

        public char nextChar(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more.charAt(0);
        }
    }
}

POJ 3532: Resistance

心累,学完数学还要学物理么,这里就不再讲解电路的知识了,有兴趣的可以参考博文: http://www.hankcs.com/program/algorithm/poj-3532-resistance.html

以及博文: http://blog.csdn.net/u012139398/article/details/41345607

我重在实现高斯算法:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

    String INPUT = "./data/judge/201708/P3532.txt";

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    static final int MAX_N = 100;
    static final double EPS = 1E-8;

    int N;
    void solve() {
        while (more()){
            N = ni();
            int M = ni();
            double[][] matrix = new double[MAX_N][MAX_N];
            for (int i = 0; i < M; ++i){
                int x = ni();
                int y = ni();
                int r = ni();
                --x;
                --y;
                double s = 1.0 / r;
                matrix[x][x] += s;
                matrix[y][y] += s;
                matrix[x][y] -= s;
                matrix[y][x] -= s;
            }
            N++;
            matrix[0][N] = 1.0;
            matrix[N - 2][N] = -1.0;
            matrix[N - 1][N - 2] = 1.0;
            out.printf("%.2f\n", gaussian(matrix));
        }
    }

    public double gaussian(double[][] cal){
        int n = N;
        for (int i = 0; i < n; ++i){
            int r;
            for (r = i; r < n; ++r){
                if (Math.abs(cal[r][i]) >= EPS){
                    break;
                }
            }

            if (r == n) continue;  // 无解直接跳过

            swap(cal, i, r);

            for (int j = i + 1; j <= n; ++j) cal[i][j] /= cal[i][i];

            cal[i][i] = 1.0;
            for (int j = 0; j < n; ++j){
                if (i != j){
                    for (int k = i + 1; k <= n; ++k){
                        cal[j][k] -= (cal[j][i] * cal[i][k]);
                    }
                    cal[j][i] = 0.0;
                }
            }
        }

        return cal[0][N] / cal[0][0];
    }

    public void swap(double[][] matrix, int i, int j){
        int n = matrix[0].length;
        for (int col = 0; col < n; ++col){
            double tmp = matrix[i][col];
            matrix[i][col] = matrix[j][col];
            matrix[j][col] = tmp;
        }
    }

    FastScanner in;
    PrintWriter out;

    void run() throws IOException {
        boolean oj;
        try {
            oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
        } catch (Exception e) {
            oj = System.getProperty("ONLINE_JUDGE") != null;
        }

        InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
        in = new FastScanner(is);
        out = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if (!oj){
            System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
        }
    }

    public boolean more(){
        return in.hasNext();
    }

    public int ni(){
        return in.nextInt();
    }

    public long nl(){
        return in.nextLong();
    }

    public double nd(){
        return in.nextDouble();
    }

    public String ns(){
        return in.nextString();
    }

    public char nc(){
        return in.nextChar();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        boolean hasNext;

        public FastScanner(InputStream is) throws IOException {
            br = new BufferedReader(new InputStreamReader(is));
            hasNext = true;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    hasNext = false;
                    return "##";
                }
            }
            return st.nextToken();
        }

        String next = null;
        public boolean hasNext(){
            next = nextToken();
            return hasNext;
        }

        public int nextInt() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Integer.parseInt(more);
        }

        public long nextLong() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Long.parseLong(more);
        }

        public double nextDouble() {
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return Double.parseDouble(more);
        }

        public String nextString(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more;
        }

        public char nextChar(){
            if (next == null){
                hasNext();
            }
            String more = next;
            next = null;
            return more.charAt(0);
        }
    }
}

需要注意的细节:进行归一化时,切记不要把当前变量给归一了,否则bug,所以有循环for从i+1开始,同理在消元时也从i+1开始。

POJ 3526: The Teacher’s Side of Math

此题的trick在于如何表达不同的αiβj\alpha^i\beta^j,很巧妙,因为在根号下,我们把式子转化为:

αimβjn

\alpha^{\frac{i}{m}}\beta^{\frac{j}{n}}

可以看出,i在(0,m)之间时,alpha一定为无理数,此题就是枚举出所有无理数之前的系数,让这些系数之和加起来等于0即可。

所以当i>m时,可以求出无理数之前的整数,比如:

αim=αi/m⋅αimodmm

\alpha^{\frac{i}{m}} = \alpha^{i / m}\cdot\alpha^{\frac{i\mod m}{m}}

i/m表示取下整哟,这样我们就可以把所有的α,β\alpha,\beta的无理数组合遍历出来,还恰好是:n*m + 1个方程。

你还可以参考:http://www.hankcs.com/program/algorithm/poj-3526-teacher-s-side-of-math-the.html

他的思路:

首先题目的隐含条件是,多项式最高次数一定为m*n。将(a1/m + b1/n)k二项展开后,除了最高次数项被题目限定为1之外,各项的系数和必须为0。以各项系数为变量,列出线性方程组,然后高斯消元求解即可。

JAVA代码如下:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main{

    String INPUT = "./data/judge/201708/P3526.txt";

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    static final double EPS = 1E-8;
    static final int MAX_N = 20 + 8;

    int[][] matrix = new int[MAX_N][MAX_N];
    int M, N, SIZE;

    void solve() {

        int[][] C = new int[MAX_N][MAX_N];
        C[0][0] = 1;
        for (int i = 1; i < MAX_N; ++i) {
            C[i][0] = 1;
            C[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            }
        }

        while (true) {
            int a = ni();
            int m = ni();
            int b = ni();
            int n = ni();
            M = m;
            N = n;
            if (a + m + b + n == 0)
                break;

            SIZE = n * m + 1;
            double[][] matrix = new double[SIZE][SIZE + 1];
            matrix[0][0] = matrix[0][SIZE] = 1;
            for (int i = 0; i < SIZE; ++i) {
                for (int j = 0; j <= i; ++j) {
                    matrix[to_index(j % m, (i - j) % n)][i < n * m ? i + 1 : 0] += C[i][j] * Math.pow((double) a, j / m)
                            * Math.pow((double) b, (i - j) / n);
                }
            }

            gaussian(matrix);

            StringBuilder sb = new StringBuilder();
            sb.append("1");
            for (int i = SIZE - 1; i >= 1; --i) {
                sb.append(" " + (int)(round(ans[i])));
            }
            out.println(sb.toString());
        }
    }

    double round(double x)
    {
        return x >= 0.0 ? Math.floor(x + 0.5) : Math.ceil(x - 0.5);
    }

    double[] ans;

    public boolean gaussian(double[][] matrix) {
        ans = new double[SIZE];
        for (int i = 0; i < SIZE; ++i) {
            int row = i;
            for (int j = i; j < SIZE; ++j) {
                if (Math.abs(matrix[j][i]) > Math.abs(matrix[row][i])) {
                    row = j;
                }
            }

            swap(matrix, i, row);

            if (Math.abs(matrix[i][i]) <= EPS)
                return false;

            for (int j = i + 1; j < SIZE + 1; ++j) matrix[i][j] /= matrix[i][i];
            matrix[i][i] = 1;

            for (int j = 0; j < SIZE; ++j) {
                if (i != j) {
                    for (int k = i + 1; k < SIZE + 1; ++k) {
                        matrix[j][k] -= (matrix[j][i] * matrix[i][k]);
                    }
                    matrix[j][i] = 0.0;
                }
            }
        }

        for (int i = 0; i < SIZE; ++i) {
            ans[i] = matrix[i][SIZE];
        }
        return true;
    }

    public void swap(double[][] matrix, int i, int j) {
        int n = matrix[0].length;
        for (int col = 0; col < n; ++col) {
            double tmp = matrix[i][col];
            matrix[i][col] = matrix[j][col];
            matrix[j][col] = tmp;
        }
    }

    public int to_index(int i, int j) {
        return i * N + j + 1;
    }

    FastScanner in;
    PrintWriter out;

    void run() throws IOException {
        boolean oj;
        try {
            oj = !System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
        } catch (Exception e) {
            oj = System.getProperty("ONLINE_JUDGE") != null;
        }

        InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
        in = new FastScanner(is);
        out = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if (!oj) {
            System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
        }
    }

    public boolean more() {
        return in.hasNext();
    }

    public int ni() {
        return in.nextInt();
    }

    public long nl() {
        return in.nextLong();
    }

    public double nd() {
        return in.nextDouble();
    }

    public String ns() {
        return in.nextString();
    }

    public char nc() {
        return in.nextChar();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        boolean hasNext;

        public FastScanner(InputStream is) throws IOException {
            br = new BufferedReader(new InputStreamReader(is));
            hasNext = true;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    hasNext = false;
                    return "##";
                }
            }
            return st.nextToken();
        }

        String next = null;

        public boolean hasNext() {
            next = nextToken();
            return hasNext;
        }

        public int nextInt() {
            if (next == null) {
                hasNext();
            }
            String more = next;
            next = null;
            return Integer.parseInt(more);
        }

        public long nextLong() {
            if (next == null) {
                hasNext();
            }
            String more = next;
            next = null;
            return Long.parseLong(more);
        }

        public double nextDouble() {
            if (next == null) {
                hasNext();
            }
            String more = next;
            next = null;
            return Double.parseDouble(more);
        }

        public String nextString() {
            if (next == null) {
                hasNext();
            }
            String more = next;
            next = null;
            return more;
        }

        public char nextChar() {
            if (next == null) {
                hasNext();
            }
            String more = next;
            next = null;
            return more.charAt(0);
        }
    }
}

这模版有点叼啊,把把第一,只怪用JAVA写的太少了吧。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

推荐阅读

  • 远程办公经验为0,如何将日常工作平滑过度到线上?

    我是一名创业者,我的公司(深圳市友浩达科技有限公司)在2018年8月8日开始运营,现在还属于微型公司。这个春节假期,我一直十分关注疫情动向,也非常关心其对公司带来的影响。

    TVP官方团队
    TAPD 敏捷项目管理腾讯乐享企业邮箱企业编程算法
  • 数据中台,概念炒作还是另有奇效? | TVP思享

    作者简介:史凯,花名凯哥,腾讯云最具价值专家TVP,ThoughtWorks数据智能业务总经理。投身于企业数字化转型工作近20年。2000年初,在IBM 研发企业级中间件,接着加入埃森哲,为大型企业提供信息化架构规划,设计,ERP,云平台,数据仓库构建等技术咨询实施服务,随后在EMC负责企业应用转型业务,为企业提供云迁移,应用现代化服务。现在专注于企业智能化转型领域,是数据驱动的数字化转型的行业布道者,数据中台的推广者,精益数据创新体系的创始人,2019年荣获全球Data IQ 100人的数据赋能者称号,创业邦卓越生态聚合赋能官TOP 5。2019年度数字化转型专家奖。打造了行业第一个数据创新的数字化转型卡牌和工作坊。创建了精益数据创新方法论体系构建数据驱动的智能企业,并在多个企业验证成功,正在向国内外推广。

    TVP官方团队
    大数据数据分析企业
  • 扩展 Kubernetes 之 CRI

    使用 cri-containerd 的调用流程更为简洁, 省去了上面的调用流程的 1,2 两步

    王磊-AI基础
    Kubernetes
  • 扩展 Kubernetes 之 Kubectl Plugin

    kubectl 功能非常强大, 常见的命令使用方式可以参考 kubectl --help,或者这篇文章

    王磊-AI基础
    Kubernetes
  • 多种登录方式定量性能测试方案

    最近接到到一个测试任务,某服务提供了两种登录方式:1、账号密码登录;2、手机号+验证码登录。要对这两种登录按照一定的比例进行压测。

    八音弦
    测试服务 WeTest
  • 线程安全类在性能测试中应用

    首先验证接口参数签名是否正确,然后加锁去判断订单信息和状态,处理用户增添VIP时间事务,成功之后释放锁。锁是针对用户和订单的分布式锁,使用方案是用的redis。

    八音弦
    安全编程算法
  • 使用CDN(jsdelivr) 优化博客访问速度

    PS: 此篇文章适用于 使用 Github pages 或者 coding pages 的朋友,其他博客也类似.

    IFONLY@CUIT
    CDNGitGitHub开源
  • 扩展 Kubernetes 之 CNI

    Network Configuration 是 CNI 输入参数中最重要当部分, 可以存储在磁盘上

    王磊-AI基础
    Kubernetes
  • 聚焦【技术应变力】云加社区沙龙online重磅上线!

    云加社区结合特殊时期热点,挑选备受关注的音视频流量暴增、线下业务快速转线上、紧急上线防疫IoT应用等话题,邀请众多业界专家,为大家提供连续十一天的干货分享。从视野、预判、应对等多角度,帮助大家全面提升「技术应变力」!

    腾小云
  • 京东购物小程序购物车性能优化实践

    它是小程序开发工具内置的一个可视化监控工具,能够在 OS 级别上实时记录系统资源的使用情况。

    WecTeam
    渲染JavaScripthttps网络安全缓存

扫码关注云+社区

领取腾讯云代金券