1 Divide and Conquer
A group of n Ghostbusters is battling n ghosts. Each Ghostbuster is armed with a proton pack, which shoots a stream at a ghost, eradicating it. A stream goes in a straight line and terminates when it hits the ghost. The Ghostbusters decide upon the following strategy. They will pair off with the ghosts, forming n Ghostbuster-ghost pairs, and then simultaneously each Ghostbuster will shoot a stream at his chon ghost. As we all know, it is very dangerous to let streams cross, and so the Ghostbusters must choo pairings for which no streams will cross. Assume that the position of each Ghostbuster and each ghost is a fixed point in the plane and that no three positions are collinear.行政总裁
i Argue that there exists a line passing through one Ghostbuster and one ghost such the number of Ghostbusters on one side of the line equals the number of ghosts on the same side. Describe how to find such a line in O(n log n) time.
别客气用英语怎么说
ii Give an O(n2 log n)-time algorithm to pair Ghostbusters with ghosts in such a way that no streams cross.
Answer:
i -ii: We assume that all the points in the plane are not in same X or Y axis using mark to stand for ghostbuster or ghosts(mark 0 stand for ghostbuster and mark 1 stand for ghosts).(This can not affect the problem becau when we get the same X or Y , we can add or minus a very little value to let all points’ X or Y are not same). First we get the deepest point (in other word, the minimum Y value). Also we compute the other points with this point ‘s angle in X axis and sort the other points with this angle. Then we iterate in this order, and get another mark which is different from the deepest point's mark also we line this two point ,and compute the bottom mark 0 's number and mark 1's number, they are the same , then we find the pair which is the deepest point and the iterate point. So we u this line to divide all points into two parts and recursive do the same above operation until the points' number is only 2 then we only get the line to connect this two points.
Algorithm:
Get_Pair(points[1-2N])
if N>1
initial a array points[1-2N] stand for the points of ghostbusters and ghosts
find the deepest point min_Point in the array points
initial the pair_Point and the index with 0
get the other 2N-1 points with this min_Point 's angle in X axis and sort the angles
initial num1 with 0 stand for the number of the other 2N-1 points which's mark is same with min_Point
initial num2 with 0 stand for the number of the other 2N-1 points which's mark is not same with min_Point
for i=1 to 2N-1
键组词
if min_Point's mark is same with points[i]'s mark
num1++
el
num2++
endif
if num1+1==num2
get this point pair_Point
index=i
break;
endif
endfor
print this pair (min_Point,pair_Point)
using pair_Point to divide points into two parts point_one[1-index-1] and point_two[index+1-2*N]
Get_Pair(point_one[1-index-1])
Get_Pair(point_two[index+1-2*N])
el
get the line to connect this two points
endif
轨迹拳
We will prove this algorithm is O(n log n) time, first we get the deepest point in O(n) time, next we compute the other points with this deepest point 's angle in X axis in O(n) time, we u quick_sort to sort the n angles in O(n log n). Last we iterator the angles in O(n) to find the pair. So all time we consume is only O(n log n) time.
Next we will prove this algorithm always can find the pair. Now we assume the deepest point stand for the Ghostbusters using mark=0, so above this point, we have n-1 Ghostbusters(mark=0) and n Ghosts(mark=1). So we can sort n-1 0 and n 1 in whole arrangement, no matter how we sort, we can get a index in 1 , which before this 1 we have the same number of 0 and 1. We can replace this problem with a new problem, we have a road for (0,0) point to (n-1,n) point , we only can move the one step in the X or Y direction. No matter which road we have, we must cross the line Y=X it means we must get the Ghost. Before this ghost, we have the same number of ghosts and ghostbusters.
Last, we will prove that solving this problem is O(n2 log n).
Easily, we get the T(n)=2*T(n/2)+O(n log n).第七座墓志铭
We u mathematical induction for assuming that T(n)<= O(n2 log n)
n=1, T(1)=O(n log n)<=O(n2 log n)
assume n<k T(n)<=O(n2 log n)人才培养方案
then n=k, T(k)=2*T(k/2)+O(k log k)<=2*O(k2 log (k/2)/ 4)+O(k log k)
=O(k2 log(k/2) /2)+O(k log k)
<=O(k2 log k)
2 Divide and Conquer
You are interested in analyzing some hard-to-obtain data from two parate databas. Each databa contains n numerical values-so there are 2n values total-and you may assume that no two values are the same. You’d like to determine the median of this t of 2学前教育管理系统n values, which we will define here to be the nth smallest value.
北京二日游
However, the only way you can access the values is through queries to the databas. In a single query, you can specify a value k to one of the two databas, and the chon databa will return the kth smallest value that it contains. Since queries are expensive, you would like to compute the median using as few queries as possible.
