首页 > 试题广场 >

黄油运输的迷思（二）

[编程题]黄油运输的迷思（二）
  • 热度指数：231 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

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

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

  • 【本题编程】假定用这两种箱子排成一片 m列n行 (m米×n米) 的阵列，不限两种箱子的使用数量，则有多少种不同的排列方式？
    注意：1米×2米 箱子不能旋转方向使用，即不能作为 2米×1米 的箱子跨列摆放在阵列中


输入描述:
第一行输入为 整数 m (1<=m<=10)
第二行输入为 整数 n (1<=n<=10)


输出描述:
第一行输出为结果整数
示例1

输入

2
2

输出

4
算法知识视频讲解
添加回答
Python
pein531头像 pein531

动态规划

在“黄油运输的迷思（一）”的算法上修改一下就行，每行的排列方法数可以复用之前快速幂求解斐波那契数列第n项的流程。要排m行，只需要根据乘法原理对每行的方法数求m次幂就可以了。 
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__":
    m = int(input())
    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])**m)

发表于 2022-04-08 14:38:05 回复(0)
Java
牛客258541934号头像 牛客258541934号
import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int M=in.nextInt();
        int N=in.nextInt();
        if(N==1){
            System.out.println(new BigInteger("1"));
            return;
        }
        BigInteger[] array=new BigInteger[N+1];
        array[0]=new BigInteger("1");
        array[1]=new BigInteger("1");
        for(int i=2;i<=N;i++){
            array[i]=array[i-1].add(array[i-2]);
        }
        System.out.println(array[N].pow(M));
        return;
    }
}
//正好前面用了Big Integer就直接用它的方法了（懒）;

发表于 2022-04-13 19:46:52 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 数据库工程师 测试开发工程师 2020 大数据开发工程师 Java工程师 智加科技
来自：【2021】智加科技校...
上传者：小小
难度：
2条回答 2478浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号