java - 折叠纸条并在展开时生成数字

Question

我有一个作业问题，我正在努力解决，需要一些指导来解决。 假设我有一张纸条，我从中间折叠它，使左半边在右半边后面。然后我按顺序给折叠的碎片编号，当我展开时得到数字如下。 1 : 2

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

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

我想在折叠 n 次时生成数字数组。因此，如果我将它折叠 25 次，我将得到 2^25 个类似顺序的数字。

这些是我的观察结果

• 第一个和最后一个数字总是 1 和 2。

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

• 索引 1 的数字是最大的数字，倒数第二个位置的数字是第二大的数字。

• 它看起来像是二叉搜索树的前序遍历，但我不知道这有什么帮助。

• 我尝试从前序构建二叉树，然后将其转换为中序，假设我可以反转此过程以获得相同的系列，但我错了。

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

我无法进行二分查找，因为这没有排序，并且当完成 25 次以上的折叠时，有超过 10 亿个数字。

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

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

编辑 2: 我尝试了其中一个答案建议的表格折叠算法，但它的内存效率不高。我无法在内存中存储超过 10 亿个数字，因此必须有一种方法可以在不实际创建数字数组的情况下找到数字索引。

Answer 1

第一折:1 2

第二次:1 4 3 2

第三次: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折为例)

Imagine you have a nth fold paper and then unfold it.

1. 生成大小为(column = 1, row = 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行表作为结果

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

---

你剩下的工作就是证明这个工作，然后编码它(我只测试了n=4，因为我很懒)