递归算法实例应用(四)

简介: 递归算法实例应用(四):(POJ 4017)爬楼梯、(POJ 1664)放苹果

递归算法实例应用(四)

爬楼梯 (POJ 4017)

Description

树老师爬楼梯,他可以每次走1级或者2级,输入楼梯的级数,求不同的走法数
例如:楼梯一共有3级,他可以每次都走一级,或者第一次走一级,第二次走两级
也可以第一次走两级,第二次走一级,一共3种方法。

Input

输入包含若干行,每行包含一个正整数N,代表楼梯级数,1 <= N <= 30

Output

不同的走法数,每一行输入对应一行输出

Sample Input

5
8
10    
AI 代码解读

Sample Output

8
34
89
AI 代码解读




算法思想:

首先,假设n充分大时,从分析第一步应如何走开始,第一步可以分为两种情况,即上一层台阶和上两层台阶;接下来考虑第二步应该怎么走,第二步与第一步一样也是可以分为两种情况,但是剩余台阶数相比于第一步减少了一层或两层;第三步同理,直至某一步时,使得台阶正好走完。

从上面分析可知,随着每一步的走法确定之后,问题规模的台阶数就会变少一层或两层。所以该问题就是一个非常明显的用递归将问题规模分解为规模更小的子问题进行求解的问题。

那么该问题的递归公式可以表示为:

n级台阶的走法 = 先走1级后n-1阶台阶的走法 + 先走2级后n-2级台阶的走法

接下来考虑递归的终止条件,输入数据规模为1 <= N <= 30,通过递归公式的逐层递归推导,可以发现几种不同的终止情况

f(n)=0,n<0

f(n)=1,n=0

对于每一个n,要么由上一层的N-1而来,要么由N-2而来:

  • 当n<0时,说明上一层的N-1或N-2的走法不成立,所以应返回0,表明不可行,即N-1或N-2有0种走法。
  • 当n=1时,说明上一层N-1或N-2走法使得仅剩下一层台阶要走,所以应仅有一种走法,即一步一个台阶。

f(n)=1,n=1
f(n)=1,n=0

同理,对于每一个n,要么由上一层的N-1而来,要么由N-2而来:

  • 当n=0时,说明上一层的N-1或N-2的走法正好走完整个楼梯,所以该层已经不需要走了,故应返回0。
  • 当n=1时,说明上一层N-1或N-2走法使得仅剩下一层台阶要走,所以应仅有一种走法,即一步一个台阶。

f(n)=1,n=1
f(n)=2,n=2

同理,对于每一个n,要么由上一层的N-1而来,要么由N-2而来:

  • 当n=1时,说明上一层N-1或N-2走法使得仅剩下一层台阶要走,所以应仅有一种走法,即一步一个台阶。
  • 当n=2时,说明上一层N-1或N-2走法使得仅剩下两层台阶要走,所以应仅有两种走法,即一步一个台阶,或一步两个台阶。

以上便列举了三种不同的终止条件,读者选择一种作为函数终止条件即可。对于终止条件的分析,应从解的递归函数出发,分析其可能终止或异常的几种状态,罗列下终止状态后,判断是否涵盖在此递归函数中所有可能出现的终止或异常状态。因为算法应涵盖在题设的输入条件下,所有可能的解的情况,保证函数的健壮性。




代码逻辑:

本题的递归递归函数和终止条件均较为简单,所以代码逻辑不再赘述。




代码整合:

int main() {
    //爬楼梯
    int n;
    while (scanf("%d", &n)) {//读入每一个输入数据
        printf("%d\n", Stairs(n));//每读入一个数据就输出该问题规模下的解
    }
    return 0;
}

int Stairs(int n) {
    //终止条件
    if (n < 0)
        return 0;
    if (n == 0)
        return 1;

    //递归公式
    return Stairs(n - 1) + Stairs(n - 2);
}
AI 代码解读




放苹果 (POJ 1664)

Description

把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。

Input

第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。

Output

对输入的每组数据M和N,用一行输出相应的K。

Sample Input

1
7 3
AI 代码解读

Sample Output

8
AI 代码解读




算法思想:

由题设输入可分为两种情况,

  1. 盘子数n > 苹果数m,此时必定至少有n-m个盘子为空,所以问题规模此时就变为将n个苹果放在n个盘子里。
  2. 盘子数n ≤ 苹果数m,此时苹果有两种放法:

    • 有空盘放法

      • 若有一个空盘,则问题规模变为,将m个苹果放在n-1个盘子里
      • 若有两个空盘,则问题规模变为,将m个苹果放在n-2个盘子里
      • 若有..个空盘,则问题规模变为,将m个苹果放在...个盘子里
      • 若有n-1个空盘,则问题规模变为,将m个苹果放在1个盘子里
    • 无空盘放法

      • 把n个盘子各放一个苹果,再将剩余的m-n个苹果放在n个盘子里,问题规模再次缩减,此时剩余的m-n个苹果可以在n个盘子里随便放。
    • 所以,综上当盘子数≤苹果数时,放法个数为又空盘放法与无空盘放法之和。

从以上分析可知,该问题也是一个用递归将问题规模分解为规模更小的子问题进行求解的问题。

若用f(m,n)表示m个苹果放在n个盘子里的放法,那么该问题的递归公式可以表示为:

f(m,n)={f(m,m),n>mf(m,n1)+f(mn,n),nm

接下来考虑递归的终止条件,通过递归公式的逐层递归推导,可以发现几种不同的终止情况

f(m,n)={1,m=00,n=0

即,当盘子数为0时,没有放法可以盘子题设要求,故解为0,当苹果数为0时,只有每个盘子都不放苹果这一种解法。

而且苹果为0时的边界优先级较盘子为0时的边界判定更高!




代码逻辑:

本题的递归递归函数和终止条件均较为简单,所以代码逻辑不再赘述。




代码整合:

int main() {
    //放苹果
    int m, n, count;
    scanf("%d", &count);
    while (count--) {
        scanf("%d%d", &m, &n);
        printf("%d\n", SetApple(m, n));//每读入一组数据就输出该问题规模下的解
    }
    return 0;
}

int SetApple(int m, int n) {
    if (n > m) {
        return SetApple(m, m);//盘子数大于苹果数,简化问题规模
    }
    if (m == 0) {//苹果数为0,只有一种全不放的放法,到达递归终止点
        return 1;
    }
    if (n == 0) {//盘子数为0,此时无解,到达递归终止点
        return 0;
    }
    //当盘子数≤苹果数时,为有空盘子放法与无空盘子放法之和
    return SetApple(m, n - 1) + SetApple(m - n, n);
}
AI 代码解读


By Ss1Two 2023/01/17

Ss1Two
+关注
目录
打赏
0
0
0
0
92
分享
相关文章
监控局域网其他电脑:Go 语言迪杰斯特拉算法的高效应用
在信息化时代,监控局域网成为网络管理与安全防护的关键需求。本文探讨了迪杰斯特拉(Dijkstra)算法在监控局域网中的应用,通过计算最短路径优化数据传输和故障检测。文中提供了使用Go语言实现的代码例程,展示了如何高效地进行网络监控,确保局域网的稳定运行和数据安全。迪杰斯特拉算法能减少传输延迟和带宽消耗,及时发现并处理网络故障,适用于复杂网络环境下的管理和维护。
员工上网行为监控中的Go语言算法:布隆过滤器的应用
在信息化高速发展的时代,企业上网行为监管至关重要。布隆过滤器作为一种高效、节省空间的概率性数据结构,适用于大规模URL查询与匹配,是实现精准上网行为管理的理想选择。本文探讨了布隆过滤器的原理及其优缺点,并展示了如何使用Go语言实现该算法,以提升企业网络管理效率和安全性。尽管存在误报等局限性,但合理配置下,布隆过滤器为企业提供了经济有效的解决方案。
101 8
员工上网行为监控中的Go语言算法:布隆过滤器的应用
企业监控软件中 Go 语言哈希表算法的应用研究与分析
在数字化时代,企业监控软件对企业的稳定运营至关重要。哈希表(散列表)作为高效的数据结构,广泛应用于企业监控中,如设备状态管理、数据分类和缓存机制。Go 语言中的 map 实现了哈希表,能快速处理海量监控数据,确保实时准确反映设备状态,提升系统性能,助力企业实现智能化管理。
22 3
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
91 3
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
42 12
基于 Python 的布隆过滤器算法在内网行为管理中的应用探究
在复杂多变的网络环境中,内网行为管理至关重要。本文介绍布隆过滤器(Bloom Filter),一种高效的空间节省型概率数据结构,用于判断元素是否存在于集合中。通过多个哈希函数映射到位数组,实现快速访问控制。Python代码示例展示了如何构建和使用布隆过滤器,有效提升企业内网安全性和资源管理效率。
45 9
|
6天前
|
探讨组合加密算法在IM中的应用
本文深入分析了即时通信(IM)系统中所面临的各种安全问题,综合利用对称加密算法(DES算法)、公开密钥算法(RSA算法)和Hash算法(MD5)的优点,探讨组合加密算法在即时通信中的应用。
14 0
解锁机器学习的新维度:元学习的算法与应用探秘
元学习作为一个重要的研究领域,正逐渐在多个应用领域展现其潜力。通过理解和应用元学习的基本算法,研究者可以更好地解决在样本不足或任务快速变化的情况下的学习问题。随着研究的深入,元学习有望在人工智能的未来发展中发挥更大的作用。
探索企业文件管理软件:Python中的哈希表算法应用
企业文件管理软件依赖哈希表实现高效的数据管理和安全保障。哈希表通过键值映射,提供平均O(1)时间复杂度的快速访问,适用于海量文件处理。在Python中,字典类型基于哈希表实现,可用于管理文件元数据、缓存机制、版本控制及快速搜索等功能,极大提升工作效率和数据安全性。
80 0

热门文章

最新文章