zero91's Blog
智力趣题--逻辑推理（1）
1、你让工人为你工作7天，给工人的回报是一根金条。金条平分成相连的7段，你必须在每天结束时给他们一段金条，如果只许你两次把金条弄断，你如何给你的工人付费？
二进制
2、请把一盒蛋糕切成8份，分给8个人，但蛋糕盒里还必须留有一份。
有点脑筋急转弯的味道。把切成的8份蛋糕先拿出7份分给7人，剩下的1份连蛋糕盒一起分给第8个人。
3、小明一家过一座桥，过桥时是黑夜，所以必须有灯。现在小明过桥要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的妈妈要8秒，小明的爷爷要12秒。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30秒就会熄灭。问：小明一家如何过桥？
这是一道非常经典的过桥问题。网上说最优答案为19，不知道是怎么来的。个人觉得不可能，应该为29。方法如下：
小明和弟弟同时过桥，3秒
小明回来，1秒
小明妈妈和爷爷同时过桥，12秒
小明弟弟回来，3秒
小明和他爸同时过桥，6秒
小明回来，1秒
小明和弟弟同时过桥，3秒。把以上加起来，即为29秒。此题具有通用的解法，具体思路如下：
设 人数为n，不妨设n>=4，因为n=1，2，3很容易知道。在这里我们采用贪心的策略，因为最慢的那个人是一定要过河的，且他的过河时间不可能减 少，每次过完河之后一定要有一个人回来，这就代表一定会有一个人一来一回，即等于没有过河，很容易想到应该选择速度较快的人去做。设n个人中最快的两个人 为A、B，最慢的两个人为C、D（过河时间A<B<C<D)，有两种过河方案：
（1）AB过河，A回，CD过河，B回，耗时A+2B+D
（2）AD过河，A回，AC过河，A回，耗时2A+C+D
在以上两种方案中选择花费时间较小的就可以了，POJ上面有这个题目：http://poj.org/problem?id=1700，看懂的朋友可以去练练手，代码非常简单。
4、 一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其他人帽子的颜色,却看不到自己的。主持人先让大家看看别人头 上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。 一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑 帽子?
假如只有一个人戴黑帽子，那他看到所有人都戴白帽，在第一次关灯时就应自打耳光，所以应该不止一个人戴黑帽子；如果有两顶黑帽子，第一次两人都只看到对方头上的黑帽子，不敢确定自己的颜色，但到第二次关灯，这两人应该明白
，如果自己戴着白帽，那对方早在上一次就应打耳光了，因此自己戴的也是黑帽子，于是也会有耳光声响起；可事实是第三次才响起了耳光声，说明全场不止两顶黑帽，依此类推，应该是关了几次灯，有几顶黑帽。
5、一楼到十楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯 从一楼到十楼，每层楼电梯门都会打开一次，只能拿一次钻石，问怎样才能拿到最大的一颗？
以 前在算法导论上看过这一题，是讲聘最优的面试者的，跟这一题几乎一模一样。具体可以这样操作：先选择一个层数如5，在第一层到第五层之间的所有钻石，不过 有多大，都不拿，记下他们最大的那颗，然后从第六层开始，一旦碰到钻石接近于或者大于记录下来的那个钻石，就拿走，不再管其他的层。这个去做，有一个极端 的情况就是，后面六层没有哪一层的钻石满足前面的条件，这样就只好去拿走最后一层的钻石了。
6、烧一根不均匀的绳要用一个小时，如何用它来判断半个小时 ?
两边同时烧就可以了。
7、有7克、2克砝码各一个，天平一只，如何只用这些物品三次将140克的盐 分成50、90克各一份？
（1）140 = 70 + 70（分成两个70克）
（2）用7克、2克两个砝码取出9克盐，分成了三份，分别是：70、61、9
（3）左边放61克盐，放2克的砝码和9克盐和50克盐（注意9克盐是上次分出来的，50克盐是这次称出来的，两者不混合就可）。
8、你有四人装药丸的罐子，每个药丸都有一定的重量，被污染的药丸是没被 污染的重量+1.只称量一次，如何判断哪个罐子的药被污染了？
第一个罐子去一粒药丸，第二个去两粒，第三个取三粒，第四个取四粒，称一下总重量就可以了。
9、如果你有无穷多的水，一个3夸脱的和一个5夸脱的提桶，你如何准确称出 4夸脱的水？
用3夸脱的提桶装满水倒入5夸脱的提桶，在用3夸脱的提桶装满水倒入刚才的那个5夸脱的提桶，直到5夸脱的提桶满了，这样3夸脱的提桶还剩下1夸脱的水， 倒掉5夸脱提桶中的水，把3夸脱中的1夸脱水倒入到5夸脱的提桶中，在用3夸脱的提桶装满水，倒入刚才的那个5夸脱的提桶中就可以了。
10、你有一桶果冻，其中有黄色，绿色，红色三种，闭上眼睛选出同样颜色 的两个，抓取同种颜色的两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻？
鸽巢原理，4个
11、假设时钟到了12点。注意时针和分针重叠在一起。在一天之中，时针和分针共重叠多少次？你知道它们重叠时的具体时间吗？
应该很多人小学的时候就看过这个题目。23次，记x为从0点开始所经历的分钟数，则有等式x%60=x/12(0 <= x < 60 * 12)。求出半天所有解。为什么是23次，应该11点那次的重合与12点的那次重合是同时的，只能算是一次。
11、中间只隔一个数字的两个素数被称为素数对，比如17和19。证明素数对之 间的数字总能被6整除（假设这两个素数都大于6）。
大于6的之间的素数对之间的元素肯定是偶数，而相邻的三个数中一定有一个数能够整除3，只能是素数对之间的那个数。
12、一个屋子有一个门（门是关闭的）和3盏电灯。屋外有3个开关，分别与这 3盏灯相连。你可以随意操纵这些开关，可一旦你将门打开，就不能变换开关了。确定每个开关具体管哪盏灯。
现在门外打开一个开关，等一会儿，然后关掉它，再另外一个开关，在走到屋内，热而不亮的一个灯泡是第一个开关所控制，亮的便是第二个，剩下的一个就是第三个开关所控制的。
13、假设你有8个球，其中一个略微重一些，但是找出这个球的惟一方法是将两个球放在天平上对比。最少要称多少次才能找出这个较重的球？
很多人第一反应估计是二分吧。这样需要称三次。其实，我们有另外一种方法，称两次就可以了。假设8个球的编号分别是1、2、3……8，把球分成三份，分别 是123、456、78，比较123和456的重量，相等则说明在要找的球在78两个球中，再比较78两个球就可以了。如果有一边较重，则说明要找的球在 较重的那一边，不妨设为123这边比较重，则再比较12两个球的重量，若相等，则3球为较重的球，否则，较重的那个球就是我们要找的那个球。
14、4，4，10，10，加减乘除，怎么出24点？
（10*10-4）/4
15、1000!有几位数，为什么？
用Stirling逼近公式。
16、已知两个1~30之间的数字，甲知道两数之和，乙知道两数之积。
甲问乙："你知道是哪两个数吗？"乙说："不知道"；
乙问甲："你知道是哪两个数吗？"甲说："也不知道"；
于是，乙说："那我知道了"；
随后甲也说："那我也知道了"；
这两个数是什么？
这一题不是我想出来的，以下是网上的一个答案：
允许两数重复的情况下
答案为x=1，y=4；甲知道和A=x+y=5，乙知道积B=x*y=4
不允许两数重复的情况下有两种答案
答案1：为x=1，y=6；甲知道和A=x+y=7，乙知道积B=x*y=6
答案2：为x=1，y=8；甲知道和A=x+y=9，乙知道积B=x*y=8
解：
设这两个数为x，y.
甲知道两数之和 A=x+y；
乙知道两数之积 B=x*y；
该题分两种情况 ：
允许重复， 有(1 <= x <= y <= 30)；
不允许重复，有(1 <= x < y <= 30)；
当不允许重复，即(1 <= x < y <= 30)；
1)由题设条件：乙不知道答案
<=> B=x*y 解不唯一
=> B=x*y 为非质数
又∵ x ≠ y
∴ B ≠ k*k (其中k∈N)
结论(推论1)：
B=x*y 非质数且 B ≠ k*k (其中k∈N)
即：B ∈(6，8，10，12，14，15，18，20...)
证明过程略。
2)由题设条件：甲不知道答案
<=> A=x+y 解不唯一
=> A >= 5；
分两种情况：
A=5，A=6时x，y有双解
A>=7 时x，y有三重及三重以上解
假设 A=x+y=5
则有双解
x1=1，y1=4；
x2=2，y2=3
代入公式B=x*y：
B1=x1*y1=1*4=4；(不满足推论1，舍去)
B2=x2*y2=2*3=6；
得到唯一解x=2，y=3即甲知道答案。
与题设条件："甲不知道答案"相矛盾，
故假设不成立，A=x+y≠5
假设 A=x+y=6
则有双解。
x1=1，y1=5；
x2=2，y2=4
代入公式B=x*y：
B1=x1*y1=1*5=5；(不满足推论1，舍去)
B2=x2*y2=2*4=8；
得到唯一解x=2，y=4
即甲知道答案
与题设条件："甲不知道答案"相矛盾
故假设不成立，A=x+y≠6
当A>=7时
∵ x，y的解至少存在两种满足推论1的解
B1=x1*y1=2*(A-2)
B2=x2*y2=3*(A-3)
∴ 符合条件
结论(推论2)：A >= 7
3)由题设条件：乙说"那我知道了"
=>乙通过已知条件B=x*y及推论(1)(2)可以得出唯一解
即：
A=x+y， A >= 7
B=x*y， B ∈(6，8，10，12，14，15，16，18，20...)
1 <= x < y <= 30
x，y存在唯一解
当 B=6 时：有两组解
x1=1，y1=6
x2=2，y2=3 (∵ x2+y2=2+3=5 < 7∴不合题意，舍去)
得到唯一解 x=1，y=6
当 B=8 时：有两组解
x1=1，y1=8
x2=2，y2=4 (∵ x2+y2=2+4=6 < 7∴不合题意，舍去)
得到唯一解 x=1，y=8
当 B>8 时：容易证明均为多重解
结论：
当B=6时有唯一解 x=1，y=6当B=8时有唯一解 x=1，y=8
4)由题设条件：甲说"那我也知道了"
=> 甲通过已知条件A=x+y及推论(3)可以得出唯一解
综上所述，原题所求有两组解：
x1=1，y1=6
x2=1，y2=8
当x<=y时，有(1 <= x <= y <= 30)；
同理可得唯一解 x=1，y=4
POJ 1191棋盘分割
原题目如下（http://poj.org/problem?id=1191）：
Description
原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。
均方差
，其中平均值 
，xi为第i块矩形棋盘的总分。请编程对给出的棋盘及n，求出O'的最小值。
Input
第2行至第9行每行为8个小于100的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。
Output
Sample Input
3 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 3
Sample Output
1.633
Source
得，只需要求出
的最小值即可，而
，不难得出如果最小，一定会有
最小，也就是说问题具有最优子结构的性质，这让我们想到了DP。题目要求在切割矩形的时候，每一次分出的一定是两个矩形，且切割矩形的时候，有两个方向可以切，横切和竖切，横切和竖切分别可以有两个不同的子问题，只需要求出这些子问题中满足题目要求的最优值即可。另外，我们需要存储当前的子问题是处于哪个子矩阵范围内，这就必然需要存储矩阵信息，最自然的就是想到用数组的下标来存储，所以，这一题可以使用数组的四维来表示一个完整的子矩阵。由以上可以知道，解决此问题就相当于求解有n个子矩阵时的最优值，而当只有1个子矩阵时，也就是该矩阵本身，这个可以直接从输入信息中得出，做一个预处理即可。采用自下向上程序实现方法就可以了。
#include <stdio.h>
#include <math.h>
#define MAX_N 8
#define MAX 15
#define INF 999999999
#define minv(a,b) ( (a) < (b) ? (a) : (b) )
int pointV[ MAX_N+1 ][ MAX_N+1 ][ MAX_N+1 ][ MAX_N+1 ];
int dp[ MAX_N+1 ][ MAX_N+1 ][ MAX_N+1 ][ MAX_N+1 ][ MAX ];
void
init( int n )
{
int x1, y1, x2, y2, i;
for( x1 = 1; x1 <= MAX_N; ++x1 )
for( y1 = 1; y1 <= MAX_N; ++y1 )
for( x2 = x1; x2 <= MAX_N; ++x2 )
for( y2 = y1; y2 <= MAX_N; ++y2 ){
if( x1 != x2 || y1 != y2 ){
pointV[x1][y1][x2][y2] = pointV[x1][y1][x2-1][y2] +
pointV[x1][y1][x2][y2-1] - pointV[x1][y1][x2-1][y2-1] +
pointV[x2][y2][x2][y2];
}
dp[x1][y1][x2][y2][1] = pointV[x1][y1][x2][y2] * pointV[x1][y1][x2][y2];
for( i = 2; i <= n; ++i )
dp[x1][y1][x2][y2][i] = INF;
}
}
void
getResult( int n )
{
int k, x1, y1, x2, y2, i;
int temp;
for( k = 2; k <= n; ++k )
for( x1 = 1; x1 <= MAX_N; ++x1 )
for( y1 = 1; y1 <= MAX_N; ++y1 )
for( x2 = x1; x2 <= MAX_N; ++x2 )
for( y2 = y1; y2 <= MAX_N; ++y2 ){
for( i = x1; i < x2; ++i ){
temp = minv( dp[x1][y1][i][y2][k-1] + dp[i+1][y1][x2][y2][1],
dp[i+1][y1][x2][y2][k-1] + dp[x1][y1][i][y2][1] );
if( temp < dp[x1][y1][x2][y2][k] )
dp[x1][y1][x2][y2][k] = temp;
}
for( i = y1; i < y2; ++i ){
temp = minv( dp[x1][y1][x2][i][k-1] + dp[x1][i+1][x2][y2][1],
dp[x1][i+1][x2][y2][k-1] + dp[x1][y1][x2][i][1] );
if( temp < dp[x1][y1][x2][y2][k] )
dp[x1][y1][x2][y2][k] = temp;
}
}
}
int
main( void )
{
int n;
int i, j;
double average = 0.0;
scanf( "%d", &n );
for( i = 1; i <= MAX_N; ++i )
for( j = 1; j <= MAX_N; ++j ){
scanf( "%d", &pointV[i][j][i][j] );
average += pointV[i][j][i][j];
}
average /= n;
init( n );
getResult( n );
printf( "%.3f\n", sqrt( (double)dp[1][1][MAX_N][MAX_N][n]/n - average*average ) );
return 0;
}
KMP算法详解(Matrix67)
转自：http://www.matrix67.com/blog/archives/115
如果机房马上要关门了，或者你急着要和MM约会，请直接跳到第六个自然段。
我们这里说的KMP不是拿来放电影的（虽然我很 喜欢这个软件），而是一种算法。KMP算法是拿来处理字符串匹配的。换句话说，给你两个字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。 比如，字符串A="I'm matrix67"，字符串B="matrix"，我们就说B是A的子串。你可以委婉地问你的MM：“假如你要向你喜欢的人表白的话，我的名字是你的告白 语中的子串吗？”
解决这类问题，通常我们的方法是枚举从A串的什么位置起开始与B匹配，然后验证是否匹配。假如A串长度为n，B串长度为 m，那么这种方法的复杂度是O (mn)的。虽然很多时候复杂度达不到mn（验证时只看头一两个字母就发现不匹配了），但我们有许多“最坏情况”，比如，A= "aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我们将介绍的是一种最坏情况下O(n)的算法（这里假设 m<=n），即传说中的KMP算法。
之所以叫做KMP，是因为这个算法是由Knuth、Morris、Pratt三个提出来的，取 了这三个人的名字的头一个字母。这时，或许你突然明白了AVL 树为什么叫AVL，或者Bellman-Ford为什么中间是一杠不是一个点。有时一个东西有七八个人研究过，那怎么命名呢？通常这个东西干脆就不用人名 字命名了，免得发生争议，比如“3x+1问题”。扯远了。
个人认为KMP是最没有必要讲的东西，因为这个东西网上能找到很多资料。但网上 的讲法基本上都涉及到“移动(shift)”、“Next函数”等概念，这非常容易产生误解（至少一年半前我看这些资料学习KMP时就没搞清楚）。在这 里，我换一种方法来解释KMP算法。
假如，A="abababaababacb"，B="ababacb"，我们来看看KMP 是怎么工作的。我们用两个指针i和j分别表示，A[i-j+ 1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。当A[i+1]=B[j+1]时，i和j各加一；什么时候j=m了，我们就 说B是A的子串（B串已经整完了），并且可以根据这时的i值算出匹配的位置。当A[i+1]<>B[j+1]，KMP的策略是调整j的位置 （减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配（从而使得i和j能继续增加）。我们看一看当 i=j=5时的情况。
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
此 时，A[6]<>B[6]。这表明，此时j不能等于5了，我们要把j改成比它小的值j'。j'可能是多少呢？仔细想一下，我们发现，j'必须 要使得B[1..j]中的头j'个字母和末j'个字母完全相等（这样j变成了j'后才能继续保持i和j的性质）。这个j'当然要越大越好。在这里，B [1..5]="ababa"，头3个字母和末3个字母都是"aba"。而当新的j为3时，A[6]恰好和B[4]相等。于是，i变成了6，而j则变成了 4：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
从 上面的这个例子，我们可以看到，新的j可以取多少与i无关，只与B串有关。我们完全可以预处理出这样一个数组P[j]，表示当匹配到B数组的第j个字母而 第j+1个字母不能匹配了时，新的j最大是多少。P[j]应该是所有满足B[1..P[j]]=B[j-P[j]+1..j]的最大值。
再后来，A[7]=B[5]，i和j又各增加1。这时，又出现了A[i+1]<>B[j+1]的情况：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
由于P[5]=3，因此新的j=3：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
这时，新的j=3仍然不能满足A[i+1]=B[j+1]，此时我们再次减小j值，将j再次更新为P[3]：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
现在，i还是7，j已经变成1了。而此时A[8]居然仍然不等于B[j+1]。这样，j必须减小到P[1]，即0：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 0 1 2 3 4 5 6 7
终于，A[8]=B[1]，i变为8，j为1。事实上，有可能j到了0仍然不能满足A[i+1]=B[j+1]（比如A[8]="d"时）。因此，准确的说法是，当j=0了时，我们增加i值但忽略j直到出现A[i]=B[1]为止。
这个过程的代码很短（真的很短），我们在这里给出：
j:=0;
for i:=1 to n do
begin
while (j>0) and (B[j+1]<>A[i]) do j:=P[j];
if B[j+1]=A[i] then j:=j+1;
if j=m then
begin
writeln('Pattern occurs with shift ',i-m);
j:=P[j];
end;
end;
最后的j:=P[j]是为了让程序继续做下去，因为我们有可能找到多处匹配。
这个程序或许比想像中的要简单，因为对于i值的不断增加，代码用的是for循环。因此，这个代码可以这样形象地理解：扫描字符串A，并更新可以匹配到B的什么位置。
现在，我们还遗留了两个重要的问题：一，为什么这个程序是线性的；二，如何快速预处理P数组。
为 什么这个程序是O(n)的？其实，主要的争议在于，while循环使得执行次数出现了不确定因素。我们将用到时间复杂度的摊还分析中的主要策略，简单地说 就是通过观察某一个变量或函数值的变化来对零散的、杂乱的、不规则的执行次数进行累计。KMP的时间复杂度分析可谓摊还分析的典型。我们从上述程序的j 值入手。每一次执行while循环都会使j减小（但不能减成负的），而另外的改变j值的地方只有第五行。每次执行了这一行，j都只能加1；因此，整个过程 中j最多加了n个1。于是，j最多只有n次减小的机会（j值减小的次数当然不能超过n，因为j永远是非负整数）。这告诉我们，while循环总共最多执行 了n次。按照摊还分析的说法，平摊到每次for循环中后，一次for循环的复杂度为O(1)。整个过程显然是O(n)的。这样的分析对于后面P数组预处理 的过程同样有效，同样可以得到预处理过程的复杂度为O(m)。
预处理不需要按照P的定义写成O(m^2)甚至O(m^3)的。我们可以通 过P[1],P[2],...,P[j-1]的值来获得P[j]的值。对于刚才的B="ababacb"，假如我们已经求出了 P[1],P[2],P[3]和P[4]，看看我们应该怎么求出P[5]和P[6]。P[4]=2，那么P [5]显然等于P[4]+1，因为由P[4]可以知道，B[1,2]已经和B[3,4]相等了，现在又有B[3]=B[5]，所以P[5]可以由P[4] 后面加一个字符得到。P[6]也等于P[5]+1吗？显然不是，因为B[ P[5]+1 ]<>B[6]。那么，我们要考虑“退一步”了。我们考虑P[6]是否有可能由P[5]的情况所包含的子串得到，即是否P[6]=P[ P[5] ]+1。这里想不通的话可以仔细看一下：
1 2 3 4 5 6 7
B = a b a b a c b
P = 0 0 1 2 3 ?
P[5]=3 是因为B[1..3]和B[3..5]都是"aba"；而P[3]=1则告诉我们，B[1]、B[3]和B[5]都是"a"。既然P[6]不能由P[5] 得到，或许可以由P[3]得到（如果B[2]恰好和B[6]相等的话，P[6]就等于P[3]+1了）。显然，P[6]也不能通过P[3]得到，因为 B[2]<>B[6]。事实上，这样一直推到P[1]也不行，最后，我们得到，P[6]=0。
怎么这个预处理过程跟前面的KMP主程序这么像呢？其实，KMP的预处理本身就是一个B串“自我匹配”的过程。它的代码和上面的代码神似：
P[1]:=0;
j:=0;
for i:=2 to m do
begin
while (j>0) and (B[j+1]<>B[i]) do j:=P[j];
if B[j+1]=B[i] then j:=j+1;
P[i]:=j;
end;
最后补充一点：由于KMP算法只预处理B串，因此这种算法很适合这样的问题：给定一个B串和一群不同的A串，问B是哪些A串的子串。
串匹配是一个很有研究价值的问题。事实上，我们还有后缀树，自动机等很多方法，这些算法都巧妙地运用了预处理，从而可以在线性的时间里解决字符串的匹配。我们以后来说。
昨天发现一个特别晕的事，知道怎么去掉BitComet的广告吗？把界面语言设成英文就行了。
还有，金山词霸和Dr.eye都可以去自杀了，Babylon素王道。
Matrix67原创
转贴请注明出处
数学之美：垂心的各种优雅的性质
转自：http://www.matrix67.com/blog/archives/4340#more-4340
下面这些文字来源于我在初三数学竞赛课的一份讲义。这节课的主题本是四点共圆，但由此引出了三角形中很多漂亮的性质，让人深感数学之美。在此整理 出来，献给所有还在中学读书的读者，以及早已远离中学数学的 80 后。不管大家是否喜爱数学，想必都会被这些奇妙的结论所震撼。
三角形的奇迹首先表现在各个“心”上：三角形内部的每一组有几何意义的线条都交于一点。三条角平分线交于一点，这个点就叫做三角形的“内 心”，它是三角形内切圆的圆心；三边的中垂线交于一点，这个点就叫做三角形的“外心”，它是三角形外接圆的圆心；三角形的三条中线也交于一点，这个点叫做 三角形的“重心”，因为它真的就是这个三角形的重心。用力学方法可以很快推导出，它位于各中线的三等分点处。这些心将会在本文后面某个出人意料的地方再次 出现。
三角形的三条高也不例外——它们也交于一点，这个点就叫做三角形的垂心。
垂心看上去很不起眼，但深入研究后即会冒出很多奇妙的结论。由于两个斜边重合的直角三角形将会产生出共圆的四点，因此画出三角形的三条高后，会出现大量四点共圆的情况，由此将挖掘出一连串漂亮的结论。让我们先来看一个简单而直接的结论：
定理：若 D 、 E 、 F 分别是 △ABC 三边的高的垂足，则 ∠1 = ∠2 。
证明：由于 ∠AFC = ∠ADC = 90°，因此 A 、 C 、 D 、 F 四点共圆，因此 ∠1 = 180° - ∠CDF = ∠A 。同理，由 A 、 B 、 D 、 E 四点共圆可知 ∠2 = ∠A 。因此 ∠1 = ∠2 。
如果把三边垂足构成的三角形称作“垂足三角形”的话，我们就有了下面这个听上去很帅的推论：
推论：三角形的垂心是其垂足三角形的内心。
证明：因为 AD 垂直于 BC，而刚才又证明了 ∠1 = ∠2，因此 ∠3 = ∠4 ，即 HD 平分 ∠EDF 。类似地， HE 、 HF 都是 △DEF 的内角平分线，因此 H 是 △DEF 的内心。
另一个有趣的推论如下：
推论：将 △ABC 沿 AC 翻折到 △AB'C ，假设 EF 翻折到了 EF' ，则 EF' 和 DE 共线。
证明：这可以直接由上图中的 ∠1 = ∠2 推出。
1775 年，Fagnano 曾经提出了下面这个问题：在给定的锐角三角形 ABC 中，什么样的内接三角形具有最短的周长。这个问题就被称作“Fagnano 问题”。 Fagnano 自己给出了答案：周长最短的内接三角形就是垂足三角形。下面我们就来证明这个结论。
定理：在 △ABC 的所有内接三角形中，垂足三角形 △DEF 拥有最短的周长。
证明：像上图那样，把三角形翻折五次，得到折线段 DEF1D2E2F3D4 。这条折线段的总长度等于内接三角形 DEF 周长的两倍。注意到，由前面提到的垂足三角形的性质可知，这条折线段正好组成了一条直线段。另外，注意到如此翻折之后， BC 和 B2C2 是平行且相等的，而且 D 和 D4 位于两线段上相同的位置，因此从 D 到 D4 的折线段总长以直线段 DD4 最短。这就说明了，垂足三角形 △DEF 拥有最短的周长。
不过，这还不够震撼，垂心还有不少的本事。四点共圆还会给我们带来其它的等角。
定理：若 D 、 E 、 F 分别是 △ABC 三边的高的垂足，则 ∠1 = ∠2 。
证明：由于 ∠BFH = ∠BDH = 90°，因此 B 、 F 、 H 、 D 四点共圆，因此 ∠1 = 180° - ∠FHD = ∠2 。
这将给我们带来了下面这个非常漂亮的推论。
推论：把 △ABC 的垂心 H 沿 BC 边翻折到 H' ，则 H' 在 △ABC 的外接圆上。
证明：由于 H 和 H' 沿 BC 轴对称，因此 ∠H' = ∠1 。而前面已经证明过了， ∠1 = ∠2 。因此， ∠H' = ∠2 。而 ∠H' 和 ∠2 都是 AC 所对的角，它们相等就意味着 A 、 C 、 H' 、 B 是四点共圆的。
换一种描述方法，这个结论还可以便得更酷：
推论：把 △ABC 的垂心 H 沿三边分别翻折到 H1 、 H2 、 H3 ，则 A 、 B 、 C 、 H1 、 H2 、 H3 六点共圆。
证明：这可以直接由前面的结论得到。
另一个更加对称美观的结论如下：
推论：若 D 、 E 、 F 分别是 △ABC 三边的高的垂足， H 是垂心，则 AH·DH = BH·EH = CH·FH 。
证明：做出 △ABC 的外接圆，然后延长 HD 、 HE 、 HF ，它们与外接圆的交点分别记作 H1 、 H2 、 H3 。前面的结论告诉我们， HH1 = 2HD ， HH2 = 2HE ， HH3 = 2HF。而相交弦定理（或者圆幂定理，可以用相似迅速得证）告诉我们， AH·HH1 = BH·HH2 = CH·HH3 。各等量同时除以 2 ，就有 AH·DH = BH·EH = CH·FH 。
让我们再来看一个与外接圆有关的定理。
定理：若 D 、 E 、 F 分别是 △ABC 三边的高的垂足， H 是垂心。过 C 作 BC 的垂线，与 △ABC 的外接圆交于点 G 。则 CG = AH 。
证明：我们将证明四边形 AHCG 的两组对边分别平行，从而说明它是一个平行四边形。注意到 CG 和 AD 都垂直于 BC ，因此 CG 和 AD 是平行的。由于 ∠BCG 是直角，这说明 BG 是圆的直径，也就说明 ∠BAG 也是直角，即 GA 垂直于 AB 。而 CF 也垂直于 AB ，所以 AG 与 CF 平行。因而四边形 AHCG 是平行四边形， CG = AH 。
它也能带来一个更帅的推论：
推论：若 H 是 △ABC 的垂心，O 是 △ABC 的外心，则 O 到 BC 的垂线段 OM 与 AH 平行，并且是 AH 长度的一半。
证明：前面我们证明了，上图中的 CG 与 AH 平行且相等。注意到 BG 是外接圆的直径， BG 的中点就是圆心，也就是 △ABC 的外心 O 。垂线段 OM 是 △BCG 的中位线，它平行且等于 CG 的一半，从而也就平行且等于 AH 的一半。
好了，下面大家将会看到的就是初等几何的瑰宝：
推论：三角形的垂心、重心和外心共线，且重心在垂心和外心连线的三等分点处。
证明：把 AM 和 HO 的交点记作 X 。刚才我们已经证明了， AH 与 OM 平行，且长度之比为 1:2 。因此， △AHX 和 △MOX 相似，相似比为 1:2 。由此可知， HX:XO = 1:2 ，即 X 在线段 HO 的三等分点处。另外， AX:XM = 1:2 ，也就是说 X 在三角形中线 AM 的 1:2 处。这说明， X 正是三角形的重心！
任意给定 一个三角形，它的垂心、重心和外心三点共线，且重心将垂心和外心的连线分成 1:2 两段。这个美妙的结论是大数学家 Euler 在 1765 年时发现的，它是众多“Euler 定理”的其中之一。
说到 Euler 定理，九点圆是不能不提的；不过由于篇幅有限，也就到这儿为止了。垂心的性质还有很多，很难在一篇文章里把它们讲完。而且，这还仅仅是与垂心相关的定理， 三角形中的心还有很多很多。1994 年，美国数学教授 Clark Kimberling 开始收集历史上被数学家们研究过的三角形的心，并建立了“三角形中心百科全书”的网站。这个网站记录了几乎所有目前已知的三角形的心。在这部百科全书里， 每个三角形的心都有一个编号，编号为 n 的心就用符号 X(n) 来表示，其中 X(1) 到 X(8) 分别为内心、重心、外心、垂心、九点圆圆心、类似重心、 Gergonne 点和 Nagel 点。不但每个心都有自己独特的几何性质，各个心之间还有大量共线、共圆的关系。
这个网站的地址是 http://faculty.evansville.edu/ck6/encyclopedia/ETC.html 。目前，整个网站已经收集了 3000 多个三角形的心，且这个数目还在不断增加。