文档章节

面向对象程序设计——多项式求导之优化篇

o
 osc_a22drz29
发布于 2019/03/27 17:19
字数 2505
阅读 8
收藏 0
red

精选30+云产品,助力企业轻松上云!>>>

<font size=6>2019面向对象程序设计——多项式求导之优化篇</font>

<font face="楷体" size="4">作者:17376482 王育斌</font>

<font color="blue" size=5>优化前言:</font>

​ 笔者励志于介绍相对全面并且难度递进的优化方法。~~笔者在三次作业的优化中顺利通过了所有强测点,但在互测中依旧暴露了微小的问题。~~在三次作业中我对ArrayList、HashMap和LinkedList对于元素的存取、管理与删除进行了较多的试验,个人不推荐在多项式求导这一单元有意向进行优化的同学使用HashMap,HashMap虽然对于元素的存取相比List而言有得天独厚的优势,但在管理方面相比List复杂,在本单元的优化中,一部分适用于List的管理方法,HashMap却不适用。当然不想优化的话,力荐HashMap。

<font size=5>一.基础化简之正项前移(适用于第一、二、三次作业)</font>

<font color="purple">难度等级:I</font>


​ 第一次作业能够进行的优化不多,主要是“正项前移”的问题,将正项放在前面可以省去一个正号,使得输出长度缩短,当然,正项前移问题在第二、三次作业中也需要考虑。个人推荐正项前移放在全部优化的最后一步。

<font color="red" face="楷体" size="4">利用工具类Collections的静态方法sort对List进行排序</font>

        Collections.sort(terms, new Comparator<Term>() {
            @Override
            public int compare(Term o1, Term o2) {
                return o2.getFactors().get(0).getCoeff()
                        .compareTo(o1.getFactors().get(0).getCoeff());
            }
        });

重写compare方法,按系数由大到小的顺序对项进行排序,可使负项在正项之后。

<font size=5>二.基础化简之去除零项(适用于第一、二、三次作业)</font>

<font color="purple">难度等级:I</font>



 0*x*sin(x)*cos(x)

​ 这种输出看起来也许让人有些不适。

不妨利用迭代器iterator遍历List,对每一项进行系数判断,若系数为0,则利用remove()方法对这一项进行删除,循环删除与添加会造成异常,后面的高级化简也均需考虑这一问题,如何有效避免,请读者思考

Iterator<Term> it = terms.iterator();
while (it.hasNext()) {
    Term term = it.next();
    if (term.getFactors().get(0).getType().equals(FactorType.constant)
            && term.getFactors().get(0).getCoeff().equals(zero)) {
        it.remove();
    }
}

效果如图,看起来清爽多了叭~

<font size=5>三.进阶化简之利用三角函数公式进行数学化简(适用于第二次作业)</font>

<font color="purple">难度等级:II</font>


​ 笔者在第二次作业种主要利用了如下四个化简公式进行化简:

		1°  
		a*sin(x)^(m+2)*cos(x)^m + b*sin(x)^m*cos(x)^(m+2) =
a*sin(x)^m*cos(x)^m+(b-a)*sin(x)^m*cos(x)^(m+2)              [if(a<b)]
b*sin(x)^m*cos(x)^m+(a-b)*sin(x)^(m+2)*cos(x)^m              [if(a>=b)]

		2° a*sin(x)^m*cos(x)^m-b*sin(x)^(m+2)*cos(x)^m = a*sin(x)^m*cos(x)^(m+2)-(b-a)*sin(x)^(m+2)*cos(x)^m

		3° a*sin(x)^m*cos(x)^m-b*sin(x)^m*cos(x)^(m+2) = a*sin(x)^(m+2)*cos(x)^m-(b-a)*sin(x)^m*cos(x)^(m+2)

		4° a*sin(x)^4 - a*cos(x)^4 = a*sin(x)^2 - a*cos(x)^2

​ 以上四条化简公式分别为如下四个基础数学公式演化而来,但由于表达式的随机性和化简的不确定性,具有更好的效果。

			1°  sin(x)^2 + cos(x)^2 = 1

​			2° 1-sin(x)^2 = cos(x)^2

​			3° 1-cos(x)^2 = sin(x)^2

​			4° sin(x)^4 - cos(x)^4 = sin(x)^2 - cos(x)^2

​ 具体实现,可用多次循环删除和循环添加实现。

<font color="red" face="楷体" size="4">优化重点:四条公式打乱优化,循环一定次数,记录每次的化简结果,输出时搜索最短结果。</font>

首先定义变量record存储化简结果

private String record = "";

每次化简之后,记录化简结果,记录后及时清空record(注意,每次化简都应该去除一次零项)

for (int i = 0; i < list.size(); i++) {
    flag = true;
    printConstant(i);
    printX(i);
    printSinx(i);
    printCosx(i);
}
if (list.size() == 0) {
    record = record + "0";
}
link.add(record);
record = "";

最后输出时搜寻最短结果输出:

LinkedList<String> link = expression.getLink();
String least = link.get(0);
for (int i = 0; i < link.size(); i++) {
    if (link.get(i).length() < least.length()) {
        least = link.get(i);
    }
}
System.out.println(least);

效果:

​ 做到这个效果,你基本赢了。

<font size=5>四.进阶化简之合并同类因子(适用于第三次作业)</font>

<font color="purple">难度等级:III</font>


实现思路:重写表达式类、项类、因子类的hashcode与equals方法,实现递归判断

​ 在此我要说一下,我阅读了wsz大佬写的优化博客,也比较推荐他的符号化思路,但经过我仔细的思考,我并不赞同“递归调用equals方法为效率低下的方法”这一判断,因为递归判断嵌套因子实际上时线性扫描的过程,与符号化方法有着相同的时间复杂度。

为了逻辑清晰,特别定义了因子种类枚举类型:

public enum FactorType {
    constant,x,sin,cos,expression
}

<font color="purple">比较两个因子相等</font>

@Override
public boolean equals(Object obj) {
    if (obj instanceof Factor) {
        Factor factor = (Factor) (obj);
        if (factor.getType().equals(type)) {
            if (type.equals(FactorType.constant)) {
                return coeff.equals(factor.getCoeff());
            } else if (type.equals(FactorType.x)) {
                return exp.equals(factor.getExp());
            } else if (type.equals(FactorType.sin)
                    || type.equals(FactorType.cos)) {
                return trInside.equals(factor.getTrInside())
                        && exp.equals(factor.getExp());
            } else {
                return inside.equals(factor.getInside());
            }
        } else {
            return false;
        }
    } else {
        return false;
    }
}

<font color="purple">比较两个项相等</font>

@Override
public boolean equals(Object obj) {
    if (obj instanceof Term) {
        Term term = (Term) (obj);
        if (term.getFactors().size() != factors.size()) {
            return false;
        } else {
            for (int i = 0; i < factors.size(); i++) {
                if (!factors.get(i).equals(term.getFactors().get(i))) {
                    return false;
                }
            }
            return true;
        }
    } else {
        return false;
    }
}

<font color="purple">比较两个表达式相等</font>

@Override
public boolean equals(Object obj) {
    if (obj instanceof Expression) {
        Expression expr = (Expression) (obj);
        if (expr.getTerms().size() == 0 && terms.size() == 0) {
            return true;
        } else if (expr.getTerms().size() != terms.size()) {
            return false;
        } else {
            for (int i = 0; i < terms.size(); i++) {
                if (!expr.getTerms().get(i).equals(terms.get(i))) {
                    return false;
                }
            }
            return true;
        }
    } else {
        return false;
    }
}

在判断因子相等之后,我们就可以进行项内因子合并工作了,大大减少项的长度。

<font size=5>五.进阶化简之合并同类项(适用于第三次作业)</font>

<font color="purple">难度等级:III</font>


笔者认为,不做因子合并,合并同类项是没有意义的

我们在合并完因子之后,在合并同类项之前还需要进行因子排序

For instance:

5*sin(x)*cos(x)=cos(x)*5*sin(x)

emmm......不进行排序的话,你是判断不了这两个项相等的。

这里提供一种排序思路。

void sort() {
    Collections.sort(factors, new Comparator<Factor>() {
        @Override
        public int compare(Factor o1, Factor o2) {
            return compare_fac(o1, o2);
        }
    });
}
public static int compare_fac(Factor o1, Factor o2) {
    if (o1.getType().equals(FactorType.sin) &&
            o2.getType().equals(FactorType.sin)) {
        return compare_fac(o1.getTrInside(), o2.getTrInside());
    } else if (o1.getType().equals(FactorType.cos) &&
            o2.getType().equals(FactorType.cos)) {
        return compare_fac(o1.getTrInside(), o2.getTrInside());
    } else if (o1.getType().equals(FactorType.expression) &&
            o2.getType().equals(FactorType.expression)) {
        if (o1.getInside().compareTo(o2.getInside()) > 0) {
            return 1;
        } else {
            return -1;
        }
    } else if (o1.getType().equals(FactorType.constant)) {
        return -1;
    } else if (o1.getType().equals(FactorType.x)) {
        if (o2.getType().equals(FactorType.constant)) {
            return 1;
        } else {
            return -1;
        }
    } else if (o1.getType().equals(FactorType.sin)) {
        if (o2.getType().equals(FactorType.constant)
                || o2.getType().equals(FactorType.x)) {
            return 1;
        } else {
            return -1;
        }
    } else if (o1.getType().equals(FactorType.cos)) {
        if (o2.getType().equals(FactorType.expression)) {
            return -1;
        } else {
            return 1;
        }
    } else {
        return 1;
    }
}

当排完序之后再调用equals方法就可以判断两项相等并进行合并了。

<font color="lightgreen">当然在因子比较环节,遇到嵌套表达式因子的时候,也建议对嵌套的表达式因子进行用项排序</font>

<font size=5>六.进阶化简之去表达式因子的括号(适用于第三次作业)</font>

<font color="purple">难度等级:IV</font>


emmm.......第六部分其实是对第四、五部分的进一步优化

​ 为什么要考虑去括号呢?

​ 因为我写的equal函数认为:

     sin((x))与sin(x),0与(0)是不equal的

去括号的方向在于,将表达式因子嵌套层数降至最低,或者转化为其他常数因子、幂函数因子或者三角函数因子。

​ 去括号这一环节我不打算扔代码,因为这必须要结合自己的架构来,而且我写的很暴力,有点面向过程~~,希望敢于尝试这一部分的学弟学妹们独立思考。

<font size=5>七.终极化简之提取公因子(适用于第三次作业)</font>

<font color="purple">难度等级:看见没?特喵的有这么大</font>


​ 笔者在本优化环节付出了巨大心血,其实实现难度并不大,真正难的地方在于,如何在互测环节不出bug,并且在可控时间复杂度内做的漂亮。笔者花大量时间完成了提取公因子的工作,但害怕强测挂点或者互测成为大礼包,最后还是注释掉了提取公因子的优化函数。

​ 我的实现思路:

​ 1.遍历表达式第一个项中的因子,记录哪些项含有当前因子,以及含有该因子的项数。最后得到最大项数及对应的因子。

​ 2.含有公因子项减去公因子的次数后,构建新的表达式因子,与公因子相乘得到新项,不含公因子的项不处理。

​ 3.循环、递归直至找不到公因子。

​ 4.去表达式因子的括号**(如果这个实现不了,就不要提取公因子了)。**

​ 举例说明笔者的实现过程:

x*sin(x)^2*cos(x)+5*x*cos(x)^2  ----->    x*(sin(x)^2*cos(x)+5*cos(x)^2)
x*(sin(x)^2*cos(x)+5*cos(x)^2)  ----->    x*(cos(x)*(sin(x)^2+5*cos(x)))

								去括号
x*(cos(x)*(sin(x)^2+5*cos(x)))  ----->    x*cos(x)*(sin(x)^2+5*cos(x))      

去括号一步尤其重要,笔者一开始没去括号,输入复杂些,输出甚至会更长。

本环节需要较多的独立思考,拒绝投放代码喂鱼。

<font size=5>八.文末寄语</font>


​ 本届的OO助教和课程组特别棒,今年的OO政策可谓非常合理了。感谢他们的辛勤付出,希望北航OO越来越好。(我太菜了)

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
2019面向对象程序设计第一单元总结

<font size=6>2019面向对象程序设计第一单元总结</font> <font size=5>一.三次作业的设计思路</font> <font size=4>Ⅰ.仅含常数和幂函数的多项式求导</font> <font color="red" face="楷体"......

osc_wmsc0xiz
2019/03/26
8
0
OO——求导作业总结

[TOC] OO——求导作业总结 程序结构的分析 第一次作业 1.设计思路 在第一次作业中,我设计了两个类:PolyDerivation(主类)、Poly。函数存在于PolyDerivation类中,作为程序的入口。PolyDeriv...

osc_15ajvvu8
2019/03/26
1
0
OO第一单元总结

OO第一次单元总结 前三次的OO作业的内容总的来说都是围绕着多项式求导,从最简单的x的幂函数的求导逐渐增加难度,最后完成含有三角函数和嵌套因子的多项式求导。但是在这三次的程序编写和deb...

osc_6oerel1o
2019/03/27
2
0
面向对象第一单元(多项式求导)总结

前言   OO三周三次作业,基于多项式求导这一问题让我们入门的面向对象的设计思想。不敢说自己真的迈进了面向对象的大门了,三次作业做得也并非尽善尽美,但愿意把自己对这三次作业的一些感...

osc_wmsc0xiz
2019/03/26
5
0
面向对象第一单元博客作业

面向对象第一单元三次作业介绍   面向对象课程第一单元的学习结束了,第一周的主要任务是使用面向对象思想进行了三次难度递增的表达式求导。下表说明了三次作业的要求情况。 作业序号 简略...

osc_wmsc0xiz
2019/03/26
2
0

没有更多内容

加载失败,请刷新页面

加载更多

linux下java环境搭建

1、jdk下载: 官方地址:https://www.oracle.com/java/technologies/javase/javase-jdk8-downloads.html 如下图所示,我这边选择的是红框中的版本 2、压缩包上传至服务器 将下载的压缩包上传...

wc_飞豆
50分钟前
17
0
面试题:Java对象不再使用时,为什么要赋值为null?

前言 许多Java开发者都曾听说过“不使用的对象应手动赋值为null“这句话,而且好多开发者一直信奉着这句话;问其原因,大都是回答“有利于GC更早回收内存,减少内存占用”,但再往深入问就回...

码农突围
52分钟前
22
0
设计模式(5) 原型模式

原型模式 原型模式的适用场景 浅拷贝 深拷贝 用Initialize方法修改初始化状态 原型模式与之前学习的各种工厂方法、单例模式、建造者模式最大、最直观的区别在于,它是从一个既有的对象“克隆...

zhixin9001
52分钟前
7
0
获取免费的pycharm激活码网站

http://www.lookdiv.com/

云烟成雨forever
52分钟前
27
0
用Helm部署Kubernetes应用,支持多环境部署与版本回滚

1 前言 Helm是优秀的基于Kubernetes的包管理器。利用Helm,可以快速安装常用的Kubernetes应用,可以针对同一个应用快速部署多套环境,还可以实现运维人员与开发人员的职责分离。现在让我们安...

南瓜慢说
53分钟前
25
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部