用 k 个排序和取消排序斐波那契位序列
Rank and unrank fibonacci bitsequence with k ones
对于正整数n和k，设一个“k-斐波那契数列n" 的位序列 k 1 其中索引 i 上的 1 描述不是 Math.pow(2,i) 但 Fibonacci(i)。这些正整数加起来为n，让给定的k的"rank"-斐波那契位序列为n 是它在所有这些斐波那契位序列的排序列表中的位置，从 0 开始按字典顺序排列。
例如，对于 n 数字 39，我们有以下有效的 k-斐波那契位序列，k <=4。本例中斐波那契位序列后面的斐波那契数列如下：
34 21 13 8 5 3 2 1
10001000 k = 2 排名 = 0
01101000 k = 3 排名 = 0
10000110 k = 3 排名 = 1
01101100 k = 4 排名 = 0
所以，我希望能够做两件事：
- 给定 n、k 和 k-斐波那契位序列 n，我想找到n的那个k-斐波那契位序列的秩。
- 给定 n、k 和一个排名，我想找到 k -具有该排名的 n 的斐波那契位序列。
我可以这样做而不必计算 n 的所有 k-斐波那契位序列，这些位序列位于感兴趣的位序列之前吗？
预赛
为简洁起见，我们说»n的k-fbs«而不是»n的k-斐波那契位序列«。
问题
Can I do this without having to compute all the k-fbs of n that come before the one of interest?
我不确定。到目前为止，我仍然需要计算 fbs 的 some。然而，您可能认为我们必须从 00…0 开始并向上计数——事实并非如此。我们可以反过来做，从最高的 fbs 开始，然后非常有效地工作。
这不是一个完整的答案。但是，有一些观察可以帮助您：
策肯多夫
在下面的伪代码中，我们使用数据类型 fbs，它基本上是一个布尔数组。我们可以使用 mySeq[i] 读取和写入单个位，其中位 i 表示斐波那契数 fib(i)。就像您的问题一样，位 myFbs[0] 和 myFbs[1] 不存在。默认情况下，所有位都初始化为 0。可以在没有 [] 的情况下使用 fbs 来读取表示的数字 (n)。辅助函数 #(fbs) returns fbs 中设置的位数 (k)。 n = 7 的示例：
fbs meaning representation helper functions
1 0 1 0
| | | `— 0·fib(2) = 0·1 ——— myFbs[2] = 0 #(myFbs) == 2
| | `——— 1·fib(3) = 1·2 ——— myFbs[3] = 1 myFbs == 7
| `————— 0·fib(4) = 0·3 ——— myFbs[4] = 0
`——————— 1·fib(5) = 1·5 ——— myFbs[5] = 1
对于任何给定的 n，我们可以轻松计算 n 的字典序最大值（在所有 k 中）fbs，因为这个 fbs 恰好是 n 的 Zeckendorf representation。
function zeckendorf(int n) returns (fbs z):
1 int i := any (ideally the smallest) number such that fib(start) > n
2 while n-z > 0
3 | if fib(i) < n
4 | | z[i] := 1
5 | i := i - 1
zeckendorf(n) 是唯一的，并且是 n 中唯一具有 k=#(zeckendorf(n)) 的 fbs。因此 zeckendorf(n) 的排名为 0。此外，不存在 k'<#(zeckendorf(n)).
的 n 的 k'-fbs
转型
n 的任何 k-fbs 都可以通过在 fbs 内的任何位置将位序列 100 替换为 011 来转换为 n 的 (k+1)-fbs。这是有效的，因为 fib(i)=fib(i-1)+fib(i-2).
如果我们输入的 n 的 k-fbs 有 rank=0 并且我们替换最右边的 100 那么我们得到的 n 的 (k+1)-fbs 也有 rank=0。如果我们替换第二个最右边的 100，我们得到的 (k+1)-fbs 有 rank=1 等等。
您应该能够使用从 zeckendorf(n) 开始的重复转换来回答您的两个问题。对于第一个问题，仅查看给定 fbs 的 k-稳定变换 011…100→100…011 和 100…011→011…100 甚至可能就足够了（想想这些转换对排名）。
对于正整数n和k，设一个“k-斐波那契数列n" 的位序列 k 1 其中索引 i 上的 1 描述不是 Math.pow(2,i) 但 Fibonacci(i)。这些正整数加起来为n，让给定的k的"rank"-斐波那契位序列为n 是它在所有这些斐波那契位序列的排序列表中的位置，从 0 开始按字典顺序排列。
例如，对于 n 数字 39，我们有以下有效的 k-斐波那契位序列，k <=4。本例中斐波那契位序列后面的斐波那契数列如下：
34 21 13 8 5 3 2 1
10001000 k = 2 排名 = 0
01101000 k = 3 排名 = 0
10000110 k = 3 排名 = 1
01101100 k = 4 排名 = 0
所以，我希望能够做两件事：
- 给定 n、k 和 k-斐波那契位序列 n，我想找到n的那个k-斐波那契位序列的秩。
- 给定 n、k 和一个排名，我想找到 k -具有该排名的 n 的斐波那契位序列。
我可以这样做而不必计算 n 的所有 k-斐波那契位序列，这些位序列位于感兴趣的位序列之前吗？
预赛
为简洁起见，我们说»n的k-fbs«而不是»n的k-斐波那契位序列«。
问题
Can I do this without having to compute all the k-fbs of n that come before the one of interest?
我不确定。到目前为止，我仍然需要计算 fbs 的 some。然而，您可能认为我们必须从 00…0 开始并向上计数——事实并非如此。我们可以反过来做，从最高的 fbs 开始，然后非常有效地工作。
这不是一个完整的答案。但是，有一些观察可以帮助您：
策肯多夫
在下面的伪代码中，我们使用数据类型 fbs，它基本上是一个布尔数组。我们可以使用 mySeq[i] 读取和写入单个位，其中位 i 表示斐波那契数 fib(i)。就像您的问题一样，位 myFbs[0] 和 myFbs[1] 不存在。默认情况下，所有位都初始化为 0。可以在没有 [] 的情况下使用 fbs 来读取表示的数字 (n)。辅助函数 #(fbs) returns fbs 中设置的位数 (k)。 n = 7 的示例：
fbs meaning representation helper functions
1 0 1 0
| | | `— 0·fib(2) = 0·1 ——— myFbs[2] = 0 #(myFbs) == 2
| | `——— 1·fib(3) = 1·2 ——— myFbs[3] = 1 myFbs == 7
| `————— 0·fib(4) = 0·3 ——— myFbs[4] = 0
`——————— 1·fib(5) = 1·5 ——— myFbs[5] = 1
对于任何给定的 n，我们可以轻松计算 n 的字典序最大值（在所有 k 中）fbs，因为这个 fbs 恰好是 n 的 Zeckendorf representation。
function zeckendorf(int n) returns (fbs z):
1 int i := any (ideally the smallest) number such that fib(start) > n
2 while n-z > 0
3 | if fib(i) < n
4 | | z[i] := 1
5 | i := i - 1
zeckendorf(n) 是唯一的，并且是 n 中唯一具有 k=#(zeckendorf(n)) 的 fbs。因此 zeckendorf(n) 的排名为 0。此外，不存在 k'<#(zeckendorf(n)).
转型
n 的任何 k-fbs 都可以通过在 fbs 内的任何位置将位序列 100 替换为 011 来转换为 n 的 (k+1)-fbs。这是有效的，因为 fib(i)=fib(i-1)+fib(i-2).
如果我们输入的 n 的 k-fbs 有 rank=0 并且我们替换最右边的 100 那么我们得到的 n 的 (k+1)-fbs 也有 rank=0。如果我们替换第二个最右边的 100，我们得到的 (k+1)-fbs 有 rank=1 等等。
您应该能够使用从 zeckendorf(n) 开始的重复转换来回答您的两个问题。对于第一个问题，仅查看给定 fbs 的 k-稳定变换 011…100→100…011 和 100…011→011…100 甚至可能就足够了（想想这些转换对排名）。