具有k个1的秩和非秩fibonacci比特序列

Question

对于正整数n和k，设“n的k-fibonacci位序列”为k1的位序列，其中索引i上的1描述不数学。pow（2，i）但是Fibonacci（i）。这些正整数加起来等于n，并让给定的k-fibonnaci位序列n的“秩”作为其在所有这些fibonacci位序列的排序列表中的位置，以字典顺序从0开始。

例如，对于数字39，我们有以下有效的k-斐波那契-比特序列，k

34 21 13 8 5 3 2 1代码

k=2秩=0

01101000k=3秩=0

k=3秩=1

01101100k=4秩=0

所以，我想做两件事：

• 给定n，k和n的k-斐波那契-比特序列，我想找到n的k-斐波那契-比特序列的秩。
• 给定n，k和秩，我想找到n的k-斐波那契-比特序列。

我可以不用计算n的所有k-fibonacci位序列就可以做到这一点吗？

Answer 1

为了简洁起见，让我们说»k-fbs of n«而不是»k-fibonacci-bitsequences of n«。

我能在不计算n的所有k-fb的情况下完成这项工作吗？

我不确定。到目前为止，我仍然需要计算一些fbs。然而，你可能认为我们必须从00开始...0并向上计数——事实并非如此。我们可以反过来做，从最高的fbs开始，非常有效地向下计算。

这不是一个完整的答案。然而，有一些观察结果可以帮助你：

在下面的伪代码中，我们使用数据类型的fbs，它基本上是一个布尔数组。我们可以使用mySeq[i]读写单个位，其中biti表示Fibonacci数fib（i）。就像在你的问题中一样，位myFbs[0]和myFbs[1]不存在。默认情况下，所有位都初始化为0。可以在没有[]的情况下使用fbs来读取所表示的数字（n）。助手函数#（fbs）返回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碰巧是n的泽肯多夫表示。

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）是唯一的，并且是唯一一个具有k=#（zeckendorf（n））的fbs。因此zeckendorf（n）的秩=0。此外，不存在带k'的n的k'-fbs

任何一个n的k-fbs都可以转换成n的（k1）-fbs，方法是在fbs内部的任何位置用011替换比特序列100。这是因为fib（i）=fib（i-1）fib（i-2）。
如果我们输入n的k-fbs的秩=0，并且我们替换最右边的100，那么我们得到的n的（k1）-fbs的秩=0。如果我们替换最右边的100，我们得到的（k1）-fbs的秩=1，依此类推。

您应该能够使用从zeckendorf（n）开始的重复转换来回答这两个问题。对于第一个问题，只看k-稳定变换就足够了→<代码>100…011和100…011→<代码>011…100给定fbs（想想这些转换对排名有什么影响）。