随机行走方案

markfang2050

从 A 到 B 距离为 2019 ，每一步可随机行走距离 1、3 或 5，从 A 到 B 给出行走方案。 共有几种走法？

王守恩

1, 1, 2, 3, 5, 8, 12, 19, 30, 47, 74, 116, 182, 286, 449, 705, 1107, 1738,
2729, 4285, 6728, 10564, 16587, 26044, 40893, 64208, 100816, 158296,
248548, 390257, 612761, 962125, 1510678, 2371987, ............

markfang2050

王守恩 发表于 2019-3-24 20:30
1, 1, 2, 3, 5, 8, 12, 19, 30, 47, 74, 116, 182, 286, 449, 705, 1107, 1738,
2729, 4285, 6728, 1056 ...

总长才2019啊

王守恩

markfang2050 发表于 2019-3-24 20:50
总长才2019啊

2019 太大，先从 “1” 算起。
从 A 到 B 距离为 “1” ，每一步可随机行走距离 1、3 或 5，从 A 到 B 共有1种走法。
从 A 到 B 距离为 “2” ，每一步可随机行走距离 1、3 或 5，从 A 到 B 共有1种走法。
从 A 到 B 距离为 “3” ，每一步可随机行走距离 1、3 或 5，从 A 到 B 共有2种走法。
从 A 到 B 距离为 “4” ，每一步可随机行走距离 1、3 或 5，从 A 到 B 共有3种走法。
从 A 到 B 距离为 “5” ，每一步可随机行走距离 1、3 或 5，从 A 到 B 共有5种走法。
从 A 到 B 距离为 “6” ，每一步可随机行走距离 1、3 或 5，从 A 到 B 共有8种走法。
从 A 到 B 距离为 “7” ，每一步可随机行走距离 1、3 或 5，从 A 到 B 共有12种走法。
从 A 到 B 距离为 “8” ，每一步可随机行走距离 1、3 或 5，从 A 到 B 共有19种走法。
从 A 到 B 距离为 “9” ，每一步可随机行走距离 1、3 或 5，从 A 到 B 共有30种走法。

markfang2050

能给出行走的细节方案吗？

markfang2050

python计算程序
# coding = UTF-8
#题目：一栋楼有N阶楼梯，兔子每次可以跳1、3或5阶，问一共有多少种走法？
#对应1，2，3阶楼梯的方法数#比如n=5，1+1+1+1+1=1+3+1=1+1+3=3+1+1=5=5，共有5种不同的方法
#n=4，1+1+1+1=1+3=3+1=4，共有3种不同的方法
#n=3，1+1+1=3=3，共有2种不同的方法
#n=2，1+1=2，共有1种不同的方法
#n=1，1=1，共有1种不同的方法
#递归法

def climbStairs1(stairs):
    '''
    :param stairs:the  numbers of stair
    :return:
    '''
    if isinstance(stairs,int) and stairs > 0:
        basic_num = {0:1,1:1,2:1,3:2,4:3,5:5}
        if stairs in basic_num.keys():
            return basic_num[stairs]
        else:
            return climbStairs1(stairs-1)  + climbStairs1(stairs-3)+ climbStairs1(stairs-5)
    else:
        print( 'the num of stair is wrong')
        return False

#递推法
def climbStairs2(stairs):
    '''递推实现
    :param stairs:  the amount of stair
    :return:
    '''
   
    if isinstance(stairs,int) and stairs > 0:
         h1=1#对应1，2，3, 4, 5阶楼梯的方法数
         h2=1
         h3=2
         h4=3
         h5=5
         n=5
         basic_num = {1:1,2:1,3:2,4:3,5:5}
         if stairs in basic_num.keys():
            return basic_num[stairs]
         else:
            for i in range(stairs-n):
            
               temp =h1
               h1 = h2
               h2 = h3
               h3 =h4
               h4=h5
               h5 =temp+h2+h4
               
            return h5
    else:
        print ('the num of stair is wrong')
        return False


for j in range(1,20):   #1-19阶楼梯
print ('递归法求得爬%d阶楼梯的方法数%d'%(j,climbStairs1(j)))#12阶楼梯
print ('递推法求得爬%d阶楼梯的方法数%d'%(j,climbStairs2(j)))
========
递归法求得爬1阶楼梯的方法数1
递推法求得爬1阶楼梯的方法数1
递归法求得爬2阶楼梯的方法数1
递推法求得爬2阶楼梯的方法数1
递归法求得爬3阶楼梯的方法数2
递推法求得爬3阶楼梯的方法数2
递归法求得爬4阶楼梯的方法数3
递推法求得爬4阶楼梯的方法数3
递归法求得爬5阶楼梯的方法数5
递推法求得爬5阶楼梯的方法数5
递归法求得爬6阶楼梯的方法数8
递推法求得爬6阶楼梯的方法数8
递归法求得爬7阶楼梯的方法数12
递推法求得爬7阶楼梯的方法数12
递归法求得爬8阶楼梯的方法数19
递推法求得爬8阶楼梯的方法数19
递归法求得爬9阶楼梯的方法数30
递推法求得爬9阶楼梯的方法数30
递归法求得爬10阶楼梯的方法数47
递推法求得爬10阶楼梯的方法数47
递归法求得爬11阶楼梯的方法数74
递推法求得爬11阶楼梯的方法数74
递归法求得爬12阶楼梯的方法数116
递推法求得爬12阶楼梯的方法数116
递归法求得爬13阶楼梯的方法数182
递推法求得爬13阶楼梯的方法数182
递归法求得爬14阶楼梯的方法数286
递推法求得爬14阶楼梯的方法数286
递归法求得爬15阶楼梯的方法数449
递推法求得爬15阶楼梯的方法数449
递归法求得爬16阶楼梯的方法数705
递推法求得爬16阶楼梯的方法数705
递归法求得爬17阶楼梯的方法数1107
递推法求得爬17阶楼梯的方法数1107
递归法求得爬18阶楼梯的方法数1738
递推法求得爬18阶楼梯的方法数1738
递归法求得爬19阶楼梯的方法数2729
递推法求得爬19阶楼梯的方法数2729

markfang2050

markfang2050 发表于 2019-3-25 12:11
能给出行走的细节方案吗？

细节方案是每一个方法的具体走法。

王守恩

markfang2050 发表于 2019-3-25 12:56
细节方案是每一个方法的具体走法。

a(01)=a(00)+1=1种具体走法
a(02)=a(01)+1=1种具体走法
a(03)=(a(02)+1)+(a(00)+3)=1+1=2种具体走法
a(04)=(a(03)+1)+(a(01)+3)=2+1=3种具体走法
a(05)=(a(04)+1)+(a(02)+3)+(a(00)+5)=003+001+001=5
a(06)=(a(05)+1)+(a(03)+3)+(a(01)+5)=005+002+001=8
a(07)=(a(06)+1)+(a(04)+3)+(a(02)+5)=008+003+001=12
a(08)=(a(07)+1)+(a(05)+3)+(a(03)+5)=012+005+002=19
a(09)=(a(08)+1)+(a(06)+3)+(a(04)+5)=019+008+003=30
a(10)=(a(09)+1)+(a(07)+3)+(a(05)+5)=030+012+005=47
a(11)=(a(10)+1)+(a(08)+3)+(a(06)+5)=047+019+008=74
a(12)=(a(11)+1)+(a(09)+3)+(a(07)+5)=074+030+012=116
a(13)=(a(12)+1)+(a(10)+3)+(a(08)+5)=116+047+019=182
a(14)=(a(13)+1)+(a(11)+3)+(a(09)+5)=182+074+030=286
a(15)=(a(14)+1)+(a(12)+3)+(a(10)+5)=286+116+047=449
a(16)=(a(15)+1)+(a(13)+3)+(a(11)+5)=449+182+074=705
a(17)=(a(16)+1)+(a(14)+3)+(a(12)+5)=705+286+116=1107
....................

markfang2050

a(09)=(a(08)+1)+(a(06)+3)+(a(04)+5)=019+008+003=30，比如这个，可以以给出所有的行走方案吗？30种。

王守恩

markfang2050 发表于 2019-3-25 15:30
a(09)=(a(08)+1)+(a(06)+3)+(a(04)+5)=019+008+003=30，比如这个，可以以给出所有的行走方案吗？30种。

a(09)——01=1+1+1+1+1+1+1+1+1
a(09)——02=1+1+1+1+1+1+3
a(09)——03=1+1+1+1+1+3+1
a(09)——04=1+1+1+1+3+1+1
a(09)——05=1+1+1+1+5
a(09)——06=1+1+1+3+1+1+1
a(09)——07=1+1+1+3+3
a(09)——08=1+1+1+5+1
a(09)——09=1+1+3+1+1+1+1
a(09)——10=1+1+3+1+3
a(09)——11=1+1+3+3+1
a(09)——12=1+1+5+1+1
a(09)——13=1+3+1+1+1+1+1
a(09)——14=1+3+1+1+3
a(09)——15=1+3+1+3+1
a(09)——16=1+3+3+1+1
a(09)——17=1+3+5
a(09)——18=1+5+1+1+1
a(09)——19=1+5+3
a(09)——20=3+1+1+1+1+1+1
a(09)——21=3+1+1+1+3
a(09)——22=3+1+1+3+1
a(09)——23=3+1+3+1+1
a(09)——24=3+1+5
a(09)——25=3+3+1+1+1
a(09)——26=3+3+3
a(09)——27=3+5+1
a(09)——28=5+1+1+1+1
a(09)——29=5+1+3
a(09)——30=5+3+1