数学中国

用户名  找回密码
 注册
帖子
热搜: 活动 交友 discuz
查看: 4599|回复: 7

矩形分割的问题

[复制链接]
发表于 2010-6-25 11:16 | 显示全部楼层 |阅读模式
已知一个大矩形和一个小矩形,请问大矩形最多可以分割成多少个小矩形,如何计算。。 。
发表于 2010-6-25 15:48 | 显示全部楼层

矩形分割的问题

[这个贴子最后由luyuanhong在 2010/06/25 03:49pm 第 1 次编辑]
下面引用由wenfengbx2010/06/25 11:16am 发表的内容:
已知一个大矩形和一个小矩形,请问大矩形最多可以分割成多少个小矩形,如何计算。。 。
楼主提出的问题说得不清楚。我猜想,可能是这样一个问题:

已知一个大矩形的长是 a ,宽是 b ;一个小矩形的长是 c ,宽是 d ( a≥b≥c≥d )。
现在要在大矩形内放置多个小矩形,放置时,要求小矩形的边与大矩形的边互相平行。
问:大矩形内最多可以放置多少个小矩形?如何计算?
发表于 2010-6-25 18:28 | 显示全部楼层

矩形分割的问题

我记得有个贴有答案。
发表于 2010-6-25 20:26 | 显示全部楼层

矩形分割的问题

有点像大园包小圆问题。这个像大方包小方啊。。
发表于 2010-6-28 06:18 | 显示全部楼层

矩形分割的问题

[这个贴子最后由luyuanhong在 2010/06/28 06:20am 第 1 次编辑]
下面引用由luyuanhong2010/06/25 03:48pm 发表的内容:
楼主提出的问题说得不清楚。我猜想,可能是这样一个问题:
已知一个大矩形的长是 a ,宽是 b ;一个小矩形的长是 c ,宽是 d ( a≥b≥c≥d )。
现在要在大矩形内放置多个小矩形,放置时,要求小矩形的边与大矩形的边互相平行。
问:大矩形内最多可以放置多少个小矩形?如何计算?
我编写了一个软件,可以用多重循环搜索的方法求出这个问题的解。
下面就是一些用这个软件求得的解实际例子:

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
发表于 2010-6-28 19:48 | 显示全部楼层

矩形分割的问题

下面引用由luyuanhong2010/06/28 06:18am 发表的内容:
我编写了一个软件,可以用多重循环搜索的方法求出这个问题的解。
下面就是一些用这个软件求得的解实际例子:
能不能简单的讲一下你用的算法啊?
发表于 2010-6-28 21:03 | 显示全部楼层

矩形分割的问题

[这个贴子最后由luyuanhong在 2010/06/28 09:06pm 第 2 次编辑]
下面引用由wangix2010/06/28 07:48pm 发表的内容:
能不能简单的讲一下你用的算法啊?

从我在第 5 楼中所举例的几个图可以看出:

每一种可能使小矩形数达到最多的放置,都可以分成图中黄、绿、蓝、灰那样的 4 块区域。
其中的某 1 块、2 块、3 块也可能不出现,相当于这一块的宽度为 0 或高度为 0 的情形。

我的多重循环搜索算法,先从黄色区域开始,让黄色区域的宽度和高度取遍各种可能的值。

在这两重循环中,每一步当黄色区域大小取定后,因为绿色区域要尽量填满黄色区域右边
的空隙,所以绿色区域的左右宽度可以确定,但是绿色区域的上下高度不确定,还可以取
各种不同的值。同时,因为蓝色区域要尽量填满黄色区域下边的空隙,所以蓝色区域的上下
高度也可以确定,但是蓝色区域的左右宽度不确定,还可以取各种不同的值。然后,再让
绿色区域的高度和蓝色区域的宽度取遍各种可能的值,这又是两重循环。
循环中每一步当
绿色和蓝色区域的大小完全确定时,因为灰色区域要尽量填满右下方的空隙,所以灰色区
域的大小可以完全确定。就这样,通过四重循环,搜遍一切可能的最优放置方法。在循环
的每一步,都计算一下小矩形的个数,通过比较,就可以找出小矩形个数最多的放置方法。
 楼主| 发表于 2010-6-30 11:24 | 显示全部楼层

矩形分割的问题

非常感谢解答,受益匪浅啊~~
您需要登录后才可以回帖 登录 | 注册

本版积分规则

LaTEX预览输入 教程 符号库 加行内标签 加行间标签 
对应的 LaTEX 效果:

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2025-7-5 03:33 , Processed in 0.104984 second(s), 17 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表
\frac{\square}{\square}\sqrt{\square}\square_{\baguet}^{\baguet}\overarc{\square}\ \dot{\baguet}\left(\square\right)\binom{\square}{\square}\begin{cases}\square\\\square\end{cases}\ \begin{bmatrix}\square&\square\\\square&\square\end{bmatrix}\to\Rightarrow\mapsto\alpha\ \theta\ \pi\times\div\pm\because\angle\ \infty
\frac{\square}{\square}\sqrt{\square}\sqrt[\baguet]{\square}\square_{\baguet}\square^{\baguet}\square_{\baguet}^{\baguet}\sum_{\baguet}^{\baguet}\prod_{\baguet}^{\baguet}\coprod_{\baguet}^{\baguet}\int_{\baguet}^{\baguet}\lim_{\baguet}\lim_{\baguet}^{\baguet}\bigcup_{\baguet}^{\baguet}\bigcap_{\baguet}^{\baguet}\bigwedge_{\baguet}^{\baguet}\bigvee_{\baguet}^{\baguet}
\underline{\square}\overline{\square}\overrightarrow{\square}\overleftarrow{\square}\overleftrightarrow{\square}\underrightarrow{\square}\underleftarrow{\square}\underleftrightarrow{\square}\dot{\baguet}\hat{\baguet}\vec{\baguet}\tilde{\baguet}
\left(\square\right)\left[\square\right]\left\{\square\right\}\left|\square\right|\left\langle\square\right\rangle\left\lVert\square\right\rVert\left\lfloor\square\right\rfloor\left\lceil\square\right\rceil\binom{\square}{\square}\boxed{\square}
\begin{cases}\square\\\square\end{cases}\begin{matrix}\square&\square\\\square&\square\end{matrix}\begin{pmatrix}\square&\square\\\square&\square\end{pmatrix}\begin{bmatrix}\square&\square\\\square&\square\end{bmatrix}\begin{Bmatrix}\square&\square\\\square&\square\end{Bmatrix}\begin{vmatrix}\square&\square\\\square&\square\end{vmatrix}\begin{Vmatrix}\square&\square\\\square&\square\end{Vmatrix}\begin{array}{l|l}\square&\square\\\hline\square&\square\end{array}
\to\gets\leftrightarrow\nearrow\searrow\downarrow\uparrow\updownarrow\swarrow\nwarrow\Leftarrow\Rightarrow\Leftrightarrow\rightharpoonup\rightharpoondown\impliedby\implies\Longleftrightarrow\leftharpoonup\leftharpoondown\longleftarrow\longrightarrow\longleftrightarrow\Uparrow\Downarrow\Updownarrow\hookleftarrow\hookrightarrow\mapsto
\alpha\beta\gamma\Gamma\delta\Delta\epsilon\varepsilon\zeta\eta\theta\Theta\iota\kappa\varkappa\lambda\Lambda\mu\nu\xi\Xi\pi\Pi\varpi\rho\varrho\sigma\Sigma\tau\upsilon\Upsilon\phi\Phi\varphi\chi\psi\Psi\omega\Omega\digamma\vartheta\varsigma\mathbb{C}\mathbb{H}\mathbb{N}\mathbb{P}\mathbb{Q}\mathbb{R}\mathbb{Z}\Re\Im\aleph\partial\nabla
\times\cdot\ast\div\pm\mp\circ\backslash\oplus\ominus\otimes\odot\bullet\varnothing\neq\equiv\not\equiv\sim\approx\simeq\cong\geq\leq\ll\gg\succ\prec\in\ni\cup\cap\subset\supset\not\subset\not\supset\notin\not\ni\subseteq\supseteq\nsubseteq\nsupseteq\sqsubset\sqsupset\sqsubseteq\sqsupseteq\sqcap\sqcup\wedge\vee\neg\forall\exists\nexists\uplus\bigsqcup\bigodot\bigotimes\bigoplus\biguplus\bigcap\bigcup\bigvee\bigwedge
\because\therefore\angle\parallel\perp\top\nparallel\measuredangle\sphericalangle\diamond\diamondsuit\doteq\propto\infty\bowtie\square\smile\frown\bigtriangledown\triangle\triangleleft\triangleright\bigcirc \wr\amalg\models\preceq\mid\nmid\vdash\dashv\nless\ngtr\ldots\cdots\vdots\ddots\surd\ell\flat\sharp\natural\wp\clubsuit\heartsuit\spadesuit\oint\lfloor\rfloor\lceil\rceil\lbrace\rbrace\lbrack\rbrack\vert\hbar\aleph\dagger\ddagger

MathQuill输入:

Latex代码输入: