#fft #recurrence #ntt
#бпф #повторение #ntt
Вопрос:
Я ищу шаблон для рекурсивного разделения массива на четные и нечетные элементы. Я попытаюсь описать проблему следующим образом:
предположим, у нас есть массив длиной 16 в виде:
a=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
Первая итерация: разбиение на четные и нечетные элементы
[0,2,4,6,8,10,12,14]
[1,3,5,7,9,11,13,15]
которые в основном являются
a[2i] for i=0:7
a[2i 1] for i=0:7
снова разбивая каждый из этих массивов на четные и нечетные элементы, мы имеем
[0,4,8,12]
[2,6,10,14]
[1,5,9,13]
[3,7,11,15]
это аналогично
4i for i=0:3
4i 2
4i 1
4i 3
повторное разделение элементов массива будет
[0,8]
[4,12]
.
.
[1,9]
или
8i for i=0:1
8i 4
8i 2
8i 6
8 1
8i 5
8i 3
8i 1
Массивы необходимо разбивать рекурсивно, пока в каждом массиве не останется только два элемента.
Одна вещь, которую я заметил, что нижняя половина похожа на верхнюю, и нам просто нужно добавить «1» к индексным терминам
Мне было интересно, как я могу найти шаблон для массива с элементами «n»?
Большое вам спасибо за ваше время.
Ответ №1:
предполагая, что ваше число n
равно степени 2 (иначе 2^k
):
тогда у вас будут m
= n/2
= 2^(k-1)
массивы со следующими номерами для i
in {0,1}
:
0: m*i f(0)
1: m*i f(1)
...
j: m*i f(j)
...
m-1: m*i f(m-1)
где f(x)
— функция, которая принимает целое число ( x
), преобразует его в k-1
десятичное двоичное число ( b
), переворачивает его ( rb
) и возвращает его десятичное значение ( y
).
Пример для k=4
(который очень похож на ваши значения):
x | b | rb | f(x)=y |
---|---|---|---|
0 | 000 | 000 | 0 |
1 | 001 | 100 | 4 |
2 | 010 | 010 | 2 |
3 | 011 | 110 | 6 |
4 | 100 | 001 | 1 |
5 | 101 | 101 | 5 |
6 | 110 | 011 | 3 |
7 | 111 | 111 | 7 |
Комментарии:
1. Большое вам спасибо. Я думал об этом несколько дней. На самом деле я планировал использовать это для разработки цифрового оборудования, и я могу легко перевернуть массивы.
2. @elec_hi ^^ Надеюсь, у вас есть фиксированное k, это упростило бы все ^^
3. Да, K исправлено, и я могу дополнить массивы нулем, если он не равен степени 2. На самом деле я собираюсь использовать это для цифровой реализации калькулятора теоретического преобразования снизу вверх.