每日5题–0613

1. 单链表倒数第N个节点
2. template中用typename和用class有什么区别？
3. 手写fab(n)函数
4. 一个大楼,10层,4个电梯,怎么设计类来实现这样一个系统?
5. 多少人在一起，生日可能出现重复概率大于0.5？

1.这个不难, 设置两个指针, 一个在第N个节点(p2), 一个在head节点(p1), 然后同步向前走, 直到P2到NULL
时, 这时候的p1就是我们要寻找的那个节点. (只是注意要考虑一下边界条件的问题就好了);
2.

http://www.csai.cn　作者：fatalerror99　来源：BLOGCSDN

没什么不同。在声明一个 template type parameter（模板类型参数）的时候，class 和 typename 意味着完全相同的东西。一些程序员更喜欢在所有的时间都用 class，因为它更容易输入。其他人（包括我本人）更喜欢 typename，因为它暗示着这个参数不必要是一个 class type（类类型）。少数开发者在任何类型都被允许的时候使用 typename，而把 class 保留给仅接受 user-defined types（用户定义类型）的场合。但是从 C++ 的观点看，class 和 typename 在声明一个 template parameter（模板参数）时意味着完全相同的东西。

3. 曾经被问道过这题, 一般有三种方法.
a. 递归 时间复杂度O(2^n)

int fab(int n)
{
      if(n<1) exit(1);
      if(n==1) return 1;
   	  else if(n==2) return 1;
	  else return fab(n-1)+fab(n-2);
}

b. Bottom Up 时间复杂度O(n)

int fab(int n)
{
	if(n<1) exit(1);
	int a[n];
	if(n==1) return 1;
	else if (n==2) return 1;
	a[0] = 1;
	a[1] = 1;
	for(int i=2;i<n;i++)
              a[i] = a[i-1]+a[i-2];
       return a[n-1];
}

c. Matrix Multiplication+Divide and Conquer
发现 fab数组可以写成矩阵相乘的形式,

又因为

这样我们就有

然后求矩阵的n次方,可以用divide and conquer来做, 近似认为可以在O(log n)时间做到,(注意是近似), 所以第三种方法的时间是O(log n) 试想在The Da Vinci Code里面的卢浮宫馆长Jacques Saunière被谋杀前用了O(log(n))的方法写出这个Fibonacci数列, 然后多出来的时间再想想有没有更好的方法让历史学家Robert Langdon更容易看出事情的端倪就好了

5. 这个问题被称作(birthday paradox), 大概结果会很出乎人的意料把, 做做看就知道了,

我们先算n个人里面生日完全不一样的概率, 很容易可以发现

那么只要计算 1-T(n)>0.5满足的最小的n值就好了, 发现 n = 23时, 概率p= 0.507297, 即是我们的解.

多说一句, 当n=50的时候, p 已经达到了惊人的0.970374,说明基本上在50个人以上的场合, 一定会有两个人的生日是一样的, 诶, 不过我怎么记得以前写同学录的时候没一个人和我生日一样的?诶, 那个属于另一个问题了把….  ;