基于递归的技术：

参考：http://www.nowamagic.net/librarys/veda/detail/2314

 

递归的感悟:

1、      保留当前的状态，开一个平行时空，寻找不同的可能性。

2、      反复对某一数组进行修饰，直到满意

递归相对于循环的优势，就是它的两个步骤递和归，虽然对于空间性的消耗是可怕的，但是它却能在”递”中找不到结果的时候，通过”归”返回到之前的结果。

递归需要满足的条件：

l  可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式。

l  存在一种简单情境，可以使递归在简单情境下退出。

递归和循环的区别：

1、      递归消耗更多的运行时间和空间，因为存在变量入栈的情况。但是在面对如汉诺塔这样的模型，递归能更好地解决

2、      递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环替换，而不影响程序的阅读，那么替换成递归往往是好的。（例如：求阶乘的递归实现与循环实现。）

 

 

 

 

 

归纳法：

归纳法的实质们从求解一个带有参数的相同问题开始，将其推广到包含所有n个物体。也就是通过找到index索引和我们最终要得到结果的一个相关关系，并用数学公式的形式表示出来。

归纳法感觉是比较基础的东西。

这里我们常用到的主要有：

排序算法方法：

选择排序 、插入排序

基数排序

对：

7467 6792 9134 9123 1239

3245 7823 9871 8765 6743

进行排序。

整数幂以及多项式求值

寻找多数元素（数量要在[n/2]）

分治：

把问题实例划分若干实例（多数情况分成两个），并分别递归地解决每个实例，然后把这些子实例的解组合起来，得到原问题实例的解。

寻找最大最小值

算法：MINMAX：

输入；n个整数的数组A[1-n]n为2的幂

输出；(x,y),A中的最大的元素和最小元素

       1.minmax(1,n)

过程：min(low,high)

1.  if high – low =1 then

2.    ifA[low] < A[high] then return (A[low],A[high])

3.    elsereturn(A[high],A[low])

4.    end if

5.  else

6.    mid =[(low + high) / 2]

7.    (x1,y2)=minmax(low,mid)

8.    (x2,y2)=minmax(mid+1,high)

9.    x = min{x1,x2}

10.    y = max{y1,y2}

11.   return (x,y)

12.   end if

eg：

 

二分搜索：

算法：BINARYSEARCH

输入；非降序排列的n个元素的数组A[1…n]

输出；如果x=A[j]，则输出j，否则输出0

1.  binarysearch(1,n)

过程：binarysearch(low,high)

1.if low >high then return 0

2.else

3.          mid =[(low+ high)]

4.          if x =A[mid] then return mid

5.          else if x< A[mid] then return binarysearch(low,mid-1)

6.          elsereturn binarysearch(mid+1,high)

7. end if

 

自底向上排序：

算法：MERGESORT

输入；那个元素的数组A[1…n]

输出；按照非降序排列数组A[1..n]

       1.mergesort（A,1,n）

过程：mergesort(low,high)

1.  if low < high

2.    mid =[(low + high)/2]

3.    mergesort(A,low,mid    )

4.    mergesort(A,mid+1,high)

5.    Merge(A,low,mid,high)

6.  end if

 

MERGE

输入：数组A[1..m]和它的三个索引p,q,r, 1<=p<=q<r<=m，两个子数组A[p..q]和A[q+1...r]各自按升序排列。

输出：合并两个子数组A[p..q]和A[q+1..r]的数组A[p..r]

1、      B[p..r]是个辅助数组

2、      s = p;t = q+1; k = p

3、      while s <= q and t <= r

4、         if A[s]<= A[t] then

5、                B[k] = A[s]

6、                s= s+1

7、         else

8、                B[k]= A[i]

9、                t= t+1

10、     end if

11、   k = k+1

12、   end while

13、  if s = q+1 then B[k..r] =A[t..r]

14、   else B[k..r] = A[s..q]

15、   end if

16、   A[p..r] = B[p..r]

 

寻找第K小元素

SELECT

输入：n个元素数组A[1..n]和整数k，1<=k<=n

输出：A中的第k小元素

1.  select(A , 1 , n, k)

过程：select(A,low,high,k)

       1.p= high – low + 1

       2.ifp < 44 then 将A排序return(A[k])

3. 将A分成q组，每组5个元素。如果5不整除   p，则排除剩余的元素

       4.将q组中的每一组单独排序，找出中项。所有中项的集合为M

       5.mm= select(M, 1, q, [q/2]) {mm为中相机和的中项}

       6.将A[low..high]分成三组

              A1= {a|a<mm}

              A2= {a|a==mm}

              A3= {a|a>min}

7.  case

|A1|>=k :return select(A1, 1, |A1| , k)

|A1| + |A2|>= k: return mm

|A1|+|A2|<k:return select(A3, 1, |A3| , k - |A1|-|A2|)

8.  end cas

动态规划

不同于分治算法的直接实现地推结果不同，动态规划导致了不止一次的递归调用，因此这种技术采用自底向上的方式地递推求值，并把中间结果存储起来以后用来计算所需要求的解。利用这种技术可以设计出特别有效的方法来解决多组合最优问题。

动态规划过程：

每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

动态规划三要素：

（1）问题的阶段

（2）每个阶段的状态

（3）从前一个阶段转化到后一个阶段之间的递推关系。

 

斐波那契数列

可以理解为：有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法。

当n为1时，f(n) = 1,n为2时，f(n) =2,就是说当台阶只有一级的时候，方法数是一种，台阶有两级的时候，方法数为2。

 

1.procedure f(n)

2.if ( n =1) or (n = 2) then return 1

3.else return f(n-1) + f(n-2)

 

斐波那契数列只是给我们展示了动态规划的大概意思，实际上完全可以用以下代替：

 F[0] = 0;F[1] = 1;

      for(i = 2; i <=N; i++)

           F[i] = F[i-1] + F[i-2];

只需要保存前两个值就基本上搞定了

 无论是动态规划，还是分治，或者是他们的基础递归，感觉还有很大空间去理解~