使用Python实现多项式系数卷积乘法
复数多项式相乘之Python实现
关键字
多项式乘法 卷积乘法 Python 多项式系数 卷积系数 复数多项式 华为机考 算法
问题来源
来源于一个华为面试题。题目内容大致如下:
题目描述
多项式 的系数[b(2) b(1) b(0)]=[1 2 5]
二者相乘所得的多项式 的系数[c(3) c(2) c(1) c(0)]=[1 3 7 5]
利用上面的计算方法,我们很容易得到:
c(0)=a(0)b(0)
c(1)=a(0)b(1)+a(1)b(0)
c(2)=a(0)b(2)+a(1)b(1)+a(2)b(0)
c(3)=a(0)b(3)+a(1)b(2)+a(2)b(1)+a(3)b(0)
其中:a(3)=a(2)=b(3)=0
在上面的基础上推广一下:
假定两个多项式的系数分别为a(n),n=0n1和b(n),n=0n2,这两个多项式相乘所得的多项式系数为c(n),则:
c(0)=a(0)b(0)
c(1)=a(0)b(1)+a(1)b(0)
c(2)=a(0)b(2)+a(1)b(1)+a(2)b(0)
c(3)=a(0)b(3)+a(1)b(2)+a(2)b(1)+a(3)b(0)
c(4)=a(0)b(4)+a(1)b(3)+a(2)b(2)+a(3)b(1)+a(4)b(0)
以此类推可以得到卷积算法:
上面这个式子就是a(n)和b(n)的卷积表达式。
通常我们把a(n)和b(n)的卷积记为:a(n)b(n),其中的表示卷积运算符
输入描述
两个最高阶数为4的复数多项式系数序列。高阶系数先输入;每个系数为复数,复数先输入实数部分,再输入虚数部分; 实部或者虚部为0,则输入为0;
每个实部和虚部的系数最大值不超过1000
输出描述
求卷积多项式系数输出;先输出高阶系数,多项式算法.
输出的期望结果是多项式乘积结果,因为自己的算法研究的不太深入,所以肤浅地了解到这个可以称之为卷积。
测试Demo
输入:
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
输出
0
2
0
4
0
6
0
8
0
10
0
8
0
6
0
4
0
2
思路和代码
方法一(数学逻辑)
思路:
利用纯数学逻辑,两个多项式相乘,是两个多项式的每个系数和另一个多项式的系数循环遍历相乘,并将次数相同的系数合并。
代码:
import time
# 定义两个多阶多项式的阶数,即每个多项式的最高次幂
# 因为幂次的变化,决定终端输入系数的个数。 此处也可以使用配置文件操作。
A_LEVEL = 4
B_LEVEL = 4
def get_plural_product(sub_as, sub_bs, an, bn):
"""
计算两个复数乘积,返回乘积结果的幂次,以及结果的实部和虚部的系数。
:param sub_as: 列表,第一个复数的两个系数
:param sub_bs: 列表,第二个复数的两个系数
:param an: 第一个复数带上的参数的幂次
:param bn: 第二个复数带上的参数的幂次
:return: 列表,0元素为结果值的幂次,1元素为实数部分结果,2元素为虚数部分结果
"""
return [an+bn, (sub_as[0] * sub_bs[0] - sub_as[1] * sub_bs[1]),
(sub_as[0] * sub_bs[1] + sub_as[1] * sub_bs[0])]
def update_plural_list(arr_mul, add_one):
"""
将两个复数的乘积系数,添加到结果列表中。
:param arr_mul: 结果列表,是列表型列表。列表中包含 (A_LEVEL + B_LEVEL + 1)
个子列表; 子列表的格式大概是[n, a, b]形式,n代表次数,a代表n
幂次的实部系数,b代表n幂次的虚部系数。
:param add_one: 遍历过程或得的临时的两个复数乘积的结果,结果也是[n, a, b]形式
:return: 更新的结果列表,将arr_mul中子列表的同add_one幂次相同的参数进行了相加操作。
"""
for a in arr_mul:
if a[0] == add_one[0]:
a[1] += add_one[1]
a[2] += add_one[2]
break
# 这里的另外一个优化的方式是可以使用字典进行寻值。
def get_multi_product(arr_a, arr_b):
"""
获取复数多项式的乘积
:param arr_a: 第一个复数多项式的系数列表,列表格式为
[最高次实部,最高次虚部,次高次实部,次高次虚部, ......, 0次实部,0次虚部]
:param arr_b: 第二个复数多项式列表
:return: 无,按照从高次幂到低次幂,从实部到虚部顺序打印结果系数。
"""
global A_LEVEL
global B_LEVEL
# 获取结果最高次幂数
top_level = A_LEVEL + B_LEVEL
# 创建初始结果列表,格式应该为:
# [[n, 0, 0], [n-1, 0, 0], [n-2, 0, 0], ..., [0, 0, 0]]
# 其中 n = (A_LEVEL + B_LEVEL), 最高次幂数。
# 子列表的 0索引位置为幂次。1索引位置为当前幂次的实数系数,2索引位置为虚数系数。
res_arr = list()
for i in range(top_level+1)[::-1]:
res_arr.append([i, 0, 0])
# print("初始结果列表为: {}".format(res_arr))
# 初始结果格式为: [[n, 0, 0], [n-1, 0, 0], [n-2, 0, 0], ..., [0, 0, 0]]
# 将原始系数列表从最高次幂到最低次幂,从实部到虚部格式的一维系数列表转换为二位列表
# 即: 将 [an, ani, ..., a0, a0i] 转换为: [[an, ani], ..., [a0, a0i]]
# 转换为列表型列表。子列表对应每个幂次的实数和虚数部分的系数。
arr_a_new = [arr_a[i:i+2] for i in range(0, len(arr_a), 2)]
arr_b_new = [arr_b[i:i+2] for i in range(0, len(arr_b), 2)]
print("更新多项式一系数结果列表: {}".format(arr_a_new))
print("更新多项式二系数结果列表: {}".format(arr_b_new))
for i in range(len(arr_a_new)):
for j in range(len(arr_b_new)):
res = get_plural_product(
arr_a_new[i], arr_b_new[j],
len(arr_a_new)-1-i, len(arr_b_new)-1-j)
update_plural_list(res_arr, res)
for ra in res_arr:
print(ra[1])
print(ra[2])
def main():
""" Main function """
global A_LEVEL
global B_LEVEL
# 定义两个多项式的系数列表
a_arr = list()
b_arr = list()
# 从终端输入两个多项式的系数,并添加到对应的列表中
# 注意系数的输入原则:
# 先输入第一个多项式的所有系数,再输入第二个多项式的所有系数
# 系数的次数从最高次到最低次, 系数先输入实数部分,再输入虚数部分
for i in range((A_LEVEL+1) * 2):
a_arr.append(int(input()))
for i in range((B_LEVEL+1) * 2):
b_arr.append(int(input()))
start_t = time.time()
# 调用函数,打印结果
get_multi_product(a_arr, b_arr)
print("数据处理消耗时间: {}".format(time.time() - start_t))
print("Done!!")
if __name__ == "__main__":
main()
方法二(算法逻辑)
思路:
利用卷积算法原理,结果中的n幂次系数为两个多项式中的x幂次和y幂次的乘积,其中:x+y=n.
代码:
参考:
第二题 多项式卷积乘法
在代码的基础上做了些注释和简单修改。
import time
A_LEVEL = 4
B_LEVEL = 4
def juanji():
"""
输入两个多阶项式的实部和虚部的系数,从高次到低次,从实部到虚数顺序输入
:return: 打印两个多阶多项式卷积结果系数。顺序同输入规则。
"""
global A_LEVEL
global B_LEVEL
# 初始化两个多项式的系数列表
a_xishu = list()
b_xishu = list()
for i in range(A_LEVEL+1):
one = list()
one.append(int(input()))
one.append(int(input()))
a_xishu.append(one)
for i in range(B_LEVEL+1):
two = list()
two.append(int(input()))
two.append(int(input()))
b_xishu.append(two)
# 这个转换很重要,利用了幂次和列表索引的联系,通过逆序转换,幂次和列表索引一致
a_xishu = a_xishu[::-1]
b_xishu = b_xishu[::-1]
star_t = time.time()
a_len = len(a_xishu)
b_len = len(b_xishu)
top_level = A_LEVEL + B_LEVEL
for i in range(top_level+1)[::-1]:
ci_s = 0
ci_x = 0
for index in range(i + 1)[::-1]:
if i - index < a_len and index < b_len:
temp = fushumulity(a_xishu[i - index], b_xishu[index])
ci_s += temp[0]
ci_x += temp[1]
print(ci_s)
print(ci_x)
print("数据处理耗时: {}".format(time.time()-star_t))
def fushumulity(x, y):
s = x[0] * y[0] - x[1] * y[1]
x = x[0] * y[1] + x[1] * y[0]
return s, x
juanji()
联系我
如果有什么疑问,可以联系探讨![email protected]
上一篇: MFC 利用opencv实现视频播放
下一篇: 写给前端的正则表达式