ChinaUnix“C语言代码”开发大赛！获奖名单公布！(奖品积分已经添加，请大家查收！)

pipipen

虚拟机里没有配中文，只好把说明写这里了

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2.17更新：问题3思路
2.18更新：加入问题8答案
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
======================
=                    测试                    =
======================
解压后运行 make test 可以运行简单的测试

======================
=                    Q1                     =
======================
为了输入大数的时候不占用太多内存，采用了逐行计算的方式。

以输入为 4 为例，矩阵为
        1,        2,        3,        4
        12,        13,        14,        5
        11,        16,        15,        6
        10,        9,        8,        7

程序开始的时候先计算出了每圈左上角数字，占用 (N+1)/2 个整型位置。
        1,        _,        _,        _
        _,        13,        _,        _
        _,        _,        _,        _
        _,        _,        _,        _

第一行所有元素都属于最外圈，每个数字都可以根据最外圈起始数字 1 算出。
        1,        2,        3,        4

第二行根据他们离中心点的距离，可以计算出 [0] 和 [3] 属于最外圈，[1] 和 [2] 属于次外圈，每个数字又都可以根据起始数字算出。
        1,        2,        3,        4
        12,        13,        14,        5

以此类推，得到每一行的数字。最多只用分配了 (N+(N+1)/2) * 4 字节内存。

======================
=                    Q2                     =
======================
因为整体区间不大（1000001个数），因此用位图的方式解决这个问题 先调用 fill_range，把每个区间对应的位都置为 1。

然后从 0 位置寻找第一个连续闭区间，寻找的方法是先找到位图中从 0 位置开始第一个设为 1 的位，作为第一个连续闭区间的左值从左值的位置开始寻找第一个设为 0 的位，作为第一个连续闭区间的右值。

从上述闭区间的右值开始寻找下一个闭区间的左值，并类推寻找出所有连续闭区间。

后续工作:
find_set() 和 find_clear() 两个函数可以重构为一个函数。

======================
=                    Q3                     =
======================
struct line{
     struct line *next;
     char s[2048];
     int len;
     int serialno;
};

分 11 个 相应数据结构，10 个用于存放，， 1 个用于读下一行。先依次读入前十行，升序链接。读入下一行，如果不比链表第一个行长，直接放弃；否则，继续沿链表比下去，找到它应该在的位置，插入，把链表头上那个原来的第十长行的数据结构拿来作为下次读入的缓冲区。

优点：
1. 避免频繁分配释放内存，以及内存拷贝。
2. 减少比较次数。虽然最长行按升序排列，但没有用二分法等查找方式，因为默认输入行是随即长度的，所以越后面的行，进入前十行的概率越小，从第十长行往上比，效率也还可以。

======================
=                    Q8                     =
======================

用了投机取巧的方法，哈哈！用 strtok 直接取每个目录，不用条件编译也行，程序如下：

#include <string.h>
#include "contest.h"

int main()
{
    int retval = 0;
    char *env = NULL;
    char *individual = NULL;

    env = getenv(ENV_VAR);
    individual = strtok(env, DELIMINATER);

    while(individual != NULL)
    {
        printf("%s\n", individual);
        individual = strtok(NULL, DELIMINATER);
    }

    return retval;
}

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

[ 本帖最后由 pipipen 于 2009-2-18 00:46 编辑 ]

ztz0223

忙，就做做第五题吧。
第五题的题目出的貌似有些小问题，输出的结果的写法不对！
比如输入：
4  7  -  2.1  5  +  *  7.1  9  -  /
输出
(4-7)*(2.1+5)/(7.1-9)

输出的写法不对！
应该是：
（(4-7)*(2.1+5) ）/(7.1-9)
括号加少了，如果把乘号换成+-号，问题就很明显了。

我做的第五题：
附件中。 5.rar (1.81 KB, 下载次数: 25)

2009-02-17 10:34 上传

点击文件名下载附件

ztz0223_cu

再给一个第一题的代码，从文件读取矩阵的维数，然后操作

steven_ml

我也来给出第一题的代码:
思路比较简单,希望其他朋友有更好的算法可以贡献出来.

//-------------------------------------------------------------------------------------------
#include <stdio.h>

#define N 9
unsigned char ARRAY[N][N] = {0};

//a : 表示数组起始下标;
//Data : 表示数组ARRAY[a][a]存放的数据;
//Layer : 表示围数;
int SetArray(unsigned char a, unsigned char Data, unsigned char Layer)
{
    unsigned char i, j;
   
    //填写数组四周的数据
    i = a;
    for(j = a; j < Layer + a; j++)
    {
        ARRAY[j] = Data++;
    }
   
    j = a + Layer - 1;
    for(i = a + 1; i < Layer + a; i++)
    {
        ARRAY[j] = Data++;
    }
   
    i = a + Layer -1;
    for(j = Layer - 2 + a; j > a; j--)
    {
        ARRAY[j] = Data++;
    }
   
    j = a;
    for(i = Layer- 1 + a; i > a; i--)
    {
        ARRAY[j] = Data++;
    }

    printf("\n");

    return Data;
}

int main()
{
    unsigned char i, j, k;
    unsigned char num = 0;
   
    //为填写最外围数据准备初始值
    i = 0;
    j = 1;
    k = N;
   
    //填写每一圈的数据,向中心靠拢
    do
    {
        num = SetArray(i, j, k - i * 2);
        j = j + 4 * (k - i * 2 - 1);
        i++;
    }while(num <= N*N);
   
    for(i = 0; i < N; i++)
    {
        for(j = 0; j < N; j++)
        {
            printf("%02d ", ARRAY[j]);
        }
        printf("\n");
    }
   
    printf("\n");
}
//-------------------------------------------------------------------------------------------

hjk857

太强大了。。。

支持！！！

nhuczp

今天刚看到。

DQP

全部8题
包括运行结果(out.txt or out.GIF)
之前发的有错误。。。
会继续完善注释和说明。。。

angle4

怎么发附件啊

angle4

ok，知道了。。。

第八题

好好恋爱