封闭形式的直接解
2023-03-14 09:45:10 时间
对于一些算法问题,求次数,种类数(答案就是一个具体的数值)这些,如果有封闭形式就可以直接解,就不用去编码大量的代码了。那我们看一个例子吧。
汉诺塔移动次数:
我们以前是求汉诺塔的移动方式,那现在要求移动多少次,那该怎么做呢?我们可以先看汉诺塔的移动次数递归式 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)一定不要是一个递推式,而是一个等式,就算只能得出递推式,也一定要想办法得出等式,这样才能直接利用这个等式解题,而免去了大量的代码工作。
相关文章
- 谷歌 Chrome 浏览器 107“内置搜索”和恐龙小游戏适配支持苹果 iOS 16 锁屏小组件
- 微软 Windows 11 21H2 Build 22000.1165(KB5018483)预览版发布(附更新内容大全)
- 微软 Windows 11 22H2 Build 22621.755(KB5018496)预览版发布(附更新内容大全)
- 开发人员不喜欢低代码和无代码的八个理由
- git 协同工作,怎样重命名、删除分支和查找分支的创建者呢?
- 如何删除远程 git 分支
- 谷歌 Chrome 浏览器 107 正式版发布,新增支持 HEVC / H.265 解码
- Go 语言怎么使用对称加密?
- 三方库移植之NAPI开发(三)通过IDE开发NAPI工程
- OpenHarmony设备开发(八)- 遥控小车
- 在Linux命令行中查找空目录
- Linux环境下补丁管理的挑战与最佳实践
- 在 Ubuntu 中配置 SSH 的完整指南
- React新文档:不要滥用Effect哦
- Sentinel与OpenFeign服务熔断那些事
- 前端开发报告:TypeScript 或将超越 Javascript 成为新的前端标准
- 如何在Linux中使用xargs命令
- Kubuntu 22.10 的新变化
- 面试官:有了解过线程组和线程优先级吗?
- 苹果 macOS 13 Ventura 正式版发布:台前调度、连续互通相机等来了