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

    solution

    Đề bài: [Toán cho CNTT] Hoán vị đảo bit (bit-reversal)

    Hoán vị đảo bit trong FFT

    FFT lặp (iterative) sắp xếp đầu vào theo thứ tự đảo bit. Với n=2bn = 2^bn=2b, chỉ số iii được ánh xạ sang số có biểu diễn nhị phân bbb-bit đảo ngược.

    Ví dụ n=8n = 8n=8 (b=3b = 3b=3): 3=0112→1102=63 = 011_2 \to 110_2 = 63=0112​→1102​=6.

    Ví dụ

    Với n=4n = 4n=4: dãy đảo bit là [0,2,1,3][0, 2, 1, 3][0,2,1,3].

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

      Một số nguyên nnn (lũy thừa của 2).

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

      n∈{1,2,4,8,…,256}n \in \{1,2,4,8,\dots,256\}n∈{1,2,4,8,…,256}.

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

      Một dòng gồm nnn số nguyên: hoán vị đảo bit của 0,1,…,n−10, 1, \dots, n-10,1,…,n−1, cách nhau dấu cách.

    Ví dụ:

    Đầu vào:

    4

    Đầu ra:

    0 2 1 3

    Giải thích:

    2-bit: 0->00->00=0, 1->01->10=2, 2->10->01=1, 3->11->11=3.

    Đang tải editor...