Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán cho CNTT] Tích chập tuyến tính qua zero-padding DFT

    Tích chập tuyến tính bằng DFT

    Tích chập tuyến tính của aaa (dài LaL_aLa​) và bbb (dài LbL_bLb​) có độ dài L=La+Lb−1L = L_a + L_b - 1L=La​+Lb​−1:

    c[m]=∑ta[t] b[m−t]c[m] = \sum_{t} a[t]\, b[m-t]c[m]=∑t​a[t]b[m−t]

    Để dùng định lý tích chập, hãy zero-pad cả hai dãy về độ dài LLL rồi thực hiện tích chập vòng qua DFT. Kết quả nguyên nên làm tròn.

    Ví dụ

    a=[1,2]a = [1, 2]a=[1,2], b=[1,1]b = [1, 1]b=[1,1] cho c=[1,3,2]c = [1, 3, 2]c=[1,3,2] (giống nhân đa thức (1+2x)(1+x)(1+2x)(1+x)(1+2x)(1+x)).

    • Định dạng đầu vào:

      Dòng 1: LaL_aLa​ rồi LaL_aLa​ số nguyên. Dòng 2: LbL_bLb​ rồi LbL_bLb​ số nguyên.

    • Ràng buộc đầu vào:

      1≤La,Lb≤321 \le L_a, L_b \le 321≤La​,Lb​≤32; ∣a[t]∣,∣b[t]∣≤100|a[t]|, |b[t]| \le 100∣a[t]∣,∣b[t]∣≤100.

    • Định dạng đầu ra:

      Một dòng gồm La+Lb−1L_a+L_b-1La​+Lb​−1 số của tích chập, cách nhau dấu cách, 4 chữ số thập phân.

    Ví dụ:

    Đầu vào:

    2 1 2
2 1 1

    Đầu ra:

    1.0000 3.0000 2.0000

    Giải thích:

    (1+2x)(1+x)=1+3x+2x^2 nen tich chap = [1,3,2].

    Đang tải editor...