关于包含简单幂函数和简单正余弦函数的导函数的求解和优化问题

  说到三角函数的化简,都是高考过的人,有谁畏惧过数学的第一道大题?从笔算到代码实现,是一个从具体到抽象的过程。内心秉持这样一种信念,笔能化简它,为什么代码不行?

提出问题

  一个表达式,由三角函数(只包含sin(x)和cos(x))和幂函数组成,输出其导数并使得结果的表达式尽可能短。

问题分析

  合并同类项是缩短结果的最基本方法之一。但合并同类项之后并非一定能获得最短的表达式,例如存在 sin(x)^2+cos(x)^2 这类并非同类项却能合并并化简的式子。

  1.合并同类项

  通过抽象后我们发现每一项都可以用四个数来唯一确定,他们分别是系数n,sin(x)的指数a,cos(x)的指数b,x的指数c。而为了便于查找,我们可以用hashmap这种数据结构来存储这些数据。对于两个不同的项,只要它的三个系数(a、b、c)相同,我们就说他是同类项,所以为了合并同类项,我们可以以指数为键,以系数为值来存放每一项。因为指数有三个,所以我们构造一个HashKey类来存放这三个指数

 1 import java.math.BigInteger;
 2 
 3 public class HashKey {
 4     private BigInteger deInSin;
 5     private BigInteger deInCos;
 6     private BigInteger deInX;
 7     
 8     public HashKey(BigInteger deInSin, BigInteger deInCos, BigInteger deInX) {
 9         this.deInSin = deInSin;
10         this.deInCos = deInCos;
11         this.deInX = deInX;
12     }
13     
14     @Override
15     public boolean equals(Object o) {
16         if (this == o) {
17             return true;
18         }
19         if (!(o instanceof HashKey)) {
20             return false;
21         }
22         HashKey hashKey = (HashKey)o;
23         return hashKey.deInSin.equals(deInSin) 
24             && hashKey.deInCos.equals(deInCos) && hashKey.deInX.equals(deInX);
25     }
26     
27     @Override
28     public int hashCode() {
29         int result = 17;
30         result = 31 * result + deInSin.intValue();
31         result = 31 * result + deInCos.intValue();
32         result = 31 * result + deInX.intValue();
33         return result;
34     }
35     
36     public BigInteger getDeInSin() {
37         return deInSin;
38     }
39     
40     public BigInteger getDeInCos() {
41         return deInCos;
42     }
43     
44     public BigInteger getDeInX() {
45         return deInX;
46     }
47 }

   (注意:需要重写equals方法和hashCode方法才能作为key。)

  这样,对于每个需要新添入的项,都可以先查找是否有相同的HashKey。如果有,更新其系数(value);否则插入新的一项。

  2.化简三角函数

  假设有两个表达式分别为s1和s2,其中s1的系数和指数分别为(n1, a1, b1, c1),s2的系数和指数分别为(n2, a2, b2, c2)。通过观察我们发现可以合并同类项的表达式有以下特点:

    1. a1 + b1 + c1 = a2 + b2 +c2

    2. |a1 - a2| = |b1 - b2| = 2

    3. c1 = c2

  因此,我们可以遍历HashMap,对于每个HashKey(ai, bi, ci),我们分别查找是否存在HashKey(ai - 2, bi + 2, ci)和HashKey(ai +2, bi - 2, ci)。不妨设存在HashKey(ai - 2, bi + 2, ci),并设HashKey(ai, bi, ci)的value为n,HashKey(ai - 2, bi + 2, ci)的value为m。合并完生成两项(n, ai-2, bi, ci)和(m-n, ai-2, bi+2, ci),完成一次化简。每执行完一次化简后结束此次遍历并重新开始遍历(防止更改已经遍历过得项导致可以在此化简),直到便利结束前后HashMap没有发生变化停止。(此次作业中由于输入限定在100字符以内,于是没有判断呢是否发生变化,而是强制执行十次后结束)。

  至此,化简大致就完成了,不过还存在一些遗留问题。

    1.对于形如 1-sin(x)^2 的项可以化简为 cos(x)^2

    2.对于形如 sin(x)^4 - cos(x)^4 的项可以化简为 sin(x)^2-cos(x)^2 进而化简为 1-2*cos(x)^2

  对于第一个问题,我的解决方法是模仿前文所述化简,对于每个HashKey(ai, bi, ci),我们查找是否存在HashKey(ai, bi + 2, ci)和HashKey(ai + 2, bi, ci)并且其value与HashKey(ai, bi, ci)的value互为相反数,找到后化简方法类似,不再赘述。

  对于第二个问题,我们可以考虑 sin(x)^4 - cos(x)^4 是如何生成的,即什么表达式的导数是 sin(x)^4 - cos(x)^4。不难发现 sin(x)*cos(x)^3+cos(x)*sin(x)^3 是其原函数之一。我们发现 sin(x)*cos(x)^3+cos(x)*sin(x)^3 可以用上述方法化简后成为 sin(x)*cos(x),再求导就会得到 1-2*cos(x)^2 而不是 sin(x)^4 - cos(x)^4。同样的若待求导表达式是 sin(x)^4 - cos(x)^4,我们发现其导数是 4*sin(x)^3*cos(x)+4*cos(x)^3*sin(x),求导后亦可用上述方法化简。于是我们可以在求导前后对表达式均化简以解决第二个问题。

  至此,此次作业的性能分就基本可以拿满了,不过上述方方仍存在可以优化的地方(强测最后一个测试点最短156个字符而我输出了157个),希望满分的大佬能分享更好的优化方法

总结

  对于优化输出的问题,相信很多人都能想到优化方法,只是是觉得太麻烦懒于用代码实现,或者没有足够的时间来写完优化。我想说的是其实优化也层层递进的,写代码时不要有畏难畏多情绪,想到一点就写一点,能短一点就多拿一点分,在不断优化和完善中一定能实现想要的结果。

上一篇:当项目中使用到缓存,我们是选择 Redis 还是 Memcached ,为什么?


下一篇:零基础,从一个抢票程序,提升自己的Python技能