1.4 剪枝

1.4剪枝

算法笔试模拟题精解之“斐波那契字符数”

贡献者 | 洪浩原

简介：本题应充分利用斐波那契数列的性质，自顶向下对问题逐步剪枝，定位需

要判断的数字位置。

题目描述

题目等级：中等

知识点：递归、剪枝

查看题目：斐波那契字符数

Tom 发现了一种神奇的字符串 - 斐波那契字符串 , 定义 f[1]=0,f[2]=1, 对于所有

的 i>2 都有 f[i]=f[i-2]+f[i-1]，其中“+”代表拼接，比如 01+10=0110，现在对于

字符串 f[n]，请判断 f[n] 的第 k 项是 0，还是 1。

输入两个数字 n 和 k(n<=300,k<=1000000000)。

输出 f[n] 的第 k 位，如果 k 大于 f[n] 的位数，则输出 -1。

本题在答题过程中很多小伙伴反应会出现超内存的现象，导致 JVM 崩溃。但其

实这道题目是不可以暴力解题的，首先来看一下一般思路解法。

方法 1：直接法（超时并超出内存限制）

这是一道找规律的题目，最简单的想法可以是自底向上地构建出从第一个字符串

f[1] 直到最后的 f[n]，然后查看 f[n] 的第 k 项是 0 还是 1。

由于斐波那契数递增速度非常快，当 n 较大时，这种暴力拼接法无法完成。

下面介绍一种优化的算法。

方法 2：找规律（提交通过）

本题应充分利用斐波那契数列的性质，自顶向下对问题逐步剪枝，定位需要判断

的数字位置。

比如，对输入 n=19, k=98：

1. 先算出 n=19 对应的字符串长度 len，也就是斐波那契数列的第 19 项。考

虑到 k 是 int 类型，故可以先算出 n=1~47 对应的斐波那契数组成的数组

（n=47 时，斐波那契数大于 2^31-1，无需再提前计算更多的斐波那契数），

然后直接在计算好的斐波那契数组中取出第 19 项。

1. 找到 n-2=17，n-1=18 对应的斐波那契字符串长度（也就是第 17/18 个斐

波那契数）len1，len2。同样也是在提前计算好的斐波那契数组中找到。

1. 对于 k=98，如果 k>len1，说明要找的数字在 n=18 对应的斐波那契字符串

中，也就是 n=19 对应的斐波那契字符串的后半部分；如果 k<=len1，说明

要找的数字在 n=17 对应的斐波那契字符串中，也就是 n=19 对应的斐波那

契字符串的前半部分。

1. 根据判断结果，将 n 赋值为 n-2 或 n-1，同时将 k 赋值为 k 或 (k-len1)，

完成剪枝。回到第 1 步，递归向下搜索。直到 n=1 或者 2，这时 k 也变为

1，定位完成，结束递归，直接返回结果。

进一步优化：

当输入的 n > 47 时，斐波那契字符串的长度超出了 int 型变量 k 的表示范围。需

要提前进行推断剪枝。你能根据 k 的 int 表示范围（小于等于 2^31-1）这一特性，对

n 较大的那些用例进行优化么？

方法 3：递归

这个问题可以使用递归的方法来求解。

题目中给出了字符串拼接的规律：f[i]=f[i-2]+f[i-1]。可以看出对于第 i 个字符串，

它的前半部分属于第 i-2 个字符串，后半部分属于第 i-1 个字符串。

这样，当给定具体的 n 和 k 时，我们可以首先判断 k 位于第 n 个字符串的前半

部分还是后半部分，然后递归的把 k 传递给第 n-2 或 n-1 个字符串。

计算过程：

1. 为了判断属于前半部分还是后半部分，需要计算每一个字符串的长度。

一个 len 数组。每个位置为对应字符串的长度。

len[1] = len[2] = 1;

len[i] = len[i-2]+len[i-1];

1. 如果 k > len[n]，则输出 -1。
2. 设置递归函数 int find(int i, int k); 这个函数返回第 i 个字符串中 k 个位置的

字符

1. 判断 k 在前半部分还是后半部分。
2. K <= len[i-2] 前半部分，调用 find(i-2, k)
3. K > len[i-2] 后半部分，调用 find(i-1, k-len[i-2])

上面的计算在第一步时会遇到问题，当 n 大于几十的时候，len 就会超出 int 的

范围。

对这个问题的解决基于对递归过程的观察，第 4 步 a）中 k 始终是不变的，i 的

奇偶性也保持不变。所以在计算第 1 步 len 时可以提前停止，当发现 len[i]>=k 且 i

与 n 的奇偶性相同时。第 4 步中的递归起始也可以使用第 i 个字符串开始，而不是第

n 个。

时间复杂度 O(2*n)

空间复杂度 O(n)

是不是感觉有思路了，立刻点击这里开启答题！

算法题目的解法并不唯一，这里介绍部分解题思路给大家，希望可以给大家启发 ~