折叠纸带并在展开时生成数字

Question

我有一个我正在努力的任务问题,需要一些方向来解决.假设我有一张纸条,我将它从中心折叠,使左半部分落在右半部分后面.然后我按顺序编号折叠的peices,当我展开如下时,我得到数字.1:2

如果我折叠两次我得到的数字展开时如下1:4:3:2

如果我三次折叠我得到如下1 8 5 4 3 6 7 2

当我折叠n次时,我想生成数字数组.因此,如果我将它折叠例如25次,我将以类似的顺序得到2 ^ 25个数字.

这些是我所做的观察

• 第一个和最后一个数字始终为1和2.

• 中间的两个数字总是4和3

• 索引1处的数字是最大数字,第二个最后位置处的数字是第二大数字.

• 它看起来像二进制搜索树的前序遍历,但我不知道这有多大帮助.

• 我尝试从预订中构造二叉树,然后将其转换为inorder,假设我可以反转此过程以获得相同的系列,我错了.

编辑:为了搜索这个生成的数组中的元素,我可以进行顺序搜索,这将是O(n)效率.但我意识到在这个系列中搜索一个数字必须有一个更快的方法.

我不能进行二分搜索,因为它没有排序,当完成25次折叠时有超过十亿的数字.

我可以使用什么样的搜索策略来查找数字及其索引？

这是我想将其转换为具有log(n)搜索效率的二叉搜索树的原因之一.

编辑2:我尝试了其中一个答案建议的表折叠算法,它不是内存效率.我无法在我的内存中存储超过十亿个数字,所以必须有一种方法来查找数字索引,而无需实际创建数字数组.

Answer 1

第一折:1 2

第二折:1 4 3 2

第3折:1 8 5 4 3 6 7 2

第4折:1 16 9 8 5 12 13 4 3 14 11 6 7 10 15 2

生成表格(示例为第4折)

想象一下,你有第n张纸然后展开它.

1. 生成一个大小为一的表(列= 1,行= 2 ^ n)并从下向上填充列,其值按升序排列

   16
   15
   14
   13
   12
   11
   10
   9
   8
   7
   6
   5
   4
   3
   2
   1
   

2. 通过从前到后将顶部x行粘贴到底部x行,递归地将表调整为大小(column = org.column*2,row = org.row/2)

   8  9
   7 10
   6 11
   5 12
   4 13
   3 14
   2 15
   1 16  
   
   4 13 12  5
   3 14 11  6
   2 15 10  7
   1 16  9  8   
   
   2 15 10  7  6 11 14  3
   1 16  9  8  5 12 13  4
   
   1 16  9  8  5 12 13  4  3 14 11  6  7 10 15  2
   

3. 最后从前到后读取最后一行表格作为结果

   1 16 9 8 5 12 13 4 3 14 11 6 7 10 15 2

剩下的工作是证明这项工作然后编码(我只测试n = 4,因为我很懒)

Answer 2

您可以通过使用位反转来计算折叠的数量而不必计算整个序列(这反转了数字的二进制表示,因此例如0001变为1000).

这些是您通过位反转获得的序列:

1 bit:    0  1
2 bits:   0  2  1  3
3 bits:   0  4  2  6  1  5  3  7
4 bits:   0  8  4 12  2 10  6 14  1  9  5 13  3 11  7 15

这些是纸张折叠序列(从0开始计算):

1 fold:   0  1
2 folds:  0  3  2  1
3 folds:  0  7  4  3  2  5  6  1
4 folds:  0 15  8  7  4 11 12  3  2 13 10  5  6  9 14  1

如果将纸张折叠序列拆分为偶数和奇数,则可以得到:

          0
             1

          0     2
             3     1

          0     4     2     6
             7     3     5     1

          0     8     4    12     2    10     6    14
            15     7    11     3    13     5     9     1

你会看到一个纸张折叠序列是相同的位反向序列,但具有与所述第二半(奇数)的反向隔行前半部(偶数).

您还会注意到,每对相邻的偶数/奇数加起来为2 ⁿ -1(其中n是折叠数),这意味着它们彼此相反,您可以使用一点来计算另一个 - 不是.

因此,要将折叠的折叠数x(从0开始)折叠n次:

将x除以2,如果x为奇数则执行按位NOT,然后按位反转(使用n位)

示例(折叠4次):

fold   x/2    binary   inverted    bit-reversed    from 1

 0      0      0000                0000       0       1
 1      0      0000      1111      1111      15      16
 2      1      0001                1000       8       9
 3      1      0001      1110      0111       7       8
 4      2      0010                0100       4       5
 5      2      0010      1101      1011      11      12
 6      3      0011                1100      12      13
 7      3      0011      1100      0011       3       4
 8      4      0100                0010       2       3
 9      4      0100      1011      1101      13      14
10      5      0101                1010      10      11
11      5      0101      1010      0101       5       6
12      6      0110                0110       6       7
13      6      0110      1001      1001       9      10
14      7      0111                1110      14      15
15      7      0111      1000      0001       1       2

示例:第十亿折:(折叠30次)

fold:            1,000,000,000
counting from 0:   999,999,999 (x is odd)
x/2:               499,999,999
binary:          011101110011010110010011111111 (30 digits)
bitwise NOT:     100010001100101001101100000000 (because x was odd)
bit-reversed:    000000001101100101001100010001
decimal:             3,560,209
counting from 1:     3,560,210

我不会说Java,但这样的事情应该可以解决问题:

public static long foldIndex(int n, long x) { // counting from zero
    return Long.reverse((x & 1) == 0 ? x >>> 1 : ~(x >>> 1)) >>> (Long.SIZE - n);
}