思维训练

 转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/70971767200910158392605/

概率部分

1.某城市发生了一起汽车撞人逃跑事件，该城市只有两种颜色的车,蓝15%绿85%，事发时有一个人在现场看见了，他指证是蓝车，但是根据专家在现场分析,当时那种条件能看正确的可能性是80%那么,肇事的车是蓝车的概率到底是多少? read more

问题

是这样的：每次只交换相邻的两个数 如何在n!次交换中找到所有的排列。

问题可能有些问题，n!-1次交换更合适，当然说n！也可以，但是不要把第一个开始元素算在呢。看到这个问题时大概想到了两个思路，一个根据排列之间的相邻关系，组成一个图，证明这个图中存在一个汉密尔顿路。另一个则是采用递归的思路，首先我假设可以利用相邻交换求出n-1个元素的全排列，然后看怎样利用这n-1，求出n个元素的全排列。 read more

陷阱1:手里拿着一个锤子，看到什么都是钉子。

首次印象判断失误+类比不严谨，比如NRV优化，比如滥用设计模式。学到一种知识，就像用，无论是否应该使用，喜欢调书袋。

比如看到这个问题N个整数，求其中任意N-1个数的乘积中的最大的一个。我想到的是另一个问题：
算法版：5082 m lonelyyanzi Apr 21 12:50 ○ 【合集】这个题怎么做？ (6.1千字)
已知：A1 A2 A3 A4 … An
 B1 = A2*A3* …*An
 B2 = A1*A3* …*An
 Bn-1 = A1*…*An-2*An
 Bn = A1*A2*…*An-1
求出各个Bi（i= 1,2 …,n)
要求不能用除法（除法效率太低），时间负责度为nlog(n), 当时我找到了一个O(n)的算法。 read more

作为一个良好的思考者，不会轻易去相信别人的主张，不会人云亦云，怀疑精神是批判性思维的基础。在批判性思维者的心中有那么的一把尺子去评价别人的主张，当我们的心中也存在着这样的一把尺子的时候，我们就具备了批判性的思维。 read more

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

作为思维的一种方法，类比大概是其中最重要的一种。

陈胜说"王侯将相，宁有种乎"，必然是经过一番比较的。仿生学的产生，比如潜艇，飞机，军装的颜色便是一种生物的模仿。了解下蜂房的构造，有助于人类建筑的改进。王阳明格物致知，格竹，这也是一番类比。类比一番，你会发现宏观世界与微观世界的惊人相似，天体力学与原子力学是统一的，光就是一种电磁波。大多数的不幸都是类似的，大多数的幸福也是类似的。时间空间本身就是人类的一种空想，梦境与真实实际上是如此模糊不清。 read more

大卫.希尔伯特说过，we must konw，we will know.

1.
一对夫妇邀请N-1对夫妇参加聚会（因此聚会上总共有2N人）。每个人都和所有自己不认识的人握了一次手。然后，男主人问其余所有人（共2N-1个人）各自都握了几次手，得到的答案全部都不一样。假设每个人都认识自己的配偶，那么女主人握了几次手？ read more

1.

将数组{32,74,25,53,28,43,86,47}按从小到大排列，每次可以交换任意两个元素，最少

需要交换_______次

答案是5次,置换的分解。

2.

给你一个已经排好序的数组a，里面可能有重复元素，比如a[] = {1, 1, 1, 2, 3, 3, 4, 5, 5}。现在需要重新调整

a里面的元素为a[] = {1, 2, 3, 4, 5, 1, 3, 5, 1}，要求里面的每个子序列都是有序的，并且其中的元素唯一。

另外，要求这样的子序列数最小，并且只能使用O(1)的辅助空间。 read more

老徐听他们实验室参加面试的人出的，有点像ms的那个选择题，具有很强的自描述性

i = 0, … n(n为自然数)

数列：A(0), A(1), …, A(i), … A(n)
A(i)表示i在上述数列中i出现的个数

比如n=3时，2 0 2 0就是一个满足条件的数列

给定n，请计算出数列，如果不存在请说明。 read more

zz自http://blog.csdn.net/pongba/archive/2008/07/20/2681668.aspx

庞加莱，这个被称为最后一位全才的人，对解题的心理学也非常有兴趣和研究。在演讲中可以发现，他对于自己解决数学问题过程中的心理过程作了深刻的反省，虽然庞加莱不是认知神经科学家，但演讲中的使用的类比以及描述基本上都是靠谱的。 read more

一个整形数组，长为n，元素范围为1~(n-1)，则这个数组内至少有一个数字出现多次，现在要求用O(n)时间,O(1)空间找出一个出现多次的数。
以下为原文：
here’s one I got asked which kicked my butt.  Write a function that takes in an array of n ints from 1…n-1.  For example, an array of 4 numbers which all have values of 1, 2, or 3.  There will obviously be at least one duplicate number.  Return one of the duplicates (EASY!) – Now do this in order n, without allocating ANY new memory (no hash table or anything).. (Note: I did figure out a solution to this, but the interview didn’t seem to like it very much but whatever).. read more

。。。笔记
1.划分问题
    点划分直线：f(n) = f(n-1) + 1
    线划分平面：g(n) = g(n-1) + f(n-1)
    平面划分空间：s(n) = s(n-1)+g(n-1)
    具有相似的递推关心，n维空间的划分与n-1维空间相关。
2.8皇后问题
   n后问题存在构造解，对于解的个数目前尚未存在定理，只能搜索
3.8数码
   数码问题存在解的条件是：与逆序对相关，观察移动过程，计算时，把0看成一个元素，考虑交换两个元素时的逆序数变化，前后总是相差奇数个，故如果逆序数的变化与0元素曼哈顿变化奇偶一致，则说明可达。 read more