# 实验2_分治法求最近点对问题.zip

• forget1
了解作者
• C/C++
开发工具
• 100KB
文件大小
• zip
文件格式
• 0
收藏次数
• 10 积分
下载积分
• 1
下载次数
• 2020-07-02 12:02
上传日期
1. 对于平面上给定的N个点，给出所有点对的最短距离，即，输入是平面上的N个点，输出是N点中具有最短距离的两点。 2. 要求随机生成N个点的平面坐标，应用蛮力法编程计算出所有点对的最短距离。 3. 要求随机生成N个点的平面坐标，应用分治法编程计算出所有点对的最短距离。

• 实验2_分治法求最近点对问题.docx
101.5KB

<html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta charset="utf-8"> <meta name="generator" content="pdf2htmlEX"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css"> <link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css"> <link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/626b76d21e41a87e8aa192ff/raw.css"> <script src="https://static.pudn.com/base/js/compatibility.min.js"></script> <script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script> <script> try{ pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({}); }catch(e){} </script> <title></title> </head> <body> <div id="sidebar" style="display: none"> <div id="outline"> </div> </div> <div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/626b76d21e41a87e8aa192ff/bg1.jpg"><div class="c x0 y1 w2 h2"><div class="t m0 x1 h3 y2 ff1 fs0 fc0 sc0 ls0 ws0">&#23454;&#39564;&#20108; &#20998;&#27835;&#27861;&#27714;&#26368;&#36817;&#28857;&#23545;&#38382;&#39064;</div><div class="t m0 x2 h3 y3 ff1 fs0 fc0 sc0 ls0 ws0">&#19968;&#12289;&#23454;&#39564;&#30446;&#30340;&#65306;</div><div class="t m0 x2 h4 y4 ff1 fs1 fc0 sc1 ls0 ws0">&#65288;<span class="ff2">1</span>&#65289;<span class="_ _0"></span>&#25484;&#25569;&#20998;&#27835;&#27861;&#24605;&#24819;&#12290;</div><div class="t m0 x2 h4 y5 ff1 fs1 fc0 sc1 ls0 ws0">&#65288;<span class="ff2">2</span>&#65289;<span class="_ _0"></span>&#23398;&#20250;&#26368;&#36817;&#28857;&#23545;&#38382;&#39064;&#27714;&#35299;&#26041;&#27861;&#12290;</div><div class="t m0 x2 h3 y6 ff1 fs0 fc0 sc0 ls0 ws0">&#20108;&#12289;&#20869;&#23481;&#65306;</div><div class="t m0 x2 h4 y7 ff2 fs1 fc0 sc1 ls0 ws0">1. <span class="ff1">&#23545;&#20110;&#24179;&#38754;&#19978;&#32473;&#23450;&#30340;<span class="_ _1"> </span></span>N<span class="_"> </span><span class="ff1">&#20010;&#28857;&#65292;&#32473;&#20986;&#25152;&#26377;&#28857;&#23545;&#30340;&#26368;&#30701;&#36317;&#31163;&#65292;&#21363;&#65292;&#36755;&#20837;&#26159;&#24179;&#38754;&#19978;&#30340;<span class="_ _2"> </span></span>N<span class="_"> </span><span class="ff1">&#20010;&#28857;&#65292;&#36755;</span></div><div class="t m0 x2 h4 y8 ff1 fs1 fc0 sc1 ls0 ws0">&#20986;&#26159;<span class="_ _2"> </span><span class="ff2">N<span class="_"> </span></span>&#28857;&#20013;&#20855;&#26377;&#26368;&#30701;&#36317;&#31163;&#30340;&#20004;&#28857;&#12290;</div><div class="t m0 x2 h4 y9 ff2 fs1 fc0 sc1 ls0 ws0">2. <span class="ff1">&#35201;&#27714;&#38543;&#26426;&#29983;&#25104;<span class="_ _1"> </span></span>N<span class="_"> </span><span class="ff1">&#20010;&#28857;&#30340;&#24179;&#38754;&#22352;&#26631;&#65292;&#24212;&#29992;&#34542;&#21147;&#27861;&#32534;&#31243;&#35745;&#31639;&#20986;&#25152;&#26377;&#28857;&#23545;&#30340;&#26368;&#30701;&#36317;&#31163;&#12290;</span></div><div class="t m0 x2 h4 ya ff2 fs1 fc0 sc1 ls0 ws0">3. <span class="ff1">&#35201;&#27714;&#38543;&#26426;&#29983;&#25104;<span class="_ _1"> </span></span>N<span class="_"> </span><span class="ff1">&#20010;&#28857;&#30340;&#24179;&#38754;&#22352;&#26631;&#65292;&#24212;&#29992;&#20998;&#27835;&#27861;&#32534;&#31243;&#35745;&#31639;&#20986;&#25152;&#26377;&#28857;&#23545;&#30340;&#26368;&#30701;&#36317;&#31163;&#12290;</span></div><div class="t m0 x2 h4 yb ff2 fs1 fc0 sc1 ls0 ws0">4. <span class="ff1">&#20998;&#21035;&#23545;<span class="_ _1"> </span></span>N=100,1000,10000,100000<span class="ff1">&#65292;&#32479;&#35745;&#31639;&#27861;&#36816;&#34892;&#26102;&#38388;&#65292;&#27604;&#36739;&#29702;&#35770;&#25928;&#29575;&#19982;&#23454;&#27979;&#25928;&#29575;&#30340;&#24046;&#24322;&#65292;</span></div><div class="t m0 x2 h4 yc ff1 fs1 fc0 sc1 ls0 ws0">&#21516;&#26102;&#23545;&#34542;&#21147;&#27861;&#21644;&#20998;&#27835;&#27861;&#30340;&#31639;&#27861;&#25928;&#29575;&#36827;&#34892;&#20998;&#26512;&#21644;&#27604;&#36739;&#12290;</div><div class="t m0 x2 h4 yd ff2 fs1 fc0 sc1 ls0 ws0">5. <span class="ff1">&#22914;&#26524;&#33021;&#23558;&#31639;&#27861;&#25191;&#34892;&#36807;&#31243;&#21033;&#29992;&#22270;&#24418;&#30028;&#38754;&#36755;&#20986;&#65292;&#21487;&#33719;&#21152;&#20998;&#12290;</span></div><div class="t m0 x2 h3 ye ff1 fs0 fc0 sc0 ls0 ws0">&#19977;&#12289;&#31639;&#27861;&#24605;&#24819;&#25552;&#31034;</div><div class="t m0 x2 h4 yf ff2 fs1 fc0 sc1 ls0 ws0">1. <span class="ff1">&#39044;&#22788;&#29702;&#65306;&#26681;&#25454;&#36755;&#20837;&#28857;&#38598;<span class="_ _1"> </span></span>S<span class="_ _1"> </span><span class="ff1">&#20013;&#30340;<span class="_ _2"> </span></span>x<span class="_"> </span><span class="ff1">&#36724;&#21644;<span class="_ _2"> </span></span>y<span class="_"> </span><span class="ff1">&#36724;&#22352;&#26631;&#36827;&#34892;&#25490;&#24207;&#65292;&#24471;&#21040;<span class="_ _2"> </span></span>X<span class="_"> </span><span class="ff1">&#21644;<span class="_ _2"> </span></span>Y<span class="_ _3"></span>,<span class="ff1">&#24456;&#26174;&#28982;&#27492;&#26102;<span class="_ _2"> </span></span>X<span class="_"> </span><span class="ff1">&#21644;<span class="_ _1"> </span></span>Y<span class="_ _2"> </span><span class="ff1">&#20013;</span></div><div class="t m0 x2 h4 y10 ff1 fs1 fc0 sc1 ls0 ws0">&#30340;&#28857;&#23601;&#26159;<span class="_ _2"> </span><span class="ff2">S<span class="_"> </span></span>&#20013;&#30340;&#28857;&#12290;</div><div class="t m0 x2 h4 y11 ff2 fs1 fc0 sc1 ls0 ws0">2. <span class="ff1">&#28857;&#25968;&#36739;&#23569;&#26102;&#30340;&#24773;&#24418;</span></div><div class="t m0 x2 h4 y12 ff2 fs1 fc0 sc1 ls0 ws0">3. <span class="ff1">&#28857;&#25968;</span>|S|&gt;3<span class="_"> </span><span class="ff1">&#26102;&#65292;&#23558;&#24179;&#38754;&#28857;&#38598;<span class="_ _2"> </span></span>S<span class="_"> </span><span class="ff1">&#20998;&#21106;&#25104;&#20026;&#22823;&#23567;&#22823;&#33268;&#30456;&#31561;&#30340;&#20004;&#20010;&#23376;&#38598;<span class="_ _2"> </span></span>S</div><div class="t m0 x3 h5 y13 ff2 fs2 fc0 sc1 ls0 ws0">L</div><div class="t m0 x4 h4 y12 ff1 fs1 fc0 sc1 ls0 ws0">&#21644;<span class="_ _2"> </span><span class="ff2">S</span></div><div class="t m0 x5 h5 y13 ff2 fs2 fc0 sc1 ls0 ws0">R</div><div class="t m0 x6 h4 y12 ff1 fs1 fc0 sc1 ls0 ws0">&#65292;&#36873;&#21462;&#19968;&#20010;&#22402;&#30452;</div><div class="t m0 x2 h4 y14 ff1 fs1 fc0 sc1 ls0 ws0">&#32447;<span class="_ _2"> </span><span class="ff2">L<span class="_"> </span></span>&#20316;&#20026;&#20998;&#21106;&#30452;&#32447;&#65292;&#32771;&#34385;<span class="_ _2"> </span><span class="ff2">X</span></div><div class="t m0 x7 h5 y15 ff2 fs2 fc0 sc1 ls0 ws0">L</div><div class="t m0 x8 h4 y14 ff1 fs1 fc0 sc1 ls0 ws0">&#21644;<span class="_ _2"> </span><span class="ff2">X</span></div><div class="t m0 x9 h5 y15 ff2 fs2 fc0 sc1 ls0 ws0">R</div><div class="t m0 xa h4 y14 ff1 fs1 fc0 sc1 ls0 ws0">&#65292;<span class="ff2">Y</span></div><div class="t m0 xb h5 y15 ff2 fs2 fc0 sc1 ls0 ws0">L</div><div class="t m0 xc h4 y14 ff1 fs1 fc0 sc1 ls0 ws0">&#21644;<span class="_ _2"> </span><span class="ff2">Y</span></div><div class="t m0 xd h5 y15 ff2 fs2 fc0 sc1 ls0 ws0">R</div><div class="t m0 xe h4 y14 ff1 fs1 fc0 sc1 ls0 ws0">&#65292;&#36825;&#37324;&#36824;&#38656;&#35201;&#25490;&#24207;&#21527;&#65311;</div></div></div><div class="pi" data-data='{"ctm":[1.611850,0.000000,0.000000,1.611850,0.000000,0.000000]}'></div></div> </body> </html>

• du零度 2021-04-14 23:38:35
啥也没有，，，，