fft - 递归地将数组拆分为奇数和偶数元素的模式
问题描述
我正在寻找一种模式来递归地将数组拆分为奇数和偶数元素。我将尝试在以下内容中描述问题:
假设我们有一个长度为 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”个元素的数组的模式?
非常感谢您的宝贵时间。
解决方案
假设您的数字n
是 2 的幂(又名2^k
):
那么您将拥有m
= n/2
=数组,其中in2^(k-1)
具有以下数字:i
{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 |
推荐阅读
- android - 为什么 Android 上的 AppBar 背景颜色不是全白?
- ruby-on-rails - Rails:在 RSpec 测试查看编辑表单时出错
- sql - 如何从具有相似表名的多个表中删除数据?
- python - 如何在不使用 .drop 命令中的所有级别的情况下从多索引 Dataframe 中删除数据?
- jdbc - 尝试获取具有 OAuth 类型的 Google Bigquery 存储客户端对象时出错:SERVICE_ACCOUNT,错误
- html - 如何限制 HTML 范围滑块超出范围
- r - For循环在R中进行回归?
- deep-learning - 针对函数而不是数据训练 LSTM 文本生成器
- java - 300万条大型数据库表查询耗时过长,如何优化性能
- google-calendar-api - Google Calendar API - 清除所有事件