UVA11955 - Binomial Theorem 题解

· · 题解

题目描述

分析

1. 组合数

一般地，要从 k 个元素中选择 t 个元素的方案数称为组合数，用 C_k^t 来表示，其计算公式为

C_k^t=\dfrac{k!}{t!\times(k-t)!}

由于 Python 自带高精度，因此定义好求阶乘函数并按照上述公式定义求组合数的公式即可直接计算。参考代码（Python 中需要用双斜杠表示整除）：

#求阶乘函数
def fact(x):return 1 if(x==0 or x==1) else x*fact(x-1)
#组合数函数
def C(n,r):return fact(n)//fact(r)//fact(n-r)

2. 二项式定理

$$(a+b)^k=C_k^0\times a^kb^0+C_k^1\times a^{k-1}b^1+C_k^2\times a^{k-2}b^2+\ldots+C_k^k\times a^0b^k$$ ### 3. 连接每一项 上述二项展开式从结构上可以看作是若干个字符串由加号进行连接的结果。在 Python 中可以使用 `"+".join(列表)` 的方法用加号连接一个列表中的所有元素，由此我们可以考虑将二项式的所有展开项存放在一个列表中进行连接。 ### 4. 输出 #### 4.1 特别注意 $k=1

这里的输出首先需要特判 k=1 的情况，如果次数为 1，直接用加号连接两个变量名输出即可：

#特判次数为1的情况, 末尾不能输出^1
if(p==1):return "%s+%s"%(v1,v2)

4.2 把每一项制成字符串

其他情况下，按照二项式定理确定每一项的次数和系数，使用 %d 和 %s 格式化数字和变量名组成相应的字符串存入列表即可。需要说明的是不能输出“1 次幂” 或者系数 1。同样，开头和结尾次数为 0 要连同变量名都不输出，参考代码：

for k in range(p,-1,-1):
  if(k!=0 and k!=p):result.append("%d*%s^%d*%s^%d"%(C(p,k),v1,k,v2,p-k))
  elif(k==0):result.append("%s^%d"%(v2,p))
  elif(k==p):result.append("%s^%d"%(v1,p))

4.3 判断幂次为 1

判断幂次/系数为 1 容易想到的办法是直接 replace("^1","")，但是由于题目中 k\le 50，这会导致幂次为 11\sim 19 时，十位的 1 被错误移除，因此这个方法不可行。判断幂次为 1 的正确方法是判断这个 ^1 后面是不是紧挨着乘号或者加号，这是这个问题的关键。参考代码：

return "+".join(result).replace("^1*","*").replace("^1+","+")

4.4 处理输入的内容

输入的两个变量和次数全部出现在同一行，一种可行的处理方法是将左括号 ( 移除，+ 和 )^ 全部替换为空格，然后用 split() 将表达式拆分为一个长度为 3 的列表。例如输入 (alpha+omega)^3，拆分后的结果为 ["alpha","omega","3"]，列表第一个元素是变量名，第二个元素是另一个变量名，第三个元素转化为整数即为次数，按照 4.1~4.3 的方法处理即可。

完整代码

笔者认为分析中 4.1~4.3 的部分宜封装为函数来完成，代码中对于这些函数的功能已经给出了相应的说明。


#求阶乘函数
def fact(x):return 1 if(x==0 or x==1) else x*fact(x-1)
#组合数函数
def C(n,r):return fact(n)//fact(r)//fact(n-r)
#输出展开式的某一部分, v1,v2是前后两个变量名,k为系数,p为次数
def output(v1,v2,p):
    result=list()
    #特判次数为1的情况, 末尾不能输出^1
    if(p==1):return "%s+%s"%(v1,v2)
    #次数不为1的话就构造字符串
    for k in range(p,-1,-1):
        if(k!=0 and k!=p):result.append("%d*%s^%d*%s^%d"%(C(p,k),v1,k,v2,p-k))
        elif(k==0):result.append("%s^%d"%(v2,p))
        elif(k==p):result.append("%s^%d"%(v1,p))
    #次数不为1的情况下,出现的^1全部都紧挨着加号或乘号,可以利用这一点将其移除
    return "+".join(result).replace("^1*","*").replace("^1+","+")

n=int(input())
for i in range(1,n+1,1):
    expr=input()
    var=expr.replace(')^',' ').replace('+',' ').replace('(','').split()
    x=var[0]
    y=var[1]
    print("Case %d:"%i,output(x,y,int(var[2])))

Extra

从效果上看，本题相当于 Mathematica 中 Expand 函数的简化版本。