给定整数x与k>1，如何计算Modified Zeckendorf二进制表示？

先明确核心规则：生成的位串里，任意两个1之间必须至少有k个0——这是Zeckendorf表示（k=1）的通用扩展，本质是用**(k+1)阶广义斐波那契数列**做唯一数值分解，具体步骤如下：

1. 构建权重数列 #

先定义一组权重值 W_n，这组值是分解x的基础：

• 前k+1项全为1：W_0 = W_1 = ... = W_k = 1
• 从第k+1项开始，每一项等于前一项加上往前数k+1位的项：W_n = W_{n-1} + W_{n-(k+1)}（n > k）

举个k=2的例子，数列前几项是：1,1,1,2,3,4,6,9...

2. 从大到小匹配权重生成位串 #

对给定的整数x，按以下步骤构建符合规则的位串：

• 找到最大的索引m，使得 W_m ≤ x
• 在位串的第m位标记1，然后令 x = x - W_m
• 跳过接下来的k个位置（这k位不能放1，否则会和刚标记的1间隔不足k个0），回到m-(k+1)的位置继续寻找下一个不大于当前x的权重
• 重复上述操作，直到x变为0
• 最后将位串整理为高位到低位的顺序（或根据需求调整）

实际示例：k=2，x=7 #

1. 权重数列中，最大的不大于7的是W₆=6，x变为7-6=1，位串第6位设为1
2. 跳过第5、4位（k=2，共跳过2位），从第3位开始查找：W₃=2>1，继续往下找到W₂=1≤1，x变为1-1=0，位串第2位设为1
3. 最终位串（高位到低位）为1001000，两个1之间有3个0，符合k=2的要求，且6+1=7，数值完全匹配

3. 关于唯一性的说明 #

和Zeckendorf表示的特性一致，这个广义斐波那契数列的递推规则保证了每个整数x都有唯一的符合规则的位串表示，不会出现多种分解方式。

注意：如果硬要用普通二进制的权重（2ⁿ）来生成位串，很多数根本无法找到符合规则的表示（比如k=2时x=3，普通二进制11不符合规则，101对应数值5>3，没有合适的位串），因此基于广义斐波那契数列的分解才是该问题的正确解法。

内容的提问来源于stack exchange，提问作者TTho Einthausend