您好，我正在解決一個似乎超出我的能力范圍的問題，因此非常感謝任何提示、閱讀材料的指示等。這就是說這里的問題：
給定數字 a, b, c ? {0, ..., n} 的 3 個子集。在 nlog(n) 中，檢查 a、b 中是否存在數字 n1、n2 和 c 中的 n3，其中 n1 n2 = n3。
我得到了將 a 和 b 轉換為多項式系數并使用 ftt 使用多項式乘法將 a 和 b 的系數相乘的提示。
現在我被困在得到多項式乘法的結果之后，接下來我該怎么做？
先謝謝了。
from numpy.fft import fft, ifft
from numpy import real, imag
def polynomial_multiply(a_coeff_list, b_coeff_list):
# Return the coefficient list of the multiplication
# of the two polynomials
# Returned list must be a list of floating point numbers.
# list from complex to reals by using the
# real function in numpy
len_a = len(a_coeff_list)
len_b = len(b_coeff_list)
for i in range(len_a-1):
b_coeff_list.append(0)
for i in range(len_b-1):
a_coeff_list.append(0)
a_fft = fft(a_coeff_list)
b_fft = fft(b_coeff_list)
c = []
for i in range(len(a_fft)):
c.append(a_fft[i] * b_fft[i])
inverse_c = ifft(c)
return real(inverse_c)
# inputs sets a, b, c
# return True if there exist n1 in a, n2 in B such that n1 n2 in C
# return False otherwise
# number n which signifies the maximum number in a, b, c
def check_sum_exists(a, b, c, n):
a_coeffs = [0]*n
b_coeffs = [0]*n
# convert sets a, b into polynomials as provided in the hint
# a_coeffs and b_coeffs should contain the result
i = 0
for item in a:
a_coeffs[i] = item
i = 1
i = 0
for item in b:
b_coeffs[i] = item
i = 1
# multiply them together
c_coeffs = polynomial_multiply(a_coeffs, b_coeffs)
# now this is where i am lost
# how to determine with c_coeffs?
return False
# return True/False
uj5u.com熱心網友回復：
感謝所有幫助過的人。我想通了，希望這可以幫助遇到類似問題的任何人。我遇到的問題是我錯誤地分配了a_coeffs和的系數b_coeffs。
這是通過測驗的解決方案，供感興趣的人使用。
from numpy.fft import fft, ifft
from numpy import real, imag
def check_sum_exists(a, b, c, n):
a_coeffs = [0] * n
b_coeffs = [0] * n
# convert sets a, b into polynomials as provided in the hint
# a_coeffs and b_coeffs should contain the result
for coeff in a:
a_coeffs[coeff] = 1
for coeff in b:
b_coeffs[coeff] = 1
# multiply them together
c_coeffs = polynomial_multiply(a_coeffs, b_coeffs)
# use the result to solve the problem at hand
for coeff in c:
if c_coeffs[coeff] >= .5:
return True
return False
# return True/False
def polynomial_multiply(a_coeff_list, b_coeff_list):
# Return the coefficient list of the multiplication
# of the two polynomials
# Returned list must be a list of floating point numbers.
# Please convert list from complex to reals by using the
# real function in numpy.
for i in range(len(a_coeff_list) - 1):
b_coeff_list.append(0)
for i in range(len(b_coeff_list) - 1):
a_coeff_list.append(0)
a_fft = fft(a_coeff_list)
b_fft = fft(b_coeff_list)
c = []
for i in range(len(a_fft)):
c.append(a_fft[i] * b_fft[i])
return real(ifft(c))
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/325479.html