首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >算法--递归--走台阶问题(2种递归+递归改循环)

算法--递归--走台阶问题(2种递归+递归改循环)

作者头像
Michael阿明
发布于 2021-02-20 02:34:58
发布于 2021-02-20 02:34:58
2.1K00
代码可运行
举报
运行总次数:0
代码可运行

递归:

一个问题可以分解成若干子问题,且求解思路一样,当到一定的情况下有终止条件,这样的问题可以用递归方法求解

注意事项:

  1. 递归调用深度太大,栈空间会耗尽溢出
  2. 注意避免调用中某些值的重复计算(见以下代码3)
  3. 递归,频繁调用函数,时间成本高(见以下代码1)
  4. 递归代码可以改成循环代码 (见以下代码2)

问题1

给你 n 个台阶,你的最大步幅是2步,可以一次走1步,也可以一次走2步,问有多少种走法?

思路
  1. 假设总共走法为 f (n) ,我现在走1步,后面还有 n-1 步(其走法为 f (n-1) )
  2. 我还可以,开始走2步,后面还有 n-2 步(其走法为 f(n-2) )
  3. 那么递推公式即: f (n) = f (n-1) + f (n-2)
  4. 终止条件:f (1) = 1; f (2) = 2;
1.递归代码(未考虑重复计算问题)

以下所有代码原来采用 size_t 溢出,改用 unsigned long

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <iostream>
using namespace std;
unsigned long cal(unsigned long n)
{
	if(n==1)
		return 1;
	else if(n==2)
		return 2;
	return cal(n-1)+cal(n-2);
}
int main()
{
    size_t n;
    cout << "请输入你要走的台阶数 n :" ;
    cin >> n;
	cout << "走台阶有 " << cal(n) << " 种方案。" << endl;
	return 0;
}

以上递归方法,在 n 比较小的时候运行时间较短 输入 n = 100 时,超过10s还没出结果,我就终止程序了。以下改用循环。

2.循环代码
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <iostream>
using namespace std;
int main()  //循环
{
    unsigned long n, step, nextStep = 2, nextnextStep = 1;
    cout << "请输入你要走的台阶数 n :" ;
    cin >> n;
    if(n > 0)
    {
        if(n == 1)
        {
            step = 1;
        } else if(n == 2)
        {
            step = 2;
        }
        else
        {
            for(int i = 2; i < n; ++i)
            {
                step = nextStep + nextnextStep;
                nextnextStep = nextStep;
                nextStep = step;
            }
        }
	    cout << "走台阶有 " << step << " 种方案。" << endl;
    }
	return 0;
}

输入 n = 100 时,改用循环,眨眼间出结果。

3.递归代码(避免重复计算问题)

代码 1 中的 f(n), 比如 n = 5 时

以下代码,屏蔽多次计算重复的值

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <iostream>
#include <iterator>
#include <map>
using namespace std;
unsigned long cal(unsigned long n, map<unsigned long, unsigned long>& n_fn_map)
{
    map<unsigned long,unsigned long>::iterator iter = n_fn_map.find(n);   //查找key n
    if(iter != n_fn_map.end())
    {
        return iter->second;    //如果找到了,就不必进行下面计算了,直接返回value
    }
	if(n==1)
    {
        n_fn_map.insert(pair<unsigned long, unsigned long>(1,1)); //把f(1)存入映射
	    return 1;
    }
	else if(n==2)
    {
        n_fn_map.insert(pair<unsigned long, unsigned long>(2,2)); //把f(2)存入映射
	    return 2;
    }
    else
    {
        size_t sum = cal(n-1,n_fn_map)+cal(n-2,n_fn_map);   //递归调用函数
        n_fn_map.insert(pair<unsigned long, unsigned long>(n,sum));       //求得的f(n)存入映射,供后面查询直接使用
        return sum;
    }
}
int main()  //递归(带避免重复计算fn的值功能)
{
    size_t n;
    cout << "请输入你要走的台阶数 n :" ;
    cin >> n;
    map<unsigned long, unsigned long> n_Fn;   //n,f(n)的 k,v 容器
	cout << "走台阶有 " << cal(n,n_Fn) << " 种方案。" << endl;
	return 0;
}

输入 n = 100,程序也是眨眼间出结果

测试运行时间

测试程序运行时间shell代码:https://blog.csdn.net/qq_21201267/article/details/81840299

问题2

给你 n 个台阶,你的最大步幅是2步,可以一次走1步,也可以一次走2步,先迈左脚,要求最后到达时是右脚,问有多少种走法?

解法1:模拟实际的行走,暴力搜索

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
/**
 1. @description: 39个台阶,一次走1步或2步,左脚出发,要求右脚到达
 2. @author: michael ming
 3. @date: 2019/4/6 18:17
 4. @modified by: 
 */
#include <iostream>
using namespace std;
void recursion(const unsigned long &targetStairs, unsigned long steps, unsigned long stairsWalkAway, unsigned long &ways)
{		//暴力搜索,n很大时效果不好
    if(stairsWalkAway > targetStairs)	//走过了,不做记录
        return;
    else if(stairsWalkAway == targetStairs && steps%2 == 0)	//正好走到,且步数为偶数(右脚到达)
    {
        ways++;	//记录一种方案可以
        return;
    }
    else	//没走到,继续递归
    {
        recursion(targetStairs, steps+1, stairsWalkAway+1, ways);
        recursion(targetStairs, steps+1, stairsWalkAway+2, ways);
    }
}
int main()
{
    unsigned long stairs = 0, steps = 0, stairsWalkAway = 0, ways = 0;
    cout << "请输入台阶个数:" << endl;
    cin >> stairs;
    recursion(stairs, steps, stairsWalkAway, ways);
    cout << "左脚出发,右脚到达的方案有:" << ways << " 种。" << endl;
    return 0;
}

解法2:递推公式和之前一样,结束条件变了

  1. n = 2 时,不论什么情况,大家都只有1种可能,使得右脚到达,f (2) = 1
  2. n = 1时,只剩1步了,如果已经走过了偶数步,那就是不可能右脚达到,f(1) = 0;如果已走过奇数步,那也只有1种可能,右脚到达,f(1) = 1
  3. 由于 f(1) 是变化的,所以不能用上面问题1的代码3那种方法存储 f(n) 的值,因为其都与 f(1) 相关。所以当 n 比较大的时候还没有找到好的解决办法。
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <iostream>
#include <map>
using namespace std;
unsigned long cal(size_t n,  size_t stepWalkAway)
{
    if(n==1)
    {
        if(stepWalkAway%2 == 0)
            return 0; //只剩1步了,如果走过了偶数步,那就是右脚达到,不可能了,0
        return 1;
    }
    else if(n==2)   //n = 2 时,不论什么情况,大家都只有1种可能,使得右脚到达
    {
        return 1;
    }
    else
    {
        return cal(n-1,stepWalkAway+1)+cal(n-2,stepWalkAway+1);   //递归调用函数
    }
}
int main()  
{
    size_t n, stepWalkAway = 0;
    cout << "请输入你要走的台阶数 n :" ;
    cin >> n;
    cout << "左脚开走,右脚走到有 " << cal(n,stepWalkAway) << " 种方案。" << endl;
    return 0;
}

解法3:动态规划,现在还不太明白 见他人博客: https://blog.csdn.net/qq_40269087/article/details/80236102 大概的思路是:自底向上

  • 用 left [ i ] 表示剩余 i 个台阶,左脚到达的可能方案, right [ i ] 表示右脚到达的方案
  • 边界条件: left [ 1 ] = 1; left [ 2 ] = 1; right [ 1 ] = 0; right [ 2 ] = 1
  • 现在还有3个台阶到达,相当于在前面到达的方案中,退一步(1个台阶或者2个台阶),那么我在剩余3个台阶时,左脚到达 left [ 3 ] = right [ 2 ] + right [ 1 ] ;(右脚可以到达的方案,后退一步就变成了左脚到达的方案)
  • 同理 right [ 3 ] = left [ 2 ] + left [ 1 ]
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <iostream>
using namespace std;
unsigned long dynamicProgram(size_t N)
{
    unsigned long left[N+1], right[N+1];
    left [1] = 1; left [2] = 1; right [1] = 0; right [2] = 1;
    for(size_t i = 3; i <= N; ++i)
    {
        left[i] = right[i-1] + right[i-2];
        right[i] = left[i-1] + left[i-2];
    }
    return right[N];    //题目要求返回右脚到达方案
}
int main()
{
    size_t N;
    cout << "请输入你要走的台阶数 n :" ;
    cin >> N;
    cout << "左脚开走,右脚走到有 " << dynamicProgram(N) << " 种方案。" << endl;
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/04/06 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
1 条评论
热度
最新
赞,学习了
赞,学习了
回复回复点赞举报
推荐阅读
Kubernetes 多卡GPU使用和分析
Kubernetes中通过device plugin将GPU作为一种resource来使用,因此需要先创建一个device plugin将GPU信息注册到Kubernetes中。NVIDIA官方提供了一个GPU device plugin,详情可见https://github.com/NVIDIA/k8s-device-plugin。
langwu 吴英文
2019/09/01
11.1K1
NVIDIA/k8s-device-plugin源码分析
Author: xidianwangtao@gmail.com k8s-device-plugin内部实现原理图 在Kubernetes如何通过Device Plugins来使用NVIDIA GP
Walton
2018/04/18
4.3K2
NVIDIA/k8s-device-plugin源码分析
HAMi源码解析——device-plugin
在介绍 HAMi 的 device-plugin 前,先了解一下 K8s 中的 Pod 是怎么使用 GPU 的。
DifficultWork
2025/06/25
3470
Kubelet Device Plugin 的工作机制
从Kubernetes 1.8开始,官方推荐使用Device Plugins方式来使用GPU、FPGA、NIC、InfiniBand等高性能硬件。
用户7020774
2020/03/02
5.8K0
Kubernetes如何通过Devi
Device Plugins Device Pulgins在Kubernetes 1.10中是beta特性,开始于Kubernetes 1.8,用来给第三方设备厂商通过插件化的方式将设备资源对接到Kubernetes,给容器提供Extended Resources。 通过Device Plugins方式,用户不需要改Kubernetes的代码,由第三方设备厂商开发插件,实现Kubernetes Device Plugins的相关接口即可。 目前关注度比较高的Device Plugins实现有: Nvidia
Walton
2018/04/16
1.8K0
Kubernetes如何通过Devi
Kubelet Deivce Manager源码分析
本文基于Kubernetes v1.10的代码,对Kubelet Device Manager的实现进行了代码走读分析,方便对kubelet与device plugin的交互有更深入的理解。另外,分别对kubelet的Register服务、kubelet调用device plugin的Allocate接口等做了分析,尤其要了解kubelet device plugins的checkpoint机制。
Walton
2018/05/03
2.2K0
Kubelet Deivce Manager源码分析
深入 kubernetes API 的源码实现
很多同学应该像我一样,第一次打开 Github 上面 kubernetes 项目源码的时候就被各种仓库搞晕了,kuberentes 组织下有很多个仓库,包括 kubernetes、client-go、api、apimachinery 等,该从哪儿仓库看起?kubernetes 仓库应该是 kubernetes 项目的核心仓库,它包含 kubernetes 控制平面核心组件的源码;client-go 从名字也不难看出是操作 kubernetes API 的 go 语言客户端;api 与 apimachinery 应该是与 kubernetes API 相关的仓库,但它们俩为啥要分成两个不同的仓库?这些代码仓库之间如何交互?apimachinery 仓库中还有 api、apis 两个包,里面定义了各种复杂的接口与实现,清楚这些复杂接口对于扩展 kubernetes API 大有裨益。所以,这篇文章就重点关注 api 与 apimachinery 这两个仓库。
米开朗基杨
2021/04/02
1.2K0
使用 Elastic GPU 管理 Kubernetes GPU 资源
徐蓓,腾讯云容器技术专家,腾讯云异构计算容器负责人,多年云计算一线架构设计与研发经验,长期深耕 Kubernetes、在离线混部与 GPU 容器化领域,Kubernetes KEP Memory QoS 作者,Kubernetes 积极贡献者。 当前存在问题 GPU 具备大量核心和高速内存,擅长并行计算,非常适合训练和运行机器学习模型。由于近几年 AI 技术愈发成熟,落地场景越来越多,对 GPU 的需求呈井喷趋势。而在资源管理调度平台上,Kubernetes 已成为事实标准。所以很多客户选择在 Kubern
腾讯云原生
2022/04/21
3.5K0
使用 Elastic GPU 管理 Kubernetes GPU 资源
Kubrenetes 设备插件详解
Kubernetes 提供了一个 设备插件框架, 你可以用它来将系统硬件资源发布到 Kubelet。
thierryzhou
2022/12/01
1.1K0
kubernetes GPU管理与Device Plugin机制
Kubernetes 在 Pod 的 API 对象里,并没有为 GPU 专门设置一个资源类型字段,而是使用了一种叫作 Extended Resource(ER)的特殊字段来负责传递 GPU 的信息。
rxg456
2025/03/26
1350
kubernetes GPU管理与Device Plugin机制
深度剖析Kubernetes动态准入控制之Admission Webhooks
Author: xidianwangtao@gmail.com Admission Controll的最佳配置 这部分内容,请参考我的上一篇博文深度剖析Kubernetes动态准入控制之Initializers External Admission Webhooks工作机制 External Admission Webhooks有什么用 我们什么时候需要用External Admission Webhooks呢?当集群管理员需要强制对某些请求或者所有请求都进行校验或者修改的时候,就可以考虑使用Vali
Walton
2018/04/16
3.2K0
如何为 Kubernetes 定制特性
Kubernetes 是非常复杂的集群编排系统,然而哪怕包含丰富的功能和特性,因为容器的调度和管理本身就有较高的复杂性,所以它无法满足所有场景下的需求。虽然 Kubernetes 能够解决大多数场景中的常见问题,但是为了实现更加灵活的策略,我们需要使用 Kubernetes 提供的扩展能力实现特定目的。
我是阳明
2021/04/26
6030
如何为 Kubernetes 定制特性
基于 Kubernetes 的 GPU 类型调度实现
3 月 27 日,ACM 宣布深度学习的三位缔造者——Yoshua Bengio、Yann LeCun 及 Geoffrey Hinton 获得了 2018 年度的图灵奖。与学术界相对应的,在工业界,人工智能大潮也正汹涌奔来。除了冲击人们的衣食住行医,人工智能也将成为企业转型的颠覆性力量,是企业抓住下一轮创新发展的重要机遇。
kubernetes中文社区
2019/06/24
1.6K0
基于 Kubernetes 的 GPU 类型调度实现
原 荐 Kubernetes HPA Con
Author: xidianwangtao@gmail.com 更多关于kubernetes的深入文章,请看我csdn或者oschina的博客主页。 关于kubernetes HPA Controller的工作原理,请参考我这篇博文。 源码目录结构分析 HorizontalPodAutoscaler(以下简称HPA)的主要代码如下,主要涉及的文件不多。 cmd/kube-controller-manager/app/autoscaling.go // HPA Controller的启动代码
Walton
2018/04/13
2K0
原                    荐                                                            Kubernetes HPA Con
如何在Kubernetes集群中利用GPU进行AI训练
Author: xidianwangtao@gmail.com 注意事项 截止Kubernetes 1.8版本: 对GPU的支持还只是实验阶段,仍停留在Alpha特性,意味着还不建议在生产环境中使用Kubernetes管理和调度GPU资源。 只支持NVIDIA GPUs。 Pods不能共用同一块GPU,即使同一个Pod内不同的Containers之间也不能共用同一块GPU。这是Kubernetes目前对GPU支持最难以接受的一点。因为一块PU价格是很昂贵的,一个训练进程通常是无法完全利用满一块GPU的
Walton
2018/04/16
3K0
如何在Kubernetes集群中利用GPU进行AI训练
Kubernetes对象深入学习之三:对象属性
程序员欣宸
2023/07/24
3160
Kubernetes对象深入学习之三:对象属性
在 Kubernetes 实施混沌工程—— Chaos Mesh® 原理分析与控制面开发
Chaos Mesh® 是由 TiDB 背后的 PingCAP 公司开发,运行在 Kubernetes 上的混沌工程(Chaos Engineering)系统。简而言之,Chaos Mesh® 通过运行在 K8s 集群中的“特权”容器,依据 CRD 资源中的测试场景,在集群中制造浑沌(模拟故障)1。
PingCAP
2021/10/27
1.5K0
彻底理解kubernetes CNI
CNI接口很简单,特别一些新手一定有克服恐惧心里,和我一探究竟,本文结合原理与实践,认真读下来一定会对原理理解非常透彻。
sealyun
2019/08/05
1.9K0
GPU 资源调度:k8s-device-plugin 知多少 ?
Hello folks,我是 Luga,今天我们来聊一下人工智能应用场景 - 基于 k8s-device-plugin 机制所实现的 GPU 资源动态调度。
Luga Lee
2024/12/09
6730
GPU 资源调度:k8s-device-plugin 知多少 ?
Kubernetes 新玩法:在 YAML 中编程
那么如何做性能测试?要么是通过编码的方式完成,写一堆脚本,用完即弃;要么是基于平台,在平台定义的流程中进行。对于后者,通常由于目标场景的复杂性,如部署特定的 workload、观测特定的性能项、网络访问问题等,往往导致性能测试平台要以高成本才能满足不断变化的开发场景的需求。
我是阳明
2020/09/24
9990
Kubernetes 新玩法:在 YAML 中编程
相关推荐
Kubernetes 多卡GPU使用和分析
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档