平面上n个点之间最近点对问题

  • w2_549856
    了解作者
  • 136.8KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-05-09 03:02
    上传日期
算法导论实验:利用分治法求平面上n个点最近点对问题,压缩包内附python源代码和实验报告以及详细时间复杂度分析。
csdn-平面上n个点之间最近点对问题.zip
  • csdn-平面上n个点之间最近点对问题.doc
    213KB
  • csdn-平面上n个点之间最近点对问题.py
    2.7KB
内容介绍
<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/627813c577d3727348f214dd/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/627813c577d3727348f214dd/bg1.jpg"><div class="c x0 y1 w2 h2"><div class="t m0 x1 h3 y2 ff1 fs0 fc0 sc0 ls0 ws0">&#12298;&#31639;&#27861;&#35774;&#35745;&#19982;&#20998;&#26512;&#12299;&#19978;&#26426;&#25253;&#21578;</div><div class="t m0 x2 h4 y3 ff1 fs1 fc0 sc1 ls0 ws0">&#22995;&#21517;&#65306;</div><div class="t m0 x3 h5 y4 ff2 fs1 fc0 sc1 ls0 ws0">*</div><div class="t m0 x4 h4 y3 ff1 fs1 fc0 sc1 ls0 ws0">&#23398;&#21495;&#65306;</div><div class="t m0 x5 h5 y4 ff2 fs1 fc0 sc1 ls0 ws0">*</div><div class="t m0 x6 h4 y3 ff1 fs1 fc0 sc1 ls0 ws0">&#26085;&#26399;&#65306;</div><div class="t m0 x7 h5 y4 ff2 fs1 fc0 sc1 ls0 ws0">2019.1<span class="_ _0"></span>1.09</div><div class="t m0 x2 h4 y5 ff1 fs1 fc0 sc1 ls0 ws0">&#19978;&#26426;&#39064;</div><div class="t m0 x8 h4 y6 ff1 fs1 fc0 sc1 ls0 ws0">&#30446;&#65306;</div><div class="t m0 x9 h4 y7 ff1 fs1 fc0 sc1 ls0 ws0">&#27714;&#24179;&#38754;&#19978;<span class="_ _1"> </span><span class="ff2">n<span class="_ _1"> </span></span>&#20010;&#39030;&#28857;&#30340;&#26368;&#36817;&#28857;&#23545;&#38382;&#39064;</div><div class="t m0 xa h4 y8 ff1 fs1 fc0 sc1 ls0 ws0">&#23454;&#39564;&#29615;&#22659;&#65306;</div><div class="t m0 xa h4 y9 ff2 fs1 fc0 sc1 ls0 ws0">CPU<span class="ff1">&#65306;</span>Intel Core i5-7200U @2.50GHz 2.70GHz ; </div><div class="t m0 xa h4 ya ff1 fs1 fc0 sc1 ls0 ws0">&#20869;&#23384;<span class="ff2">:16G; </span>&#25805;&#20316;&#31995;&#32479;&#65306;<span class="ff2">Window10 </span>&#20225;&#19994;&#29256;<span class="ff2"> 1903; </span>&#36719;&#20214;&#24179;&#21488;&#65306;<span class="ff2">python3.6.5 ;</span></div><div class="t m0 xa h4 yb ff1 fs1 fc0 sc0 ls0 ws0">&#19968;&#12289;&#31639;&#27861;&#35774;&#35745;&#19982;&#20998;&#26512;&#65306;</div><div class="t m0 xa h4 yc ff1 fs1 fc0 sc1 ls0 ws0">&#39064;&#30446;&#19968;&#65306;&#27714;&#24179;&#38754;&#19978;<span class="_ _1"> </span><span class="ff2">n<span class="_ _1"> </span></span>&#20010;&#39030;&#28857;&#30340;&#26368;&#36817;&#28857;&#23545;&#38382;&#39064;</div><div class="t m0 xa h4 yd ff1 fs1 fc0 sc1 ls0 ws0">&#32473;<span class="_ _2"></span>&#20986;<span class="_ _2"></span>&#20108;<span class="_ _2"></span>&#32500;&#24179;<span class="_ _2"></span>&#38754;<span class="_ _2"></span>&#19978;<span class="_ _3"> </span><span class="ff2">n<span class="_ _4"> </span></span>&#20010;<span class="_ _2"></span>&#28857;<span class="_ _2"></span>&#30340;<span class="_ _2"></span>&#22352;&#26631;<span class="_ _5"></span><span class="ff2"> <span class="_ _2"></span>(x</span></div><div class="t m0 xb h6 ye ff2 fs2 fc0 sc1 ls0 ws0">i</div><div class="t m0 xc h5 yd ff2 fs1 fc0 sc1 ls0 ws0">, <span class="_ _2"></span>y</div><div class="t m0 xd h6 ye ff2 fs2 fc0 sc1 ls0 ws0">i</div><div class="t m0 xe h4 yd ff2 fs1 fc0 sc1 ls0 ws0">)<span class="_ _2"></span><span class="ff1">&#65292;<span class="_ _2"></span>&#35774;&#35745;<span class="_ _2"></span>&#19968;<span class="_ _2"></span>&#20010;<span class="_ _2"></span>&#31639;<span class="_ _2"></span>&#27861;<span class="_ _2"></span>&#25214;<span class="_ _2"></span>&#20986;<span class="_ _2"></span>&#36825;&#20123;<span class="_ _2"></span>&#28857;<span class="_ _2"></span>&#20013;<span class="_ _2"></span>&#36317;<span class="_ _2"></span>&#31163;<span class="_ _2"></span>&#26368;<span class="_ _2"></span>&#36817;<span class="_ _2"></span>&#30340;</span></div><div class="t m0 xa h4 yf ff1 fs1 fc0 sc1 ls0 ws0">&#20004;&#28857;&#22352;&#26631;&#65292;&#24182;&#27714;&#20986;&#36317;&#31163;&#12290;</div><div class="t m0 xa h4 y10 ff1 fs1 fc0 sc0 ls0 ws0">&#20108;&#12289;&#26680;&#24515;&#20195;&#30721;&#65306;</div><div class="t m0 xa h4 y11 ff1 fs1 fc0 sc0 ls0 ws0">&#39064;&#30446;&#19968;&#65306;</div><div class="t m0 xa h4 y12 ff1 fs1 fc0 sc1 ls0 ws0">&#31639;&#27861;&#24605;&#24819;&#65306;&#20998;&#27835;&#27861;</div><div class="t m0 xf h4 y13 ff2 fs1 fc0 sc1 ls0 ws0">1.<span class="_ _6"> </span><span class="ff1">&#20998;<span class="_ _2"></span>&#21035;&#23558;<span class="_ _2"></span>&#28857;&#38598;<span class="_ _2"></span>&#20381;<span class="_ _2"></span>&#25454;&#27178;<span class="_ _2"></span>&#22352;<span class="_ _2"></span>&#26631;&#20174;<span class="_ _2"></span>&#23567;&#21040;<span class="_ _2"></span>&#22823;<span class="_ _2"></span>&#21644;&#32437;<span class="_ _2"></span>&#22352;<span class="_ _2"></span>&#26631;&#20174;<span class="_ _2"></span>&#23567;&#21040;<span class="_ _2"></span>&#22823;<span class="_ _2"></span>&#36827;&#34892;<span class="_ _2"></span>&#25490;<span class="_ _2"></span>&#24207;&#24471;<span class="_ _2"></span>&#21040;&#25968;<span class="_ _2"></span>&#32452;<span class="_ _7"> </span></span>X</div><div class="t m0 x10 h4 y14 ff1 fs1 fc0 sc1 ls0 ws0">&#21644;<span class="_ _1"> </span><span class="ff2">Y</span>&#65307;</div><div class="t m0 xf h4 y15 ff2 fs1 fc0 sc1 ls0 ws0">2.<span class="_ _6"> </span><span class="ff1">&#26681;<span class="_ _8"></span>&#25454;<span class="_ _8"></span>&#26377;<span class="_ _8"></span>&#24207;<span class="_ _8"></span>&#25968;<span class="_ _8"></span>&#32452;<span class="_ _7"> </span></span>X<span class="_ _9"></span><span class="ff1">&#65292;<span class="_ _8"></span>&#25214;<span class="_ _9"></span>&#21040;<span class="_ _8"> </span>&#22402;<span class="_ _8"></span>&#30452;<span class="_ _8"></span>&#20110;<span class="_ _7"> </span></span>x<span class="_ _7"> </span><span class="ff1">&#36724;<span class="_ _8"></span>&#30340;<span class="_ _8"></span>&#30452;<span class="_ _9"></span>&#32447;<span class="_ _7"> </span></span>x=l<span class="_ _7"> </span><span class="ff1">&#23558;<span class="_ _8"> </span>&#28857;<span class="_ _8"></span>&#38598;<span class="_ _8"></span>&#22343;<span class="_ _9"></span>&#20998;<span class="_ _8"> </span>&#20026;<span class="_ _8"></span>&#20004;<span class="_ _8"></span>&#37096;<span class="_ _8"></span>&#20998;</span></div><div class="t m0 x10 h4 y16 ff2 fs1 fc0 sc1 ls0 ws0">X_l,X_r<span class="ff1">&#65307;</span></div><div class="t m0 xf h4 y17 ff2 fs1 fc0 sc1 ls0 ws0">3.<span class="_ _6"> </span><span class="ff1">&#26681;&#25454;<span class="_ _1"> </span></span>X_l,X_r<span class="_ _1"> </span><span class="ff1">&#23558;<span class="_ _1"> </span></span>Y<span class="_ _1"> </span><span class="ff1">&#25968;&#32452;&#20063;&#23545;&#24212;&#30340;&#20998;&#20026;&#20004;&#37096;&#20998;&#65292;</span>Y_l,Y_r<span class="ff1">&#65307;</span></div><div class="t m0 xf h4 y18 ff2 fs1 fc0 sc1 ls0 ws0">4.<span class="_ _6"> </span><span class="ff1">&#20998;&#21035;<span class="_ _2"></span>&#23545;&#24038;<span class="_ _2"></span>&#36793;&#28857;<span class="_ _2"></span>&#38598;&#21644;<span class="_ _2"></span>&#21491;&#36793;<span class="_ _2"></span>&#28857;&#38598;<span class="_ _2"></span>&#27714;&#26368;<span class="_ _2"></span>&#23567;&#36317;<span class="_ _2"></span>&#31163;<span class="_ _a"> </span><span class="ff3">&#948;</span></span></div><div class="t m0 x11 h6 y19 ff2 fs2 fc0 sc1 ls0 ws0">1</div><div class="t m0 x12 h4 y18 ff1 fs1 fc0 sc1 ls0 ws0">&#65292;<span class="ff3">&#948;</span></div><div class="t m0 x13 h6 y19 ff2 fs2 fc0 sc1 ls0 ws0">2</div><div class="t m0 x14 h4 y18 ff1 fs1 fc0 sc1 ls0 ws0">&#65292;&#24182;<span class="_ _2"></span>&#36820;&#22238;<span class="_ _2"></span>&#26368;&#23567;<span class="_ _2"></span>&#36317;&#31163;<span class="_ _2"></span>&#30340;&#20004;<span class="_ _2"></span>&#28857;</div><div class="t m0 x10 h4 y1a ff1 fs1 fc0 sc1 ls0 ws0">&#22352;&#26631;&#65307;</div><div class="t m0 xf h4 y1b ff2 fs1 fc0 sc1 ls0 ws0">5.<span class="_ _6"> </span><span class="ff1">&#20196;<span class="_ _4"> </span><span class="ff3">&#948;</span></span>=min(<span class="ff3">&#948;</span></div><div class="t m0 x15 h7 y1c ff3 fs2 fc0 sc1 ls0 ws0">1</div><div class="t m0 x16 h8 y1b ff3 fs1 fc0 sc1 ls0 ws0">, &#948;</div><div class="t m0 x17 h7 y1c ff3 fs2 fc0 sc1 ls0 ws0">2</div><div class="t m0 x18 h4 y1b ff2 fs1 fc0 sc1 ls0 ws0">)<span class="_ _2"></span><span class="ff1">&#65292;&#26500;<span class="_ _2"></span>&#36896;<span class="_ _1"> </span></span>Y<span class="_ _2"></span>&#8217;<span class="_ _b"></span> = <span class="_ _2"></span>{Point<span class="ff3">&#8712;</span>Y <span class="ff1">&#19988;<span class="_ _2"></span></span> Point.x<span class="_ _2"></span><span class="ff3">&#8712;</span>(l-<span class="ff3">&#948;,l+&#948;</span>)}<span class="ff1">&#65292;<span class="_ _2"></span>&#29616;<span class="_ _2"></span>&#22312;&#21482;<span class="_ _2"></span>&#38656;</span></div><div class="t m0 x10 h4 y1d ff1 fs1 fc0 sc1 ls0 ws0">&#20877;&#35745;&#31639;&#20986;<span class="_ _1"> </span><span class="ff2">Y&#8217;</span>&#20013;&#28857;&#30340;&#26368;&#36817;&#36317;&#31163;&#21363;&#21487;&#65292;&#32780;&#30001;&#20960;&#20309;&#30693;&#35782;&#19988;<span class="_ _a"> </span><span class="ff2">Y&#8217;</span>&#20013;&#28857;&#26159;&#25353;&#32437;&#22352;&#26631;&#26377;</div><div class="t m0 x10 h4 y1e ff1 fs1 fc0 sc1 ls0 ws0">&#24207;&#25490;<span class="_ _2"></span>&#21015;&#30340;&#65292;<span class="_ _2"></span>&#21482;&#38656;<span class="_ _2"></span>&#36941;&#21382;<span class="_ _4"> </span><span class="ff2">Y&#8217;<span class="_ _2"></span></span>&#20013;&#25152;&#26377;<span class="_ _2"></span>&#28857;&#65292;<span class="_ _2"></span>&#27599;&#20010;&#28857;&#27714;<span class="_ _2"></span>&#23427;&#19982;<span class="_ _2"></span>&#20854;&#21518;&#38754;<span class="_ _a"> </span><span class="ff2">7<span class="_ _1"> </span></span>&#20010;&#28857;<span class="_ _2"></span>&#30340;&#36317;&#31163;<span class="_ _2"></span>&#21363;</div><div class="t m0 x10 h4 y1f ff1 fs1 fc0 sc1 ls0 ws0">&#21487;&#65292;&#24471;&#21040;&#26368;&#23567;&#36317;&#31163;<span class="_ _1"> </span><span class="ff3">&#948;</span></div><div class="t m0 x19 h7 y20 ff3 fs2 fc0 sc1 ls0 ws0">3 </div><div class="t m0 x9 h4 y1f ff1 fs1 fc0 sc1 ls0 ws0">&#21644;&#26368;&#23567;&#36317;&#31163;&#20004;&#28857;&#22352;&#26631;&#65307;</div><div class="t m0 xf h4 y21 ff2 fs1 fc0 sc1 ls0 ws0">6.<span class="_ _6"> </span><span class="ff1">&#27604;&#36739;<span class="_ _1"> </span><span class="ff3">&#948;</span></span></div><div class="t m0 x1a h7 y22 ff3 fs2 fc0 sc1 ls0 ws0">1</div><div class="t m0 x1b h4 y21 ff1 fs1 fc0 sc1 ls0 ws0">&#65292;<span class="ff3">&#948;</span></div><div class="t m0 x1c h7 y22 ff3 fs2 fc0 sc1 ls0 ws0">2</div><div class="t m0 x1d h4 y21 ff1 fs1 fc0 sc1 ls0 ws0">&#65292;<span class="ff3">&#948;</span></div><div class="t m0 x1e h7 y22 ff3 fs2 fc0 sc1 ls0 ws0">3</div><div class="t m0 x1f h4 y21 ff1 fs1 fc0 sc1 ls0 ws0">&#65292;&#21462;&#26368;&#23567;&#20540;&#21363;&#20026;&#25152;&#27714;&#30340;&#32467;&#26524;&#65292;&#21516;&#26102;&#36755;&#20986;&#23545;&#24212;&#20004;&#28857;&#65307;</div><div class="t m0 xf h4 y23 ff3 fs1 fc0 sc1 ls0 ws0">7.<span class="_ _c"> </span><span class="ff1">&#36882;&#24402;&#30340;&#20013;&#27490;&#26465;&#20214;&#26159;&#24403;&#28857;&#38598;&#20013;&#21482;&#26377;&#19968;&#20010;&#28857;&#26102;&#12290;</span></div><div class="t m0 xa h4 y24 ff1 fs1 fc0 sc1 ls0 ws0">&#26680;&#24515;&#20195;&#30721;&#35828;&#26126;&#65306;</div><div class="t m0 xf h4 y25 ff2 fs1 fc0 sc1 ls0 ws0">1.<span class="_ _6"> </span><span class="ff1">&#25968;&#25454;&#32467;&#26500;&#65306;</span></div><div class="t m0 x10 h4 y26 ff2 fs1 fc0 sc1 ls0 ws0">p1,p2: <span class="ff1">&#29992;&#20110;&#23384;&#25918;&#26368;&#32456;&#32467;&#26524;&#30340;&#20004;&#20010;&#28857;&#65307;</span></div><div class="t m0 x10 h4 y27 ff2 fs1 fc0 sc1 ls0 ws0">l: <span class="ff1">&#21010;&#20998;&#24038;&#21491;&#28857;&#38598;&#30340;&#30452;&#32447;<span class="_ _1"> </span></span>x=l<span class="ff1">&#65307;</span></div><div class="t m0 x10 h4 y28 ff2 fs1 fc0 sc1 ls0 ws0">x_l,<span class="_ _2"></span> <span class="_ _2"></span>x_r<span class="_ _0"></span>,<span class="_ _2"></span> <span class="_ _2"></span>y_l,<span class="_ _2"></span> <span class="_ _2"></span>y_r<span class="_ _2"></span>: <span class="_ _d"> </span><span class="ff1">&#23558;<span class="_ _5"></span>&#28857;<span class="_ _9"></span>&#38598;<span class="_ _5"></span>&#21010;<span class="_ _9"></span>&#20998;<span class="_ _5"></span>&#20026;<span class="_ _9"></span>&#24038;<span class="_ _2"></span>&#21491;<span class="_ _9"></span>&#38598;<span class="_ _5"></span>&#21512;<span class="_ _9"></span>&#21518;<span class="_ _5"></span>&#23545;<span class="_ _9"></span>&#24212;<span class="_ _5"></span>&#30340;<span class="_ _7"> </span></span>x<span class="_ _9"></span><span class="ff1">&#65292;<span class="_ _5"></span></span>y<span class="_ _a"> </span><span class="ff1">&#38598;<span class="_ _5"></span>&#21512;<span class="_ _9"></span>&#30340;<span class="_ _5"></span>&#24038;<span class="_ _9"></span>&#21491;<span class="_ _5"></span>&#21010;</span></div><div class="t m0 x10 h4 y29 ff1 fs1 fc0 sc1 ls0 ws0">&#20998;&#65307;</div><div class="t m0 x10 h4 y2a ff2 fs1 fc0 sc1 ls0 ws0">delta1, poi1, poi2: <span class="ff1">&#24038;&#36793;&#28857;&#38598;&#35745;&#31639;&#24471;&#21040;&#30340;&#26368;&#36817;&#36317;&#31163;&#20197;&#21450;&#23545;&#24212;&#30340;&#20004;&#28857;&#65307;</span></div><div class="t m0 x10 h4 y2b ff2 fs1 fc0 sc1 ls0 ws0">delta2, poin1, poin2: <span class="ff1">&#21491;&#36793;&#28857;&#38598;&#35745;&#31639;&#24471;&#21040;&#30340;&#26368;&#36817;&#36317;&#31163;&#20197;&#21450;&#23545;&#24212;&#30340;&#20004;&#28857;&#65307;</span></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>
评论
    相关推荐