`
digiter
  • 浏览: 120723 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

高斯消元

    博客分类:
  • ICPC
J# 
阅读更多
import java.util.*;
import java.io.*;
import java.math.*;

class Fraction {
    BigInteger a = BigInteger.ZERO, b = BigInteger.ONE;
    Fraction() { }
    Fraction(BigInteger a, BigInteger b)
    {
        BigInteger d = a.gcd(b);
        a = a.divide(d); b = b.divide(d);
        if (b.compareTo(BigInteger.ZERO) < 0) {
            a = a.negate(); b = b.negate();
        }
        this.a = a; this.b = b;
    }
    @Override
    public String toString()
    {
        BigInteger d = a.gcd(b);
        a = a.divide(d);
        b = b.divide(d);
        if (b.compareTo(BigInteger.ONE) == 0)
            return a.toString();
        return a + "/" + b;
    }
    public Fraction add(Fraction p)
    {
        return new Fraction(a.multiply(p.b).add(b.multiply(p.a)), b.multiply(p.b));
    }
    public Fraction subtract(Fraction p)
    {
        return new Fraction(a.multiply(p.b).subtract(b.multiply(p.a)), b.multiply(p.b));
    }
    public Fraction muliply(Fraction p)
    {
        return new Fraction(a.multiply(p.a), b.multiply(p.b));
    }
    public Fraction divide(Fraction p)
    {
        return new Fraction(a.multiply(p.b), b.multiply(p.a));
    }
    public Fraction abs()
    {
        return new Fraction(a.abs(), b.abs());
    }
    public int compareTo(Fraction p)
    {
        return a.multiply(p.b).subtract(b.multiply(p.a)).signum();
    }
}

class Matrix {
    Fraction data[][];
    
}

public class Main {
    
    // Gaussian elimination
    public static Fraction[] gaussianElimination(Fraction A[][], int m) throws Exception
    {
        for (int i = 0; i < m; ++i)
        {
            // Find pivot in column i, starting in row i:
            int maxi = i;
            for (int k = i + 1; k < m; ++k)
                if (A[k][i].abs().compareTo(A[maxi][i].abs()) > 0)
                    maxi = k;
            if (A[maxi][i].a.compareTo(BigInteger.ZERO) == 0)
                throw new Exception("no solution");
            // swap rows i and maxi, but do not change the value of i
            // Now A[i,i] will contain the old value of A[maxi,i].
            if (i != maxi) {
                Fraction tmp[] = A[i];
                A[i] = A[maxi];
                A[maxi] = tmp;
            }
            // divide each entry in row i by A[i,i]
            // Now A[i,i] will have the value 1.
            for (int k = m; k >= i; --k)
                A[i][k] = A[i][k].divide(A[i][i]);
            // subtract A[u,j] * row i from row u
            // Now A[u,j] will be 0, since A[u,j] - A[i,j] * A[u,j] = A[u,j] - 1 * A[u,j] = 0.
            for (int u = i + 1; u < m; ++u)
                for (int k = m; k > i; --k)
                    A[u][k] = A[u][k].subtract(A[u][i].muliply(A[i][k]));
        }
        
        Fraction x[] = new Fraction[m];
        x[m - 1] = A[m - 1][m].divide(A[m - 1][m - 1]);
        for (int i = m - 2; i >= 0; --i)
        {
            x[i] = A[i][m];
            for (int k = i + 1; k < m; ++k)
                x[i] = x[i].subtract(x[k].muliply(A[i][k]));
            x[i] = x[i].divide(A[i][i]);
        }
        return x;
    }
    
    public static void main(String args[])
    {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        Fraction a[][] = new Fraction[105][105];
        Fraction x[] = new Fraction[105];
        
        while (cin.hasNext())
        {
            int m = cin.nextInt();
            for (int i = 0; i < m; ++i)
                for (int j = 0; j <= m; ++j)
                {
                    BigInteger tmp = cin.nextBigInteger();
                    a[i][j] = new Fraction(tmp, BigInteger.ONE);
                }
            try {
                x = gaussianElimination(a, m);
                for (int i = 0; i < m; ++i)
                    System.out.println(x[i]);
                System.out.println();
            } catch (Exception e) {
                System.out.println("No solution.");
                System.out.println();
            }
            
        }
    }
}

分享到:
评论

相关推荐

    YOLO算法-数据集数据集-330张图像带标签-椅子-书桌.zip

    YOLO系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,包含数据集配置文件data.yaml,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中,文件名末尾是部分类别名称; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值; 【注】可以下拉页面,在资源详情处查看标签具体内容;

    java毕设项目之ssm蜀都天香酒楼的网站设计与实现+jsp(完整前后端+说明文档+mysql+lw).zip

    项目包含完整前后端源码和数据库文件 环境说明: 开发语言:Java 框架:ssm,mybatis JDK版本:JDK1.8 数据库:mysql 5.7 数据库工具:Navicat11 开发软件:eclipse/idea Maven包:Maven3.3 服务器:tomcat7

    weixin138社区互助养老+ssm(论文+源码)-kaic.zip

    weixin138社区互助养老+ssm(论文+源码)_kaic.zip

    光纤到户及通信基础设施报装申请表.docx

    光纤到户及通信基础设施报装申请表.docx

    java毕设项目之ssm基于jsp的精品酒销售管理系统+jsp(完整前后端+说明文档+mysql+lw).zip

    项目包含完整前后端源码和数据库文件 环境说明: 开发语言:Java 框架:ssm,mybatis JDK版本:JDK1.8 数据库:mysql 5.7 数据库工具:Navicat11 开发软件:eclipse/idea Maven包:Maven3.3 服务器:tomcat7

    功能完善的电商数据智能爬虫采集系统项目全套技术资料.zip

    功能完善的电商数据智能爬虫采集系统项目全套技术资料.zip

    YOLO算法-刀数据集-198张图像带标签-刀-枪.zip

    YOLO系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,包含数据集配置文件data.yaml,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中,文件名末尾是部分类别名称; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值; 【注】可以下拉页面,在资源详情处查看标签具体内容;

    Android程序开发初级教程WORD文档doc格式最新版本

    ### Android程序开发初级教程(一):初识Android **平台概述** Google推出的Android操作系统平台已经正式亮相,这是一个基于Linux内核的开源操作系统。对于开发者而言,了解其架构和支持的开发语言至关重要。以下是Android平台的架构概览: **平台架构及功能** 1. **应用框架(Application Framework)**:包含可重用和可替换的组件,确保所有软件在该层面上的平等性。 2. **Dalvik虚拟机(Dalvik Virtual Machine)**:一个基于Linux的虚拟机,为Android应用提供运行环境。 3. **集成浏览器(Integrated Browser)**:基于开源WebKit引擎的浏览器,位于应用层。 4. **优化图形(Optimized Graphics)**:包括自定义的2D图形库和遵循OpenGL ES 1.0标准的3D实现。 5. **SQLite数据库**:用于数据存储。 6. **多媒体支持(Media Support)**:支持通用音频、视频以及多种图片格式(如MPEG4, H.264

    【组合数学答案】组合数学-苏大李凡长版-课后习题答案

    内容概要:本文档是《组合数学答案-网络流传版.pdf》的内容,主要包含了排列组合的基础知识以及一些经典的组合数学题目。这些题目涵盖了从排列数计算、二项式定理的应用到容斥原理的实际应用等方面。通过对这些题目的解析,帮助读者加深对组合数学概念和技巧的理解。 适用人群:适合初学者和有一定基础的学习者。 使用场景及目标:可以在学习组合数学课程时作为练习题参考,也可以在复习考试或准备竞赛时使用,目的是提高解决组合数学问题的能力。 其他说明:文档中的题目覆盖了组合数学的基本知识点,适合逐步深入学习。每个题目都有详细的解答步骤,有助于读者掌握解题思路和方法。

    .net core mvc在线考试系统asp.net考试系统源码考试管理系统 主要技术: 基于.net core mvc架构和sql server数据库,数据库访问采用EF core code fir

    .net core mvc在线考试系统asp.net考试系统源码考试管理系统 主要技术: 基于.net core mvc架构和sql server数据库,数据库访问采用EF core code first,前端采用vue.js和bootstrap。 功能模块: 系统包括前台和后台两个部分,分三种角色登录。 管理员登录后台,拥有科目管理,题库管理,考试管理,成绩管理,用户管理等功能。 教师登录后台,可进行题库管理,考试管理和成绩管理。 用户登录前台,可查看考试列表,参加考试,查看已考试的结果,修改密码等。 系统实现了国际化,支持中英两种语言。 源码打包: 包含全套源码,数据库文件,需求分析和代码说明文档。 运行环境: 运行需vs2019或者以上版本,sql server2012或者以上版本。

    YOLO算法-易拉罐识别数据集-512张图像带标签-可口可乐.zip

    YOLO系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,包含数据集配置文件data.yaml,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中,文件名末尾是部分类别名称; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值; 【注】可以下拉页面,在资源详情处查看标签具体内容;

    (175415460)基于SpringBoot的通用管理系统源码+数据库+项目文档,前后端分离的通用管理系统模版,可用于开发毕业设计

    包含了登陆注册、用户管理、部门管理、文件管理、权限管理、日志管理、个人中心、数据字典和代码生成这九个功能模块 系统采用了基于角色的访问控制,角色和菜单关联,一个角色可以配置多个菜单权限;然后再将用户和角色关联,一位用户可以赋予多个角色。这样用户就可以根据角色拿到该有的菜单权限,更方便管理者进行权限管控。 本系统还封装了文件管理功能,在其他模块如若要实现图片/文件上传预览时,前端只需导入现成的 Vue 组件即可实现(使用 viewerjs 依赖实现),后端只需定义 String 类型的实体类变量即可,无需再去研究文件上传预览的相关功能,简化了开发者的工作量。内容来源于网络分享,如有侵权请联系我删除。另外如果没有积分的同学需要下载,请私信我。

    三相10Kw光伏并网逆变器 包含全套理图 PCB 源代码

    三相10Kw光伏并网逆变器。包含全套理图 PCB 源代码

    GJB 5236-2004 军用软件质量度量

    GJB 5236-2004 军用软件质量度量文档,本称准规定了车用软件产品的质重模型和基本的度量。本标准为确定车用软件质量需求和衡量军用 软件产品的能力提供了一个框架。

    (179941432)基于MATLAB车牌识别系统【GUI含界面】.zip

    基于MATLAB车牌识别系统【GUI含界面】.zip。内容来源于网络分享,如有侵权请联系我删除。另外如果没有积分的同学需要下载,请私信我。

    (9546452)宿舍管理系统

    【宿舍管理系统】是一种专为高校或住宿机构设计的信息化解决方案,旨在提高宿舍管理的效率和准确性。该系统包含了多项核心功能,如宿舍管理员管理、宿舍信息维护、查询、卫生检查以及电费缴纳等,旨在实现全面的宿舍运营自动化。 **宿舍管理员管理**功能允许指定的管理员进行用户权限分配和角色设定。这包括对管理员账户的创建、修改和删除,以及设置不同的操作权限,例如只读、编辑或管理员权限。通过这样的权限控制,可以确保数据的安全性和管理的规范性。 **宿舍添加与管理**是系统的基础模块。管理员可以录入宿舍的基本信息,如宿舍号、楼栋、楼层、房间类型(单人间、双人间等)、容纳人数、设施配置等。此外,系统还支持批量导入或导出宿舍信息,方便数据的备份和迁移。 **查询功能**是系统的重要组成部分,它允许管理员和学生根据不同的条件(如宿舍号、楼栋、学生姓名等)快速查找宿舍信息。此外,系统还可以生成各种统计报告,如宿舍占用率、空闲宿舍数量等,以便于决策者进行资源优化。 **卫生检查**功能则是对宿舍卫生状况进行定期评估。管理员可设定检查计划,包括检查周期、评分标准等,并记录每次检查的结果。系统能自动生成卫生报表,用于

    YOLO算法-包装好的服装数据集-654张图像带标签-.zip

    YOLO系列算法目标检测数据集,包含标签,可以直接训练模型和验证测试,数据集已经划分好,包含数据集配置文件data.yaml,适用yolov5,yolov8,yolov9,yolov7,yolov10,yolo11算法; 包含两种标签格:yolo格式(txt文件)和voc格式(xml文件),分别保存在两个文件夹中,文件名末尾是部分类别名称; yolo格式:<class> <x_center> <y_center> <width> <height>, 其中: <class> 是目标的类别索引(从0开始)。 <x_center> 和 <y_center> 是目标框中心点的x和y坐标,这些坐标是相对于图像宽度和高度的比例值,范围在0到1之间。 <width> 和 <height> 是目标框的宽度和高度,也是相对于图像宽度和高度的比例值; 【注】可以下拉页面,在资源详情处查看标签具体内容;

    九缸星形发动机点火器3D

    九缸星形发动机点火器3D

    小程序毕业设计项目-音乐播放器

    本项目可以作为小程序毕设项目,主要功能为音乐播放器,主要功能是:可以播放歌曲(采用mp3网络连接实现)、专辑封面播放时可以旋转,能够实现开始和暂停播放,可以点击下一首歌曲,主页面实现动态轮播图

    出差审批单(表格模板).docx

    出差审批单(表格模板).docx

Global site tag (gtag.js) - Google Analytics