我是搞不明白为什么这东西叫算法，还是感觉叫策略好一些。。。
下面是用分治法计算最近点对问题，在程序跑出来之前先把代码记录一下
基本想法：输入N个点（x，y），按x从小到大排序（可以调用C++自带的sort（vec.begin(),vec.end()）进行排序）
将这个点集在x轴的中间那个点一分为二，分别查找两边的最小距离和对应的两个点，查找方法还是一分为二，一分为二……直到不能再分（一个点集只有一个或两个点）
找到最小距离和那两个点后，假设当前这个点集是上一个点集分出来的左半部分，那么将它与右半部分合并，找两个点集合起来后的最小距离：这时不用想暴力求解那样两两计算距离，有一种更省力的方法——
对于这个点集左半部分的所有点，在右边最多有和它在y轴方向上最接近的6个点可能有比两边的最小距离更小的距离，所以计算6*n个距离即可（n表示左半边的点数），计算出来的最小的距离，一定就是左右合并起来的点集里的最短距离。
上代码:
#include <iostream>
///分治算法、蛮力法最近点对问题
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#define INF 0xFFFFFF
using namespace std;
class point {
private:
double x;
double y;
public:
explicit point(double _x = 0, double _y = 0) {
x = _x;
y = _y;
}
double getx() {
return x;
}
double gety() {
return y;
}
double operator-(point p) {
return sqrt(pow(x - p.getx(), 2) + pow(y - p.gety(), 2));
}
bool operator<(point p) {
return x < p.getx();
}
bool operator^(point p) {
return y > p.gety();
}
};
vector<point> pointsX;
vector<point> pointsY;
void merge(int left, int right) {
int mid = (left + right) / 2;
int l = left, r = mid + 1;
int index = l;
while (l <= mid && r <= right) {
if (pointsX[r] ^ pointsX[l]) {
pointsY[index++] = pointsX[l++];
} else {
pointsY[index++] = pointsX[r++];
}
}
while (l <= mid) {
pointsY[index++] = pointsX[l++];
}
while (r <= right) {
pointsY[index++] = pointsX[r++];
}
for (l = left; l <= right; l++) {
pointsX[l] = pointsY[l];
}
}
double divide(vector<point> px, int l, int r, point &p1, point &p2) {
if (r - l <= 0) {
return INF;
} else if (r - l == 1) {
merge(l, r);
return px[l] - px[r];
} else {
point lp1, lp2;
point rp1, rp2;
double min_distance;
int i, j;
int mid = (r + l) / 2;
double middle_x = pointsX[mid].getx();
double min_distance_l = divide(px, l, mid, lp1, lp2);
double min_distance_r = divide(px, mid + 1, r, rp1, rp2);
if (min_distance_l < min_distance_r) {
min_distance = min_distance_l;
p1 = lp1;
p2 = lp2;
} else {
min_distance = min_distance_r;
p1 = rp1;
p2 = rp2;
}
vector<point> temp(r - l + 1);
int number = 0;
merge(l, r);
for (i = l; i <= r; i++) {
if (fabs(px[i].getx() - middle_x) <= min_distance) {
temp[number++] = px[i];
}
}
double temp_distance;
for (i = 0; i < number; i++) {
for (j = i + 1; j < i + 1 + 6 && j < number; j++) {
temp_distance = temp[i] - temp[j];
if (temp_distance < min_distance) {
min_distance = temp_distance;
p1 = temp[i];
p2 = temp[j];
}
}
}
return min_distance;
}
}
double violent(vector<point> &vec, point &p1, point &p2) {
double minDistance = INF;
int size = vec.size();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i != j) {
double d = vec[i] - vec[j];
if (d < minDistance) {
minDistance = d;
p1 = vec[i];
p2 = vec[j];
}
}
}
}
return minDistance;
}
int main() {
int n = 100000;
vector<double> x = vector<double>(n);
vector<double> y = vector<double>(n);
srand(10);
for (int i = 0; i < n; i++) {
x[i] = rand() / 10000.0;
y[i] = rand() / 10000.0;
}
clock_t start;
clock_t end;
start = clock();
sort(x.begin(), x.end());
int size = x.size();
vector<point> points = vector<point>(size);
pointsX = vector<point>(size);
pointsY = vector<point>(size);
for (int i = 0; i < size; i++) {
points[i] = point(x[i], y[i]);
pointsX[i] = point(x[i], y[i]);
pointsY[i] = point(x[i], y[i]);
}
point p1, p2;
divide(points, 0, size - 1, p1, p2);
end = clock();
cout << "\n Time consumed= " << (double) end - start << endl;
cout << "\nMin distance: " << p1 - p2 << endl;
cout << "\np1: (" << p1.getx() << "," << p1.gety() << ")" << endl;
cout << "\np2: (" << p2.getx() << "," << p2.gety() << ")" << endl;
cout << "\n---Violent method---" << endl;
start = clock();
violent(points, p1, p2);
end = clock();
cout << "\n Time consumed= " << (double) end - start << endl;
cout << "\nMin distance: " << p1 - p2 << endl;
cout << "\np1: (" << p1.getx() << "," << p1.gety() << ")" << endl;
cout << "\np2: (" << p2.getx() << "," << p2.gety() << ")" << endl;
}
另一个问题——比赛时间表问题
问题很简单，直接贴代码
///分治算法循环赛日程表安排问题
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
using namespace std;
void gameTable1(vector<vector<int>> &vec) {
int s = vec.size();
int k = 0;
k = round(log(s) / log(2));
//初始化
vec[0][0] = vec[1][1] = 1;
vec[0][1] = vec[1][0] = 2;
for (int i = 2; i <= k; i++) {
int length = (int)pow(2,i);
int half = length/2;
for(int row=0;row<half;row++) {
for(int col=0;col<half;col++) {
//左下角的子表中项为左上角子表对应项加half=2^(i-1)
vec[row + half][col] = vec[row][col] + half;
//右上角的子表等于左下角子表
vec[row][col + half] = vec[row + half][col];
//右下角的子表等于左上角子表
vec[row + half][col + half] = vec[row][col];
}
}
}
}
bool isOdd(int n){
return n/2.0-n/2>0.1;
}
void gameTable2(vector<vector<int>> &table){
int num_of_team=table.size();
for(int i=0;i<num_of_team;i+=2){
for(int j=0;j<num_of_team;j+=2){
table[i][j]=table[i+1][j+1]=(i+j)%num_of_team+1;
table[i][j+1]=table[i+1][j]=(i+j+1)%num_of_team+1;
}
}
}
int main(){
int size=10;
vector<vector<int>> table=vector<vector<int>>(size,vector<int>(size));
gameTable2(table);
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
cout<<table[i][j]<<"\t";
if(j==0) cout<<"- ";
}
cout<<endl;
}
return 0;
}