博文
三种最基本排序实现(2007-04-22 22:38:00)
摘要：#include <iostream>using namespace std;
void swap(int *p,int i,int j){ int temp=p[i]; p[i]=p[j]; p[j]=temp;}//插入排序void insertSort(int *A,int n){ for(int i=0;i<n;i++) for(int j=1;j<=i;j++) if(A[i]<A[j]) swap(A,i,j);}//稍改进的冒泡排序算法。加标志tag.void ebuSort(int *A,int n){ int tag=1; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) if(A[i]<A[j]) { swap(A,i,j); tag=0; } if(tag==1) break; }}//选择排序void selectSort(int *A,int n){ int temp; for(int i=0;i<n;i++) { temp=i; for(int j=i+1;j<n;j++) if(A[temp]>A[j]) temp=j; swap(A,i,temp); }}void print(int *A,int n){ cout<<"print all number in sort: "; for(int i=0;i<n;i++) cout<<......
引进美国卡耐基·梅隆大学软件系统开发（SSD）课程体系(2007-04-21 22:44:00)
摘要：引进美国卡耐基·梅隆大学软件系统开发（SSD）课程体系
西北工业大学软件与微电子学院在国家外专局、中国国际人才交流基金会和陕西省外专局的组织和支持下，完成了第一阶段课程引进工作，为国家软件工程人才培养与中美软件工程教育合作迈出了新的一步。
在软件工程教育领域，卡耐基·梅隆大学在全球始终排名第一。该校的软件工程课程代表了最先进的软件工程管理思想，被誉为软件界的金领。国家软件人才国际培训（西安）基地此次从卡耐基·梅隆大学引进的软件工程系列课程，是美国iCarnegie公司在卡耐基·梅隆大学计算机科学课程的基础上，采用国际开发案例改进后用于开发实践的软件工程课程体系，它突破了原有的软件教学模式，注重实践，不是简单的课程引进，而是教育思路、教育管理体系和方法的引进；不但在我国软件人才培养中发挥重要作用，对教育思想、方法以及国际教育合作也具有重大意义。
截至目前引进课程教师培训班分两批在国家软件人才国际培训（西安）基地依托单位西北工业大学软件学院顺利举行，参加培训的学院共九所，分别是西北工业大学软件学院、四川大学软件学院、南开大学软件学院、北京交通大学软件学院、湖南大学软件学院、中山大学软件学院、武汉大学软件学院、东北大学软件学院、 哈尔滨 工业大学软件学院，参加培训的骨干教师120人。
通过教师培训引进的SSD系列课程体系既兼顾了先进性与实用性，又充分注意了本地化与国际化并举的问题，为中国的软件教育提供了一种规范、专业、实用的国际化软件人才培养途径。
中美软件工程教育合作项目标志着国家关于国际化工程型软件人才培养部署又迈出了新的一步，我国软件业已经开始建立与国际开发模式和水准相接轨的软件高级人才培养基地。
项目主要引进其软件系统开发（SSD）课程体系，卡耐基·梅隆大学授权iCarnegie公司开发的面向工程型软件人才培训的本科系列课程。SSD设置的十门课程可为两个层次：信息系统导论、计算机系统导论、面向对象编程与设计、用户界面设计与测试以及数据结构与算法这五门课程是针对计算机编程人员的；系统级编程、数据库系统、网络和分布式系统、软件系统规范、测试和维护及软件项目的组织和管理这五门课程则是面向软件系统设计与开发人员的。
软件系统开发课程：
SSD1 信息系统导论
SSD2计算机系统导论
SSD3面向对象编程与设计
......
排列组合算法1：生成全部有序列(2007-04-21 01:56:00)
摘要：生成长度为N的全部有序列(n-tuples)
在QQ群上和朋友聊天（嗯，我还在用QQ，尽情鄙视我吧。什么时候MSN支持像QQ那样任意添加表情，任意贴图，而不是把我添加的表情图压缩得面目全非，我再放弃QQ不迟。连“彻底地全身心地毫无保留地崇拜你”都不能用，MSN my ass。QQ上的表情：
同样的图添加到MSN后： 。什么世道！），常遇到的话题之一是怎么生成一个有序列的所有组合，一个集合的所有子集（幂集），或者所有的全排列。一些论坛上也常出现类似的问题。很有意思的话题。在编程中时不时要遇到之外，也是锻炼大脑防止老年痴呆的上佳练习材料，尤其适合好静坐，喜油条， 30岁以上从不上健身房的程序员。不用左右看了。就是老大您！做这类题目还有个好处：重温当年写小程序的快乐。不知道多少人会享受搭建工资管理系统的全过程，津津有味地调试奇形怪状的API，反复修改庞杂的XML配置文件。反正我不会。写小程序就不同了。没有最后期限的压力，不用担心系统的羁绊，无需顾虑程序的架构。可以纠缠算法的每一个细节，也可以执着于提高代码的每一分性能。施主随喜。心智澄明，目光通透，心随意动，运指如飞。敲下的字符直切问题要害，摧枯拉朽。层层屏障随着代码的延伸支离破碎。写小程序解谜题的过程，就好像懵懂小孩儿扎堆游戏，纯粹为了好玩儿。一晃眼，一下午过去。他们满身泥浆，精疲力尽。但他们眼神依然兴奋，依然盼望下一次游戏。嗯，今年不收礼，收礼只收智力题。
今天又开始犯贱，万事压身就是不想动手。不过秉承拖拉也要拖有所得的原则，干脆聊聊这类问题的常用算法。
知道怎么生成全部有序列的算法，也就知道怎么生成幂集。这两者有直观的对应关系。生成全排列则另有一套算法。生成所有有序列要简单些，所以先用它开胃。当然，这类问题早有大牛写了详尽的指南， 我也就当当廉价的搬运工而已。好在还能用大牛本人的话安慰一下自己：每当发现什么有趣的问题后，轻轻Google一把，总能不幸发现有聪明人已经做出答案。
一个N-tuple是一个包含N个元素的序列，一般写作 。比如说 就是一个6-tuple。注意tuple和集合的区别。Tuple里可以包含重复的元素。而且Tuple的元素是有序的，就跟数组的元素一样。
那么给定一个N-tuple, ，我们怎么生成全部有序列呢？由简入繁总是学习的不二法门。所以我们从简单的二进......
盖茨清华演讲全文：未来之路，在中国共同创新(2007-04-21 01:46:00)
摘要：
4月19日，微软公司董事长比尔·盖茨开始第二天的访华行程。盖茨当日上午在清华大学发表主题为《未来之路：在中国共同创新》的演讲，并接受清华大学颁发的名誉博士学位证书。以下为演讲全文：
尊敬的顾校长，清华大学的老师、同学们：
获得清华大学这所世界一流大学的名誉博士学位，让我感到非常荣幸。清华是一所有着百年历史的名校，这里诞生了很多杰出的科学家、商业和政治领袖。
我上一次访问清华是在1997年。当时，中国学生的才华、热情和创造性给我留下了很深的印象。之后，我决定在中国设立微软亚洲研究院。在沈向洋博士的领导下， 在清华等大学优秀毕业生的协助下，微软亚洲研究院取得了成功，为微软公司作出了巨大贡献。在各种国际会议上都可以见到他们的身影。他们也为微软的新产品如Windows Vista的诞生，付出了辛勤的努力。在计算机科学迅速发展的今天，身为清华的学生是件激动人心的事。
我们才刚刚开始接触到软件魔法带来的奇妙体验。全世界有十亿计算机用户，他们才刚刚开始分享信息。随着半导体、光纤技术的发展，软件可以做更多的事情：
今天的电视还是被动的，在未来，你可以从因特网下载节目，电视将能和人交流、互动；
昨天我参观了中国农科院稻米研究所，看到那里的技术人员开始用软件来区分不同的稻米，为其排序，以后还可以通过软件的分析计算，用较少的农药培育出高产量的优良品种；
医学界已经开始用软件来管理数据库；
今天的手机已经成为我们的“数字钱包”，可以显示地图，上网查找信息，未来它还将可以和人交流；
平板电脑的出现，使得在教室可以无线上网，用电脑录音、识别手写的文字。这样，学生无需课本就能实现更有效的学习，老师也可以看到世界各地的优秀教案。
当然，软件的未来还面临很多挑战， 比如：如何使得用户更容易掌握？如何实现人工智能？但不管怎样，就计算机科学而言，我们所处的都是最激动人心的时代。
中国正在快速发展，对世界经济、科技创新正在做出越来越大的贡献。微软公司愿意帮助中国公司的成长，帮助所有的中国公民享受到计算机科学进步所带来的成果：
微软已经开展项目，帮助中国的进城务工人员、残疾人尤其是盲人享受科技成果；
微软已经捐资设立了五所希望小学和五所网上希望小学；
微软也同中国政府及大学合作，设立了很多学术交流项目，鼓励优秀外......
微软过桥问题的图论解法(2007-04-21 01:40:00)
摘要： 微软过桥问题的图论解法
微软的过桥问题说的是4个人在晚上过一座小桥，过桥时必须要用到手电筒，只有一枚手电筒，每次最多只可以有两人通过， 4个人的过桥速度分别为1分钟、2分钟、5分钟、10分钟，试问最少需要多长时间4人才可以全部通过小桥？
这个问题如果用图论来建模的话，就可以以4个人在桥两端的状态来作为节点来构造一个有向图，如下图所示，以已经过桥了的人的状态作为图的节点，初始时没有人过桥，所以以空表示，第一轮有两个人过桥，有6种可能的组合，(1，2)（1，5）（1，10）（2，5）（2，10）（5，10），从空的状态转换到这些状态的需要的时间分别为2，5，10，5，10，10分钟，时间就作为有向边的权值。当有两个人过桥后，需要一个人拿手电筒回去接其他人，这时有四种可能的情况，分别是1，2，5，10中的一人留在了河的对岸，（1，2）这种状态只能转换到（1）（2）两种状态，对应的边的权值分别为2，1分钟，（1，2）转换到（1）时也就是2返回了，返回需要耗时2分钟，以此类推可以建立以下的图论模型。
要求出最少需要多长时间4人全部通过小桥实际上就是在图中求出（空）节点到（1，2，5，10）节点间的最短路径。
根据Dijkstra最短路径算法很容易求出其最短路径，如图中的粗线所示。
这样总时间为2＋1＋10＋2＋2＝17分钟
所以能够活学图论的话，这类智力问题就变成了图论的入门级的问题。
......
微软过桥问题与测试人员素养 (2007-04-21 01:38:00)
摘要：1.1.1 微软过桥问题与测试人员素养
微软面试题过桥问题在IT业内几乎已变成一个众所周知的问题，问题如下：
4个人在晚上过一座小桥，过桥时必须要用到手电筒，只有一枚手电筒，每次最多只可以有两人通过（人多了桥支撑不住就塌了）， 4个人的过桥速度分别为1分钟、2分钟、5分钟、10分钟，试问最少需要多长时间4人才可以全部通过小桥？
一般人碰到这道题目也许马上就在想该如何安排这4个人的过桥顺序使得过桥时间最少，稍微聪明一些的人也许马上就想到了答案：“先让1、2过去，1回来，5、10再过去，2回来，1、2再过去”，总共需要17分钟就可以让4个人都过去。
当然如果数学知识足够好的话，可能会用图论来分析这个问题，最后发现这是一个图论的最短路径算法问题，只要根据过桥的状态建立一张有向图，然后求出最短路径就可以得到最少时间的过桥方案。（如果读者对如何用图论问题解这个问题感兴趣的话，可以看我的博客中的另外一篇讲微软过桥问题图论解法的文章）。
现在如果让一个测试人员来回答这个问题的话，是不是也象上述一样回答就可以了呢？如果能在很短时间内象上面一样回答问题，当然说明你人比较聪明，但是如果作为测试人员的话，需要的不是简单的结果，而是要全面分析问题，仅仅回答出最短时间为17分钟的答案是达不到测试人员的要求的。
作为一个测试人员，首先得对问题中的许多未知因素提出疑问，下面一些问题也许是测试人员所想知道的：
n 这4个人为什么要在晚上过这座桥，他们是在正常回家的路上还是野外探险迷路还是被人追杀？如果是被人追杀会不会有2人过去后独自逃走不回来接......
清华学子七问盖茨 “拷问”微软创新能力(实录)(2007-04-21 01:34:00)
摘要：4月19日，微软公司董事长比尔·盖茨开始第二天的访华行程。盖茨上午在清华大学发表主题为《未来之路：在中国共同创新》的演讲，并接受清华大学颁发的名誉博士学位证书。
清华参加活动的学生向盖茨提出了7个问题，如下：
问题一：盖茨先生，上午好。我来自软件试验班，最近有关量子计算的理论和应用正在高速发展。有人认为，这将在信息技术领域引起一场新的革命。今年早些时候，在2月13日，一家加拿大公司——D-Wave System——称他们世界上首次生产出可行的商用16位量子计算机。那么，微软公司将如何应对这场可能发生的变革，并且请您谈一下您对计算机未来的一些看法。谢谢。
盖茨：和世界顶尖大学合作并且关注这些重大突破对于微软非常重要。既然量子计算理论发生了如此重大的突破，我们就要改善我们的软件使他们能在新的平台下运行。我们也有一个量子计算方面的研究项目，我很兴奋我们也是该领域的参与者之一。但是考虑到量子计算机在未来五年内成为主流的可能性非常小。关于计算机，我们还有许多重要事情要做，比如容量问题，成本问题等等。过去二十年，这方面的研究已经有了一些进展，我很乐观在这方面还会进一步发展。我们需要确定是否真的应该让我们的工程师投入到这个新的领域。有许多比我们拥有更好技术人员的大公司比如IBM、Digital Equipment、HP等并不认为这将会改变计算机的本质，这和我们的看法是一致的。我们每天都在想什么东西我们错过了，什么事情要发生。我们的工程师一直在接触和关注这些先进的事情，我们也关注着量子计算可能会做出的贡献，但这不是一朝一夕的事情。
问题二：盖茨先生，上午好，我的问题是关于微软的研究。在很多领域有深入研究而且和大学联系如此紧密，这对于大公司非常罕见。您最初怎么想到要建立这些研究中心，它们对微软有什么影响？谢谢。
盖茨：微软从大学和公司比如XEROX和AT&T的研究中受益菲浅。既然我们知道我们可以从中获益，我们有责任，同时这对我们也有好处，对研究事业做出我们应有的贡献。当然我们也害怕比如像AT&T和XEROX这样的大公司对研究投入了很多而且使人们收益但是他们没有获得应有的商业上的成功。像XEROX早期在Palo Alto Research Center做了很多图形化界面，AT&T做出了UNIX系统。所以我们希望既能够像他们......
学术大师间的对话：21世纪信息科学人才什么样(2007-04-21 01:31:00)
摘要：在比尔·盖茨被授予清华大学名誉博士学位之前，一场学术大师间的交流和对话悄然展开，对话的中心议题是：21世纪信息科学的发展以及对人才的要求。我们选取工业界和学术界的两个代表人物，看看他们怎么说———
工业界：微软亚洲研究院已做出了世界一流的成绩
比尔·盖茨(微软公司创始人、董事长)：计算机科学是当今世界最活跃的领域，我们现在正在朝数字革命方向前进，还要在软件上有进一步的突破，最重要的包括传输速度和人工智能。
微软在中国的研究团队已经做出了世界一流的成绩，这确实令人激动。这其中很大程度上要归功于清华在人才培养方面的努力。
在美国，许多优秀学生毕业后进入金融和咨询领域，我感到非常不可理解———最令人激动的合作是在科学领域的合作，尤其是在计算机领域。我想中国不仅有一大批优秀人才，而且有很多人步入这一领域，这是很大的优势。而在美国，步入科学以及计算机科学领域的人数正在下降。这对我来说非常奇怪，因为这些领域是非常重要的领域。
如果我可以选择何时何地重新上大学的话，我可能要选20世纪80年代早期的斯坦福大学或者90年代晚期的清华大学。
学术界：清华大学将培养出世界上最优秀的本科生
姚期智(世界著名计算机专家、2000年图灵奖获得者)：我相信大家都认为信息技术已经改变了世界，如何培养能够引领技术革新的真正人才，并让其才能得到充分发挥，这是世界上所有国家共同面临的挑战。毋庸置疑，大学是应对这场挑战的关键。大学实验室孕育出了很多创新，同时，大学还将学生培养成为下一代创新者。
如果有人问“就拿清华大学来说，我们能使清华大学变成下一个斯坦福大学或者伯克利大学吗？”，通过我过去几年的观察，我的回答是肯定的。
原因有三点：一、我们有许多优秀的大学生；二、中国拥有大量有才能的工程师和科学家；三、我们有来自政府和学校的大力支持。
还有就是微软以帮助的姿态来到中国。微软亚洲研究中心和清华大学之间的密切合作，正在为我们创造一个机会，可以为计算机教学做出特殊的贡献。所以在两年前，清华大学就和微软公司决定联合建立一个“计算机科学实验班”。
这个实验班有以下几个特点：第一，每年从清华大学的优秀学生中选出30名学生进入该实验班学习；第二，专门为实验班设置了8门课程，科学基础和软件技术并重。我们要让学生在打好扎实的理论知识基......
百度之星程序设计大赛初题目(2007-04-21 00:49:00)
摘要：1.百度语言翻译机 百度的工程师们是非常注重效率的，在长期的开发与测试过程中，他们逐渐创造了一套独特的缩略语。他们在平时的交谈、会议，甚至在各种技术文档中都会大量运用。
为了让新员工可以更快地适应百度的文化，更好地阅读公司的技术文档，人力资源部决定开发一套专用的翻译系统，把相关文档中的缩略语和专有名词翻译成日常语言。
输入要求：输入数据包含三部分：1. 第一行包含一个整数N(N<=10000)，表示总共有多少个缩略语的词条；2. 紧接着有N行的输入，每行包含两个字符串，以空格隔开。第一个字符串为缩略语（仅包含大写英文字符，长度不超过10字节），第二个字符串为日常语言（不包含空格，长度不超过255字节）；3. 从第N+2开始到输入结束为包含缩略语的相关文档（总长度不超过1000000个字节）。例：6PS 门户搜索部NLP 自然语言处理PM 产品市场部HR 人力资源部PMD 产品推广部MD 市场发展部百度的部门包括PS，PM，HR，PMD，MD等等，其中PS还包括NLP小组。样例：in.txt
输出要求：输出将缩略语转换成日常语言后的文档。（将缩略语转换成日常语言，其他字符保留原样）。例：百度的部门包括门户搜索部，产品市场部，人力资源部，产品推广部，市场发展部等等，其中门户搜索部还包括自然语言处理小组。样例：out.txt
2.饭团的烦恼 “午餐饭团”是百度内部参与人数最多的民间组织。同一个部门的、同一所大学的、同一年出生的、使用同一种型号电脑的员工们总是以各种理由组织各种长期的、临时的饭团。
参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们增进感情。但是，随着百度的员工越来越多，各个饭团的管理变得繁杂起来。特别是为了照顾员工们越来越挑剔的胃，饭团的点菜负责人的压力也越来越大。现在，这个任务就交给“百度之星”了，因为，你将要为所有的百度饭团设计一个自动点菜的算法。
饭团点菜的需求如下：1．经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近12元越好。2．菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。3．请谨记，百度饭团在各大餐馆享受8折优惠。
输入要求：1．输入数据第一行包含三个整数N，M......
戒烟-你痛苦吗？(2007-04-20 22:36:00)
摘要：
对于程序员可能很多都有抽烟的习惯。也是有许多每天都在跟自己说。我要戒烟。但是每次跟自己说了之后。还是跟每天要吃饭一样的。是那样的需要。你是不是有这样的痛苦呢？明知道抽烟就是在慢性自杀。但是还是每天的在割自己一刀。其实很多时候就是在电脑边的时候觉得对烟的需求是那样的急切。或者打牌，打游戏。说的再多还是要戒烟的。所以我今天收集了一些戒烟的方法。其实要戒烟就是对自己意志力的考验。相信自己吧。能。I can do it! 我希望老外常说的话。自己也能去做到。
行动吧！
文章一：
一、订立戒烟日期企图以逐月少吸的办法逐渐戒掉这个习惯，并没有多大效用。摆脱尼古丁的过程会缓慢而痛苦。改吸尼古丁含量低的牌子也没有什么帮助。许多改吸这些牌子的人，都会用多抽几根香烟和吸入更深的办法来补偿。 有一种经过修改后的完全戒烟办法似乎最好。先减少吸烟几个星期，然后定下完全停止吸烟的日期（最好定在大约一个月之后，而且一经决定，无论如何也不能更改。为鼓励自己，不妨列出想戒烟的所有理由。例如： ·你讨厌吸烟引起的咳嗽。 ·吸烟的人可能脸上的皱纹出现得更早更多。 ·吸烟不但损害味觉，而且损害嗅觉。 ·一天抽两包烟每年的花费很可观，足够到外地去度假，两年足可以买一架电视机。 ·吸烟可导致癌症，肺气肿和心脏病。 二、准备戒烟 ·第一天点燃第一根香烟时，延迟15分钟，以后每天再多延迟15分钟。 ·不要在烟瘾一来时就点燃一根烟。找些分心的事情做。和别人谈话，喝杯开水，或者闭眼想象自己在一个喜欢去的地方。 ·定下“不吸烟时间”，然后逐渐把时间延长。 ·饭后，立即离桌去散步或刷牙。 ·试用自已平常不用的那支手吸烟。 ·每次只买香烟一包，吸完了才再买一包。 ·每......