呼和浩特网站建设电话西安专业网站建设公司哪家好

呼和浩特网站建设电话,西安专业网站建设公司哪家好,个体户可以做企业网站,国外手机网站模板问题一只青蛙想要跳到第 n 级台阶#xff08;n 为非负整数#xff09;。它每次只能跳 1 级 或 2 级 台阶#xff0c;问这只青蛙跳到第 n 级台阶共有多少种不同的跳法#xff1f;举例首先我们先从简单的开始分析#xff1a;当n1时#xff1b;青蛙只有一种跳法#xff1a;…问题一只青蛙想要跳到第n级台阶n为非负整数。它每次只能跳1 级或2 级台阶问这只青蛙跳到第n级台阶共有多少种不同的跳法举例首先我们先从简单的开始分析当n1时青蛙只有一种跳法就是跳一级台阶当n2时青蛙只有两种跳法1.一次跳一级台阶共跳两次2.一次跳两级台阶共跳一次当n3时青蛙有三种跳法1.一次跳一级台阶共跳三次2.第一次跳两级台阶第二次跳一级台阶共跳两次3.第一次跳一级台阶第二次跳两级台阶共跳两次当n4时青蛙有五种跳法1.一次跳一级台阶共跳4次2.第一次跳一级台阶第二次跳两级台阶第三次跳一级台阶共跳三次3.第一次跳一级台阶第二次跳一级台阶第三次跳两级台阶共跳三次4.第一次跳两级台阶第二次跳一级台阶第三次跳一级台阶共跳三次5.第一次跳两级台阶第二次跳两级台阶......我们看青蛙共有2种跳跃方式一级或两级台阶假设要跳跃的台阶为a级每次跳跃后以跳跃到的台阶为起点发现剩余跳跃的台阶为a-1或a-2级按照数学思想a级的台阶跳跃数的种类为(a-1)与(a-2)的种类数之和。由此我们可以用函数的递归来解决这类问题。代码验证#includestdio.h int frog(int n) { if(n2){return n;} else return frog(n-1)frog(n-2); } int main() { int a; printf(请输入青蛙要跳跃的台阶数\n); scanf(%d,a); printf(青蛙跳跃%d级台阶共有%d种方法,a,frog(a)); return 0; }扩展那如果青蛙可以跳k级台阶呢k ≤ n即每次最多跳当前剩余台阶数分析由原问题分析可得当kn时符合上述问题分析即可将n级台阶分为k组n级台阶的跳法n-1与n-2与...n-k级台阶跳法之和)代码验证#include stdio.h long long frog(int n, int k) { long long recur(int m) { if (m 0) { return 1; } long long sum 0; for (int i 1; i k i m; i) { sum recur(m - i); } return sum; } return a(n); } int main() { int n, k; printf(请输入台阶数n非负整数和最大跳级k); scanf(%d %d, n, k); long long res frog(n, k); printf(跳到第%d级台阶共有%lld种不同跳法\n, n, res) return 0; }总结青蛙跳台阶1~k 级版的本质是多阶递推的组合问题递归思路适合理解问题本质嵌套函数实现符合语法要求但需记忆化优化性能动态规划是工程最优解兼顾时间 / 空间效率核心是抓住 “当前级跳法数 所有合法前序级跳法数之和” 的递推关系同时做好边界过滤和数据类型适配。