没有合适的资源?快使用搜索试试~ 我知道了~
首页C++递推算法详解:动态规划与数字三角形求解
本资源是一份关于基础算法的C++教程,主要聚焦于递推算法这一章节。递推算法在数学和计算机科学中起着关键作用,尤其在数值计算中被广泛应用。递推法的核心思想是通过找出问题解决过程中各步骤之间的数量关系,通常表现为递推公式,从而从已知结果反推出初始条件,这种方法在解决涉及序列问题时尤为有效。 递推算法的特点在于,它避免了直接寻找通项公式,而是将复杂问题分解成一系列简单的重复计算。例如,递推算法在数字三角形问题中表现得淋漓尽致。题目要求编写一个程序,计算从三角形顶部到底部的路径中,使得路径上数字之和最大化。参与者需要理解,从顶层到达每一层,最优的选择是沿着路径上具有最大数字的方向前进。这个过程可以通过定义状态变量a[i][j]来表示从位置i,j到顶点的最大和,然后通过递推公式a[i][j] = max{a[i][j]+a[i+1][j], a[i][j]+a[i+1][j+1]}来更新这些状态。 该资源提供了一个C++实现的示例程序,通过三层嵌套循环结构,首先读入数字三角形的值,然后从底部向上进行递推计算,最终得到从顶层到底层的路径中最大和。这个程序展示了递推算法如何通过迭代的方式解决问题,并且通过递归调用自身来计算不同位置的最大和。 本资源对于学习递推算法及其在实际问题中的应用非常有价值,不仅介绍了递推算法的基本概念,还提供了实际编程案例,有助于理解递推与动态规划(DP)的关系,以及如何将其应用于解决信奥CSP-J和NOIP等竞赛中的问题。对于想要提升算法思维和编程能力的学生和工程师来说,这是一份不可多得的学习资料。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/78030829/bg10.jpg)
第几个月
1 2 3 4 5 6
r1
R1 R1 R1 R1 R1
r2 R2 R2 R2
r3 R3 R3
r4 R4
r5 R5
r6
r7
r8
![](https://csdnimg.cn/release/download_crawler_static/78030829/bg11.jpg)
【例3】 有 2xn的一个长方形方格,用一个1*2的骨牌铺满方格。
编写一个程序,试对给出的任意一个n(n>0), 输出铺法总数。
【算法分析】
(1)面对上述问题,如果思考方法不恰当,要想获得问题的解答
是相当困难的。可以用递推方法归纳出问题解的一般规律。
(2)当n=1时,只能是1种铺法,铺法总数有示为x
1
=1。
(3)当n=2时:骨牌可以两个并列竖排,也可以并列横排,再无
其他方法,如下左图所示,因此,铺法总数表示为x
2
=2;
![](https://csdnimg.cn/release/download_crawler_static/78030829/bg12.jpg)
(4)当n=3时:骨牌可以全部竖排,也可以认为在方格中已
经有一个竖排骨牌,则需要在方格中排列两个横排骨牌(无重
复方法),若已经在方格中排列两个横排骨牌,则必须在方格
中排列一个竖排骨牌。
如上右图,再无其他排列方法,因此铺法总数表示为x
3
=3。
由此可以看出,当n=3时的排列骨牌的方法数是n=1和n=2排
列方法数的和。
9273:PKU2506Tiling
http://noi.openjudge.cn/ch0202/9273/
![](https://csdnimg.cn/release/download_crawler_static/78030829/bg13.jpg)
(5)推出一般规律:对一般的n,要求x
n
可以这样来考虑,若第一个骨
牌是竖排列放置,剩下有n-1个骨牌需要排列,这时排列方法数为x
n-1
;若
第一个骨牌是横排列,整个方格至少有2个骨牌是横排列(1*2骨牌),因
此剩下n-2个骨牌需要排列,这是骨牌排列方法数为x
n-2
。从第一骨牌排列
方法考虑,只有这两种可能,所以有:
x
n
=x
n-1
+x
n-2
(n>2)
x
1
=1
x
2
=2
x
n
=x
n-1
+x
n-2
就是问题求解的递推公式。
任给n都可以从中获得解答。例如n=5,
x
3
=x
2
+x
1
=3
x
4
=x
3
+x
2
=5
x
5
=x
4
+x
3
=8
![](https://csdnimg.cn/release/download_crawler_static/78030829/bg14.jpg)
下面是输入n,输出x
1
~x
n
的c++程序:
#include<iostream>
using namespace std;
int main()
{
int n,i,j,a[101];
cout<<"input n:"; //输入骨牌数
cin>>n;
a[1]=1;a[2]=2;
cout<<"x[1]="<<a[1]<<endl;
cout<<"x[2]="<<a[2]<<endl;
for (i=3;i<=n;i++) //递推过程
{
a[i]=a[i-1]+a[i-2];
cout<<"x["<<i<<"]="<<a[i]<<endl;
}
}
剩余102页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/f592ccf136744be2b966ff59bc7b59f6_dllglvzhenfeng.jpg!1)
![](https://csdnimg.cn/release/wenkucmsfe/public/img/user-vip.1c89f3c5.png)
dllglvzhenfeng
- 粉丝: 1w+
- 资源: 1869
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测:静态代码分析与数据流方法
- 青苔数据CEO程永:技术生态与阿里云开放创新
- 制造业转型: HyperX引领企业上云策略
- 赵维五分享:航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛:AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器:设计与实现
- 猩便利工程师仲小玉:Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享:高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会:阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)