本校同學想要代碼的郵件我
sgu的數據太強了，真是太折磨人了
sgu115:calendar
sgu的水題
sgu114:找中位點
算法導論Excercise 9.3-9的題目
看了答案之后我的理解性簡單證明：
1.sgu的題目等價于有n個點，每個點有一個人，p個人的話，可以看作是p個坐標相同的點。
2.考慮n的節點個數
設此時的左半邊的費用和設為a ,右半邊的費用和設為b
如果n是偶數
設最優解坐標為x1,x2
*假設最優解在n / 2 和 n / 2 + 1兩個點之間
Cost = a + b;
如果移動最優解的坐標，很容易可以證明
只要坐標還在兩個中位點之間，那么解的值就不變。假設在兩個中位點之間左移d個單位
Cost = a - (n/2) * d + b + (n/2) * d
= a + b;
右移同理
*假設向左移出了中位點的距離
Cost = a - (n/2-1) * d + b + (n/2-1) * d + x2 - x1 + d
= a + b + d;
如果移動超過這兩個點，那么解的值都將變大
如果n是奇數
*設最優解坐標為x,最優值一定在中位點上。
此時Cost = a + b;
*假設最優解左移d個單位
此時Cost = a - (n/2)*d + b + (n/2)*d + d
= a + b + x - d
向右移同理
所以中位點是最優值
114此題就是多了個計數和排序
sgu113:素數
可以發現，只要求sqrt(1000000000) 個素數即可,也就是判斷tmp = m / primes[i]
判斷tmp是否是素數即可
trick是，tmp可能大于sqrt(1000000000)!!
sgu112:大數冪
sgu111:大數求平方根
方法很多，大多數人都是模擬手算開方，我看了半天沒看明白，于是弄了哥迭代法 + java 水過
稍微有一點猥瑣...
c++版的求平方根方法
double eps = 1e-8;
int main()
{
int x,i,j,k;
while(scanf("%d",&x) == 1) {
double r = x; //盡量靠近sqrt(x)，這里是為了一個通解
double p = 1;
while(p + eps < r) {
r = (r + p) / 2;
p = x / r;
}
printf("%f\n",r);
}
return 0;
}
原版的算法，我改了改
1. Start with an arbitrary positive start value r (the closer to the square root of x, the better).
2. Replace r by the average between r and x/r, that is: (r + x/r) / 2 ,
(It is sufficient to take an approximate value of the average in order to ensure convergence.)
3. Repeat step 2 until r and x/r are as close as desired.