首页 > 试题广场 >

黄油运输的迷思（一）

[编程题]黄油运输的迷思（一）

热度指数：476 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

当智加科技的无人驾驶车队首次进行横跨美洲的生鲜运输时，工程师阳阳注视着一桶桶的黄油陷入了沉思。他突发奇想，要这一切都是标准化包装物件，那么其尺寸不仅节约控件、提升干线物流运输效率，同时也让简化车辆的动力学、运动学建模，帮助自动驾驶算法更精准、灵敏地操控车辆（但愿如此）。
如果现有两种包装物品的包装运输箱，尺寸分别是长宽 1米×1米和 1米×2米

【本题编程】假定用这两种箱子排成一个 1米×n米的队列，不限两种箱子的使用数量，则有多少种不同的排列方式？

输入描述:

第一行输入为整数 n (1<=n<=100)

输出描述:

第一行输出为结果整数

示例1

输入

输出

算法知识视频讲解

Python

pein531

动态规划

很容易看出来是去除第一项的斐波那契数列，问题在于这个数据类型，竟然让不取模地输出最终结果，Java得用BigInteger，C++怕是得自己手撸个大数乘法。懒得写，直接用python来做了，用矩阵快速幂来加速计算过程。

能用快速幂来做的条件是：除了初始的几项，dp序列中某一项的计算必须严格依赖前面的某几项，无论递归深度达到多少都满足，不存在终止递归的递归头，程序什么时候停止完全依赖于你设置让它算到哪一轮。

def multiMat2D(A, B):
    return [[A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]],
            [A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]]]

if __name__ == "__main__":
    n = int(input())
    base = [[1, 1], [1, 0]]
    ans = [[1, 0], [0, 1]]
    p = n - 1
    while p != 0:
        if (p & 1) != 0:
            ans = multiMat2D(ans, base)
        base = multiMat2D(base, base)
        p >>= 1
    print(ans[0][0] + ans[1][0])

编辑于 2022-04-08 14:31:04 回复(0)