2023-04-26
班门弄斧
00
请注意,本文编写于 594 天前,最后修改于 337 天前,其中某些信息可能已经过时。

目录

CSDN每日一练题目
做答过程
测试示例:
1、普通递归法(错误)
代码
结果
2、递归优化(错误)
代码
结果
3、使用排列组合公式、并优化
基本排列组合
结果
优化公式计算逻辑
总结

本文是从我的CSDN搬运过来的:共n阶台阶,每次上1或2阶,有几种上法?

CSDN每日一练题目

  • 2022-08-02日CSDN每日一练中等难度题目。
  • 题目要求 1 <= N <= 50,当输入N后在一秒钟之内计算出结果。
  • 题目类型:递归、循环

在这里插入图片描述

做答过程

测试示例:

  • n = 3 , 正确结果为 3
  • n = 4 , 正确结果为 5
  • n = 5 , 正确结果为 8
  • n = 6 , 正确结果为13

1、普通递归法(错误)

  • 刚开始思路不是很明确,就随便写写,写出个递归,但是当N较大时,计算效率极低。

代码

java
class Main { public static void main(String[] args) { System.out.println(System.currentTimeMillis()); int n = 50; int result = solution(n); System.out.println(result); System.out.println(System.currentTimeMillis()); } public static int solution(int n) { int result = 0; if (n >= 1 && n <= 2){ result = n; } else { result = solution(n -1) + solution(n - 2); } return result; } }

结果

  • 因为计算时间较长,官方没有说明计算结果是否正确,只是说明超时。

2、递归优化(错误)

  • 第一种递归效率很低,所以想着优化递归。
  • 优化思路:因为只能走1级或2级台阶,那么可以先确定走1级和2级总的搭配种类,举例说明:如共5级台阶,那么可以先确定1和2的搭配方式有:5次1级、3次1级和1次2级、1次1级和2次2级。先不管第几步走1级或2级,基本的搭配就这三种,先确定这三种搭配,再对每种搭配进行排序即可。

代码

java
class Main { public static void main(String[] args) { System.out.println(System.currentTimeMillis()); int n = 20; int result = solution(n); System.out.println(result); System.out.println(System.currentTimeMillis()); } public static int solution(int n) { int result = 0; for (int oneNum = n; oneNum >= 0; oneNum--) { if ((n - oneNum) % 2 == 0) { result += countNum(oneNum, (n - oneNum) / 2); } } return result; } public static int countNum(int oneNum, int twoNum) { if (oneNum == 0 || twoNum == 0) { return 1; } else if (oneNum == 1 || twoNum == 1) { return oneNum + twoNum; } int total = 0; for (int i = 0; i <= oneNum; i++) { if (oneNum - i == 0) { total += 1; } else { total += countNum(oneNum - i, twoNum - 1); } } return total; } }

结果

  • 虽然优化有一定的效果,但当N较大时依然很慢,所以这种写法还不是答案。

3、使用排列组合公式、并优化

  • 在第二种写法时,递归的时候,就已经觉得是高中时学的排列组合问题了,由于一时没想起来公式是啥,就没有去实践。但结果仍然不对,那就只能去思考使用高中的排列组合公式能否可行。

  • 排列公式:本题中不适用排列公式

  • 在这里插入图片描述

  • 组合公式:其中阶乘式比较适合使用,转化为本题,公式中n就是走1级次数和走2级次数的总和,m可以是1级次数或2级次数,结果相同。

  • 在这里插入图片描述

基本排列组合

java
class Main { public static void main(String[] args) { System.out.println(System.currentTimeMillis()); int n = 20; int result = solution(n); System.out.println(result); System.out.println(System.currentTimeMillis()); } public static int solution(int n) { int result = 0; for (int oneNum = n; oneNum >= 0; oneNum--) { if ((n - oneNum) % 2 == 0) { result += countNum(oneNum, (n - oneNum) / 2); } } return result; } public static int countNum(int oneNum, int twoNum) { if (oneNum == 0 || twoNum == 0) { return 1; } else if (oneNum == 1 || twoNum == 1) { return oneNum + twoNum; } int total = 0; int top = 1; for (int i = oneNum + twoNum; i > 1; i--) { top *= i; } int down = 1; for (int i = oneNum; i > 1; i--) { down *= i; } for (int i = twoNum; i > 1; i--) { down *= i; } total = top / down; return total; } }

结果

  • 使用此代码测试,当N过大时,计算无法正常执行,会报错,原因是当N过大时,阶乘后数字过大,超出类型存储数字范围,导致数字变成0,最终导致分母为0计算出错。

优化公式计算逻辑

  • 优化思路:
  • 1、先对公式进行约分,减小阶乘数值
  • 2、m选取较小的数字,如果走1级台阶的次数小,就将1级台阶次数置为m,反之则是2级台阶次数。
java
class Main { public static void main(String[] args) { System.out.println(System.currentTimeMillis()); int n = 20; int result = solution(n); System.out.println(result); System.out.println(System.currentTimeMillis()); } public static int solution(int n) { int result = 0; for (int oneNum = n; oneNum >= 0; oneNum--) { if ((n - oneNum) % 2 == 0) { result += countNum(oneNum, (n - oneNum) / 2); } } return result; } public static int countNum(int oneNum, int twoNum) { if (oneNum == 0 || twoNum == 0) { return 1; } else if (oneNum == 1 || twoNum == 1) { return oneNum + twoNum; } int total = 0; int topMin = 1; int downMax = 1; if (oneNum > twoNum) { topMin = oneNum; downMax = twoNum; } else { topMin = twoNum; downMax = oneNum; } int top = 1; for (int i = oneNum + twoNum; i > topMin; i--) { top *= i; } int down = 1; for (int i = downMax; i > 1; i--) { down *= i; } total = top / down; return total; } }

总结

结果很不幸,当天没有去认真回忆排列组合公式,导致没有写完优化后这种方案,最后没有提交结果,不知道最后的答案是否正确。

感悟:

  • 1、很多问题用初中高中的知识就能解决,可惜你都忘了。
  • 2、有些问题不要死磕,网上查查,能节省很多时间。
  • 3、算法真难。-.-
如果对你有用的话,可以打赏哦
打赏
ali pay
wechat pay

本文作者:DingDangDog

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!