well的窝窝

　　很多年没有在夜晚来临的时候，关上灯，细细体会远久时那种没有灯，黑黑却很宁静和享受的生活，今天无意识的关了灯，再次感受了下，原来这么美妙，这种远离生活的烦恼和压力，体会一种纯粹干净的生活的味道，真是千金不换的~

　　好多从前的美好，都遗失在了繁杂的现代化生活中~~

　　这些年以来，特别的生病后，感觉由于种种原因，导致自己过度要强，陷入到一种盲目追求一些没多大意义的“成功”里去了，身心都为之耗尽，而且过的一直都不愉快，到后来也找不到自己所要的那种快乐感！
　　现在随着自己身体的康复，以及对自己的反思，感觉自己确实偏离了生活的正轨，陷入到了一种狭隘和极端的生活方式中，带来的只是自己和他人的不愉快。最大的感觉就是现在的生活方式是为了“成功”（无非是名利之争）而努力，并以此期待获得成功后的快乐，结果发现无论是过程还是结果都不快乐！反倒是损耗了身心和年华～　嗟～！
　　所以决定从今天起，为了快乐而生活，为了内心中真正需要的东西而生活，不想为了快乐而再绕“成功”这个没必要的弯子。相信如此，快乐、生活和真正的成功会不期而至吧！~
　　ps：对此的心理分析：生活是为努力而服务，而不是努力是为生活服务，潜在的推动因素应该还是名利导致的一种无形的推力和压力
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　09.11.15 亮草于北京庐中

这里记录一下平时和大家聊天、讨论、灌水时发现的一些有趣的话题，不断记录中。。

实验室里有3盏灯，室外有3个开关分别控制它们，进实验室前，门关着，也没有任何途径从外面知道里面灯的状态等。进去后不能再改变开关的状态。如何知道那个开关控制哪盏灯 。
一个容易想到的方法是通过温度来考察哪盏灯亮过，群里几位同学想到了这个方法，但有个问题是，至少有2个灯都有温度或者都没温度，如果区分它们？我的一个方法是先让两个开关相异，保持比如20分钟，在这期间，第3个开关前10分钟处于一个状态，后十分钟换一个状态，（或者进门前改变第3个开关的状态），应该可以通过温度的高低区分其中2个亮过的灯了。感觉这种解法的思想就是通过亮度和温度来组合出2^2>3种状态，从而获得结论。
比较奇怪的方法有破坏性方法，反而改变一个开关的状态直到对应的灯无法为人民服务，然后。。或者扯出一根电线。。或者通过某种方法改造开关，从而能得一些信息。
期待更多更好的方法。

　　如果有2个psp给你，如何在100层楼测试psp的抗摔性（我的理解是：找到哪层刚好摔碎）？（这是我加上的:psp的伤害不保持，要么原样，要么坏了。）要求测试方法最佳。
cfan 340期上看到的，听说是Google面试题。
由于要找到准确的层，显然必须有k层和k+1层的信息才可能。而这2层都必须要摔才可以得到信息，无法通过推断得到（谁有好方法请告诉我？）。这样，我们可以先用一个psp，称为psp1，确定大致范围，比如从10楼开始，每间隔10楼摔一次，如果那次摔坏了，那么可以在那层下面的9层测试另一个psp，称为psp2。这样可以得到一个模型，设psp1的步进为L，那么最大需要摔得次数为：ceil(100/L) + (L-1) 次。一个典型的极值问题。但这么考虑的角度是否“最佳”，还值得怀疑。。

昨天群里的 东方欲晓 说了个程序问题：
完成程序，实现对数组的降序排序
#include
void sort( );
int main()
{
int array[]={45,56,76,234,1,34,23,2,3}; //数字任意给出
sort( );
return 0;
}
void sort( )
{
}
sort()不能传参 。
目前我的方法是通过stack frame找到array，然后访问其内容。sort函数的帧栈里偏移为0的地方保存了main的%ebp，所以可以通过它找到main的帧栈，main的%ebp的下面就是array的地址。具体实现程序下次写上，同时期待更好的方法。。

对 Bubble Sort 关注较少，最近学习了下作个笔记。感觉它是基础但不太高效的算法，曾被称为[待补充]。但也有自己的长处（不然就没几个鱼儿喜欢冒泡了 ：）），首先它是稳定排序法（笨人有笨福 ：）），其次它能探测序列是否已排好序（聪明的 Quicksort 等即使对完全有序的序列，还是忙个不停，hoho），再次，对于小规模的问题（有的说n<=50，有的说n<=20（参见《算法艺术与信息学竞赛》），有的说n<=10（见 Wikipedia）），它的实际执行速度反而比高级算法快（简单的好处），例如在 XFree86-3.3/xc/programs/Xserver/hw/xfree86/common/xf86Config.c:1150-1159(1160-1169?) 里，X Window System 用于选择一个显示设备的方法就是冒泡（谁会有超过10个的显示设备呢？：））。最后，冒泡有多种冒法，所以可以稍作学习研究一下。

传统的冒泡法如下：

[code=cpp]
/* Classical bubble sort, code by well */
void bubble_sort(int *arr, int n)
{
    int i, j, tmp, flag;
    
    for (i = n - 1; i > 0; i--) {
        flag = 0;
        for (j = 0; j < i; j++) {
            if (arr[j] > arr[j+1]) {
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                flag = 1;
            }
        }
        if (!flag)
            break;
    }
}
[/code]

另外一种实现方式：
[code=pascal]

/* Classical bubble sort, alternate implementation, code from wikipedia */
procedure bubbleSort( A : list of sortable items ) defined as:
  n := length( A )
  do
    swapped := false
    for each i in 0 to n - 2  inclusive do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
    n := n - 1
  while swapped
end procedure

[/code]

算法分析：Bubble sort 的一个特点是对基本有序的序列，时间复杂度是 O(n)，但如果比较乱序甚至反序，则算法时间复杂度退化为 O(n^2)。

导致它在大部分情况下速度比较慢的原因有不少，一个是 Wikipedia 提到的兔子和乌龟的情况，就是部分元素很快移动到了头部，而其他很多移动很缓慢；另外数据结构自考教材上提到了一个例子，对初始关键字序列 12，18，42，44，45，67，94，10 仅需一趟扫描，而如果重的气泡位于头部，如前面那个序列变成 94，10，12，18，42，44，45，67 就需七趟扫描。我想这 2 个方面都说明了排序的不对称性，解决的方法是采用交替方向的排序法，则可以缓解这个问题。比如 Wikipedia 提到的 Cocktail Sort 就是一个例子，应该就是双向排序[待查]。此外 Wikipedia 还提到了 Comb Sort 这种基于 Bubble sort 却可以与 Quicksort 媲美的算法，初看了下，有点 Shell sort 的感觉，[待进一步学习]。
附上 Cocktail sort 的伪代码：

[code=pascal]
/* cocktail sort, code from wikipedia */
procedure cocktailSort( A : list of sortable items ) defined as:
  do
    swapped := false
    for each i in 0 to length( A ) - 2 do:
      if A[ i ] > A[ i + 1 ] then // test whether the two elements are in the wrong order
        swap( A[ i ], A[ i + 1 ] ) // let the two elements change places
        swapped := true
      end if
    end for
    if swapped = false then
      // we can exit the outer loop here if no swaps occurred.
      break do-while loop
    end if
    swapped := false
    for each i in length( A ) - 2 to 0 do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
  while swapped // if no elements have been swapped, then the list is sorted
end procedure
[/code]

几点想法：
1。改变方向时，有没有必要依赖当前状态觉得下次扫描的方向呢？如果需要，由什么决定？感觉有点智能算法的味道了。
2。能否并行冒泡~?
3。并行加上双方向
。。。

待录。。

这么久以来第一天基本正常的生活了一天，久违的感觉～ ：） 真好，特此纪念一下! 自己开始回到原来的状态了～ ：）

笔记一是对第一部分前4章的记录。读完这部分，感觉最深的几句话是：

p16 的“面试是一个双方信息沟通及达成合作目的的会谈，是一个双方彼此考量和认知的过程”，以及p22的“生活的和谐还是要放在首位的”，还有p29面的倒数第二段“年轻人在职业生涯的。。”。

16面的那句道出了求职时的心态，人下则安身立命，上则有所作为，面试不仅仅是去混个饭吃，也是自己理想得以实现的途径，同时也是协助公司实现战略梦想的一个过程。公司在考量自己，自己也要看准boss，选择一个明主。

后面p22的那句以及p29的那段则道出了生活的态度。感觉现在太多人是“外逐荣势，内忘忧欢”了，这些年，由于各方面的原因，我也是这样的，唯一的感受就是无论自己怎么挣扎怎么做，就是找不会小时候的那种快乐。现在明白了，如果为了实现“快乐”而去努力，可能就永远不会快乐；如果是把一切当作目的而不是手段，能够体会到当下的幸福，那么快乐会永远伴随自己，而且成功也会不期而至。

p14面的题目6，根据主定理(master theorem)，a=25, b=5, a*f(n/b)=25*n^2/5^2=n^2, a*f(n/b)=f(n)，所以，时间复杂度为 O(f(n)*log_b(n))=O(n^2*log_5(n))
题目7，有 n 个顶点的图的生成树(spanning tree)含有构成一棵树的 n-1 条边，多一条边则会形成环(circle)，所以，本题应该就是去掉 m-(n-1)=m-n+1 条边。