Go语言视频零基础入门到精通

javalearner

问题：
设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。

1. 蛮力算法描述：
   
2. int ClosestPoints(int n, int x[ ], int y[ ]){
   
3.    minDist=Double.POSITIVE_INFINITY;;
   
4.    for (i=1; i< n; i++)
   
5.       for (j=i+1; j<=n; j++)
   
6.      {
   
7.          d=(x[i]-x[j])* (x[i]-x[j])+(y[i]-y[j])* (y[i]-y[j]);
   
8.          if (d< minDist) {
   
9.              minDist=d;
   
10.              index1=i;
    
11.              index2=j;
    
12.         }
    
13.       }
    
14.      return  minDist;
    
15. }

复制代码

程序：

1. import java.util.*;
   
2. public class ClosestPair1{
   
3. public static void main(String[] args)
   
4. {
   
5.   /**
   
6.    *输入需要比较的点的对数存在变量n中
   
7.    */
   
8.   Scanner in=new Scanner(System.in);
   
9.   System.out.println("How many pairs of points to compare?(有多少对点需要比较?)");
   
10.   int n=in.nextInt();
    
11.   
    
12.   int[] x=new int[n];
    
13.   int[] y=new int[n];
    
14.   /**
    
15.    *输入这些点的横坐标和纵坐标分别存储在x[n]和y[n]
    
16.    */
    
17.   System.out.println("Please enter these points,X-coordinate(请输入这些点,横坐标):");
    
18.   for(int i=0;i< n;i++)
    
19.   {
    
20.    x[i]=in.nextInt();
    
21.   }
    
22.   
    
23.   System.out.println("Please enter these points,Y-coordinate(请输入这些点,纵坐标):");
    
24.   for(int i=0;i< n;i++)
    
25.   {
    
26.    y[i]=in.nextInt();
    
27.   }
    
28.   
    
29.   double minDist=Double.POSITIVE_INFINITY;
    
30.   double d;
    
31.   int indexI=0;
    
32.   int indexJ=0;
    
33.         /**
    
34.          *求解最近对距离存于minDist中
    
35.          */
    
36.         double startTime=System.currentTimeMillis();//startTime
    
37.   for(int i=0;i< n-1;i++)
    
38.   {
    
39.    for(int j=i+1;j< n;j++)
    
40.     {
    
41.      d=Math.sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    
42.      if(d< minDist)
    
43.      {
    
44.       minDist=d;
    
45.       indexI=i;
    
46.       indexJ=j;
    
47.      }      
    
48.     }
    
49.   }
    
50.   double endTime=System.currentTimeMillis();//endTime
    
51.   /**
    
52.    *打印输出最后求出的结果，最近的是哪两个点，以及最近距离和程序用的时间
    
53.    */
    
54.   System.out.println("The closest pair is:("+x[indexI]+","+y[indexI]+") and ("+x[indexJ]+","+y[indexJ]+")");
    
55.   System.out.println("The closest distance is "+minDist);
    
56.   System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!");
    
57. }
    
58. }

复制代码

运行：


分治算法 描述：
    可以划一条垂线，把点集分成两半：PL和PR。于是最近点对或者在PL中，或者在PR中，或者PL，PR各有一点。
把三种距离情况定义为dL, dR, dC.

     其中dL, dR可以递归求解，于是问题就变为计算dC。

设s=min(dL, dR). 通过观察能得出结论：如果dC<s,则只需计算dC。如果dC满足这样的条件，则决定dC的两点必然在分割线的s距离之内，称之为带（strip）
否则不可能满足dC<s, 于是缩小了需要考虑的点的范围。

1. 程序：
   
2. import java.util.*;
   
3. public class ClosestPair2
   
4. {
   
5. public static void main(String[] args)
   
6. {
   
7.   /**
   
8.    *输入需要比较的点的对数存在变量n中
   
9.    */
   
10.   Scanner in=new Scanner(System.in);
    
11.   System.out.println("How many pairs of points to compare?(有多少对点需要比较?)");
    
12.   int n=in.nextInt();
    
13.   /**
    
14.    *输入这些点的横坐标和纵坐标，存储在点数组S[n]中
    
15.    */
    
16.   System.out.println("Please enter these points,X-coordinate and Y-coordinate.(请输入这些点，x坐标和y坐标)：");
    
17.   Point[] S=new Point[n];
    
18.   
    
19.   double startTime=System.currentTimeMillis();//starttime
    
20.   
    
21.   for(int i=0;i< n;i++)
    
22.   {
    
23.    int x=in.nextInt();
    
24.    int y=in.nextInt();
    
25.    S[i]=new Point(x,y);
    
26.    System.out.println("("+S[i].getX()+","+S[i].getY()+")");
    
27.   }
    
28.   
    
29.   /**
    
30.    *求出这点的x坐标的中位数mid
    
31.    */
    
32.   int minX=(int)Double.POSITIVE_INFINITY;
    
33.   int maxX=(int)Double.NEGATIVE_INFINITY;
    
34.   for(int i=0;i< n;i++)
    
35.   {
    
36.    if(S[i].getX()< minX)
    
37.     minX=S[i].getX();
    
38.    if(S[i].getX()>maxX)
    
39.     maxX=S[i].getX();
    
40.   }
    
41.   
    
42.   int mid=(minX+maxX)/2;
    
43.   /**
    
44.    *以mid为界把S中的点分为两组分别存放在范型数组列表point1和point2中
    
45.    */
    
46.   ArrayList
47.    
48.       point1=new ArrayList
49.      
50.       ();
    
51.   ArrayList
52.       
53.         point2=new ArrayList
54.       
55.         ();
    
56.   for(int i=0;i< n;i++)
    
57.   {
    
58.    if(S[i].getX()<=mid)
    
59.     point1.add(S[i]);
    
60.    else
    
61.     point2.add(S[i]);
    
62.   }
    
63.   
    
64.   /**
    
65.    *将范型数组列表转换为数组类型S1和S2
    
66.    */
    
67.      Point[] S1=new Point[point1.size()];
    
68.      Point[] S2=new Point[point2.size()];
    
69.      point1.toArray(S1);
    
70.      point2.toArray(S2);
    
71.          
    
72.   /**
    
73.    *将S1和S2中的点按x 坐标升序排列
    
74.    */
    
75.   sortX(S1);
    
76.   sortX(S2);
    
77.   
    
78.   /**
    
79.    *打印输出排序后S1和S2的点
    
80.    */
    
81.   System.out.print("The points in S1 are:");
    
82.   for(int i=0;i< S1.length;i++)
    
83.    System.out.print("("+S1[i].getX()+","+S1[i].getY()+") ");
    
84.   System.out.println();
    
85.   System.out.print("The points in S2 are:");
    
86.   for(int i=0;i< S2.length;i++)
    
87.    System.out.print("("+S2[i].getX()+","+S2[i].getY()+") ");
    
88.   System.out.println();
    
89.   
    
90.   /**
    
91.    *求S1中点的最近对及其距离并打印输出结果
    
92.    */
    
93.   double minDist1=Double.POSITIVE_INFINITY;
    
94.   int indexI1=0;
    
95.   int indexJ1=0;
    
96.   for(int i=0;i< S1.length-1;i++)
    
97.    {
    
98.     for(int j=i+1;j< S1.length;j++)
    
99.      {
    
100.       double d=Math.sqrt(Math.pow((S1[i].getX()-S1[j].getX()),2)+Math.pow((S1[i].getY()-S1[j].getY()),2));
     
101.       if(d< minDist1)
     
102.        {
     
103.         minDist1=d;
     
104.         indexI1=i;
     
105.         indexJ1=j;
     
106.        }      
     
107.      }
     
108.    }
     
109.    
     
110.   System.out.println("The closest pair in S1 is: "+"("+S1[indexI1].getX()+","+S1[indexI1].getY()+")"+
     
111.    "and("+S1[indexJ1].getX()+","+S1[indexJ1].getY()+")"+",and the distance is "+minDist1);
     
112.   /**
     
113.    *求S2中点的最近对及其距离并打印输出结果
     
114.    */
     
115.   double minDist2=Double.POSITIVE_INFINITY;
     
116.   int indexI2=0;
     
117.   int indexJ2=0;
     
118.   for(int i=0;i< S2.length-1;i++)
     
119.    {
     
120.     for(int j=i+1;j< S2.length;j++)
     
121.      {
     
122.       double d=Math.sqrt(Math.pow((S2[i].getX()-S2[j].getX()),2)+Math.pow((S2[i].getY()-S2[j].getY()),2));
     
123.       if(d< minDist2)
     
124.        {
     
125.         minDist2=d;
     
126.         indexI2=i;
     
127.         indexJ2=j;
     
128.        }      
     
129.      }
     
130.    }
     
131.   System.out.println("The closest pair in S2 is: "+"("+S2[indexI2].getX()+","+S2[indexI2].getY()+")"+
     
132.    "and("+S2[indexJ2].getX()+","+S2[indexJ2].getY()+")"+",and the distance is "+minDist2);
     
133.   
     
134.   double d1=Math.min(minDist1,minDist2);
     
135.   /**
     
136.    *在S1,S2中收集距离中线两侧小于dl的点，分别存在P1[]和P2[]中
     
137.    */
     
138.   ArrayList< Point> pp1=new ArrayList< Point>();
     
139.   ArrayList< Point> pp2=new ArrayList< Point>();
     
140.   for(int i=0;i< S1.length;i++)
     
141.   {
     
142.    if((mid-S1[i].getX())< d1)
     
143.     pp1.add(S1[i]);
     
144.   }
     
145.   for(int i=0;i< S2.length;i++)
     
146.   {
     
147.    if((S2[i].getX()-mid)< d1)
     
148.     pp2.add(S2[i]);
     
149.   }
     
150.   
     
151.   Point[] P1=new Point[pp1.size()];
     
152.      Point[] P2=new Point[pp2.size()];
     
153.      pp1.toArray(P1);
     
154.      pp2.toArray(P2);
     
155.          
     
156.   /**
     
157.    *将P1和P2中的点按Y坐标升序排列
     
158.    */
     
159.   sortY(P1);
     
160.   sortY(P2);
     
161.   /**
     
162.    *求解P1和P2两者之间可能的最近对距离
     
163.    */
     
164.   double d2=Double.POSITIVE_INFINITY;
     
165.   for(int i=0;i< P1.length;i++)
     
166.   {
     
167.    for(int j=0;j< P2.length;j++)
     
168.    {
     
169.     if(Math.abs(P1[i].getY()-P2[j].getY())< d1)
     
170.     {
     
171.      double temp=Math.sqrt(Math.pow((P1[i].getX()-P2[j].getX()),2)+Math.pow((P1[i].getX()-P2[j].getX()),2));
     
172.      if(temp< d2)
     
173.       d2=temp;   
     
174.     }   
     
175.    }
     
176.   }
     
177.   
     
178.   double endTime=System.currentTimeMillis();//endtime
     
179.   /**
     
180.    *打印输出最后求出的结果，最近的是哪两个点，以及最近距离和程序用的时间
     
181.    */
     
182.   System.out.print("The points in P1 are:");
     
183.   for(int i=0;i< P1.length;i++)
     
184.    System.out.print("("+P1[i].getX()+","+P1[i].getY()+") ");
     
185.   System.out.println();
     
186.   System.out.print("The points in P2 are:");
     
187.   for(int i=0;i< P2.length;i++)
     
188.    System.out.print("("+P2[i].getX()+","+P2[i].getY()+") ");
     
189.   System.out.println();
     
190.   System.out.println("d2="+d2);
     
191.   double minDist=Math.min(d1,d2);
     
192.   System.out.println("The closest distance is "+minDist);
     
193.   
     
194.   System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!");  
     
195. }
     
196. /**
     
197.   *设计按点Point的x坐标升序排列的函数sortX
     
198.   */
     
199. public static void sortX(Point[] p)
     
200. {
     
201.   for(int i=0;i< p.length-1;i++)
     
202.   {
     
203.    for(int j=0;j< p.length-1-i;j++)
     
204.    {
     
205.     if(p[j].getX()>p[j+1].getX())
     
206.     {
     
207.      int t=p[j].getX();
     
208.      p[j].setX(p[j+1].getX());
     
209.      p[j+1].setX(t);
     
210.      
     
211.      int n=p[j].getY();
     
212.      p[j].setY(p[j+1].getY());
     
213.      p[j+1].setY(n);
     
214.     }
     
215.    }
     
216.   }
     
217. }
     
218. /**
     
219.   *设计按点Point的y坐标升序排列的函数sortY
     
220.   */
     
221. public static void sortY(Point[] p)
     
222. {
     
223.   for(int i=0;i< p.length-1;i++)
     
224.   {
     
225.    for(int j=0;j< p.length-1-i;j++)
     
226.    {
     
227.     if(p[j].getY()>p[j+1].getY())
     
228.     {
     
229.      int t=p[j].getY();
     
230.      p[j].setY(p[j+1].getY());
     
231.      p[j+1].setY(t);
     
232.      
     
233.      int n=p[j].getX();
     
234.      p[j].setX(p[j+1].getX());
     
235.      p[j+1].setX(n);
     
236.     }
     
237.    }
     
238.   }
     
239. }
     
240. }
     
241. /**
     
242. * 建立自己的类Point
     
243. */
     
244. class Point implements Cloneable
     
245. {
     
246. public Point()
     
247. {
     
248.   x=0;
     
249.   y=0;
     
250. }
     
251. 
     
252. public Point(int x,int y)
     
253. {
     
254.   this.x=x;
     
255.   this.y=y;
     
256. }
     
257. 
     
258. public void setX(int x)
     
259. {
     
260.   this.x=x;
     
261. }
     
262. 
     
263. public void setY(int y)
     
264. {
     
265.   this.y=y;
     
266. }
     
267. 
     
268. public int getX()
     
269. {
     
270.   return x;
     
271. }
     
272. 
     
273. public int getY()
     
274. {
     
275.   return y;
     
276. }
     
277.   
     
278. private int x;
     
279. private int y;
     
280. }
281.       
282.       
283.      
284.    

复制代码

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/25/000420531.zip