一. 青蛙跳台阶问题一只青蛙一次可以跳1 级台阶也可以跳2 级台阶。求跳到第 n 级台阶一共有多少种跳法。1. 思路想跳到第 n 级最后一步只有两种可能从 n - 1 级 跳 1 级 上来 → 跳法 jump(n - 1)从 n - 2 级 跳 2 级 上来 → 跳法 jump(n - 2)方法总数 两种情况相加。二.算法实现递归法/循环法1. 递归方法代码问题1大量重复计算效率极低2比如算 jump(5) 时jump(3) 会被算 2 次jump(2) 会被算 3 次3n 40 时电脑会卡顿很久4 n 太大时栈溢出5递归深度太深程序崩溃。2. 代码优化循环法循环法最快、无溢出、最稳定。#define_CRT_SECURE_NO_WARNINGS//青蛙跳台阶问题//一只青蛙一次可以跳1 级台阶也可以跳2 级台阶。//求跳到第 n 级台阶一共有多少种跳法#includestdio.hintjump(intn){// 处理非法输入if(n1){return-1;}//递归终止条件出口if(n1){return1;// 1级台阶只有 1 种跳法}elseif(n2){return2;// 2级台阶11、2 → 共 2 种}returnjump(n-1)jump(n-2);//想跳到第 n 级最后一步只有两种可能//从 n - 1 级 跳 1 级 上来 → 跳法 jump(n - 1)//从 n - 2 级 跳 2 级 上来 → 跳法 jump(n - 2)//总数 两种情况相加}//递归方法代码问题//1. 大量重复计算效率极低//比如算 jump(5) 时//jump(3) 会被算 2 次//jump(2) 会被算 3 次//n 40 时电脑会卡顿很久//2. n 太大时栈溢出//递归深度太深程序崩溃//优化代码用循环计算intjump1(intn){// 处理非法输入if(n1){return-1;}if(n1)return1;if(n2)return2;inta1;// f(n-2)intb2;// f(n-1)intc0;// f(n)// 从3开始循环到nfor(inti3;in;i){cab;ab;bc;}returnb;}intmain(){intn0;printf(请输入要调到的台阶数\n);scanf(%d,n);//递归法intcountjump(n);//打印输出if(count-1)printf(递归法台阶数输入错误\n);elseprintf(\n递归法青蛙调到%d级台阶共有%d种跳法。\n,n,count);intcount1jump1(n);//打印输出if(count1-1)printf(循环法台阶数输入错误\n);elseprintf(\n循环法青蛙调到%d级台阶共有%d种跳法。\n,n,count1);}三. 运行结果