技术 – 第 14 页

NOIp 2006 提高组 2 金明的预算方案

　　首先要考虑的是，如果没有主件和附件的话，那题目将会非常的简单，那这就是最简单的01背包了，但是麻烦的是题目有主件和附件。那我们怎么办呢？不做了？开玩笑，既然你走了OI这条路，那就千万别回头！那我能不能用01背包来处理这个题目呢？当然是能的，注意题目中的这句话“每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。”额，这个条件有什么用呢？当然有用啦，那么我就可以转化为01背包了，先只考虑主件，那就可以进行01背包了，然后对每个主件进行记录，每个主件拥有多少个附件，哪些附件，然后再进行动态规划就能解决了。
　　我把思路再整理一下，就是说先判断主件是否该买，如果它有一个附件的话，那么再考虑是否要购买这一个附件；如果有两个附件的话，那么就考虑是否购买第一个附件，第二个附件或者两个附件一起买（考虑他们的时候就一定要加上主件！）
　　代码如下，提交了两次，问题出在一个符号上：

#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
struct thing{
        int priece, cost;
        struct {
                int priece, cost;
        }sub[2];
        int len;
}buy[60];
int num[60];
int len;
int f[32001];

int main(void)
{
        int m, n;
        int i, j, k;
        int a, b, c;
        struct thing t;
        scanf("%d%d", &m, &n);
        for(i = 0; i < n; i++){
                scanf("%d%d%d", &a, &b, &c);
                if(c == 0){
                        num[len++] = i;
                        buy[i].priece = a b;
                        buy[i].cost = a;
                }else{
                        t = &buy[c – 1];
                        t->sub[t->len].priece = a * b;
                        t->sub[t->len].cost = a;
                        t->len++;
                }
        }
        for(i = 0; i < len; i++){
                t = &buy[num[i]];
                for(j = m; j >= t->cost; j–){
                        f[j] = max(f[j], f[j – t->cost] + t->priece);
                        for(k = 0; k < t->len; k++){
                                if(j – t->cost – t->sub[k].cost >= 0){
                                        f[j] = max(f[j], f[j – t->cost – t->sub[k].cost] + t->priece + t->sub[k].priece);
                                }
                        }
                        if(t->len == 2 && (j – t->cost – t->sub[0].cost – t->sub[1].cost >= 0)){
                                f[j] = max(f[j], f[j – t->cost – t->sub[0].cost – t->sub[1].cost] + t->priece + t->sub[0].priece + t->sub[1].priece);
                                                //把减法写成了加法,,
                        }
                }
        }
        printf("%d\n", f[m]);
        return 0;
}

2010年9月2日

NOIP 2006 提高组 1 能量项链

　　因为以前做过这一题，所以很快就写出来了，不过在一个细节的地方纠结了好久，具体位置见注释。
　　思路和以前是一样的，f[i][j] = max(map[i] map[i + a] map[i + j] + f[i][a] + f[i + a][j – i]); f[i][j]表示从第i个珠子往后j个所能获得的最大能量，然后代码就写出来了：

#include <stdio.h>
int n;
int map[200];
unsigned f[100][101];

void deal(int a, int b)
{
        int i;
        unsigned max = 0, t;
        for(i = 1; i < b; i++){
                t = map[a] map[a + i] map[a + b]
                                        //这里的a+b写成了a + i + 1
                        + f[a][i] + f[(a + i) % n][b – i];
                if(t > max){
                        max = t;
                }
        }
        f[a][b] = max;
}

int main(void)
{
        int i, j;
        unsigned max;
//      freopen("abc.txt", "r", stdin);
        scanf("%d", &n);
        for(i = 0; i < n; i++){
                scanf("%d", &map[i]);
                map[i + n] = map[i];
        }
        for(j = 2; j <= n; j++){
                for(i = 0; i < n; i++){
                        deal(i, j);
                }
        }
        max = 0;
        for(i = 0; i < n; i++){
                if(max < f[i][n]){
                        max = f[i][n];
                }
        }
        printf("%d\n", max);
//      getch();
        return 0;
}

2010年9月1日

NOIp 2007 提高组 4 树网的核

　　这个题目网上有很多题解，不过直接照抄的话确实不太好，我还是说说我自己的过程吧。
　　首先，可以知道的是“核”越长越好，确实说不太清楚，看下面的图吧：

　　如果核是A-B的话，A-B距离X的值为B到X的距离，假设为x，即B至X的距离，但是如果核是A-C的话，那么A-C距离X的值就会小于x，所以“核”还是越长越好！
　　后只需要从一条直径上寻找核就可以了，为什么的话，我觉得吧，最好的“核”选择有两点，第一点如上所述，越长越好；我觉得第二点就是越靠近中点越好，至于为什么的话，你自己想想，中点距离所有点的最长距离就是半径，而重点之外的就会大于半径，那么不就是长了？所以的话还是越靠近中点越好，所以从一条直径搜索应该是够了的（我知道这样解释是行不通的，但是我自己也不知道是什么原因，只好这么说了。）
　　直径的寻找就是随意使用一个点寻找最远的距离的节点，这就是一条直径的一端，然后从最远距离的节点出发再寻找一次最远距离，这就构成了一条直径，至于为什么，距离一个节点最远的距离为什么一定是一条直径的一端，我的理解是距离一个节点最远的距离一定是距离中点的距离加上半径的长度，也就是说最远的距离是先经过中点再去寻找半径。
　　寻找到了半径再根据s求枚举所有的核的可能，这里要注意的一点就是（我烦的错误），寻找d(F, V)的时候是先取距离整条边最长的节点，然后取所有边（核）中最小的一个。
　　代码附上：

#include <stdio.h>
#include <string.h>
#define bzero(a, b) memset((a), 0, (b))
int n, s;
int map[300][300];

int ans = 10000000;

int used[300];
int prev[300];
int dist[300];
int max, loc;

void d(int i, int sum)
{
        int j;
        used[i] = 1;
        if(sum > max){
                loc = i;
                max = sum;
        }
        for(j = 0; j < n; j++){
                if(!used[j] && map[i][j]){
                        dist[j] = sum + map[i][j];
                        prev[j] = i;
                        d(j, dist[j]);
                }
        }
}

void dfs(int node)
{
        bzero(used, sizeof(used));
        bzero(prev, sizeof(prev));
        bzero(dist, sizeof(dist));
        max = 0;
        prev[node] = –1;
        d(node, 0);
}

int lis[300];
int lenth;

void find(void)
{
        int i;
        dfs(0);
        dfs(loc);
        i = loc;
        while(i != –1){
                lis[lenth++] = i;
                i = prev[i];
        }
}

int tmp[90000];

//先删除本路径, 再逐个dfs,, 再恢复路径
void deal(int a, int b)
{
        int i, m;
        //删除本路劲
        for(i = a; i < b; i++){
                tmp[i – a] = map[lis[i]][lis[i + 1]];
                map[lis[i]][lis[i + 1]] = 0;
                map[lis[i + 1]][lis[i]] = 0;
        }
        //获取距离本路径最远的距离
        m = 0;
        for(i = a; i <= b; i++){
                dfs(lis[i]);
                if(m < max){
                        m = max;
                }
        }
        //更新ans
        if(ans > m){
                ans = m;
        }
        //恢复路径
        for(i = a; i < b; i++){
                map[lis[i]][lis[i + 1]] = tmp[i – a];
                map[lis[i + 1]][lis[i]] = tmp[i – a];
        }
}

void work(void)
{
        int i, j;
        int d;
        for(i = 0; i < lenth; i++){
                //寻找尽可能长的核
                d = map[lis[i]][lis[i + 1]];
                for(j = i + 1; j < lenth && d <= s; j++){
                        d += map[lis[j]][lis[j + 1]];
                }
                //获取此核的长度, 并更新ans
                deal(i, j – 1);
        }
}

int main(void)
{
        int i;
        int a, b, c;
        scanf("%d%d", &n, &s);
        for(i = 1; i < n; i++){
                scanf("%d%d%d", &a, &b, &c);
                a–, b–;
                map[a][b] = map[b][a] = c;
        }
        //寻找半径,, 然后用lis数组记录半径的线路
        find();
        //寻找最小的偏心距,,  用ans记录
        work();
        printf("%d\n", ans);
        return 0;
}

2010年8月31日

S-K-YServer beta版发布

　　此次发布的版本，已经成为真正的服务器雏形了，按照Liun的话，成功独立出线程池，以后写Ftp服务器阿，写一些本地的文件处理阿，之类的都能够直接调用线程池中的函数了，也就是说线程池完全独立出来了，和服务器已经没有直接的关系了，惟一的关系就是服务器要调用线程池的函数。

　　这一次将线程池的锁分配到线程，每个线程一把锁，然后用两个列队来报存正在工作的线程和空闲线程，当然，每个列队自身也有一把锁，不然不久K.O.了。
　　然后本次升级提升了服务器的健壮性，当遇到非HTTP协议时不会自动退出了（我自己写了个客户，只是连接服务器，然后就关闭套接口，结果服务器就崩溃了。），然后我想想还有什么更新。。
　　但是还需要修改的地方是：增加当线程用完时，能够再分配指定数量的线程；第二，使用更快的列队（如：堆）。
　　哈哈，本次升级之后已经能够使用了，但是我还能想到一个漏洞，不是服务器，而是自己写一个客户端程序，请求文件../../../（因为8080只能是管理员打开，所以就能够读取所有文件了，这是一个很棘手但很好处理的漏洞。）
　　暂时先不修复，因为OI我一个星期没一点动静了，该OI了，虽然明天开学，虽然今天没有OI，但是还是挺开心的，服务器写到了这个程度（我很自豪!）。

2010年8月30日

网络的漏洞

　　我先有话在先，我现在15岁，高一，只是对Linux, Unix有些爱好，如果说的什么都不是千万不要喷。。

　　我是在看Unix网络编程第一卷第三版 38页的时候想到的一个思路，当然我不可能实现咯……就是说TCP在关闭时会有一个TIME_WAIT状态，这个状态是为了两个理由存在的：1，实现可靠的TCP全双工连接的终止;2，允许老的重复分解在网络中消逝。看到这里和下文我就想了，数据被传输是通过路由的对吧，也就是可以表示成：

　　(我习惯的画图工具Flash 没装, 就用的Windows 7的图画工具)

　　这样是没有错的吧? 然后针对TIME_WAIT存在的第二个理由，消逝的理由就是防止数据在下一次连接中出现，避免不必要的问题对吧，那我就想了，如果我能控制路由的话，在分节消逝之后再让它出现在网络中会怎么样呢？

　　把这个思路再进一步修改一下，当数据经过我的路由时我对它进行拦截+分析+修改，然后发送过后的数据到目的地去，就能够让网络不正常吧？当然咯，我这个想法很天真，因为全世界不止我这一台路由，但是如果有数据从我这台路由上通过的话我能否这样实现呢？

　　如果可以的话，我会再把这个玩狠一点：当有数据经过我的路由器时，将数据拦截下来，如果是ACk分节的话，将ACK分节发送给目的地。然后再发送（以发送源的身份）一个FIN n+1(n是ack的值)，然后对源（以目的的身份）发送一个FIN；如果不是ACK分节就更好，直接对双发发送FIN分节。

　　嘿嘿，总之就是说接收到分节，不是直接将其转发，而是进行分析之后对双发发送FIN分节，如图：

　　思路大概就是这样，但是这一切的前提都是我能够控制路由器，而且有数据经过我的路由器，最重要的是我非常无聊。。
　　思路我先留着，看以后能实现不，控制路由。。暂时还有点远，现在是NOIp。

2010年8月28日

TYVJ 第三题滑雪解题报告

题目:

背景 Background

成成第一次模拟赛第三道

描述 Description

　　trs喜欢滑雪。他来到了一个滑雪场，这个滑雪场是一个矩形，为了简便，我们用r行c列的矩阵来表示每块地形。为了得到更快的速度，滑行的路线必须向下倾斜。

　　例如样例中的那个矩形，可以从某个点滑向上下左右四个相邻的点之一。例如24-17-16-1，其实25-24-23…3-2-1更长，事实上这是最长的一条。

输入格式 Input Format

输入文件

第1行: 两个数字r，c(1<=r,c<=100)，表示矩阵的行列。

第2..r+1行:每行c个数，表示这个矩阵。

输出格式 Output Format

输出文件

仅一行: 输出1个整数，表示可以滑行的最大长度。
我的解答:

　　我以为题目就是要找出连续的最大的数字呢, 就是说顺着路径找出最大的~! 一提交,, 40分..
#include <stdio.h>
int map[100][100];
int n, m;

int getv(int x, int y)
{
        if(x < 0 || x >= m || y < 0 || y >= n){
                return –1;
        }
        return map[x][y];
}

int main(void)
{
        int i, j;
        int k;
        int a, b;
//      freopen(“abc.txt”, “r”, stdin);
        scanf(“%d%d“, &m, &n);
        for(i = 0; i < m; i++){
                for(j = 0; j < n; j++){
                        scanf(“%d“, &map[i][j]);
                        if(map[i][j] == 1){
                                a = i;
                                b = j;
                        }
                }
        }
        k = 1;
        while(k < m * n){
                if(getv(a – 1, b) == k + 1){
                        a = a – 1;
                        k++;
                        continue;
                }
                if(getv(a + 1, b) == k + 1){
                        a = a + 1;
                        k++;
                        continue;
                }
                if(getv(a, b – 1) == k + 1){
                        b = b – 1;
                        k++;
                        continue;
                }
                if(getv(a, b + 1) == k + 1){
                        b = b + 1;
                        k++;
                        continue;
                }
                break;
        }
        printf(“%d\n“, k);
//      getch();
        return 0;
}

　　后来又以为是求最大的顺序(不一定是1 2 3, 也可以是1 3 4,) 就是跳跃式前进的, 结果是30分..

#include <stdio.h>
int map[100][100];
int n, m;

int getv(int x, int y)
{
        if(x < 0 || x >= m || y < 0 || y >= n){
                return –1;
        }
        return map[x][y];
}

int main(void)
{
        int i, j;
        int k, t, s;
        int a, b;
        int d, f;
//      freopen(“abc.txt”, “r”, stdin);
        scanf(“%d%d“, &m, &n);
        for(i = 0; i < m; i++){
                for(j = 0; j < n; j++){
                        scanf(“%d“, &map[i][j]);
                        if(map[i][j] == 1){
                                a = i;
                                b = j;
                        }
                }
        }
        k = 1;
        while(k < m * n){
                s = 10000000;
                t = getv(a – 1, b);
                if(t > k && t < s){
                        d = a – 1;
                        f = b;
                        s = t;
                }
                t = getv(a + 1, b);
                if(t > k && t < s){
                        d = a + 1;
                        f = b;
                        s = t;
                }
                t = getv(a, b – 1);
                if(t > k && t < s){
                        d = a;
                        f = b – 1;
                        s = t;
                }
                t = getv(a, b + 1);
                if(t > k && t < s){
                        d = a;
                        f = b + 1;
                        s = t;
                }
                if(t == k){
                        break;
                }
                a = d;
                b = f;
                k = s;
        }
        printf(“%d\n“, k);
//      getch();
        return 0;
}

2010年8月27日

TYVJ 第二题第K极值

　　思路很简单, 将数据进行一次排序, 取第t个和倒数第t个, 然后倒数第t个减去第t个, 再判断差是否为素数..
　　听前辈们说NOIp不能使用库函数qsort, 而我一老使用, 为了避免考试0分的情况, 这里就自己写了一个快排, 当快拍的元素少于15个时就使用插入排序进行排序.
　　代码如下:

#include <stdio.h>
#include <math.h>
#define swap(a, b) do{\
        if(!((a) ^ (b))){\
                break;\
        }\
        (a) ^= (b);\
        (b) ^= (a);\
        (a) ^= (b);\
}while(0)
unsigned long map[10000];

int compare(int a, int b)
{
        return a – b;
}

void insert_sort(unsigned long *a, int start, int end)
{
        int i, j;
        int key;
        for(i = start + 1; i <= end; i++){
                key = a[i];
                for(j = i – 1; j >= 0 && compare(key, a[j]) < 0; j–){
                        a[j + 1] = a[j];
                }
                a[j + 1] = key;
        }
}

int getmiddle(unsigned long a[], int s, int e)
{
        int m;
        m = (s + e) / 2;
        if(compare(a[m], a[s]) < 0){
                swap(a[m], a[s]);
        }
        if(compare(a[s], a[e]) > 0){
                swap(a[s], a[e]);
        }
        if(compare(a[m], a[e]) > 0){
                swap(a[m], a[e]);
        }
        return m;
}

void quick_sort(unsigned long *a, int start, int end)
{
        int middle;
        int len = end – start + 1;
        int i, j;
        unsigned key;
        if(len <= 15){
                insert_sort(a, start, end);
                return;
        }
        middle = getmiddle(a, start, end);
        key = a[middle];
        swap(a[end – 1], a[middle]);
        i = start;              //除去三值的头
        j = end – 1;           //除去三值的尾
        while(i < j){
                while(compare(a[++i], key) < 0){
                }
                while(compare(a[–j], key) > 0){
                }
                if(i < j){
                        swap(a[i], a[j]);
                }
        }
        swap(a[i], a[end – 1]);
        quick_sort(a, start, i – 1);
        quick_sort(a, i + 1, end);
}

int isprime(unsigned long n)
{
        int limit = sqrt(n);
        int i;
        if(n == 1 || n == 0){
                return 0;
        }
        for(i = 2; i <= limit; i++){
                if(n % i == 0){
                        return 0;
                }
        }
        return 1;
}

int main(void)
{
        int n, t, i;
        unsigned long ans;
        scanf(“%d%d“, &n, &t);
        for(i = 0; i < n; i++){
                scanf(“%d“, &map[i]);
        }
        quick_sort(map, 0, n – 1);

        ans = map[n – t] – map[t – 1];
        if(isprime(ans)){
                printf(“YES\n“);
        }else{
                printf(“NO\n“);
        }
        printf(“%d\n“, ans);

        return 0;
}

2010年8月27日

NOIp 2007 第三题矩阵取数游戏

　　题目困扰了我很久，后来才知道，该怎么解题。
　　这题说是说矩阵取数，但是仔细看看能够知道，和矩阵没什么关系，只每行的最大值有关，因为每行之间的最大没有任何关系。那么就将矩阵取数转变成了对数组取数，对数组取数很容易看出来是DP，DP方程如下：f[i][j] = max( 2 map[i] + 2 f[i + 1][j], 2 map[j] + 2 f[i][j – 1] )。最初状态是f[i][i] = 2 map[i]。f[i][j]的是i~j之间的能够取的最大值。
　　方程我还解释一下，比如第一个数据吧：

　　　　　2 3

　　　　　1 2 3

　　　　　3 4 2

　　我只说明第一行，f[0][0] = 2, f[1][1] = 4, f[2][2] = 6，然后f[0][1] = max( 2 map[0] + 2 f[1][1], 2 map[1] + 2 f[0][0] ) = 10，也就是说"1 2"这两个数据应该先取1再去二，然后f[1][2] = 14.f[0][2] = 82..
　　就是这样的思路，其实思路我三天前就有了，但是因为数据太大，2^80以上，用long long 都装不下，那只能使用高精度了，但是实在很难下手啊。
　　怎么办？没办法了，只好先用int来写，然后封装起来，再把int改成高精度，啥？这句话没看懂？
　　意思就是说我先写了下面第一段代码，没用高精度，只得了40分，但是下面这个代码的框架封装的很好，然后直接将几个函数修改一下就能够使用高精度了：
#include <stdio.h>
#include <string.h>
/ ===============对使用"数"类型的封装=============== /
typedef struct{
int num;
}num;

void give(num a, int n)
{
a->num = n;
}

void add(num a, num b)
{
a->num += b->num;
}

void addnum(num a, int n)
{
a->num += n;
}

void copy(num a, num b)
{
a->num = b->num;
}

int compare(num a, num b)
{
return a->num – b->num;
}

void output(num a)
{
printf("%d\n", a->num);
}

/ ===============程序的实现=============== /

num f[80][80];
num ans;
num s1, s2;
int map[80];

void srch(int n)
{
        int i, k;
        num t;
        memset(f, 0, sizeof(f));
        for(i = 0; i < n; i++){
                give(&f[i][i], map[i]);
                addnum(&f[i][i], map[i]);
        }
        for(k = 1; k < n; k++){
                for(i = 0; i < n – k; i++){
                        copy(&s1, &f[i + 1][i + k]);
                        addnum(&s1, map[i]);
                        copy(&s2, &f[i][i + k – 1]);
                        addnum(&s2, map[i + k]);
                        if(compare(&s1, &s2) < 0){
                                t = &s2;
                        }else{
                                t = &s1;
                        }
                        copy(&f[i][i + k], t);
                        add(&f[i][i + k], t);
                }
        }
}

int main(void)
{
        int m, n;
        int i, j;
        memset(&ans, 0, sizeof(ans));
        scanf("%d%d", &n, &m);
        for(i = 0; i < n; i++){
                for(j = 0; j < m; j++){
                        scanf("%d", &map[j]);
                }
                srch(m);
                add(&ans, &f[0][m – 1]);
        }
        output(&ans);
        return 0;
}
　　高精度的代码等下发上来。

#include <stdio.h>
#include <string.h>
#include <math.h>
/ =====================高精度实现部分===================== /
#define max(a, b) ((a)>(b)?(a):(b))
#define TOTAL 40
const int used = 100000000;
#define bits ((int)log10(used))
typedef struct{
int num[TOTAL];
int len;
}num;

static void deal(num a)
//防止高精度的漏洞.
//如:used = 10000, give(a, 10000), give(a, 1), give(b, 10000), add(a, b)
//此时a为20001而不是10001
{
        int i;
        for(i = a->len; i < TOTAL; i++){
                a->num[i] = 0;
        }
}

void give(num a, int n)
{
        int i;
        for(i = 0; n; i++){
                a->num[i] = n % used;
                n /= used;
        }
        a->len = i;
        deal(a);
}

void add(num a, num b)
        //这里有个bug, a和b 不能相同
{
        int i;
        int len = max(a->len, b->len);
        int re = 0;

        for(i = 0; i < len; i++){
                a->num[i] += b->num[i] + re;
                re = a->num[i] / used;
                if(re > 0){
                        a->num[i] %= used;
                }
        }
        a->len = len;
        if(re > 0){
                a->len++;
                a->num[i] = re;
                //掉了 a->num[i] = re; 这一行
        }
}

void addnum(num a, int n)
{
        int i;
        int re = 0;
        for(i = 0; n; i++){
                a->num[i] += (n % used) + re;
                n /= used;
                re = a->num[i] / used;
                if(re > 0){
                        a->num[i] %= used;
                }
        }
        a->len = max(i, a->len);
        if(re > 0){
                a->num[i] += re;
                //写成了=re;
                a->len = max(i + 1, a->len);
        }
}

void copy(num a, num b)
{
memcpy(a, b, sizeof(num));
}

int compare(num a, num b)
{
        if(a->len != b->len){
                return a->len – b->len;
        }

        int i;
        for(i = a->len – 1; i >= 0; i–){
                                //是i–不是i++
                if(a->num[i] != b->num[i]){
                        return a->num[i] – b->num[i];
                }
        }
        return 0;
        return a->num – b->num;
}

void output(num a)
{
        int i;
        int len = a->len, num = a->num;
        printf("%d", num[len – 1]);
        len–;
        for(i = len – 1; i >= 0; i–){
                printf("%.d", bits, num[i]);
        }
        printf("\n");
}

/ =====================主函数部分===================== /

num f[80][80];
num ans;
num s1, s2;
int map[80];

void srch(int n)
{
        int i, k;
        num t;
        memset(f, 0, sizeof(f));
        for(i = 0; i < n; i++){
                give(&f[i][i], 2 * map[i]);
        }
        for(k = 1; k < n; k++){
                for(i = 0; i < n – k; i++){
                        copy(&s1, &f[i + 1][i + k]);
                        addnum(&s1, map[i]);
                        copy(&s2, &f[i][i + k – 1]);
                        addnum(&s2, map[i + k]);

                        if(compare(&s1, &s2) < 0){
                                t = &s2;
                        }else{
                                t = &s1;
                        }
                        copy(&f[i][i + k], t);
                        add(&f[i][i + k], t);
                }
        }
}

int main(void)
{
        int m, n;
        int i, j;
        memset(&ans, 0, sizeof(ans));
        scanf("%d%d", &n, &m);
        for(i = 0; i < n; i++){
                for(j = 0; j < m; j++){
                        scanf("%d", &map[j]);
                }
                srch(m);
                add(&ans, &f[0][m – 1]);
        }
        output(&ans);
        return 0;
}

2010年8月24日

Http服务器正式版

　　经过昨天一晚上的奋斗+今天一早上的奋斗，服务器总算是能够真正的使用了。

昨晚上：

　　今天晚上拼了命在写服务器，打算把进程池写出来，反复的翻Unix 环境高级编程，天啊，进程之间的通信真的很麻烦，没对进程都需要两个管道（如果需求移植能力强的话是2个，不然可以是1个。）然后我就放弃了，考虑线程池，但是不知道怎么样调度线程，后来翻到了线程可以单独接收信号，打算从这里下手，写了好久，把线程锁，信号集都用上了，但是还是Failed了。最后打算直接使用线程锁+数据的正负性来下手（程序的效率不会高的，因为每个线程都有可能加锁然后发现数值错误，再解锁。），正在撰写中。
　　忽然想到了另外一种方法，用进程池，之间直接使用信号来管理，思路不错，但是等线程池失败了再考虑。
　　线程池的成功了，不过前面的一种方法，就是使用信号的，也不一定失败了，因为我之前写的时候掉了一个函数，现在再试试这种效率高的方法。
　　很可惜，还是失败了，那我就先用那种效率低的方法吧。。
　　最后发现竟然是机子的问题，我把服务客户的函数去掉了，不过不知道为什么，accept只能接受一个客户请求。。只好明天早上再写了（现在已经00:30了.）

今天早上：

　　把需要的函数加上后，尝试了昨天的两种线程调度的方法，第一种还是失败了，sigwait的用法还是不够清楚，我就直接使用了第二种，使用线程锁，主线程一直锁上，tmpsock=-1，然后其他的线程再为锁而睡眠，当主线程接收到客户，就把全局变量tmpsock设置成套接字文件描述父，就把锁释放，然后马上夺取。然后其他线程也会夺取这个线程锁，主线程得到锁之后判断tmpsock是否为-1，如果是就返回主函数，否则放锁再夺取，其他线程判断tmpsock是否为-1，如果是就放缩，否则就把这个套接字设为自己的，然后置tmpsock为-1，然后对客户发送Html文件。
　　此方案已经成功了，不过效率可能不高，因为可能一直是主线程得锁，又放锁；还可能是一个线程得到套接字文件描述符之后，其他的线程反反复复的再得锁又防锁（解锁）。
　　但总之这个方案已经实现了，自己挺自豪的，这样服务器就成为了真正的并发服务器。

2010年8月20日

Http 服务器 beta 0.1 版

　　修改了一两个小时，把文件的源代码由一个分成了几个，每个文件完成各自的功能，（有点模块化的感觉，哈哈）。然后自然是写了一个Makefile，不过只有2行代码咯，关键是可以捕捉信号了，就是说可以处理子进程僵死的问题了，成功升级为真正的并发服务器，关于这点我打算写成线程池或进程池，可以可以提高服务器的性能。记得僵死进程的时候，一下子30几个僵死进程，在那儿吓死人！！！

S-K-Y Http 服务器 beta 0.0 – S-K-Y Http 服务器 beta 0.1

1.增加自动显示首页功能。

2.增加404 页面无法找到功能。

3.增加信号捕捉功能, 处理服务器产生的僵死进程。

4.使服务器的代码更具可读性。

5.增加了Makefile文件。

2010年8月20日

分类： 技术

分类：技术