博文
（转）厚积薄发，有的放矢(2006-07-21 18:03:00)
摘要：厚积薄发，有的放矢――李开复博士给中国计算机系学生的建议
很多在校的大学同学问我们：“我今年还没有到毕业班，但我很想知道，如果将来我想申请Google中国工程研究院，现在应该如何让自己做好准备？”下面是Google中国总裁李开复博士和其他一些Google资深的华人工程师给广大同学的建议。
（1）练内功。不要只花功夫学习各种流行的编程语言和工具，以及一些公司招聘广告上要求的科目。要把数据结构、算法、数据库、操作系统原理、计算机体系结构、计算机网络，离散数学等基础课程学好。不妨试试Donald Knuth的Art of Computer Programming里的题目，如果你能够解决其中的大部分题目，就说明你在算法方面的功力不错了。
（2）多实战。通过编程的实战积累经验、内化知识。建议大家争取在大学四年中积累编写十万行代码的经验。
（3）求实干。不要轻视任何的实际工作，比如一些看似简单的编码或测试。要不懈追求对细节一丝不苟的实干作风与职业精神。
（4）不放弃数学。数学是思维的体操，数学无处不在。尤其当你对一些“数学密集型”的领域有兴趣，例如视频、图像处理等等，你需要使它成为你的利器。
（5）培养团队精神，学会与人合作。
（6）激励创新意识，不为书本和权威所约束。
（7）有策略地“打工”。在不影响学业的前提下，寻找真正有意义的暑期工作或兼职。去找一个重视代码的公司，在一个好的“老板”指导下完成真正会被用户使用的程序。不要急于去一个要你做“头”而独挡一面的地方，因为向别人学习，是你的目的。打工和找工作一样，“不要只看待遇和职衔，要挑一个你能够学习的环境，一个愿意培养员工的企业，一个重视你的专业的公司，最后，要挑一个好老板。” 大学生如何为加盟Google做准备 厚积薄发，有的放矢李开复博士给中国计算机系大学生的建议
转自：开复学生网......
（转）北大牛人唐翔(2006-07-21 17:23:00)
摘要：题记：想必很多人都看过这篇文章吧。我也是很久以前就看过，今天看见篇解释文章，顺便一起转了。比如说，我的老板姜伯驹和王诗宬，一个是两院院士，一个是长江学者，都曾获得过陈省身数学奖。我当然跟他们彼此认识，甚至可以说熟悉。那他们有没有唐翔牛呢？窃以为没有。又比如说，我还是见过几位当代一流数学家的：陈省身、丘成桐、Smale、Atiyah，但他们根本不知道我是何许人，所以他们不能算我认识的人。那他们有没有唐翔牛呢？我觉得不好比较。不光是我觉得不好比较，很多人都有类似的感觉。有一次老谢（这是一个精通数学物理和数论的家伙）说：“二十世纪中国最伟大的三位数学家是陈省身、华罗庚、唐翔。”“不对！”何旭反驳道。这位几个月后将坐在MIT里研究李群的表示论的好吃懒做的不敢吃辣的重庆人意味深长地说道：“应该是唐翔、陈省身、华罗庚。”另外一个需要澄清的概念是“牛”。很多认识唐翔的人都认为，唐翔除了数学牛以外，再没什么长处了。但我这里说的“牛”是把各个方面：数学、物理、化学、语文、外语、泡mm、灌水、切星际……都加到一起。在每个领域中定义一个牛指标，然后把它们生加到一起。我将之称为“综合牛指标”。所谓某甲比某乙牛，就是说某甲的综合牛指标大于某乙的综合牛指标。容易证明，我认识的其他人的综合牛指标都是有限数，但唐翔在数学领域的牛指标是趋于+∞的，而他在别的领域的牛指标至少是非负数，所以唐翔的综合牛指标大于我认识的其他人的综合牛指标，也就是说唐翔是我认识的最牛的人。证毕。--对于一个学数学的人来说，认识唐翔是他的不幸。这个不幸很不幸地降临在了96级数学系除了唐翔以外的师兄师姐们身上，也降临在了97级数学系大部分同仁的身上。我的不幸始于大二下学期。那时我们年级好多人都一窝蜂地去选大三的拓扑课，我也跟着去选，然后就认识了唐翔。唐翔身材魁梧，膀大腰圆，戴眼镜，坐前排，听讲非常认真。看不出来是一个牛人，因为通常牛人都是不大听课的，比如我的偶像Smale，据说大学期间常翘课，而且经常坐在台阶上很深沉地望着夕阳。我们年级有一位mm也选了拓扑课，也总坐在前排，于是乎就经常向唐翔请教问题，没想到两年后这位mm会成为唐翔的gf……当然这位mm跟唐翔大概并不是在拓扑课上认识的，因为两年后这位mm会成为唐翔的gf……当然这位mm跟唐翔大概并不是在拓扑课上认识的，因为他们都担任一定职务，平时可能经常一起开会什么的。至于其中......
(转)ACM竞赛之新人向导(2006-07-21 17:15:00)
摘要：刚刚接触信息学领域的同学往往存在很多困惑，不知道从何入手学习，在这篇文章里，我希望能将自己不多的经验与大家分享，希望对各位有所帮助。 一、语言是最重要的基本功
无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当不利的。其实，笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维，因为对于小程序来说这不旦需要花费更多的时间去编写代码，也会降低程序的执行效率。
接着说C和C++。许多现在参加讲座的同学还在上大一，C的基础知识刚刚学完，还没有接触过C++，其实在赛场上使用纯C的选手还是大有人在的，它们主要是看重了纯C在效率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只要提高了自己在算法设计上的造诣，纯C一样能发挥巨大的威力。
而C++相对于C，在输入输出流上的封装大大方便了我们的操作，同时降低了出错的可能性，并且能够很好地实现标准流与文件流的切换，方便了调试的工作。如果有些同学比较在意这点，可以尝试C和C++的混编，毕竟仅仅学习C++的流操作还是不花什么时间的。
C++的另一个支持来源于标准模版库（STL），库中提供的对于基本数据结构的统一接口操作和基本算法的实现可以缩减我们编写代码的长度，这可以节省一些时间。但是，与此相对的，使用STL要在效率上做出一些牺牲，对于输入规模很大的题目，有时候必须放弃STL，这意味着我们不能存在“有了STL就可以不去管基本算法的实现”的想法；另外，熟练和恰当地使用STL必须经过一定时间的积累，准确地了解各种操作的时间复杂度，切忌对STL中不熟悉的部分滥用，因为这其中蕴涵着许多初学者不易发现的陷阱。
&nb......
STL算法学习(三)(2006-07-21 10:42:00)
摘要：/*copy 函数原型： template <class InputIterator,class OutputIterator> OutputIterator copy(InputIterator first1,InputIterator last1,OuputIteratoo first2); 功能：将序列[first1,last1)内的元素从由first2指定的开始位置依次进行拷贝。函数 返回拷贝后指向最后一个元素的下一个位置的迭代器。 copy_backward 函数原型： template <class BidirectionalIterator1,class BidirectionalIterator2> BidirectionalIterator2 copy_backward(BidirectionalIterator1 first1,BidirectionalIterator1 last1, &nb......
STL算法学习(二)(2006-07-20 12:27:00)
摘要：/*adjacent_find 函数原型： template <class ForwardIterator> ForwardIterator adjacent_find(ForwardIterator first,ForwardIterator last); template <class ForwardIterator,class BinaryOperation> ForwardIterator adjacent_find(ForwardIterator first,ForwardIterator last BinaryOperation op); 功能：第一个版本，在序列[first,last)中查找相邻元素之间第一对相 等的元素，并返回这样一个前向迭代器，若找到它指向相等元素 对的第一个元素，没找到，则返回last。第二个版本相邻元素之 间的关系由用户指定。
binary_search 函数原型： template <class F......
集合的全排列(2006-07-19 16:37:00)
摘要： 设R={r1,r2,r3,....,rn}是要进行排列的n个元素，Ri=R - {ri}.集合X中元素的全排列 记为perm(X).(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀ri,得到的排列。 R的全排列可归纳如下定义如下： 当n=1时，perm(R)=perm(r),其中r是集合R中的唯一元素。 当n>1时，perm(R)的全排列可由(r1)perm(R1),(r2)perm(R2),....,(rn)perm(Rn)构成。 依此定义，可产生计算集合R的全排列的算法如下： public static void perm(Object []list,int k,int m) { //产生list[k,m]的所有排列 if (k == m) { //单元素序列 for (int i = 0; i <= m; i++) System.out.print(list[i]); System.out.println(); } else&n......
STL算法学习(一)(2006-07-19 10:51:00)
摘要：/*accumulate(): * 函数原型：template <class InputIterator,class Type> * Type accumulate(InputIterator first,InputIterator last,Type init); * template <class InputIterator,class Type,class BinaryOperation> * Type accumulate(InputIterator first,InputIterator last,Type init,BinaryOperation op) * * 功能：函数的第一个版本将Iterator[fisrt,last)范围内对象和init累加起来，函数返回计算 的 * 结果值。例如，序列(1,5,6,9,8,5,3)，init为2，应用该函数后结果是39。第二个版本， * 用对象的操作 不再是加法了，具体操作由用户指定。由于这个函数是算术操作， 因此我们在使用它的时 候，必须包含头文件<numeric> 。 * *......
动态规划习题（一）(2006-07-17 20:26:00)
摘要：题目如下：
最大的和
一天，笨笨带着一道题目找到了你，希望你能帮她解决这道题目：
给你n个数a[1], a[2], ..., a[n]，(0<n<=16,000, -1,000<=a[i]<=1,000)和0<L1<=L2<=n 求长度在[L1,L2]的连续若干个数a[i], a[i+1], ..., a[j], (即L1<=j+1-i<=L2) 使得a[i]+a[i+1]+...+a[j]取到最大值, 你只需要输出那个最大值即可。
由于n非常大，所以笨笨就算数学再好也无法很好的解决这道题目。这下该看你的了，身为计算机小组的你，应该能轻松搞定这道题目吧。
输入文件：
输入文件第一行为三个整数n，L1， L2， 接下来是用空格或者换行符隔开的n个数, 第i个数表示a[i]。
输出文件：
仅一个数，表示a[i]+a[i+1]+...+a[j]的最大值。
Sample Input
5 3 4
3 -1 -2 5 3
Sample Output
6
分析：这是一道求最值问题的试题。首先很自然就想到用动态规划思想。于是小弟就试着用这种思想去试试。程序如下：
#include <iostream>using namespace std;
int N,l1,l2;int a[16000];int num[16000]; //当前取最大值时所包含的连续的元素个数 int maxValue[16000]; //第i个元素的最大值
int f(int n)//第n个元素的最大值，即为状态 { if (n == 1) { num[n] = 1; return maxValue[n] = a[1]; } &......
（转）初识A*算法(2006-06-25 00:58:00)
摘要： 写这篇文章的初衷是应一个网友的要求，当然我也发现现在有关人工智能的中文站点实在太少，我在这里抛砖引玉，希望大家都来热心的参与。
还是说正题，我先拿A*算法开刀，是因为A*在游戏中有它很典型的用法，是人工智能在游戏中的代表。
A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法，我看还是先说说何谓启发式算法。
一、何谓启发式搜索算法
在说它之前先提提状态空间搜索。状态空间搜索，如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一条解题的过程可以从求解的开始到问题的结果（好象并不通俗哦）。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。
常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。这两种算法在数据结构书中都有描述，可以参看这些书得到更详细的解释。
前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。在这里就要用到启发式搜索了。
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。
启发中的估价是用估价函数表示的，如：
f(n) = g(n) + h(n)
其中f(n)是节点n的估价函数，g(n)实在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n)&......
求两个字符串的最长公共子序列(2006-06-24 19:54:00)
摘要：//原程序见 http://blog.programfan.com/article.asp?id=14838
#include<iostream>#include<string>using namespace std;void maxstring(string str1,string str2){ int max,tag,i,j; int length1=str1.size(); int length2=str2.size(); int a[length1+1][length2+1]; for(i=0;i< length1;i++) for(j=0;j< length2;j++) a[i][j]=0;
//初始化状态a[0][0...length1]和a[0..length2][0] for (j = 0; j < length2; j++) if (str1[0] == str2[j])a[0][j] = 1; for (i = 0; i < length1; i++) if (str1[i] == str2[0])a[i][0] = 1; max = a[0][0]; tag = 0; /*应该是......