思维训练

思维陷阱及一些设计思路

2009年1月14日 阅读(644)

通常人们会犯两种错误,一种是低估了问题的难度,一种是高估了问题的难度。这样的两种错误,通常又会导致同一种后果,不去尝试解决问题。一种是不屑,一种是不敢,同样的后果最终导致解决问题的能力低下。对于实现的观点也是如此。

思考,人们倾向于从直接看到的,眼前的状况出发,却容易忽略历史的或者未来的因素。同样的导致无法看清问题。举个例子,校园里流传着这样的说法,本科生住最好的楼,硕士生其次,博士住最差的楼,可见学校更关爱本科生。请问这样的结论所依据的观察有什麽问题?是的,有些问题。因为我们习惯于从眼前的情况出发,忽略了历史,因为我们看到的只是现在的情况,因为新的楼房只是近几年才盖起来的,那么在没有盖这些楼之前的状况是怎样的呢?

很多情况很多问题,可以用同一种思想解决,某些情况下只是貌似而已。而其中的差异,需要仔细的洞察,就像找出其中的相同那样。很多时候思维的惯性会占据主导,导致无法做出公正的判断。

曾经流传较光的一个问题是这样的:今有a b c d 四人在晚上都要从桥的左边到右边。此桥一次最多只能走两人,而且只有一支手电筒,过桥是一定要用手电筒。四人过桥最快所需时间如下为:a 2 分;b 3 分;c 8 分;d 10分。走的快的人要等走的慢的人,请问过桥需要的最短时间?

这里有一个最基本的陷阱: 我们容易忘掉,并不是每次让a过去就最快,实际上如果可以让两个最慢的人一块过去,也是可能可以节省大量时间的。实际上,有时当问题的前提不是那么清楚的时候,我们还需要问一个问题:手电筒的势力范围如何,能否在中间覆盖两头等等,如果加上这个因素答案或许就不是如上了。

在比如:地球上有多少个这样的点:往南走1公里,往东走1公里,再往北走1公里,你能回到原来的出发点。
通常我们可以想起北极点,可是真的只有这一个吗?

通用的设计策略:
1.n个数两个数和,差最大,小,中值
排序+杨氏矩阵

2.子序列和
前缀和

3.环上的子串查找
倍增 环-》变成链

4.字符串逆转
转置 循环移动

5.链表环的检测 确保追击成功
12追击法

6.模型转换
差分约束 不等式-》最短路
二分匹配 -》最短流
多源单目的最短路 -》单源最短路

7.
线段树 -》子序列和,最大,最小
后缀数组-》字符串处理
树状数组-》子序列和

 

 

 

You Might Also Like