Java实现求解二项式系数及代码重构

      摘要： 通过代码重构，优化二项式系数求解。包括：使用动态规划法和值对象节省空间效率；接口改造；大整数支持等。

      难度： 初级 

      在上一篇文章中，我总结了从阅读《编程珠玑I》中获得的一些启示。其中有非常重要的一条：代码重审和回顾。通过对以前写过的代码进行重新审视和改进（以现在的经验），使之更具实用性，从而学习新的东西。你敢于面对以前写过的代码吗？如果你都不敢面对，谁还能有这个勇气？

        作为代码重审和回顾的一个例子，我对以前的一个粗糙的二项式定理实现进行了重审和改写。当时，主要是为了学习动态规划法技术，运用它来计算二项式系数。

            简单回顾二项式定理的相关知识：

           (a+b)^n= a^n + C(n,1)a^(n-1)b+...+C(n,k)a^(n-k)b^k +...+ C(n,n-1)ab^(n-1) +b^n

           其中： C(n,0)= C(n,n) = 1; C(n,k) = C(n, n-k); C(n,k)= C(n-1, k-1) + C(n-1,k)

           计算方法： 例如C(4,2)

            S1:构造数组： a[0:4][0:4]= 0

            S2:a[0][0] = 1;

            S3:a[1][0] = 1; a[1][1] = 1;

            S4:a[2][0] = 1; a[2][1] = 2; a[2][2] = 1

            S5:a[3][0] = 1; a[3][1] = 3; a[3][2] = 3; a[3][3] = 1

            S6:a[4][0] = 1; a[4][1] = 4; a[4][2] = 6

        如上所示，自上向下运用公式计算即可得到a[4][2] = 6.动态规划法通过保存并重用已经计算的值，从而避免不必要的计算时间，提高运行时间效率；其代价是一定的空间效率。这里，空间效率是O(n^2)；后面可以看到，通过重用空间，空间效率可以降低到O(n)（否则，很快就内存不足了）。

        如何改写呢？首先要定义好类的接口和功能。对于该二项式类BinomialTheorem(命名要贴切，英文不知道如何拼写？搜索！)：

          1.  提供唯一参数为 二项式的幂 ，通过公共构造器传入；

          2.  显示该二项式展开式的字符串表示。

               这里，仅仅只留出两个公共接口。简单的接口可使类更易使用；此外，在改写的过程中，发现要提供一个计算组合系数C(n,k)的便利方法。

         改进的几个方面：

         [1]  将其改为值对象。值对象是状态不可变的对象；对于同样的值应当返回同一个实例。值对象需要覆写equals 和hashCode方法；而如何使得对于同一个值参数返回同一个实例呢？参考Integer.ValueOf()实现，定义了一个内部嵌套类BinoTheoremCache，存放256个缓存BinomialTheorem对象。若取BinomialTheorem(i), 0[]{}); long start = System.nanoTime(); testMethod.invoke(obj, new Object[] {}); long end = System.nanoTime(); time[i] = ((end - start) / (double)1000000) ; } } catch (Exception e) { e.printStackTrace(); System.out.println(e.getMessage()); } } /** * showTime : 显示已经测量获得的运行时间，在 measureTime 方法调用后调用该方法。 */ public void showTime() { for (int i=0; i < time.length; i++) { System.out.printf("n = %12d : " , power10(i+1)); System.out.printf("%12.3f/n", time[i]); } } private int power10(int n) { int result = 1; while (n > 0) { result *= 10; n--; } return result; } } 

    BinomialTheorem 测试类 ： BinomialTest.java