中级编程通关练习题 #5 – 二项展开式

给定一个字符串包含数学算式（ax + b）^ n，a 和 b都是整数，n 为正整数。实现一个函数把它做二项式展开。譬如，字符串”(-2x-3)^5″ 做二项式展开后的结果是：

-32x^5-240x^4-720x^3-1080x^2-810x-243。

输入样例：

“(-3y+5)^7”

输出样例：

-2187y^7+25515y^6-127575y^5+354375y^4-590625y^3+590625y^2-328125y+78125

算法思路：

• 首先使用正则表达式把字符串中需要的数值和数学符合提取出来
• 然后按照二项式的计算公式将它展开，注意下面的特殊情况
  • 如果 n 是 0，那么返回值是 1
  • 如果 n 是 1， 那么返回值是 ax + b
  • 如果 b 是 0， 那么返回值是 （ax)^n
• 计算二项式的系数需要用到阶乘，实际上二项式的每一个系数都可以看作是一个组合数。譬如二项展开式：(a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴
  • a⁴ – 四选四的组合只有一种可能：C(4, 4) = 4!/4!，所以系数是 1。
  • 4a³b – 四选三的组合有四种可能：C(4, 3) = 4!/((4-3)!*3!)，所以系数是 4。
  • 6a²b² – 四选二的组合有六种可能：C(4, 2) = 4!/((4-2)!*2!)，所以系数是 6。
  • 4ab³ – 同样，四选三的组合有四种可能，所以系数是 4。
  • b⁴ – 最后四选四的组合是一种可能，所以系数是 1。