信箱中那两个不算太难的题——解答

第一题：

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。

这个是杨氏矩阵（young），使用类似与堆排序的过程。

 

 

第二题：

（1）F(N)=F(N-1)+F(N-2), 斐波那契数列，具体实现，可以用矩阵，这样可以是用动态规划

Fn              = 1 1 *  Fn-1

Fn-1              1 0     Fn-2

 

F1=1；

F2=2;

 

迭代计算方式，

动态规划，memoize, LogN次矩阵乘法

如果不考虑大数计算的话，很容易实现。如果需要考虑大数，还需要再思考下。。。。不记得FFT管用么（2个大数相乘）。

 

 (2）(1+x)^N ;展开式 因此恰好为2^N (=igma(C(n,k))，2^N次，