要登上20级台阶,每步只能登上2级或3级,要登上20一共要多少步?
问题描述:
要登上20级台阶,每步只能登上2级或3级,要登上20一共要多少步?
答
您是问总共需要多少步,还是总共有多少种方法?
总共多少步,用不定方程(或者枚举法)解决:
可能有:
全用2级:共10步
7次2级,2次3级:9步
4次2级,4次3级:8步
1次2级,6次3级:7步
总共有多少种方法,递推法解决:
共2级台阶:1种
共3级台阶:1种
共4级台阶:1种
共5级台阶:1+1=2种(分成最后一步登2级和最后一步登3级两类,分别相当于登3级和2级台阶)
共6级台阶:1+1=2种(同上,4级和3级之和)
共7级台阶:1+2=3种
共8级台阶:1+2=3种
共9级台阶:2+3=5种
共10级台阶:3+3=6种
共11级台阶:3+5=8种
共12级台阶:5+6=11种
共13级台阶:6+8=14种
共14级台阶:8+11=19种
共15级台阶:11+14=25种
共16级台阶:14+19=33种
共17级台阶:19+25=44种
共18级台阶:25+33=58种
共19级台阶:33+44=77种
共20级台阶:44+58=102种