从品牌网站建设到网络营销策划,从策略到执行的一站式服务
一只青蛙一次可以跳上 1 级台阶,也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法
创新互联是专业的肥乡网站建设公司,肥乡接单;提供成都网站设计、网站制作,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行肥乡网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
假设,一级台阶,有f(1)种方法,二级有f(2)种,以此类推,n级有f(n)种方法。
可以看出,f(1)=1;f(2)=2。
那么,假设n级台阶,那么第一步就有两种情况,跳一步,跟跳两步。
情况一:跳一步,那么接下去的就是f(n-1);
情况二:跳两步,那么接下去的就是f(n-2)。
所以总数是f(n)=f(n-1)+f(n-2)。
public int cal(int n){ if(n<=0){ return -1; } if(n==1||n==2){ return n; } else{ return cal(n-1)+cal(n-2); } }
假设f(n)是n个台阶跳的次数。
f(1) = 1
f(2) 会有两个跳得方式,一次1阶或者2阶,这回归到了问题f(1),f(2) = f(2-1) + f(2-2)
f(3) 会有三种跳得方式,1阶、2阶、3阶,那么就是第一次跳出1阶后面剩下:f(3-1);第一次跳出2阶,剩下f(3-2);第一次3阶,那么剩下f(3-3).因此结论是
f(3) = f(3-1)+f(3-2)+f(3-3)
f(n)时,会有n中跳的方式,1阶、2阶...n阶,得出结论:
f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1) == f(n) = 2*f(n-1)
public long jumpFloor(int n) { if (n <= 0) return -1; if (n == 1) return 1; return 2 * jumpFloor(n - 1); }
考虑到效率,也可以改成迭代来做。
成都网站建设公司地址:成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220
成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.
专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网! | 成都网站建设哪家好? | 网站建设地图