封闭形式的直接解

  对于一些算法问题,求次数,种类数(答案就是一个具体的数值)这些,如果有封闭形式就可以直接解,就不用去编码大量的代码了。那我们看一个例子吧。

汉诺塔移动次数:

  我们以前是求汉诺塔的移动方式,那现在要求移动多少次,那该怎么做呢?我们可以先看汉诺塔的移动次数递归式 f(n) = 2f(n-1)+1 。那是怎么得出这个式子呢,我们可以先举例,假如只有一个盘子,那么只有一种移动方式,如果有两个盘子,那么就有三种移动方式,那如果有三个盘子,就有7种移动方式,于是我们可以得出一个等式  f(n) = 2n-1,那么这个等式就叫做封闭形式的解,那如果求n个盘子的移动次数,那直接代入这个式子就可以得出解了。就不用进行大量递归等操作了。

  那我们就可以总结一下了,封闭形式的解呢就是利用发现的规律,利用数学求和等知识,总结出一个关于n的算式 f(n),就可以直接利用这个算式算出f(n)。那这个就相当于高中时求数列的一个通项公式,有些规律不太好发现,我们也可以做些合理的假设,然后找些简单的数据进行验证。比如2n,cos,sin这些都可以做些假设。

  那比如上面求汉诺塔移动次数,那实际上就是求数列1,3,7......关于n的一个通项公式嘛,可以发现这既不是等差数列,也不是等比数列,那如果我们再加一那不就是等比数列了吗,那就可以直接利用高中所学的通项公式求出这个数列的通项了。有的通项公式可以利用前面数据得出后面的数据,有的直接就可以得出关于n的一个表达式,而有的就需要去猜测一些常见的表达式,然后再去补充验证。

  但是要注意,这里求f(n)一定不要是一个递推式,而是一个等式,就算只能得出递推式,也一定要想办法得出等式,这样才能直接利用这个等式解题,而免去了大量的代码工作。

原文地址:https://www.cnblogs.com/xiaoyh/p/10345363.html