Introduction To Problem Solving & Programming
http://www.youtube.com/view_play_list?p=94CA590D7781A9B9
好人 坏人
有n个人，其中超过半数是好人，剩下的是坏人
好人只说真话，坏人可能说真话也可能说假话
这n个人互相都知道对方是好人还是坏人
现在要你从这n个人当中找出一个好人来，只能通过以下方式：
每次挑出两个人，让这两个人互相说出对方的身份，
你根具两个人的话进行判断。
问通过何种方法才能最快的找出所有人的身份(最坏的情况下)
解法：
首先分析只有两个人的情况：a和b
1、a说b是好人，b说a是好人：则a和b是同样的人，同为好人或者同为坏人
2、a说b是好人，b说a是坏人：则a肯定是坏人，b不确定
3、a说b是坏人，b说a是好人：要么a好b坏，要么a坏b坏，则b肯定是坏的
4、a说b是坏人，b说a是坏人：要么a好b坏，要么a坏b好，要么a坏b坏。
那么现在就顺序的从n人中抽出一个人i来，和剩下的人来依次比较。
假设挑出来的坏人，那么最坏的情况前面n/2个都相互说是坏人，这样就无法判断了？
如果符合1的情况超过1/2，则i是好人
如果符合2，则i是坏人，去掉i，再取一个i
如果符合3，则把集合中的对应的人去掉，继续下一个
如果符合4的情况超过1/2，则i是坏人，去掉i，再取一个i
反复如此，可以找到所有人的身份。
如果管理时间
读李笑来把时间当作朋友的感想
1、时间无法改变，要改变自己
2、为每天做的事情做记录，有个供反省的对照
3、以绝对做标准，而不是相对，即尽量不要和别人比较
4、要面对资源的分配本来就是不均的这个现实，把时间用于可以改变的事情
5、目标要可实现然后持之以恒，方法可以在实践中摸索
6、尽量多做有用而无趣的事情，但尽量不做有趣而无用的事
7、不要相信运气，那只是成功者的托辞，背后肯定有受罪的事
8、要克服大脑天生的好动、自我保护、选择性失明的特点，要用理性来克服它
9、每天能否坚持做有用而无趣的事2小时以上
10、优秀的人才会有高质量的朋友
Linux 的 Out-of-Memory (OOM) Killer
转载自http://www.dbanotes.net/database/linux_outofmemory_oom_killer.html
同事在 Linux 服务器上遇到点小问题，我也上去折腾半天。这还是第一次注意到 Linux 这个多年来就存在的特性：OOM Killer 。说白了 OOM Killer 就是一层保护机制，用于避免 Linux 在内存不足的时候不至于出太严重的问题，把无关紧要的进程杀掉，有些壮士断腕的意思。
先要学习点老知识，在 32 位CPU 架构下寻址是有限制的。Linux 内核定义了三个区域：
# DMA: 0x00000000 - 0x00999999 (0 - 16 MB)
# LowMem: 0x01000000 - 0x037999999 (16 - 896 MB) - size: 880MB
# HighMem: 0x038000000 - <硬件特定>
LowMem 区 (也叫 NORMAL ZONE ) 一共 880 MB，而且不能改变(除非用 hugemem 内核)。对于高负载的系统，就可能因为 LowMem 利用不好而引发 OOM Killer 。一个可能原因是 LowFree 太少了，另外一个原因是 LowMem 里都是碎片，请求不到连续的内存区域【根据我遇到的一个案例，一个猜想是 有些应用一次性请求比较大的内存，恰恰又是 880M 之内的，空闲的(LowFree)不够大，就会触发 OOM Killer 出来干活】。检查当前 LowFree 的值：
# cat /proc/meminfo |grep LowFree
检查LowMem内存碎片：
# cat /proc/buddyinfo
上面这条命令要在 2.6 Kernel 环境下有效。据说使用 SysRq 的方式更好，不过 Hang 的时候再用吧。参见 Metalink Note:228203.1 。
根据一些文档描述，OOM Killer 在 2.4 与 2.6 上表现是不一样的。2.4 的版本中是把新进来(新申请内存)的进程杀掉。而 2.6 上是杀掉占用内存最厉害的进程(这是很危险的，很容易导致系统应用瘫痪)。
对于 RHEL 4 ，新增了一个参数： vm.lower_zone_protection 。这个参数默认的单位为 MB，默认 0 的时候，LowMem 为 16MB。建议设置 vm.lower_zone_protection = 200 甚至更大以避免 LowMem 区域的碎片，是绝对能解决这个问题的(这参数就是解决这个问题出来的)。
而对于 RHEL 3 (Kernel 2.4) 似乎没什么好办法，一个是用 Hugemem 内核(天知道会不会引入新的毛病)，一个是升级到 2.4.21-47 并且使用新的核心参数 vm.vm-defragment 控制碎片的数量。再就是使用 RHEL 4 (Kernel 2.6)，这又绕回去了。说白了，如果遇到 OOM Killer ，基本上是低版本 Kernel 设计上有点缺陷。
其它，如果去查询 RedHat 的 Bug 库，会发现不少 Kernel 版本也有 Bug 的。尤其在使用 NFS 的场景。
Tip: OOM Killer 的关闭与激活方式：
# echo "0" > /proc/sys/vm/oom-kill
# echo "1" > /proc/sys/vm/oom-kill
更多参考信息:
- 1) OOM killer "Out of Memory: Killed process" SOLUTIONS / SUMMARY【对我遇到的案例没鸟用】
- 2) Metalink Notes : Linux Kernel Lowmem Pressure Issues and Kernel Structures
- 3) Respite from the OOM killer
成都日记 5月12日 晚
到宜必思之前，樊汝离开了我们，他一直惦念他家中的小猫。
到了宜必思后，看到门前树立了警戒线，电也停了。已经不许人进入房间休息了，即使是陈博这样的房客也不行，但是经过协商，陈博进去拿了些衣服。不过遗憾的是陈博的书包和钱包都遗留在了成都研发中心。
我们三个不得已在门前的一片空地上坐了下来，留心听着周围人的讨论，后来我们和宜必思的女经理聊了起来，她相当的负责任，除了耐心的劝解大家不要进住，还和我们聊了起来，以舒缓我们的情绪。宾馆的员工看得出来也都很尽责，似乎没有人回家，都在现场维持着秩序，这是我对成都人在此次地震中留下良好印象的开始。后来宜必思给了我们三瓶水和两把雨伞。因为天下起了雨。同时我还在不断的和北京的同事使用短信联系，相互慰问。
差不多待了半小时，我们决定回我和赵永强住的777酒店看看，看是否能够入住，这时候我们没有对地震的恐惧反而是对可以舒服的躺在床上充满了期待。
沿途上，空地上、立交桥下、草坪中、街道两旁已经挤满了人，很多都从家中带来了席子、被子，铺在地上。但是看不到太多的惊慌，很多人都在打牌，在聊天。还有人在收听广播，等待政府的权威广播。
回到777后，发现这里还是继续停电，但是没有人阻止我们上去房间，我们的房间在6楼。我和赵上去打算把笔记本带上去，这样也能轻松一下。楼道里一片昏暗，我们只能小心的爬楼梯。到了我们的房间时，让我们大吃一惊，房间门竟然洞开着，不过里面的东西倒没有缺少，反而多了一件东西—电视上的抹布，我猜测是服务员正在收拾房间时，地震开始了，她急忙撤走，忘了抹布，也忘了关门。可以想象她当时的惊慌。
回到楼下，我提议现在先去吃一顿饱饭，肚中有粮，心中不慌。我们走向我们熟悉的浏阳河湘菜馆，到了那里，发现早就关门，而且门口也被黄色警戒线围住，感觉比较危险，想想也在情理之中，因为它对面的法院门口可以看出掉下来很多东西。这时我们开始听一辆汽车里传出的成都电台的广播，里面宣读了成都市政府的公报，在不断的安抚大家。
听了一会儿，我们开始往回走，到路口的白天鹅酒家吃饭，那里没有关门。里面吃饭的人还不少。我们吃得很饱，还一人喝了一瓶啤酒，此后的几天，啤酒一直是我们主要的饮料。
饭后我们再次回到了宜必思，过不久，来电了。我们到了宜必思的大厅里看电视，里面不断播放着地震当时成都的情况、很多记者在采访市民。感觉大家都还很镇定。但是一直没有震中的消息。
不久，我和赵又回去了777酒店，那里还没有电，为了防止一直没电，我特地买了4根蜡烛。我们点着蜡，摸索着上楼梯进房间。
到了差不多9点，终于来电了，我们赶忙打开电视，这是电视里开始播放地震的详情了，不过后来大家耳熟能详的那些地名像映秀、北川、青川、什邡还没有出现，电视里在不断播放着都江堰的情况，看来情况严重。
不久，电话响了，孙塑辉通知我们立即到宜必思集合，一起出发去成都市公安局进行现场保障。虽然知道又要熬一夜，但我还是暗自庆幸，可以避免在6楼经历余震了。
成都日记 5月12日
5月12日 星期一
上午9点多到了天翼的三层会议室。先开始和项娇沟通浩特的版本问题和功能问题。
樊汝来了后，开始协调浩特的事情，感觉时间过得很快，中午的时候黄豪请我们去吃饭。
午饭后，陈博去了成都研发中心，我们则到了天翼的一楼运维部继续开始协调浩特前端问题，我在rtx上和继续和项娇沟通如何看浩特前端的问题。
突然我感觉脚底下摇晃的很厉害，以为有人在搬运东西，并没有特别在意，这时候坐在我左边的孙塑辉质问我
为什么要摇晃，我奇怪的回答，我没有啊。然后他看了看地，突然说：“地震”。我立刻懵了，转身对右边的赵永强说：
“地震了，快跑”。赵永强立刻站了起来向外跑去，我跟在他后面，跑出了天翼办公室，并很快的跑到了写字楼外的草坪上。
回过头来看的时候，大批的人流正在涌出写字楼。这时候明显的感动脚下的地面在摇动，但还不是很严重，还可以站住身子。这时有人
惊呼：“快看”。我这是看到写字楼的顶层(6层)，正在剧烈的摇晃，外墙上的瓷砖纷纷掉落，我当时感觉这座楼马上就要塌了。这时我还是没有真正意识到这是地震，毕竟没有经历过，我先开始以为只有天翼的楼在摇晃。这时候我看到周围写字楼下也聚满了人，我才意识到真的是地震。过了几分钟，楼停止了摇晃，这时候开始寻找熟悉的人，很快和赵永强、樊汝、天翼的人聚到了一起，大家面面相觑，毕竟都没有经历过地震。又过了大约10分钟，我们看到了陈博，他刚从成都研发赶过来，据他说，成研的人都已经顺利撤出。
这时候看到一部分人正回到楼里取物品，我和赵也寻思了一下，还是回去把笔记本取出来比较好。而且我们想余震不太可能立刻发生。我们赶紧跑回去后，取出了笔记本。这是我们看到天翼黄豪正在打电话并拍照，我不得不佩服他的勇气。在他的影响下，我也在rtx留下了：“各位成都刚刚发生大地震，我们先撤了”的留言。（现在想起来还是有点冒险）之后我们又回到了草坪上，我打开电脑开始在rtx上和北京聊天，并上网查询。
30分钟后，我们开始撤走，打算先回宾馆。此时终于打通了和家里的电话，报了平安。
我们先回了陈博所住的宜必思宾馆，在路上我们发现大量的群众都到了街道和草坪上，机动车挤满了道路。路上我们巧遇了王小朋和欧阳光大家都很平安。
成都日记 5月11日
5月11日 星期日
今天周日，度过了无聊的一天，赵永强去了都江堰玩(很幸运)，陈博去天府广场逛街。我则去肖家河的雅安面馆吃饭，顺便买了个手机万能充电器。睡了一下午觉，下午4点多被樊汝的电话吵醒，说晚上天翼请客。
晚上，陈博、赵永强、樊汝、我和天翼的黄豪、孙塑辉去洛总开的泰吉火锅吃饭，然后又去了望江楼附近的酒吧一条街上的升级酒吧聊天，聊了一晚上到12点。期间听说王小朋和欧阳光要过来，一直在等他们，但他们一直没到。
出差归来
从成都回来了。对于成都的饮食非常适应，5天时间里吃了4顿火锅，最后一天晚上的胖妈火锅感觉最佳，不是很辣，比较对味。又一次去肖家河吃了雅安面条，一如既往的好吃。
此次没有时间瞎逛，只是周日一起去了趟新五朵金花之一的XX梅林，体会了一下成都城乡一体化建设的成果，环境很舒适，北京是没有这种离城市中心如此近的休闲地方啊。
从堵车想到的
因为前几天老是迟到，所以今天特意比平时早起了15分钟，但没想到遇到了堵 车，结果到公司的时间比平时还晚。个人的努力就这样被交通这个大的非线性系统给消耗殆尽了。这让我想到，历史上有很多人都很努力，想要创一番事业，不过都 被当时社会这个大系统所淹没了，没有留下一点痕迹。为什么会被淹没呢？我想是因为社会的复杂性造成的。复杂性在于组成社会的元素众多有人、自然、以及他们之间的各种 组合，这些组合我们称之为条件。这些条件或多或少都会影响你对这个社会所施加的影响也就是你个人的努力。我把个人努力当作输入施加给社会这个系统，输出呢 就是社会所给予个人的影响，包括地位、金钱、家庭等等。由于这个社会的复杂性导致社会系统本身不是线性的，你的输入和社会的输出有时不能成正比，有人把这 称之为运气，这确实不可捉摸。但是你又不能不努力，因为没有输入肯定是没有输出的，这是个颠扑不破的真理。我们希望社会成为一个线性系统，你的努力将会得 到成正比的回报。时势造英雄，英雄肯定是努力的，而当时的社会在英雄努力的方向上是线性的。那最后我要问的是我该怎么办呢？要回答这个问题我得理清一个问 题，就是个人会给系统一个输入，但是个人并没有独立于系统而存在，他本身就在这个系统里，他的输入其实就构成了系统众多条件中的一个或多个，看个人对社会的参与程度了。那么我想如果你想让系统给你的输出正比于你的输入，那么最好力争把这个系统改造成一个线性的系统，你可以，因为你是社会系统的一分子。
另外，不仅个人的输入构成了系统的众多条件，个人对于系统输出的反馈也是条件。个人与社会关系何其复杂。联想到刚刚逝去的混沌学之父所说的“亚马逊雨林的蝴蝶扇了下翅膀，导致了美国加州的龙卷风”，我想个人确实要慎重考虑给予社会的输入。
(此文为旧文，写于2年前，近期又有新的感悟，有所补充)
围棋自动提子的算法
可以仿照迷宫的算法来编制，假设是白棋提黑子：
1、以白棋当前下的点为例，遍历此白子的四个邻接子（上下左右）
2、如果此邻接子为黑子则分别向它的四个临接点做遍历；如果为白子则返回第1步取下一个邻接子
3、如果遇到白棋，则此个方向的遍历结束，此方向黑棋无气；
4、如果遇到棋盘边界，则此个方向的遍历结束，此方向黑棋无气；
5、如果遇到空（临界点处无棋子），则整个遍历结束，黑棋还有气；
6、如果遇到黑棋，则又向它的三个临接点遍历（去除掉来路的那个临接点），继续执行3-6部，直到遇到结束条件返回；
7、如果4个邻接子都遍历完则结束否则返回第1步，去下一个邻接子。
在整个遍历过程中要记住所有黑棋的位置，在整个遍历结束后，如果不是因为第四种情况结束的，则所有的黑棋将被删除。