【算法趣题】Q15 走楼梯

引言

【算法趣题】是来自图灵程序设计丛书绝云译的《程序员的算法趣题》，书中是用Ruby实现的。这里是用python来实现。

问题描述

A上楼梯时，B从同一楼梯往下走。每次不一定只走1级，最多可以一次跳过3级（即直接前进4级）。

但无论走多级级，1次移动所需时间不变。两人同时开始走，求共有多少种“两人最终同时停在同一级”的情况（假设楼梯宽度足够，可以相互错开，不会撞上。另外，同时到达同一级时视为结束）。

举个例子，有4级楼梯的时候，结果如表所示，共有4种情况（假设每级楼梯上写着0~4这几个数字）。

有5级楼梯的时候，共有如下8种情况：

问题：求当存在10级楼梯，且移动规则相同时，有多少种两人最终同时停在同一级的情况？

思路及Python3实现

A和B都是简单按顺序移动，仿照【算法趣题】Q08 优秀的扫地机器人，扫地机器人是移动n步即停止，而这里，A和B分别从两端开始移动，两人最终同时挺在同一级。如此，只要A所在的级数和B所在的级数相等或者A所在的级数大于B所在的级数就可以停止了。

涉及到每次移动多少级，按题目要求有

steps = range(1,5)

即 steps就是每次可以走的级数的列表

另外 a是A当前所在的级数，b是B当前所在的级数

tracea 是A的移动路径，traceb是B的移动路径

def move(a, b, steps, traceb, tracea=[0] ):

    # A所在的级数大于B所在的级数

    if a > b:

        return 0

    # A所在的级数等于B所在的级数

    if a == b:

        print('->'.join(map(str, tracea)))

        print('->'.join(map(str, traceb)))

        print('---------------------')

        global count

        count = count + 1

        return 1

    for da in steps:

        # A移动da级，则A移动到新的级数为b-db

        tracea_copy = tracea.copy()

        tracea_copy.append(a+da)

        for db in steps:  

            # B移动db级，则A移动到新的级数为a+da

            traceb_copy = traceb.copy()

            traceb_copy.append(b-db)

            move(a+da, b-db,steps,traceb_copy,tracea_copy)

# N为楼梯的总级数

def get_move_count(N, steps):

    global count

    count = 0

    move(0,N,steps,[N])

    return count

以上运行结果跟例子中的结果一致。

最终结果为

即当有10级楼梯上，满足条件的共有201种。

书上还有一种动态规划法，可以尝试下。