шаблон рекурсивного разбиения массива на четные и нечетные элементы

#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. На самом деле я собираюсь использовать это для цифровой реализации калькулятора теоретического преобразования снизу вверх.