小学数学题， 100 平方米的正方形可以最多分成多少个 7cm x 5cm 的长方形？
yazoox · 2021-07-02 20:13:07 +08:00 · 2201 次点击这是一个创建于 1265 天前的主题，其中的信息可能已经有所发展或是发生改变。
刚才看到的，小学数学题？
10mx10m 的正方形 (1000cm x 1000cm)
7cmx5cm 的长方形
最多可以分成多少个？
如果用计算机编程，怎么解决？
dp? 好像要用到图论......
 |
1
Jooooooooo 2021-07-02 20:20:05 +08:00
想了一下不知道怎么证明小长方形斜着放"不好".
|
 |
2
yazoox OP @Jooooooooo 要不，规定不能斜着放吧
|
 |
3
pcbl 2021-07-02 20:28:28 +08:00
200*140?
|
 |
4
ynyounuo 2021-07-02 20:30:45 +08:00
我感觉 n × n 的正方形能放多少 a × b 的长方形（ n >> a, n >> b, a ≠ b ）的问题应该不是 polynomial time 可解的
当然个体例子应该可以 |
 |
5
thunderw 2021-07-02 20:32:07 +08:00
如果不用写斜着放的话，横放竖放排列组合？
横放一行、两行，依次试一下， 剩下的竖着放 --- --- ||||| 要是允许斜着放就不好办了。 /// \\\ 也行 |
 |
6
IgniteWhite 2021-07-02 21:01:19 +08:00 via iPhone
dp 听起来是对的方向……
|
 |
7
oott123 2021-07-02 21:41:57 +08:00  1
切成 1x1 的然后拼起来……？这样比较小学数学一点
|
 |
8
Muninn 2021-07-02 22:49:45 +08:00
这感觉不小学啊
|
 |
9
gwy15 2021-07-02 22:50:04 +08:00 1
https://en.wikipedia.org/wiki/Rectangle_packing
里面的第一篇引用讨论了一个排列算法，但是只允许旋转 90 度，有的情况下允许任意旋转是可以达到更优的排列的，比如 11x11 的平面排 4x4 的正方形，用 +0+ 0x0 +0+ |
 |
10
bwangel 2021-07-02 22:55:17 +08:00
横铺 200 * 140 共 28000 个
竖铺 14 * 4 共 56 个 这样一共可以铺 28056 个，剩余面积 40 cm^2 |
 |
11
clockwise9 2021-07-03 01:27:31 +08:00 via Android
如果允许裁剪再拼接的话，是不是只要考虑面积就行了
|
 |
12
Elethom 2021-07-03 07:24:18 +08:00 via iPhone
外星小学？
|
 |
13
oneforallsoft 2021-07-03 10:19:15 +08:00
|
 |
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² |
|
15
bwangel 2021-07-03 12:57:09 +08:00
@oneforallsoft
#10 的答案我写错了 横铺 200 * 140 共 28000 个 竖铺 142 * 4 共 568 个 这样一共可以铺 28568 个，剩余面积 6*20 = 120 平方厘米 |
Select Language