前言

• 第一次作业一共八道题,此次作业也是这三次作业中最接近面向过程程序设计的题目集,整体难度偏低,总耗时1.5h,主要的知识点在熟悉Java的语法上,整体题目的逻辑非常清晰简单,但最后一个判断三角形类型中有一些小坑(踩进去以后才发现原来是轻敌了)。
  
• 第二次题目集的考察内容主要为类和对象的设计,此次题目集开始培养我们的面向对象思维,整体题目难度偏中等,一共五道题,耗时3h,主要卡在求前n天的算法设计,其中忽略了一些特殊情况。
  
• 第三次题目集可以说是这三次中最难的一次了,一共三道题,前两道是那种题目要求清晰,设计思路明显的题,所以很快就做完了。最最最上头的还是最后一道题,一元多项式的求导,前前后后一共花了四个晚上,但是有一个5分的测试点(合法性)一直过不去,后来也在尝试写能够覆盖所有类型的正则,但是这一点还是优化失败了,后面会着重说明解题与优化其他点的思路:).
  

设计与分析

题目集01 7-8 判断三角形类型

• 第一次作业判断三角形类型,按照大学之前积累的关于图形的知识,其实就可以根据边的关系判断此三角形的类型(但是,这是我们的判断),对于机器内部,可不是这样的,其中一个直角三角形的判定测试点一直过不去,按照正常思维,只要任意两条边的平方和等于第三边,我们就默认它为直角三角形.But对于无理数而言,这个等式有时是不成立的,所以在这种情况下,只有对相应的值取精度判定,例如:(a*a+b*b-c*c<1e^-2),这里的1e^-2就是精度,加上这个条件后,直角三角形才能被判定(太能卡了,这里一直迷惑:)).
• 此外,这里判定三角形的条件if的先后顺序也非常重要,有一些相类似的判定条件,如果顺序放错了,结果可能也会出错。例如:判断等腰三角形的条件放在了判断等腰直角三角形的前面,判断直角三角形的条件放在了判断等腰直角三角形的前面,最后的结果虽然在数学层面来说可能是对的,但是对于此题目的要求却有可能达不到.对于第一种情况,三条边的长度可以分别为根号2,根号2,2，判断的结果为等腰三角形,但是对于题目来说他就是等腰直角三角形,第二个就不做赘述了,还有其他的组合可能,都会出现类似的需求错误。
• SourceMonitor分析结果

Percent Branch Statements 0.0
Method Call Statements 18
Percent Lines with Comments 5.1
Classes and Interfaces 1
Methods per Class 4.00
Average Statements per Method 3.75
Line Number of Most Complex Method 6
Name of Most Complex Method Main.main()
Maximum Complexity 1
Line Number of Deepest Block 22
Maximum Block Depth 5
Average Block Depth 2.70
Average Complexity 1.00

Most Complex Methods in 1 Class(es)

Complexity, Statements, Max Depth, Calls

1, 6, 2, 4

UML类图

判断的条件均写在了方法里,这次没有做类的设计,将方法写在了主类中,判断用了多重if嵌套,其实逻辑很清晰,就只要注意直角三角形判断的精度和判断的顺序,这道题就可以完美解决啦。

题目集02 7-1 IP地址转换

• 这道题其实就已经可以用到正则表达式的知识了,题目的输入要求很简单,但是如果用String自带的charAt或类似的方法判断输入是否合法,可能就比较冗余了,Regex="[0|1]{32}".
• 接下来就是对字符串的操作了,这里有一个比较大的坑,就是在接收输入的时候得是接收nextLine()的输入,不然如果输入空字符,这时候接收的还是next(),这时候程序不会输出WrongFormat,而会一直等待输入。而如果接收的是nextLine(),这时候输入回车,程序将会直接输出WrongFormat。
• 这里想稍微讨论一下解决字符串转换的问题(这里一定有更高效的算法来处理,给大伙分享一下我的拙见),我用的是Integer内带的parseInt方法和String类内部的SubString处理的规范字符串
  
• 这里用的还是面向过程的思维,但是这其实是进制转换的一个过程,查到的资料内部还有位操作符的概念=w=。

题目集02 7-4求下一天

• 题目要求不允许使用Java中的日期相关的类和方法,并且给我们提供了几个必须实现的方法。
  
• 先说一下这个合法性吧,在题目提供的合法性范围内,年份月份和日期都很明确了,所以在写checkInputValidity方法的时候按理来说就是照着抄的,但是笔者在写的时候忽略了一个问题,每个月他的日期并不是在1到31之间就是合法的,其中一三五七八十腊月都是31天,四六七九十一月都是30天,二月根据是否为闰年,判断为28天还是29天。对于每月多少天的设计,我的想法是封装在一个方法内部设计在一个dayPerMonth方法来简化判断操作,方法内部使用Switch判断(刚开始用if else语句判断,好家伙,圈复杂度直接起飞),这里还可以使用数组来存每个月对应的天数,在对应的闰年将二月份的天数改一下就好了.
  
• 接下来就是求规定日期的下一天的算法设计了,这里笔者是先考虑各种特殊情况,例如12月的最后一天,每个月的最后一天,最后才是考虑一般的情况,这里逻辑比较简单,就不做赘述了。
  
• SourceMonitor分析结果
  Percent Branch Statements 49.0
  Method Call Statements 10
  Percent Lines with Comments 9.1
  Classes and Interfaces 1
  Methods per Class 4.00
  Average Statements per Method 9.50
  Line Number of Most Complex Method 40
  Name of Most Complex Method isLeapYear().if(()
  Maximum Complexity 2
  Line Number of Deepest Block 19
  Maximum Block Depth 3
  Average Block Depth 1.37
  Average Complexity 1.50

Most Complex Methods in 2 Class(es):
Complexity, Statements, Max Depth, Calls

isLeapYear().if(() 2, 3, 2, 0
Main.main() 1, 6, 2, 4

UML类图

题目集02 7-5 求前N天

• 这里的其他方法相较题目四都无区别,唯一有区别的就是,上道题的求下一天变成了求前N天,这时考虑的范围就要稍微扩大一点了,需要判断N天前是否跨年,是否跨月了,但是思维没有发生太大的改观,都是先处理特殊情况,再处理一般情况,这里唯一踩过的坑就是在判断差值的时候,把judge=0的情况判断在else中,导致需求输出0天前,系统输出的是Wrong Format.
  
• 其实这里用类的设计思维可以使得程序变得更加简洁明了,如果按照这个设计风格的话,就还是停留在面向过程程序设计的层次了，这个在后面的题目集中进行了修改。

• SourceMonitor分析结果

Percent Branch Statements 45.6
Method Call Statements 15
Percent Lines with Comments 16.7
Classes and Interfaces 1
Methods per Class 6.00
Average Statements per Method 8.33
Line Number of Most Complex Method 16
Name of Most Complex Method Main.DaysAgo()
Maximum Complexity 7
Line Number of Deepest Block 71
Maximum Block Depth 4
Average Block Depth 1.82
Average Complexity 3.33

Most Complex Methods in 2 Class(es):
Complexity, Statements, Max Depth, Calls

isValid().if(() 2, 3, 2, 0
Main.DaysAgo() 7, 10, 3, 9
Main.main() 1, 7, 2, 5

UML类图

题目集03 7-2 定义日期类 求下一天

• 这几次的日期题采用了迭代升级难度的方式,一步步把我们面向过程设计的思想带到面向对象设计来.题目给出了类图,不得不说看着类图写程序,思路是真的清晰,不管是写部分功能也好,写工程项目设计也罢,一种良好的设计模式总是能让设计事半功倍，所以在处理问题前至少需要花70％的时间来设计类图.

• Date类中要求设计的每月多少天的数组,简化了DayPerMonth中的操作与判断,在使用时,只需要判断该年是否为闰年,将数组中第三个元素改为29or28就行了.
  private int[] mon_maxnum = new int[]{0,31,28,31,30,31,30,31,31,30,31,30,31};

• SourceMonitor分析结果

Percent Branch Statements 17.9
Method Call Statements 9
Percent Lines with Comments 4.6
Classes and Interfaces 2
Methods per Class 6.50
Average Statements per Method 3.00
Line Number of Most Complex Method 64
Name of Most Complex Method isLeapYear().if(()
Maximum Complexity 2
Line Number of Deepest Block 31
Maximum Block Depth 3
Average Block Depth 1.07
Average Complexity 1.50

Most Complex Methods in 2 Class(es):
Complexity, Statements, Max Depth, Calls

isLeapYear().if(() 2, 3, 2, 0
Main.main() 1, 7, 2, 4

UML类图

• 在大多数情况下,需要尽可能完美的解决一个问题,一个类其实是不太妥当的,这很可能就违背了类的单一职责原则(这个原则在规范思想的时候真的超管用！！)
  

• 在我的理解中,对此题进一步的优化就是,将Date中处理日期,输出日期的方法,放到另外一个类中,这个类里有Date的实例化对象(这个在下一题处理多项式的项中会有比较好的体现),专门用来处理用户自定义类Date里边的数据,提高了程序的可扩展性.

题目集03 7-3 一元多项式求导(类设计)

• 说实话一开始读完这个OO作业3-3作业指导书,我是毫无头绪的,但是对于这个业务背景我们又是非常熟悉的,什么是带符号整数,幂函数,项,相应的表达式以及对应的求导算法,我们可以说是知根知底了,但是真的需要将其抽象起来,思维就好像是一片空白.

正则表达式书写

• 但是冷静下来,仔细梳理一下,发现也许大体思路很清晰,用户输入对应的字符串后,可能其中含有空格,如果有空格的话,后面写正则需要考虑的情况就多了很多了,所以综合考量后,决定在主程序中就把空格干掉！replaceAll("[ ]", ""),这里说下我犯的小错把,这里一开始正则表达式没有带旁边的中括号,前面系数字符串里就是一个空格,最后的结果就是,系统不认这个正则,处理后的字符串和处理前的没区别=w=,好了,接下来就是对正则表达式进行一个合法性判断,刚开始,我一直纠结什么样的表达式才算是合法的,这次的需求分析内只是说有带符号常数,幂函数,那么肯定要把相应的项种类设置成对应的类,这样也方便后面的求导算法扩展,那么常数和幂函数的正则表达式都挺好写的
  (这里的写法很多,我分享一下我的思路吧)

• 常数正则:"(([+-])?(([1-9][0-9]*)|[0-9]))"

• 幂函数正则:"((([+-])?([1-9][0-9]*\\*)?))x((([\\^][+-]?[1-9][0-9]*)|()))"

• 后来想了一下,既然这道题对项的定义内这两个都有,那么一个合法的项应该是常数或者幂函数,借助这个思路,也就顺水推舟写出了多项式的正则了,笼统点理解就是一项or大于一项的正确的项

• 项正则:"(((([+-])?([1-9][0-9]*\\*)?))x((([\\^][+-]?[1-9][0-9]*)|())))|(([+-])?(([1-9][0-9]*)|[0-9]))"

• 多项式正则:"((((([+-])?([1-9][0-9]*\\*)?))x((([\\^][+-]?[1-9][0-9]*)|())))|(([+-])?(([1-9][0-9]*)|[0-9])))*"

这两个正则唯一的区别就是:(多了个星号*)

• 如果没有正则表达式的话,这道题的工作量将难以想象的大了AwA,他就像是总结了这个元素的规则,在编写前一定一定要尽可能地将所有的条件都考虑到,这样无论是在判断,还是在之后的组合优化,都会非常方便。

• 那么这里的难点就在于,多项式个相对复杂的正则应该怎么写,个人观点:就像题目集的迭代一样,在一开始把问题需要解决的各个part细心分析出来,再一步步细化,就有点自顶向下的味道了。多项式->项->(常数,幂函数),一步步的将其简单化,最后根据相应的需求进行组合就ok啦。

多项式求导

对于这部分的大体思路是:先对项求导,再将项求导后的结果存储起来,拼接成一个完整的字符串.

但是这里其实有四个问题需要解决

• 项求导算法的设计
• 求导前后的元素存储结构设计
• 如何根据输入的项创建不同种类的对象
• 如何将求导后的对象按照任务书的需求拼接

项求导算法的设计

在说设计之前,需要说明的一点就是,因为这里的各个项的系数测试点内部,有超过Int类型的值测试用例存在,所以这里的属性声明采用BigInteger类型.不然用int型是装不下二三十位数的:)

– 设置的抽象父类

– 常数项
常数项的求导真的非常简单,这里在不考虑常数前符号的情况下,对于任意常数,求导结果都为0

不过在设计常数转换为字符串的抽象方法实现时,需要考虑到常数的符号,再转换成相应的字符串

– 幂函数

对幂函数的求导,按照求导算法,这里先对系数和指数进行求导操作

比常数要复杂一些,这里需要对系数和指数的各个情况进行综合考虑,求导之后若系数为0,则说明系数在处理之前就已经为0了,也就是说这其实是一个不合法的幂函数表达式,在处理这类表达式时,把他看成常数项处理（这里不管怎么求导都是0).求导之后若系数不为0,则该表达式为幂函数,我们就创建一个对应幂函数的对象,该方法返回的是一个Factor对象(提一下,这里的Factor是PowerFunction和ConstantNum的抽象父类),在处理多项式求导的类中运用了这几个类的多态来解决设计问题.

求导前后的元素存储结构设计

在设计之初,是想用数组存储的,但是转念一想,我需要存储的是一项项对象,而不是简单的存储字符串,如果按照存储字符串的思维来想的话,又跳转到面向过程的设计结构了,所以这里把数组的念头给打消了,运用了ArrayList<class>来存储指定类型的对象,ArrayList是一种动态数组,在添加数据时,就不需要考虑会不会溢出了,同时这里很多封装的方法(增add删remove改set查indexof插)使用的也很方便,先按照判断项的正则将多项式分解为项,均存入Term中,再进行一项项求导,结果存入AfterDev中,细节在下方创建不同种类对象说明.

包括接下来对ArrayList中的对象元素存储也是使用ArrayList存储,这儿的处理思想就是按照字符串来处理了,比较好理解。

正则表达式书写

• 但是冷静下来,仔细梳理一下,发现也许大体思路很清晰,用户输入对应的字符串后,可能其中含有空格,如果有空格的话,后面写正则需要考虑的情况就多了很多了,所以综合考量后,决定在主程序中就把空格干掉！replaceAll("[ ]", ""),这里说下我犯的小错把,这里一开始正则表达式没有带旁边的中括号,前面系数字符串里就是一个空格,最后的结果就是,系统不认这个正则,处理后的字符串和处理前的没区别=w=,好了,接下来就是对正则表达式进行一个合法性判断,刚开始,我一直纠结什么样的表达式才算是合法的,这次的需求分析内只是说有带符号常数,幂函数,那么肯定要把相应的项种类设置成对应的类,这样也方便后面的求导算法扩展,那么常数和幂函数的正则表达式都挺好写的
  (这里的写法很多,我分享一下我的思路吧)

• 常数正则:"(([+-])?(([1-9][0-9]*)|[0-9]))"

• 幂函数正则:"((([+-])?([1-9][0-9]*\\*)?))x((([\\^][+-]?[1-9][0-9]*)|()))"

• 后来想了一下,既然这道题对项的定义内这两个都有,那么一个合法的项应该是常数或者幂函数,借助这个思路,也就顺水推舟写出了多项式的正则了,笼统点理解就是一项or大于一项的正确的项的组合

• 项正则:"(((([+-])?([1-9][0-9]*\\*)?))x((([\\^][+-]?[1-9][0-9]*)|())))|(([+-])?(([1-9][0-9]*)|[0-9]))"

• 多项式正则:"((((([+-])?([1-9][0-9]*\\*)?))x((([\\^][+-]?[1-9][0-9]*)|())))|(([+-])?(([1-9][0-9]*)|[0-9])))*"

这两个正则唯一的区别就是:(多了个星号*)

• 如果没有正则表达式的话,这道题的工作量将难以想象的大了AwA,他就像是总结了这个元素的规则,在编写前一定一定要尽可能地将所有的条件都考虑到,这样无论是在判断,还是在之后的组合优化,都会非常方便。

• 那么这里的难点就在于,多项式个相对复杂的正则应该怎么写,个人观点:就像题目集的迭代一样,在一开始把问题需要解决的各个part细心分析出来,再一步步细化,就有点自顶向下的味道了。多项式->项->(常数,幂函数),一步步的将其简单化,最后根据相应的需求进行组合就ok啦。

项求导算法的设计

在说设计之前,需要说明的一点就是,因为这里的各个项的系数测试点内部,有超过Int类型的值测试用例存在,所以这里的属性声明采用BigInteger类型.不然用int型是装不下二三十位数的:)

– 设置的抽象父类

– 常数项
常数项的求导真的非常简单,这里在不考虑常数前符号的情况下,对于任意常数,求导结果都为0

不过在设计常数转换为字符串的抽象方法实现时,需要考虑到常数的符号,再转换成相应的字符串

– 幂函数

对幂函数的求导,按照求导算法,这里先对系数和指数进行求导操作

比常数要复杂一些,这里需要对系数和指数的各个情况进行综合考虑,求导之后若系数为0,则说明系数在处理之前就已经为0了,也就是说这其实是一个不合法的幂函数表达式,在处理这类表达式时,把他看成常数项处理（这里不管怎么求导都是0).求导之后若系数不为0,则该表达式为幂函数,我们就创建一个对应幂函数的对象,该方法返回的是一个Factor对象(提一下,这里的Factor是PowerFunction和ConstantNum的抽象父类),在处理多项式求导的类中运用了这几个类的多态来解决设计问题.

求导前后的元素存储结构设计

在设计之初,是想用数组存储的,但是转念一想,我需要存储的是一项项对象,而不是简单的存储字符串,如果按照存储字符串的思维来想的话,又跳转到面向过程的设计结构了,所以这里把数组的念头给打消了,运用了ArrayList<class>来存储指定类型的对象,ArrayList是一种动态数组,在添加数据时,就不需要考虑会不会溢出了,同时这里很多封装的方法(增add删remove改set查indexof插)使用的也很方便,先按照判断项的正则将多项式分解为项,均存入Term中,再进行一项项求导,结果存入AfterDev中,细节在下方创建不同种类对象说明.

包括接下来对ArrayList中的对象元素存储也是使用ArrayList存储,这儿的处理思想就是按照字符串来处理了,比较好理解。

如何根据输入的项创建不同种类的对象

UML类图

• 除了主类以外,这里一共有五个类,一个抽象类,四个实体类,其中ConstantNum(常数)与PowerFunction(幂函数)类继承抽象类Factor,polynomial类是多项式类,内部写了大致的处理框架与规范输出框架,具体的处理细节在DealInputItems中的DealItems方法,返回的是Factor类型的值,因为在处理项之前并不知道是常数项还是幂函数项,所以将返回值设置为两个类的父类,这样在polynomial类中实现多项式求导算法就可以借助DealInputItem的实体类完成处理了。

现在我分享一下我处理这个问题的思路吧,这里用排列组合的方式大致分出了幂函数的所有类型,根据有无正负号,有无指数,系数是否为1(这里的前提是不为0),分为8种情况,这里我用数组将各种情况的正则表达式存储起来,用于判断该项若是幂函数,应该归类到哪类的幂函数(这里的实现方法可能相对效率低,后面迭代会去学着用Map类中的键值对思想来实现,因为之前查阅资料综合分析之后,发现Map和Tree的思想更适合该类题目的设计)

该函数的主逻辑思维大致如下:

• 根据幂函数正则与常数正则判断该项的类型.
• 若匹配常数,则直接返回ConstantNum类的对象.将系数直接赋值。
  
  若匹配的是幂函数,则对该项进行依次的正则匹配,此时的系数与指数的赋值与分配就有所差异了。

对于没有系数和指数的幂函数,对系数和指数的赋值创建对象就很简单了,可以直接赋值,就像这样

那么大部分情况其实还是需要我们去分割字符串的,在有系数或者有指数的情况下,我们需要将指系数分离,借助String类中的split方法,取得相应的值,再赋给对应参数,break后返回相应Factor对象。

完成上面这一步后,逻辑就返回到polynomial类中的求导算法,由于返回的是Factor类对象,所以在判断求导之前,需要判断返回的对象是哪一个类的实例化,再创建实例化的对象,调用求导方法

最后返回的值通过AfterDev存储

如何将求导后的对象按照任务书的需求拼接

本来以为通过上面的步骤之后,就已经可以达到预期了,直到我碰到了这个测试用例

如果第一眼看上去,凭感觉这个结果肯定是错误的,但是仔细一分析,求导算法是对的,但是这个结果显示在屏幕上就是我们不愿意看到的结果

后来我想弄明白到底是哪里出错的时候,我决定在项和项之间加上空格判断.

仔细查看每一项的求导结果,都是对的,大数测试也是对的,唯一的错误点在于,当后面一项为正数时,前一项与后一项之间没有“+”号,导致所有的项输出都挤在一起了,那么怎么判断这些项的正负呢(这其实也就是写的大方面正则的一个特例),通过这个判断,决定相应的项前需不需要加上“+”号。

接上正号后,输出的结果是这样的

好家伙,原本以为到这里就结束了,但是本着好奇的心,我对输入输出规则的每一项进行了校验,结果证明我还是忽略了一些要素.

可以看到当求导结果为0时,结果并没有按照任务指导书上说的那样”不显示“,反而非常倔强弹出来个0,那么我想到的是,在输出之前,对每一项做一个equals检测,如果为”0″(字符串),就把他remove.

处理后的结果是这样的

但是当整个表达式的求导结果为”0″时

我的判定直接把所有的项都移除了(不得不说这就好像是面向需求编程=w=)

于是就有了下面这项操作

• 虽然整体结果是几乎成功把所有的条件都考虑清楚并解决的,但是实际上这样写,复杂度会升的很快,同时代码也比较冗余,需要一遍遍的去应对出现的各种状况,优化的改进就需要在类的设计上对各个情况先进行处理（在生成实例化对象之前,就对该项的每一种情况进行分析返回）,或者,换一种思路,使用Map,是一种映射表的概念,指数作为键,系数作为值,对每一项的求导值做一个映射(在题目集结束后参考各路大佬后得到了比较新颖的idea),不过自始自终这些分享只能作为参考,真正的融会贯通还需要自己思考,在已有的情况上进行不断的优化改进。

SourceMonitor分析结果

Percent Branch Statements 21.3
Method Call Statements 59
Percent Lines with Comments 12.3
Classes and Interfaces 5
Methods per Class 5.00
Average Statements per Method 6.44
Line Number of Most Complex Method 231
Name of Most Complex Method DealInputItems.DealItems()
Maximum Complexity 12
Line Number of Deepest Block 257
Maximum Block Depth 6
Average Block Depth 1.96
Average Complexity 2.23

Most Complex Methods in 4 Class(es):

总结

• 这其实也不是第一次接触正则表达式了,之前在做C语言课设的时候就已经做到了所有的输入信息校验,真的非常方便,不仅能规范输入,还能降低因为误输入而导致的程序崩溃,方便处理传入的信息。那么在接下来的OOP题目集中,正则的使用范围将会越来越广,优势也愈加明显。
• 另外,在程序设计基础语言的函数模块化设计的基础思维上,面向对象编程不断的强化模块化与面向对象化的思想,从一Main到底,代码紊乱->Main最简洁,函数内部疯狂套娃调用->各个模块各司其职,粘连性低,易维护扩展。
• 大部分题目其实如果真的只想达到需求的话,完全可以按照面向对象语言的思想一个个列出来,但是Java这门语言为我们提供各种强大的工具与语法,让我们能够以更加清晰的目光去看待问题中抽象的事物,抽象事物具体化。
• 在看到测试点一个个的由绿变红,心中充满喜悦的同时,其实也是对一次次优化的肯定,两个小时连续提交十来二十次也不是什么怪事,找到问题,分析问题,解决问题,总结复盘与提升才是真正的挑战!