2016区域覆盖问题设计报告.docx

名目一、 问题重述二、 问题分析三、 模型假设四、 定义与符号说明五、 模型的建立与求解模型 I(正方形模型)模型 II(正六边形模型)推广 ：以圆求解模型六、 对模型的评价七、 参考文献八、 附录一 ﹑ 问题重述给定一个m*n 的矩形区域，假设半径为r 的圆对其进展完全掩盖， 要求相邻两个圆相交的公共面积不小于一个圆面积的 k%，使得完全 掩盖整个图形时所用圆的个数最少，求解掩盖模型二 ﹑ 问题分析对于问题的分析， 要求我们要完全一样的最少的圆完全掩盖矩形 区域，这样削减圆的个数，让其求解该题的思路更加清楚该问题属 于数学中的几何问题， 通常承受几何作图的方法再结合几何定理尝试 解决该问题的模型， 再通过具体数据对模型进展验证优化， 筛选出最1优模型对于问题所要求的结果进展分析： 题目要求使用完可能少的完全 一样的圆完全掩盖矩形区域， 要使其完全掩盖那么圆与圆之间必有重叠 局部基于上述要求，此题就从削减重叠局部着手又由于此题给出 了一组数据，利用数据可使得问题简化从实际结合理论要求，我们 承受推测、推理、证明的方法首先，正方形是一个特别的四边形， 用圆进展掩盖， 把两个特别的图形联系起来。

很自然的想到利用正方 形进展掩盖， 而用正方形的外接圆再掩盖矩形区域 再从具体的数据 入手计算， 考虑完全掩盖的最优个数问题 那么其他的正多边形是否 可以同样利用外接圆的思想对矩形区域进展完全掩盖计算？通过证 明可以知道正三角形、正方形、正六边形可以满足要求〔见附录 1.2〕 利用几何定理自然地可以推广到正六边形这就是本文的根本思路综合以上缘由，首先，我们建立了一个以正方形为单位对矩形区 域进展掩盖的模型 I，然后，建立了一个以正六边形为单位的对矩形 区域进展掩盖的模型 II先对两个模型进展推测，再利用所给的实 际数据进展计算，对结果进展了分析最终，得出较优模型三、模型假设⑴．掩盖区域为一个矩形;⑵．每一个圆都是半径一样的等圆；⑶．相邻两个圆相交的公共面积不小于一个圆面积的 k%;⑷.假设一个圆只有局部在图形中，也按一个计算；⑸．用一样的正多边形完全掩盖矩形，相邻正多边形间无缝隙四、定义与符号说明MNr矩形区域的长矩形区域的宽外接圆的半径2K%A1B1A2B2cS1S相邻两个圆相交的公共面积所占一个圆面积的百分比矩形长所包含的正六边形的个数矩形宽所包含的正六边形的个数矩形长所包含的正方形的个数矩形宽所包含的正方形的个数掩盖矩形所用的正多边形个数两个正多边形外接圆相交的重合面积一个正多边形外接圆面积3模型的建立与求解一 以正方形为单位的对矩形区域进展掩盖的模型 I在解决本问题的过程中，我们需要考虑的问题主要有以下几点： 一、怎样用圆掩盖矩形区域，且使得所用圆的个数最少？二、相邻两 个圆重合面积的怎样计算？由于题中最终给出了一边长为 1000 的正 方形， 半径为 100 的圆去填充正方形， 故我们可以通过该特别例子的 求解方案建立模型，从而推广到一般的矩形区域掩盖问题。

针对 m=n=1000.r=100,的掩盖问题的求解解题思路如下：建立以正方形为根底，通过以正方形外接圆为单位去掩盖例题中所给的正方形， 然后依据例题作进一步的推广到矩形 如以下图所示小正方形的对角线 ab 为 200，那么可以通过计算得到小正方形的边长为 100 2 141 .42 〔注 2 1.4142〕小正方形的外接圆半径 r=100，用小正方形外接圆去掩盖小正方形当正方形边长为 1000 时，可以 将此正方形分解为对角线长为 200 的假设干小正方形， 没有被分为小正 方形局部为小矩形， 然后用小正方形的外接圆去掩盖小正方形， 剩余 的小矩形补为对角线长为 200 的小正方形， 然后用小正方形外接圆去 掩盖小正方形通过编程得到〔附录 3〕如以下图100080060040020000 200 400 600 800 1000 1200共要 8*8=64 个小方形此时相邻两正方形外接圆重合面积为 S1 如以下图所示S1=( r2 1 r2 1 ) 2 S= r 24 24K%=S1Sr 2r 2r 2r 2=18.15%以上是对边长为 1000 的正方形的计算，通过该计算思想可以推广到 矩形区域掩盖问题上矩形的长为 m，宽为 n ，用半径为 r 的圆去掩盖矩形，可把矩 形分成假设干个对角线长为 2r 的小正方形，没有被分为小正方形局部 为小矩形， 然后用小正方形的外接圆去掩盖小正方形， 剩余剩余的小 矩形补为对角线长为 200 的小正方形， 然后用小正方形外接圆去掩盖小正方形。

建立如下公式 m m m 0A2= r 2 r 2 r 2 m 1 m m 0 r 2 r 2 r 2 n n n 0B2= r 2 r 2 r 2 n n 1 n n 0 r 2 r 2 r 2 0且 0 1 0且 0 1 0且 0r 2 n m n n m m m n m m n n r 2 r 2 r 2 r 2 r 2 r 2 m n m m n n S=A2*B2= r 2 r 2 r 2 r 2 r 2 r 2 n m n n m m r 2 1 1 0且 0 r 2 r 2 r 2 r 2 r 2 r 2 依据以上公式我们可以通过编程计算出要用多少个圆去掩盖矩形， 该求解该模型的思路和求解上一特例的思路一样， 即相邻两正方 形外接圆重合面积与上例一样 k%=18.15%5下用正六边形求解矩形区域掩盖问题二 以正六边形形为单位的对矩形区域进展掩盖的模型 II 〔 1〕模型的学问预备在满足完全掩盖矩形区域的条件下，使得所用圆个数最少，就要 充分利用每个圆掩盖的区域范围， 尽可能减小重叠局部。

为便于争辩， 考虑三个圆相交的状况，如图 1〔a〕中以 o1,o2,o3 为圆心的圆，我 们的目标是要使得他们之间相互重合局部面积到达最小，又从图1〔b〕 可以看出三圆重叠的面积比 1〔a 〕中更小6o1o2o2o1o3o3图 1〔a〕 图 1〔b〕定理 1：假设三个半径一样的圆两两相交且掩盖面积最大，那么三圆必 交于一点定理 2：假设三圆两两相交于一点并且三个圆心围成等边三角形，那么其掩盖面积最大图 2证明： 由定理 1 如图 2 设 O 为三个圆的交点， 每个圆圆心到交点的距 离均为 r 三圆心必定在以 O 为圆心 r 为半径的圆周上要使得三圆掩盖面积最大，即求阴影局部S S S 最小又在同一圆中，必1 2 3有 AOB BO C CO A 2 ；1 2 32 r 扇形AOB 扇形BO C 扇形CO A= ；1 2 3设以上三个扇形总面积为 S，那么 S= r 2； S S S =S-六边形AOBO CO ；1 2 3 1 2 3 要使阴影局部面积最小，就要让六边形面积最大，也就是三角形面积最大。

要使得三角形面积最大，又由于O O O 共圆，所以三角形1 2 3为等边三角形时面积最大又从定理 2 可知当掩盖的面积最大时三圆心构成了等边三角形，7O5O4 IHO6D O10GO9EFO7O8图 3如图 3 所示EO F = ，由一个圆与六个一样半径的圆相交构成了10 3一个正六边形 如此相互掩盖就形成了以正六边形为单位的掩盖模 型由程序〔见附录 4 〕可得如以下图形：8从图可知用正六边形掩盖正方形区域共需 45 个此时相邻两正六边形外接圆重合面积为 S1 如以下图所示s 2 1 r2 3 r2 s r 21 6 4 。