算法设计与分析 ------最近对问题与8枚硬币问题

利用减治法实现8枚硬币问题：

参考资料：http://blog.csdn.net/wwj_748/article/details/8863503 算法设计--八枚硬币问题

 1 #include "stdafx.h"
 2 #include <iostream>
 3 #include <stdio.h>
 4 using namespace std;
 5 
 6 
 7 void eightcoin(int arr[]);
 8 void compare(int a,int b,int real,int index1,int index2);//这句话是为了在两个当中比较谁真，谁假。
 9 void print(int jia,int zhen,int i);//这句话是为了输出在某个位置的假硬币的信息。
10 int main()
11 {
12     int arr[8];
13     //分别输入8枚硬币的重量
14     while(1)
15     {
16         for(int i=0; i<8; ++i)
17         {
18             cin >> arr[i];
19         }
20         eightcoin(arr);
21     }    
22     return 0;
23 }
24 void eightcoin(int arr[])
25 {
26     int abc = arr[0] + arr[1] + arr[2];
27     int def = arr[3] + arr[4] + arr[5];
28     int a = arr[0];
29     int b = arr[1];
30     int c = arr[2];
31     int d = arr[3];
32     int e = arr[4];
33     int f = arr[5];
34     int g = arr[6];
35     int h = arr[7];
36 
37     if (abc > def) //6枚硬币必有一枚假币，g,h为真币 
38     {
39         if ((a+e) > (d+b))//去掉c,f，且b，e互换后，没有引起天平变化，说明假币必然是a，d中的一个  
40         {
41             compare(a,d,g,0,3);
42         }
43         else if ((a+e) == (d+b))
44         {
45             compare(c,f,g,2,5);
46         }
47         else 
48         {
49             compare(b,e,g,1,4);
50         }
51     }
52     else if (abc == def)
53     {
54             compare(g,h,a,6,7);   
55     }
56     else
57     {
58         if ((a+e) > (d+b))
59         {
60             compare(b,e,g,1,4);
61         }
62         else if ((a+e) == (d+b))
63         {
64             compare(c,f,g,2,5);
65         }
66         else 
67         {
68             compare(a,d,g,0,3);
69         }
70     }
71 }
72 
73 
74 
75 void compare(int a,int b,int real,int index1,int index2)
76 {
77     if( a > real)
78         print(a,real,index1);
79     else
80         print(b,real,index2);
81 }
82 void print(int jia,int zhen,int i)
83 {
84     if (jia > zhen)
85     {
86         cout << "位置在："<< i+1 << "是假币" << "且较重！" << endl;
87     }
88     else
89     {
90         cout << "位置在："<< i+1 << "是假币" << "且较轻！" << endl;
91     }
92 }

利用蛮力法与分治法实现最近对问题：

参考资料：http://wenku.baidu.com/link?url=49Zq90UzxulQCJTtKfgum_6lAohBWHnynyr7jbHlXrT0z1SGIFLkJZYEPkuKrZ9aMjJLf0EZQfvjrL3b9QksbFKO6hsist_HDOT1gV72nVe

http://blog.sina.com.cn/s/blog_6364615e0100o67v.html

参考了我前面的一篇日志，sort的用法。

  1 // ClosestPoints.cpp : 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 #include <Windows.h>
  6 #include <time.h>
  7 #include <math.h>
  8 #include <iostream>
  9 #include <algorithm>
 10 using namespace std;
 11 typedef struct Point   //定义数据结构
 12 {
 13    long x;
 14    long y;
 15 } Point;
 16 Point points[200],P1[100],P2[100];
 17 const long MAX = 6000000;
 18 
 19 int cmp(Point a, Point b)   //对平面内的坐标进行有规则的排序
 20 {
 21    if (a.x != b.x)
 22    {
 23        return a.x < b.x;
 24    }
 25    else
 26    {
 27        return a.y < b.y;
 28    }
 29 }
 30 
 31 int cmp2(Point a, Point b)   //升序排列
 32 {
 33     return a.y < b.y;
 34 }
 35 long Distance(Point a,Point b)
 36 {
 37     long dist = (a.x - b.x)*(a.x - b.x) + (a.y - a.y)*(a.y - b.y);
 38     return dist;
 39 }
 40 
 41 //int min1(int a,int b)
 42 //{
 43 //    if (a>b)
 44 //    {
 45 //        return b;
 46 //    }
 47 //    else
 48 //    {
 49 //        return a;
 50 //    }
 51 //}
 52 //蛮力法，每个都找一遍，两两寻找
 53 long ClosestPoints(Point points[],int n,int *index1,int *index2)
 54 {
 55     long minDist = MAX;
 56     long Dist = 0;
 57     for (int i=0; i<n; ++i)
 58    {
 59        for (int j=i+1; j<n; ++j)
 60        {
 61            Dist = Distance(points[i],points[j]);
 62            if (Dist < minDist)
 63            {
 64                minDist = Dist;
 65                *index1 = i;
 66                *index2 = j;
 67            }
 68        }
 69    }
 70     return minDist;
 71 }
 72 
 73 
 74 //分治法函数
 75 long DivPoints(Point points[],int begin,int end)
 76 {
 77    int n = end - begin + 1;
 78    int m = (end + begin)/2;
 79    if (n == 2)
 80    {
 81        return Distance(points[begin],points[end]);
 82    }
 83    if (n == 3)   //三者当中找最小
 84    {
 85        long d1 = Distance(points[begin],points[begin+1]);
 86        long d2 = Distance(points[begin],points[end]);
 87        long d3 = Distance(points[begin+1],points[end]);
 88        if (d1<=d2 && d1<= d3)
 89        {
 90            return d1;
 91        }
 92        else if (d2 <= d3)
 93        {
 94            return d2;
 95        }
 96        else 
 97            return d3;
 98    }
 99    long left = DivPoints(points,begin,m);
100    long right = DivPoints(points,m+1,end);
101    long d = min(left,right);
102    int k1 = 0, k2 = 0;
103    for (int i = begin ; i <= m; ++i)      //中位数的左边区域
104    {
105         if (points[m].x - points[i].x<sqrt((float)d))
106         {
107             P1[k1].x = points[i].x;
108             P1[k1].y = points[i].y;
109             k1++;//在有两个以上的变量进行赋值的时候，不能用这个。而用此赋值方法
110         }
111    }
112    for (int i = m + 1 ; i <= end; ++i)   //中位数的右边区域，分割成两个P1与P2数组
113    {
114         if (points[i].x - points[m].x<(int)sqrt((float)d))
115         {
116             P2[k2].x = points[i].x;
117             P2[k2].y = points[i].y;
                k2++;
118         }
119    }
120    
121    //page 90 ，需要依据y进行升序排列，然后两两比较，找出最小
122   sort(P1,P1+k1,cmp2);
123   sort(P2,P2+k2,cmp2);
124   long dist=0;
125   long dMin=MAX;
126   for (int i = 0; i < k1 ; ++i)    //排序之后找里面最小的，这个部分是合并部分的工作。
127   {
128       for (int j = 0; j < k2; ++j)
129       {
130           dist = Distance(P1[i],P2[j]);
131           dMin = min(dist,dMin);//递归求最小距离
132       }
133   }
134 
135 
136 
137    //int k,l,flag=0;//k与l分别是记录左右两边<d的点的位置
138    ////找到以m为中心与m横坐标距离小于sqrt（d）的点
139    //for(int i = begin; i <= end; ++i)
140    //{
141       // if (flag == 0 && (points[m].x - points[i].x<sqrt(d)))//遍历左半部分
142       // {
143    //       flag = 1;
144    //       k = i;
145       // }
146       // if (flag == 1 &&(points[i].x - points[m].x<sqrt(d)))//遍历右半部分
147       // {
148    //       l = i;
149       // }
150    //}
151    //for (i = k ; i <= m; ++i)
152    //{
153       // for (j=m+1; j<=1 && fabs((points[j].y-points[i].y)<sqrt(d)); ++j)
154       // {
155          //  if (Distance(points[i],points[j]) <= d)
156          //  {
157             //   d = Distance(points[i],points[j]);
158          //  }
159       // }
160    //}
161    return min(d,dMin);   //比较d与dMin的大小，并返回，合并。
162 }
163 
164 
165 
166 int _tmain(int argc, _TCHAR* argv[])
167 {
168     
169     LARGE_INTEGER frequency,begin,end;
170 
171     while (1)
172  {
173     int n;
174     cout << "随机生成n个点"<<endl;
175     cin >> n;
176     cout << "随机生成"<<n<<"个点的X与Y坐标如下："<<endl;
177     /*
178       srand()的功能就是就是设置产生随机数的公式的参数（随机数种子），如果使用相同的种子，
179       那么得到的随机数也就是相同的。自然，如果使用不同的种子，得出的随机数序列也是不同的。
180       不同的种子会得到 固定 的 不同的随机数序列。
181     */
182     srand((unsigned int)time(0));//产生不同的随机数
183     for (int i=0; i<n;++i)
184     {
185         points[i].x = rand();
186         points[i].y = rand();
187         cout << points[i].x << "," << points[i].y <<" ";
188     }
189     cout << endl;
190 
191     int index1 = 0;
192     int index2 = 0;
193     QueryPerformanceFrequency(&frequency);
194     QueryPerformanceCounter(&begin);
195     long minDist = ClosestPoints(points,n,&index1,&index2);
196     QueryPerformanceCounter(&end);
197     cout << "蛮力法所用时间为"<< (double)(end.QuadPart - begin.QuadPart)/frequency.QuadPart<<endl;
198     cout << "最短距离为"<< minDist <<endl;
199     /*cout << points[index1].x << " "<< points[index1].y << endl;
200     cout << points[index2].x << " "<< points[index2].y << endl;*/
201 
202 
203     QueryPerformanceFrequency(&frequency);
204     QueryPerformanceCounter(&begin);
205     
206     sort(points,points+n,cmp);//当成数组
207     minDist = DivPoints(points,0,n-1);
208     QueryPerformanceCounter(&end);
209     cout << "分治法所用时间为"<< (double)(end.QuadPart - begin.QuadPart)/frequency.QuadPart<<endl;
210     cout << "最短距离为"<< minDist <<endl;
211 
212   }
213     return 0;
214 }