V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
yazoox
V2EX  ›  算法

小学数学题, 100 平方米的正方形可以最多分成多少个 7cm x 5cm 的长方形?

  •  
  •   yazoox · 2021-07-02 20:13:07 +08:00 · 2175 次点击
    这是一个创建于 1229 天前的主题,其中的信息可能已经有所发展或是发生改变。

    刚才看到的,小学数学题?

    10mx10m 的正方形 (1000cm x 1000cm)

    7cmx5cm 的长方形

    最多可以分成多少个?

    如果用计算机编程,怎么解决?

    dp? 好像要用到图论......

    16 条回复    2021-07-03 13:04:03 +08:00
    Jooooooooo
        1
    Jooooooooo  
       2021-07-02 20:20:05 +08:00
    想了一下不知道怎么证明小长方形斜着放"不好".
    yazoox
        2
    yazoox  
    OP
       2021-07-02 20:24:26 +08:00
    @Jooooooooo 要不,规定不能斜着放吧
    pcbl
        3
    pcbl  
       2021-07-02 20:28:28 +08:00
    200*140?
    ynyounuo
        4
    ynyounuo  
       2021-07-02 20:30:45 +08:00
    我感觉 n × n 的正方形能放多少 a × b 的长方形( n >> a, n >> b, a ≠ b )的问题应该不是 polynomial time 可解的
    当然个体例子应该可以
    thunderw
        5
    thunderw  
       2021-07-02 20:32:07 +08:00
    如果不用写斜着放的话,横放竖放排列组合?
    横放一行、两行,依次试一下,
    剩下的竖着放
    ---
    ---
    |||||

    要是允许斜着放就不好办了。
    ///
    \\\
    也行
    IgniteWhite
        6
    IgniteWhite  
       2021-07-02 21:01:19 +08:00 via iPhone
    dp 听起来是对的方向……
    oott123
        7
    oott123  
       2021-07-02 21:41:57 +08:00   ❤️ 1
    切成 1x1 的然后拼起来……?这样比较小学数学一点
    Muninn
        8
    Muninn  
       2021-07-02 22:49:45 +08:00
    这感觉不小学啊
    gwy15
        9
    gwy15  
       2021-07-02 22:50:04 +08:00   ❤️ 1
    https://en.wikipedia.org/wiki/Rectangle_packing

    里面的第一篇引用讨论了一个排列算法,但是只允许旋转 90 度,有的情况下允许任意旋转是可以达到更优的排列的,比如 11x11 的平面排 4x4 的正方形,用
    +0+
    0x0
    +0+
    bwangel
        10
    bwangel  
       2021-07-02 22:55:17 +08:00
    横铺 200 * 140 共 28000 个
    竖铺 14 * 4 共 56 个

    这样一共可以铺 28056 个,剩余面积 40 cm^2
    clockwise9
        11
    clockwise9  
       2021-07-03 01:27:31 +08:00 via Android
    如果允许裁剪再拼接的话,是不是只要考虑面积就行了
    Elethom
        12
    Elethom  
       2021-07-03 07:24:18 +08:00 via iPhone
    外星小学?
    oneforallsoft
        13
    oneforallsoft  
       2021-07-03 10:19:15 +08:00
    @bwangel
    200 * 142 = 28400
    28400 + 142 = 28542
    剩余 142 cm^2
    wayne233
        14
    wayne233  
       2021-07-03 11:23:58 +08:00
    竖铺 140 排 200 列,共 28000 个,余 20 x 1000 空间;
    横铺 4 排 140 列,共 560 个,余 20 x 20 空间;
    20 x 20 空间目前能想到可以放置 10 个,余 50cm²
    即:总共放置 28570 个小矩形,余 50cm²
    bwangel
        15
    bwangel  
       2021-07-03 12:57:09 +08:00
    @oneforallsoft

    #10 的答案我写错了

    横铺 200 * 140 共 28000 个
    竖铺 142 * 4 共 568 个

    这样一共可以铺 28568 个,剩余面积 6*20 = 120 平方厘米
    bwangel
        16
    bwangel  
       2021-07-03 13:04:03 +08:00
    @bwangel #14

    #14 楼的答案对,剩下的 6*20 中,还可以横着放置两个

    所以总数量是 28000 + 568 + 2 = 28570 个 剩余面积 1*20 + 6 * 5 = 50 平方厘米

    ----

    由于其他面积都可以被铺满,所以这个问题可以简化成

    20 * 20 的正方形里,最多可以放多少个 5 * 7 的矩形

    目前找到的答案是 10 个,剩余 50 cm^2 的面积。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1160 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 22:58 · PVG 06:58 · LAX 14:58 · JFK 17:58
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.