アルゴリズムの設計と分析——分治アルゴリズム
46280 ワード
#include
#include
#include
using namespace std;
/* */
typedef struct {
double x, y;
}point;
/* */
void IntRand(int*& A, int min, int max, int num);//
int Max(int A[], int l, int r);//
void Full(int** A, int num, int begin, int size);//
void MergeSort(int* A, int l, int r);//
void Merge(const int* A, int* B, int l, int m, int r);
void QuickSort(int* A, int l, int r);//
int Partition(int* A, int l, int r);
int MaxSum(int* A, int l, int r);//
double Closest(point* p, int l, int r);//
int ClosetCmp(point p, point q);
double Distance(point p, point q);
/* */
//
void IntRand(int*& A, int min, int max, int num)
{
A = new int[num];
for (int i = 0; i < num; i++)
{
A[i] = rand() % (max - min + 1);
A[i] += min;
}
}
//
int Max(int A[], int l, int r)
{
if (l == r) return A[l];
int mid = (l + r) / 2;
int maxLe = Max(A, l, mid);
int maxRi = Max(A, mid + 1, r);
return maxLe > maxRi ? maxLe : maxRi;
}
//
void Full(int** A, int num, int begin, int size)
{
if (size == 0) return;
if (size == 1) { A[begin][begin] = num; return; }
int i = begin, j = begin;
for (int k = 0; k < size - 1; k++) A[i++][j] = num++;
for (int k = 0; k < size - 1; k++) A[i][j++] = num++;
for (int k = 0; k < size - 1; k++) A[i--][j] = num++;
for (int k = 0; k < size - 1; k++) A[i][j--] = num++;
Full(A, num, begin + 1, size - 2);
}
//
void MergeSort(int* A, int l, int r)
{
if (l == r) return;
int mid = (l + r) / 2;
int B[100];
MergeSort(A, l, mid);
MergeSort(A, mid + 1, r);
Merge(A, B, l, mid, r);
for (int i = l; i <= r; i++)
A[i] = B[i];
}
void Merge(const int* A, int* B, int l, int m, int r)
{
int i = l, j = m + 1, k = l;
while (i <= m && j <= r)
{
if (A[i] <= A[j]) B[k++] = A[i++];
else B[k++] = A[j++];
}
while (i <= m) B[k++] = A[i++];
while (j <= r) B[k++] = A[j++];
}
//
void QuickSort(int* A, int l, int r)
{
if (l < r)
{
int m = Partition(A, l, r);
QuickSort(A, l, m - 1);
QuickSort(A, m + 1, r);
}
}
int Partition(int* A, int l, int r)
{
int flag = A[l];
while (l < r)
{
while (l < r && flag < A[r]) r--;
if (l < r) A[l++] = A[r];
while (l < r && A[l] < flag) l++;
if (l < r) A[r--] = A[l];
}
A[l] = flag;
return l;
}
//
int MaxSum(int* A, int l, int r)
{
int sum = 0;
if (l == r) sum = A[l];
else
{
int mid, sumLe, sumRi, sumMid, s1, s2, lefts, rights;
mid = (l + r) / 2;
sumLe = MaxSum(A, l, mid);
sumRi = MaxSum(A, mid + 1, r);
sum = sumLe > sumRi ? sumLe : sumRi;
//x~mid
s1 = 0; lefts = 0;
for (int i = mid; i >= l; i--)
{
lefts += A[i];
if (lefts > s1) s1 = lefts;
}
//mid~y
s2 = 0; rights = 0;
for (int i = mid; i >= l; i--)
{
rights += A[i];
if (rights > s1) s1 = rights;
}
sumMid = s1 + s2;
sum = sum > sumMid ? sum : sumMid;
}
return sum;
}
//
double Closest(point* p, int l, int r)
{
double min;
if (l >= r) min = 0;//
else if (r - l == 1) min = Distance(p[l], p[r]);//
else if (r - l == 2)//
{
double min1, min2, min3;
min1 = Distance(p[l], p[l + 1]);
min2 = Distance(p[l], p[r]);
min3 = Distance(p[l + 1], p[r]);
min = min1 < min2 ? min1 : min2;
min = min < min3 ? min : min3;
}
else
{
int mid = (l + r) / 2, ll = mid, rr = mid;
double midx, minLe, minRi;
if ((l - r + 1) % 2 == 0) midx = (p[mid].x + p[mid + 1].x) / 2;
else midx = p[mid].x;
minLe = Closest(p, l, mid);
minRi = Closest(p, mid + 1, r);
min = minLe < minRi ? minLe : minRi;
while (midx - p[ll].x < min) ll--;
while (p[rr].x - midx < min) rr++;
for(int i=ll;p[i].x<=midx;i++)
for (int j = rr; p[j].x > midx; j--)
{
double temp = Distance(p[ll], p[rr]);
if (temp < min) min = temp;
}
}
return min;
}
int ClosetCmp(point p, point q)
{
return p.x < q.x;
}
double Distance(point p, point q)
{
return sqrt(pow(p.x - q.x, 2) + pow(p.y - q.y, 2));
}
int main()
{
/*
int n;
cin >> n;
int** A = new int*[n];
for (int i = 0; i < n; i++)
A[i] = new int[n];
Full(A, 0, 0, n);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout.width(5);
cout << A[i][j];
}
cout << endl;
}
*/
/*
int n;
cin >> n;
int* A = new int[n];
for (int i = 0; i < n; i++)
A[i] = rand() % 100;
cout << " :";
for (int i = 0; i < n; i++)
{
cout.width(3);
cout << A[i];
}
MergeSort(A, 0, n - 1);
cout << "
:";
for (int i = 0; i < n; i++)
{
cout.width(3);
cout << A[i];
}
*/
/*
int n;
cin >> n;
int* A = new int[n];
for (int i = 0; i < n; i++)
A[i] = rand() % 100;
cout << " :";
for (int i = 0; i < n; i++)
{
cout.width(3);
cout << A[i];
}
QuickSort(A, 0, n - 1);
cout << "
:";
for (int i = 0; i < n; i++)
{
cout.width(3);
cout << A[i];
}
*/
/*
int* a, n, maxSum;
cin >> n;
MyRand(a, -10, 10, n);
maxSum = MaxSum(a, 0, n - 1);
for (int i = 0; i < n; i++)
cout << a[i] << ' ';
cout << "
:" << maxSum;
*/
/*
int n, * temp;
cin >> n;
point* p = new point[n];
IntRand(temp, 0, 1000, 2 * n);
for (int i = 0; i < n; i++)
{
p[i].x = temp[2 * i] / 100.0;
p[i].y = temp[2 * i + 1] / 100.0;
}
sort(p, p + n, ClosetCmp);
double min = Closest(p, 0, n - 1);
for (int i = 0; i < n; i++)
{
cout.width(4);
cout << p[i].x << ',' << p[i].y << endl;
}
cout << "cloest distance:" << min;
*/
return 0;
}