欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

使用Python实现多项式系数卷积乘法

程序员文章站 2024-03-19 23:02:40
...

关键字

多项式乘法 卷积乘法 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]