关于算法的文章我一直想写，但算法是我的软肋，自己难于下笔。首先自己非科班出身，没有进行过系统的算法设计课程训练；再者自己到目前为止还从未独立设计过一个完整的、实用的算法，在平时工作中较少的涉及到算法设计，这不能说不是一个遗憾。也许有人会问："算法难道还没有过时吗，算法不是属于'Donald E. Knuth'那一代人的事情吗?'。我很难回答这个问题，不过当我今天看到CSDN上的一篇题为'算法是百度工程师的利器'的文章后，我隐约看到了算法的回归！

谈到目前互联网上最热的是什么？100个人有99个会回答：'搜索'，剩下的一个的答案是'Google'。没错！技术公司出身的Google和Baidu在成功背后到底是什么在支撑呢？名为技术，实则算法。Google的成功难道不是'page rank'算法的贡献么？Baidu站在行业的顶峰其脚下也少不了优秀的算法设计。从Baidu工程师入司的练习题也可以看出Baidu是何等的重视算法。可以说搜索引擎技术带来了算法的回归。

2006第四期'程序员'杂志推出了一期技术专题，叫'算法的力量'，在我的印象中'程序员'杂志好像是第一次推出算法专题。由于没买这期杂志所以这里也不知道其中的细节。谈到算法我们不能不提到算法的学习。Donald E. Knuth的'The Art Of Computer Programming'可以说是举世公认的算法领域的鼻祖之作，以至于很多人把这三卷书买回家恭恭敬敬的'供起来'^_^。从这点也可以看出如果拿这本书作为教程的话，难度可见一斑。我们还是介绍点'通俗'的。首当其冲的就是MIT的'算法导论'开放课程(6046)，最新一期的开放课程还有Video可供下载，主讲教师就是'算法导论第二版'的作者之一Charles E.Leiserson。我觉得大师级人物的课与一般讲师不同之处在于其对知识本源的发掘、揭示和解释，有着亲身体会的大师们的见解会让你身临其境印像深刻。当然这门儿课也是一门'大部头'的课，其教材'算法导论第二版'也是一本足以'砸死人'的'大砖头'，国内早在2003年就出版了其英文版，出版社应该是高教。记得当时还在读大三，但我去母校的大学书店买书的时候，店员告诉我"这是哈尔滨第一批展示品，本来是不准备卖的，你消息还挺灵通的吗"。就这样我买下了那本大部头，遗憾的是到目前为止它还和刚买来的时候一样新^_^。

正如百度首席架构师所说："搜索引擎开发中使用的基本算法大部分都在大学课程中涵盖了。对于一个人来说，在学校学习过这个算法，和能够灵活运用是两个概念。只有通过参与较多的项目开发和程序编写，将算法和应用相结合，才能在这方面得到较好的发展。"，单单死扣书本上的东西去学习算法是不能设计出好算法的，必须通过一个不断思考、实践、创新和总结的良性循环，你才能发现算法设计的真谛。最近自己也在理论和实践相结合的锻炼自己的算法能力，而尝试ACM练习是一个很好的将理论和实践相结合的方法，大家也不妨试试。

要想在算法领域有所深入，数学基础必不可少，相信很多人都能意识到这一点，前几天Google的一位科学家吴军在'Google黑板报'上贴出了一篇叫'数学之美'的Blog，也谈了数学工具在Google内部技术研究的重要性。其实对计算机知识认识越深的人越能认识到数学无处不在，CSDN编辑孟岩的一篇文章'数学与算法随想'让我们感受到数学语言的魅力！

题外话：在'南合文斗'的'让泪化作相思雨'-歌曲美妙节奏的驱动下，我的思维好像跑在美国的高速公路上，那是相当的快！周末了，一切都要放下放下！^_^

这又是一道ACM练习题，我的原则就是如果有时间，坚持每天考虑解决一道吸引我的ACM练习题，今天这道'Mixing Milk'题并不难，不过里面蕴含着一个基础的算法，毕竟对算法一类的知识生疏已久，今天就拿它做一次回顾吧！

这道'Mixing Milk'(1003)题目前在'在线测试'系统上的状态是474/1207=39.27%(即accepted/submit=ratio)，算是中等偏下难度的题了，照比我昨天作的1002题要简单(我的感觉)。起码看题之后思路清晰^_^。

'Mixing Milk'的题目大概是这样的，原题是英文，这里把它简单用中文描述一下：说牛奶制品行业是个薄利的边缘行业，那么这个行业靠什么赚钱呢？只有靠降低采购成本。现在有这么一家牛奶厂，每天的牛奶采购量为N(0 <= N <= 2,000,000)，而这些牛奶是从M(0 <= M <= 5,000)个奶农那采购的。当然奶农的牛奶的价格是不一致的，现在你是一个牛奶采购员，如果让你去到奶农那采购牛奶，如何能使采购量为N，而成本却最小，最后根据输入计算出这个成本值。输入输出的格式参见下面的例子：
输入：
100 5 — (1)
5 20 — (2)
9 40
3 10
8 80
6 30
输出：
630

简单说一下输入输出，输入部分第一行(1)，这里输入两个数，依次为牛奶厂一天的采购量以及奶农的个数；输入第二行至最后一行描述的都是奶农的信息，以(2)行为例：5 表示 奶农牛奶代价，20表示这天奶农能够提供的最大牛奶量。输出就是采购的总成本。

其实很多人看到这个题就会马上有思路了，可能很多人都会有这样的大众想法："即将输入按照牛奶代价从低到高排序，然后从低的开始采购，直到采购足一天需要的奶量即可"。

这里一个让我回忆起大学曾经学过的诸多排序算法：冒泡排序、选择排序、插入排序、希尔排序、快速排序、堆排序等等，这里我选择了'插入排序'。也许很多人记不清插入排序是怎么回事儿了，见怪不怪，工作之后接触业务流程性的东西较多，而接触基本算法的机会则少只有少，大多数情况你只需要调用一个已经封装好的接口或着基础库即可。这里简单回顾一下'插入排序'算法，更精确的说法是'直接插入排序'。

[直接插入排序算法]
(1) 基本思想
每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。
(2) 算法描述
Input: R[1..N]

/* 对R[1..N]按递增序进行插入排序, R[0]是'哨兵'
Procedure InsertSort(Var R[N] : DataType);
 Begin
  for I := 2 To N Do
  begin
     R[0] := R[I]; J := I – 1;
     While R[0] < R[J] Do /* 查找R[I]的插入位置 */
     begin
        R[J+1] := R[J]; /* 将大于R[I]的元素后移 */
        J := J – 1
     end
     R[J + 1] := R[0] ; /* 插入R[I] */
  end
 End; /* InsertSort */

(3) 效率分析
由于算法中有一个嵌套选环，所以估算直接插入排序的时间复杂度为O(n^2)，是一个稳定的排序方法。

(4) 示例
初始序列 5|  2  8  9  7  1
i = 1           2  5|  8  9  7  1
i = 2           2  5  8|  9  7  1
i = 3           2  5  8  9|  7  1
i = 4           2  5  7  8  9|  1
i = 5           1  2  5  7  8  9|
 
这个算法实现起来并不很难，下面是'Mixing Milk'的解决方案(实现插入排序时没有使用'哨兵'，和上面的算法描述不完全一致)，已被在线测试系统Accepted，但未经雕琢过哟(感觉这道题算法重要，其他次之)，呵呵。

/*
 * solution for 1003 in Problems Volume I
 */

#include
#include

int main(void) {
        int     total_milk_per_day;
        int     total_farmers;
        int     i;
        int     j;
        int     k;
        int     h;
        int     *price_amount_pair;
        int     total_price     = 0;
        int     cur_amount      = 0;

        /*
         * 获取牛奶厂每天需要牛奶量和供货商总数
         */
        (void)scanf("%d %d", &total_milk_per_day, &total_farmers);

        price_amount_pair = (int*)malloc(total_farmers * 2 * sizeof(int));

        /*
         * 获取每个供货商的单价和提供量
         */
        for (i = 0; i < total_farmers; ++i) {
                k = 2 * i;
                (void)scanf("%d %d", price_amount_pair + k, price_amount_pair + k + 1);
        }

        /*
         * 利用插入排序使列表从前到后, 单价递增
         */
        for (i = 1; i < total_farmers; ++i) {
                for(j = 0; j < i; ++j) {
                        if (*(price_amount_pair + 2 * j) > *(price_amount_pair + 2 * i)) {
                                k = *(price_amount_pair + 2 * j);
                                h = *(price_amount_pair + 2 * j + 1);
                                *(price_amount_pair + 2 * j) =  *(price_amount_pair + 2 * i);
                                *(price_amount_pair + 2 * j + 1) =  *(price_amount_pair + 2 * i + 1);
                                *(price_amount_pair + 2 * i) = k;
                                *(price_amount_pair + 2 * i + 1) = h;
                        }

                }
        }

        for (i = 0; i < total_farmers; ++i) {
                if (cur_amount < total_milk_per_day) {
                        k = *(price_amount_pair + 2 * i + 1);
                        h = *(price_amount_pair + 2 * i);
                        if ((cur_amount + k) > total_milk_per_day) {
                                j = total_milk_per_day – cur_amount;
                                cur_amount += j;
                                total_price += (h * j);
                                break;
                        } else {
                                cur_amount += k;
                                total_price += (h * k);
                        }
                } else {
                        break;
                }
        }

        printf("%d\n", total_price);
        free(price_amount_pair);
        return 0;
}

发现做ACM练习题居然可以上瘾！^_^