博文
百度首席架构师揭密：算法是百度工程师的利器（来自《程序员》杂志）(2006-04-12 13:57:00)
摘要：百度首席架构师揭密：算法是百度工程师的利器
2006.04.06 来自：《程序员》杂志 周利民
“工欲善其事，必先利其器”，对于百度工程师来说，算法就是他们解决难题的利器。
为什么这么说？因为百度搜索引擎研发的各个环节都离不开算法。我们需要快速，准确、实用、创新和不断改进的算法来满足用户的需求。
百度面对的是海量的互联网数据，以及每天上亿次的检索请求。它要求百度能够收录和索引超过10亿的中文网页，并提供快速的检索服务。这只有高效率的算法才能完成。
百度招聘的工程师在加入公司后，有一道入门练习题，就是编写一个数据扫描分析程序，要求写出的程序能在1分钟之内扫描分析完千万量级的数据，才算及格。高水平的程序员可以利用高效的算法在10秒以内解决问题，甚至只要六七秒。但如果没用对算法，花一星期的时间，也做不到1分钟之内。
大家可以设想一下，百度有十亿以上的网页，如果要在一周甚至三天内处理一遍，平均每秒处理要多少个？每天1亿次的检索又意味着峰值时每秒要处理多少次检索？事实上，针对一个问题，我们可以想出很多的算法，但如果效率不高，是无法真正投入使用的。
Web搜索引擎是一个很新的研究领域，因为从它诞生到现在不过10年左右的时间。学术界IR(Information Retrieval)领域的研究为搜索引擎提供了不少算法方面的理论基础模型，但这些理论距构建一个好的Web搜索引擎还有很大一段距离。这需要我们探索和开发很多新的算法及系统。实际上，百度搜索引擎中的很多算法都极具创新性，而且都是基于实际应用的需求。这是和学术界研究工作的一个较大差异。学术界的算法研究主要是为了解决某个学术方面的问题，不是太关注实用性，以及效率。
举个例子来说，在传统的中文分词算法研究中，学术界最关注的是能达到多高的准确率，但对算法的运行速度上考虑的相对较少。可在百度，如果使用的分词算法速度太慢，就根本无法应用。此外，百度面对的是Web上的大量数据，大部分传统的IR算法都会遇到信息爆炸的问题，我们需要想出很多新的方法来解决这些问题。这对我们的工程师的算法提出了很高的要求。
Web上的数据是不断变化的，用户......
算法：元素选择问题总结(2006-01-15 16:42:00)
摘要：元素选择问题
注：中位数：中间大小的数 ；上取整用| |表示，下取整用[ ]表示
1．选最大
输入：n个不等的数
输出：max
算法1 Findmax
1. max←L[1]
2. for i←2 to lenth[L]
do if max ......
数学猜想(转）(2005-11-25 14:47:00)
摘要：数学猜想
1.【回归数猜想】
英国大数学家哈代(G.H.Hardy,1877-1947)曾经发现过一种有趣的现象:
153=13+53+33 371=33+73+13 370=33+73+03 407=43+03+73
他们都是三位数且等于各位数字的三次幂之和,这种巧合不能不令人感到惊讶.更为称奇的是,一位读者看过哈代的有趣发现后,竟然构造出其值等于各位数字四(五,六)次幂之和的四(五,六)位数:
1634=14+64+34+44 54748=55+45+75+45+85 548834=56+46+86+86+36+46
像这种其值等于各位数字的 n 次幂之和的 n 位数,称为 n 位 n 次幂回归数.本文只讨论这种回归数,故简称为回归数,人们自然要问:对于什么样的自然数 n 有回归数?这样的 n 是有限个还是无穷多个?对于已经给定的 n ,如果有回归数,那么有多少个回归数?
1986年美国的一位数学教师安东尼.迪拉那(Anthony Diluna)巧妙地证明了使 n 位数成为回归数的 n 只有有限个.
设 An 是这样的回归数,即:
An=a1a2a3...an=a1n+a2n+...+ann (其中 0<=a1,a2,...an<=9)
从而 10n-1<=An<=n9n 即 n 必须满足 n9n>10n-1 也就是 (10/9)n<10n ⑴
随着自然数 n 的不断增大,(10/9)n 值的增加越来越快,很快就会使得 ⑴ 式不成立,因此,满足⑴的 n 不能无限增大,即 n 只能取有限多个.进一步的计算表明:
(10/9)60=556.4798...<10*60=600......
2005年9月12日电脑报第36期编程点将(2005-09-12 20:45:00)
摘要：2005年9月12日电脑报第36期编程点将
题目：请编程实现将1到9 这九个数字分成三个3位数，要求第一个3位数，正好是第二个3位数的二倍，是第三个3位数的三倍。问应当怎样分法。
首先，我认为题目是错的。
原题：请编程实现将1到9 这九个数字分成三个3位数，要求第一个3位数，正好是第二个3位数的二倍，是第三个3位数的三倍。
按这样编的话应该是没有结果的，
我认为应该是：
第一个3位数，是第三个3位数的三倍，而第二个数是第三个数的两倍。
按修改后的题目：以下是我的程序：
程序的主要思想参考我的c语言程序设计百例的第60题，不过里面的题目也是错的，好像电脑报今年的编程点将有90％取自里面的题目。
/*算法思想：根据题意，最小的三位数m可能是在123－333之间，因此循环取尽这些值，
并由此计算出最大的三位数为：3*m,第二个数为：2*m(按原题应该是：3*m/2)。然后判断每个三位数
的各个位是否有重复，没有的话就完成了任务。当然，可能的分发不止一种，
我们采用count来计算可能的分法并输出来
*/
#include<iostream>
using namespace std;
int ok(int t,int *z);//判断每个三位数的各个位是否已经被取过
int A[9];//存放从小到大的三个三位数的各个位
void main()
{
int m,count=0;
for(m=123;m<=333;m++) /*最小的三位数的可能值*/
if(ok(m,A)&&ok(2*m,A+3)&&ok(3*m,A+6)) /*若满足题意*/
cout<<"第"<<++count<<"种可能的三个数是："<<3*m<<" "<<2*m<<" "<<m<<"\n";
}
int ok(int t,int *z) /*取得t的各个位的值，将其存入z指向的三个数......
2005年5月2日第17期电脑报编程点将(2005-09-10 21:15:00)
摘要：2005年5月2日第17期电脑报编程点将
题目：十个小孩围成一圈分糖果，老师分给第一个小孩10块，第二个小孩2块，第三个小孩8块，第四个小
孩22块，第五个小孩16块，第六个小孩4块，第七个小孩10块，第八个小孩6块，第九个小孩14块，第十个
小孩20块。然后所有的小孩同时将手中的糖分一半给右边的小孩；糖块数为奇数的人可向老师要一块。问
经过这样几次后大家手中的糖的块数一样多？每人各有多少块糖？
我的程序：（这道题在我的c语言程序设计百例里面的第75题）
/*这道题看起来简单，但是其实要一次完全做完整不不是很容易。
当然，这题目本身就有点歧义：起初我是这样理解的：第一个人把一半糖给第二个人，
然后第二个人检查一下糖是不是偶数，不是的话就再要一个糖，
然后再把总的糖分一半给第三个……后来发现这样做没有答案。
我的答案和获奖程序一基本上是一样的，主要的不同点在我的程序的注释的部分。
算法的思路比较简单就不分析了。
*/
#include<iostream>
using namespace std;
void main()
{
const int n=10;
int child[n]={10,2,8,22,16,4,10,6,14,20};
int temp,i,count=0;
bool tag=true;//标志分配完后是否每个数值都是相等的，相等时为false，不等时为true
while(tag)
{
count++;
&nb......
2005年4月25日第16期电脑报编程点将(2005-09-10 20:03:00)
摘要：2005年4月25日第16期电脑报编程点将
题目：小明有五本新书，要借给A,B,C三位小朋友，若每人每次只能借一本，则可以有多少种不同的借法？
我的程序：
/*算法思想：其实这是一个排列的问题，这里我们假设五本书的编号室从1——5，
用数组ABC[3]来表示A，B，C三个人，其数值表示这三个人所借的是什么书
（也就是哪个编号的书）。穷举使三个人都可能借到每一本书，
当然，不能两个人借同一本书。
*/
#include<iostream>
using namespace std;
void main()
{
int ABC[3],count=0;
for(ABC[0]=1;ABC[0]<=5;ABC[0]++)
for(ABC[1]=1;ABC[1]<=5;ABC[1]++)
for(ABC[2]=1;ABC[2]<=5;ABC[2]++)
if(ABC[0]!=ABC[1]&&ABC[0]!=ABC[2]&&ABC[1]!=ABC[2])
count++;
cout<<"总的借书方式有:"<<......
2005年8月22日第33期电脑报编程点将(2005-09-09 23:54:00)
摘要：2005年8月22日第33期电脑报编程点将
题目：某侦察队接到一项紧急任务，要求在A,B,C,D,E,F六个队员中尽可能多挑若干个人去完成任务，但有以下限制条件：
（1）A和B两人中至少去一个；
（2）A和D不能一起去；
（3）A、E和F三人中要派两个人去；
（4）B和C都去或者都不去；
（5）C和D两人中去一个；
（6）若D不去，则E也不去。
请用程序求出应该让哪几个人去？
我的分析和程序：
/*用整数a，b，c，d，e，f来表示这六个人去或者不去，值为0代表不去，值为1代表去。用循环让这六个数可以取遍0和1，
当满足题目所要求的条件就显示出来，题目中的条件可以通过下面的来判断：
(a||b)==1//条件（1）
&&(a&&d)==0//条件（2）
&&(((a&&e)==1&&f==0)||((a&&f)==1&&e==0)||((e&&f)==1&&a==0))//条件（3）
&&(b==c)//条件（4）
&&(c!=d)//条件（5）
&&(e<=d))//条件（6）
*/
初步程序：————这里没有考虑题目中的：尽可能多挑选若干个人去。也就是人应该尽量多
该程序在VC＋＋6.0通过运行，结果：可以叫下面的人去：A B C F
#include<iostream>
using namespace std;
int AA[6];
char BB[]={'A','B','C','D','E','F'};
void main()
{
int &a=AA[0],&b=AA[1],&c=AA[2],&d=AA[3],&e=AA[4],&f=AA[5......
2005年9月5日第35期电脑报编程点将台(2005-09-10 18:44:00)
摘要：2005年9月5日第35期电脑报编程点将台
题目：构造N*N阶的拉丁矩阵（2<=N<=9)，使方阵中的每一行和每一列中的数字1到N只出现一次。如N＝4时：
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
我的程序：
/*算法思想：
通过观察，我们可以发现规律就是：第一行从1开始递增直到n，
第二行从2开始递增，当超过n是就得到其与n的模加上1即可，
以此类推直到完成所有的排列。
我的程序的问题：没有考虑所有可能的情况，只是根据已有的得出规律
其实相当于是不完全归纳法。不过，要是想得出所有可能的情况的时间复杂度将比较大
*/
#include<iostream>
using namespace std;
void main()
{
int i,j,n;
const int maxsize=9;
int AA[maxsize][maxsize];
cin>>n;
if(n<2||n>9)
{
cout<<"You are wrong!";
return ;
}
for(i=0;i<n;i++)//初始化
&......
2005年5月16日第19期电脑报编程点将台(2005-09-09 22:45:00)
摘要：2005年5月16日第19期电脑报编程点将台
题目：三对情侣参加婚礼，三个新郎为A,B,C,三个新娘为X,Y,Z。有人不知道谁和谁结婚，于是询问了六
个新人中的三人，但是听到的回答是这样的：A说他将和X结婚；X说她将的未婚夫是C；C说他将的Z结婚。
这人听后知道他们在开玩笑，全是假话。请编程找出谁将和谁结婚。
我的程序：
/*算法思想：对三个新娘分别分别新郎，当满足以下条件时就输出：
X!='A'&&X!='C'&&Z!='C'表示三个假话，&&X!=Y&&X!=Z&&Y!=Z
表示每个新娘的新郎都不一样（^_^也就是没有一妻多夫）
我的程序的时间复杂度是：n的三次方，所以不是很好，
但是要是直接从题目中推理然后去掉一些可能性后再配对的话，
那么其实马上可以得出答案，也就是这题其实出得很差得，完全没
必要用计算机来推理。
在我的程序的后面是那期获奖的两个程序。大家可以参考。不过，感觉我的程序
的可读性比较好，获奖的程序我也看了很久理解什么怎么得出来的。
*/
#include<iostream>
using namespace std;
void main()
{
char X,Y,Z;
for(X='A';X<='C';X++)
for(Y='A';Y<='C';Y++)
for(Z='A';Z<='C';Z++)
......
2005年8月15日第32期电脑报编程点将(2005-08-25 16:46:00)
摘要：2005年8月15日第32期电脑报编程点将
题目：有30个人，其中有男人、女人和小孩，他们在一家饭馆吃饭，总共花了50元；每个人吃饭的花费是：男人3元，女人2元，小孩1元。请编程求解男人、女人和小孩各几人？
我的分析和程序：
这道题其实跟“百钱买百鸡”几乎是完全相同，很easy。在题目中说：有30个人，其中有男人、女人和小孩。因此就是说这三种人都应该有。我们用mNum,woNum,chNum分别来表示男人，女人和小孩的数量，这他们的值至少为1。
程序：
#include<iostream>
using namespace std;
void main()
{
int mNum,woNum,chNum,count=0;
for(mNum=1;mNum<16;mNum++)
for(woNum=1;woNum<=23;woNum++)
{
chNum=30-mNum-woNum;
if(3*mNum+2*woNum+chNum==50)
cout<<"第"<<++count<<"种可能是男人、女人、小孩分别为："
&......