本校同學(xué)想要代碼的郵件我
sgu的數(shù)據(jù)太強(qiáng)了，真是太折磨人了
sgu115:calendar
sgu的水題
sgu114:找中位點(diǎn)
算法導(dǎo)論Excercise 9.3-9的題目
看了答案之后我的理解性簡(jiǎn)單證明：
1.sgu的題目等價(jià)于有n個(gè)點(diǎn)，每個(gè)點(diǎn)有一個(gè)人，p個(gè)人的話，可以看作是p個(gè)坐標(biāo)相同的點(diǎn)。
2.考慮n的節(jié)點(diǎn)個(gè)數(shù)
設(shè)此時(shí)的左半邊的費(fèi)用和設(shè)為a ,右半邊的費(fèi)用和設(shè)為b
如果n是偶數(shù)
設(shè)最優(yōu)解坐標(biāo)為x1,x2
*假設(shè)最優(yōu)解在n / 2 和 n / 2 + 1兩個(gè)點(diǎn)之間
Cost = a + b;
如果移動(dòng)最優(yōu)解的坐標(biāo)，很容易可以證明
只要坐標(biāo)還在兩個(gè)中位點(diǎn)之間，那么解的值就不變。假設(shè)在兩個(gè)中位點(diǎn)之間左移d個(gè)單位
Cost = a - (n/2) * d + b + (n/2) * d
= a + b;
右移同理
*假設(shè)向左移出了中位點(diǎn)的距離
Cost = a - (n/2-1) * d + b + (n/2-1) * d + x2 - x1 + d
= a + b + d;
如果移動(dòng)超過(guò)這兩個(gè)點(diǎn)，那么解的值都將變大
如果n是奇數(shù)
*設(shè)最優(yōu)解坐標(biāo)為x,最優(yōu)值一定在中位點(diǎn)上。
此時(shí)Cost = a + b;
*假設(shè)最優(yōu)解左移d個(gè)單位
此時(shí)Cost = a - (n/2)*d + b + (n/2)*d + d
= a + b + x - d
向右移同理
所以中位點(diǎn)是最優(yōu)值
114此題就是多了個(gè)計(jì)數(shù)和排序
sgu113:素?cái)?shù)
可以發(fā)現(xiàn)，只要求sqrt(1000000000) 個(gè)素?cái)?shù)即可,也就是判斷tmp = m / primes[i]
判斷tmp是否是素?cái)?shù)即可
trick是，tmp可能大于sqrt(1000000000)!!
sgu112:大數(shù)冪
sgu111:大數(shù)求平方根
方法很多，大多數(shù)人都是模擬手算開方，我看了半天沒(méi)看明白，于是弄了哥迭代法 + java 水過(guò)
稍微有一點(diǎn)猥瑣...
c++版的求平方根方法
double eps = 1e-8;
int main()
{
int x,i,j,k;
while(scanf("%d",&x) == 1) {
double r = x; //盡量靠近sqrt(x)，這里是為了一個(gè)通解
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.