从一个问题开始
假如有 7 个台阶,每次你可以跨 1 个台阶或者 2 个台阶,那么走这 n 个台阶有多少种走法?你可以 2、2、2、1 这样子上去,也可以 1、2、1、1、2 这样子上去,也可以 1、2、1、1、2 这样子上去,总之走法有很多,那总共究竟有多少种走法呢?
最近在学习极客时间里的王争的《数据结构与算法之美》,以上是其中举的一道例题。
穷举
我一开始是一头雾水的,不知从何下手。王争老师给出了思路,可以根据第一步的走法把所有的走法分为两类,第一类是第一步走了1 个台阶,另一类是第一步走了 2 个台阶。然后对于后面的第一步走法,都可以这样分类。
我先暴力穷举,用这种思路画了一下,用圆形代表一次走一个台阶,用矩形代表一次走两个台阶:
如果一共只有 1 个台阶
只有一种走法,对应的图中要从根节点到叶子节点只有一条路径。
如果一共是 2 个台阶
一共有两种走法,对应的图中要从根节点到所有的叶子节点,有两条路径。
如果一共是 3 个台阶
如果一共是 4 个台阶
画到这里,我已经看出了规律,对于 4 个台阶的走法树形图,是由 3 个台阶的走法树和 2 个台阶的走法树分别做为其左子树和右子树拼成的,左子树一共有 3 条路径,而右子树一共有 2 条路径,形成的新的树,就是左右子树路径之和,即 5 条路径,也就是一共有 5 种走法。
如果一共是 5 个台阶
一共 8 种走法,对应 8 条路径,也即 8 个叶子节点。
如果一共是 6 个台阶
一共 13 种走法,对应 13 个叶子节点。
如果一共是 7 个台阶
不用想就是 21 种走法,也即 21 个叶子节点。
递归
要写代码来计算的话,可以先假设问题已经得到了解决,由于并不知道真正的答案,可以用一个代号来表示。由于不同的台阶数有不同的结果,所以这个代号还得有一个编号。对于七级台阶,不妨假设有f(7)种走法。在上面的穷举中,已经知道了,对于n级台阶,都可以在第一步时,分成是一步走一个台阶还是一步走两个台阶这两种情况。对于7级台阶,第一步如果是走一个台阶,那么还剩下6级台阶,即f(6)种走法。如果第一步走了两个台阶,那么还剩下5级台阶,即f(5)种走法。
总之,f(7)=f(6)+f(5)。
终止条件
以上,显然,f(n)=f(n-1)+f(n-2)。在穷举中我们知道了,f(1)=1,f(2)=2。
最张递推式
f(n) = f(n-1) + f(n-2), n > 2
f(2)=2
f(1)=1
你可能早就看得不耐烦了,这不就是斐波那契数列吗!我反应慢,我是到了这一步才突然意识到,咦,这个问题的解决方法怎么就和斐波那契数列产生了关系呢?突然感觉到一股神奇的力量!不仅如此,仔细回看穷举图,还发现有分形呢!
最终代码
既然是斐波那契数列,那这个代码我可太会写了!
javascript function f(n) { if (n === 1 || n === 2) { return n; }
return f(n-1) + f(n-2); }
再一次怀疑人生,因为我自认为对斐波那契数列是非常熟悉的,但却一开始不会这道题!这种感觉就像,遇见一道门,被锁上了。而钥匙明明就在手中,却仍然不知道怎么打开门。
优化
我对斐波那契数列真是太熟悉了,并且非常喜欢用它来做为面试题。在聊正题前,总会先对面试者说,用你最熟悉的语言写一个计算斐波那契数列第n项的函数吧。我竟然经常碰到面试者没听过这个数列,于是就耐心地解释,这个数列有这样的特征,第1项是1、第2项是2、从第3项开始,其值都是前两项之和,比如第3项是3,第4项是5,第5项是8,如此类推。
如果有人恰好写出来了,并且用的是我最喜欢的 JavaScript,我就会再刁难一下:这个是对的,但是效率不高,存在重复计算,你能再优化一下吗?
我心中的答案当然是用缓存。一个示例如下:
javascript const cache = {};
function f(n) { if(cache[n]) { console.log(缓存命中: , n); return cache[n]; }
console.log(计算 n = , n);
if (n === 1 || n === 2) { console.log(计算 n = , n, . f(n) = , n);
cache[n] = n;
return n;
}
const result = f(n - 1) + f(n - 2);
console.log(计算 n = , n, . f(n) = , result);
cache[n] = result; return result; }
console.log(f(7));
我最喜欢的缓存写法是利用记忆函数 memoize,自己实现这个 memoize 或者是使用一些库中提供的,都可以。
我曾经自己实现过一个,详见《(闭包的妙用 —— memoize - Jeff Tian的文章 - 知乎)[https://zhuanlan.zhihu.com/p/353365352] 》。
但是如果要让这种 memoize 函数发挥效果,就需要改写一下递归函数的写法。也就是说,如果不对递归函数本身的写法进行改变,直接套用 memoize 就会失效。不信你可以试试,但应该怎么改写呢?大致思路是将函数自己做为一个参数传进去,在递归调用时,不要直接调用自己,而是调用这个参数函数,不过还没有验证过,欢迎热心网友给出一些实现。
超纲实现
通过使用缓存,可以将时间复杂度从O(2^n)降低到 O(n)。但是空间复杂度增加了,有的面试者通过迭代循环的方式,也能实现O(n)时间复杂度,同时不增加空间复杂度。但是有一次一个面试者,直接写出了如下实现:
javascript function f(n) { const phi = (1 + Math.sqrt(5)) / 2;
return Math.round( ( Math.pow(phi, n+1) - Math.pow(-phi, -(n+1)) ) / Math.sqrt(5) ); }
console.log(f(7));
我看了之后惊呆了,这是啥?心想:你不会就不会,可以直说啊,瞎蒙什么呀!于是笑笑对他说:我觉得我们没有必要聊下去了。面试者看到我懵逼的神情,也摇了摇头笑着叹了口气,说同意,没必要聊下去了。
这件事过去了很多年,我最近开始学习《离散数学》了,因为不想再做一个野生的程序员,所以开始补课了。学到一种叫做 Closed Formula 封闭公式的东西,突然听到老师提到了斐波那契数列的封闭公式,我突然觉得似曾相识!这不就是多年前那个面试者写的实现吗?我赶紧重新写了一下运行试试看:
答案完全正确,并且实现了 O(1) 的时间和空间复杂度!
我脸红了……
故事点估算方法
我脸红了,但是很快我释然了:我只是一个一线搬砖的程序员而已,哪里会这些高深的东西!而且再说了,什么斐波那契数列,平时搬砖根本用不到呀!
没想到,很快就用到了,而且每两周都要和它打交道一到两次,那就是故事点估算环节。
以前,我抱怨过,认为敏捷开发方法被实际落地中被歪曲了,还发了篇报怨文章《程序员,困在敏捷里 - Jeff Tian的文章 - 知乎 》。但是后来进入了一个还算正确使用敏捷方法的团队,每两周会固定一个时间开待办事项梳理会议,还会看情况不定时增加一个额外的梳理会议。在会议上,有一个环节,就是对故事进行复杂度估计。这个估算在不同的团队中有不同的做法,这里分享一下我们的做法。
我们采用的正是斐波那契数列来进行估算的,梳理会议上的流程大致是这样,产品经理打开一个故事详情,大家先看,看完后不许提问,大家先给出自己的估算结果,这个结果是斐波那契数列中的一个数字。
如果一致,则开始看下一个用户故事详情。如果不一致, 就开始讨论和提问,直到大家达成一致。
尽管有很多工具,特别是我们使用了 JIRA ,它自带了一个估算工具,但是我们采用了https://hatjitsu.toolforge.org/,它足够简单,使用方便。我们估算的原则大致如下:
故事的复杂度既包含了固有的复杂度,也包含了一些不确定性。如果不确定性很高,那么复杂度也会很高。因为不确定性高的话,就会涉及到额外的调研、探索和其他的消除不确定性的工作。
0:没有复杂性
这个用户故事微不足道,不需要工作量。要么是已经实现了,或者是太简单以至于用不着讨论。
1:非常低的复杂性
这个用户故事非常简单直接,可以很快完成,只需要最小的工作量,并且不存在完成它的风险。
2:低复杂度
这个故事很简单,但是比1所需要的工作量更多。可能会涉及一些小的配置工作,或者需要处理一些比较容易的小改动。
3:普通复杂度
这个用户故事有一定的复杂性,但仍然是在可控的范围内。要完成它不会碰到太多麻烦,尽管会涉及到多个步骤,或者需要一些基本的问题解决能力。
5:可观的复杂性
这个故事的复杂必已经开始引入注意了,它需要规划,并且需要多个步骤来完成它。并且可能存在一些不确定性以及和其他的任务存在相互依赖。
8:高复杂度
这个故事比较复杂,需要非常大的工作量。甚至可能需要多个团队成员相互协作来完成。有很大的概率会碰到问题,需要反复复查和修改。
13:非常高的复杂性
这个故事非常复杂 ,需要特别多的时间资源来完成。涉及到高风险、多依赖以及很大程度上的不确定性。如果故事复杂度达到这个点数,就需要考虑分解成更小的更可控的多个故事了。
21:极端复杂
这个故事极端复杂,几乎快要过于复杂了。它涉及多个团队、需要大量的计划,实现时大概率会碰到严重的问题。对于这种复杂度,几乎总是需要分解成更多的更小的更可控的故事。
34:超纲复杂度(爆表复杂度)
这个故事如此复杂以至于不可能给出一个合理的复杂度估计。它需要被分解成一些更小的任务,并且在分解之后再次评估。
以几个小问题结束
不知道你们平时有用到斐波那契数列吗?是在什么场景呢?你们又是怎么实践敏捷开发的?以及如何对用户故事进行估算的呢?
附
穷举部分用的文本绘图源码:
plain graph TD; A{0} -- 第一步 --> A1((1)) A -- 第一步 --> A2[2]
A1 -- 第二步 --> A11((1))
A1 -- 第二步 --> A12[2]
A2 -- 第二步 --> A21((1))
A2 -- 第二步 --> A22[2]
A11 -- 第三步 --> A111((1))
A11 -- 第三步 --> A112[2]
A12 -- 第三步 --> A121((1))
A12 -- 第三步 --> A122[2]
A21 -- 第三步 --> A211((1))
A21 -- 第三步 --> A212[2]
A212 -- 第四步 --> A2121((1))
A22 -- 第三步 --> A221((1))
A221 -- 第四步 --> A2211((1))
A111 -- 第四步 --> A1111((1))
A111 -- 第四步 --> A1112[2]
A112 -- 第四步 --> A1121((1))
A121 -- 第四步 --> A1211((1))
A211 -- 第四步 --> A2111((1))
A2111 -- 第五步 --> A21111((1))
A1111 -- 第五步 --> A11111((1))
A22 -- 第三步 --> A222[2]
A211 -- 第四步 --> A2112[2]
A122 -- 第四步 --> A1221((1))
A121 -- 第四步 --> A1212[2]
A1211 -- 第五步 --> A12111((1))
A1121 -- 第五步 --> A11211((1))
A1112 -- 第五步 --> A11121((1))
A11111 -- 第六步 --> A111111((1))
A1111 -- 第五步 --> A11112[2]
A112 -- 第四步 --> A1122[2]
A111111 -- 第七步 --> A1111111((1))
A11112 -- 第六步 --> A111121((1))
A11121 -- 第六步 --> A111211((1))
A1122 -- 第五步 --> A11221((1))
A11211 -- 第六步 --> A112111((1))
A1121 -- 第五步 --> A11212[2]
A1112 -- 第五步 --> A11122[2]
A12111 -- 第六步 --> A121111((1))
A1211 -- 第五步 --> A12112[2]
A1212 -- 第五步 --> A12121((1))
A1221 -- 第五步 --> A12211((1))
A122 -- 第四步 --> A1222[2]
A21111 -- 第六步 --> A211111((1))
A2111 -- 第五步 --> A21112[2]
A2112 -- 第五步 --> A21121((1))
A2121 -- 第五步 --> A21211((1))
A212 -- 第四步 --> A2122[2]
A2211 -- 第五步 --> A22111((1))
A221 -- 第四步 --> A2212[2]
A222 -- 第四步 --> A2221((1))
A11111 -- 第六步 --> A111112[2]