算法分析与设计复习笔记

插入排序

1. void insert_sort(int A[ ],int n)

2. {  

3.     int  a,i,j;                                    

4.     for (i=1;i<n;i++) {

5.         a = A[ i ];

6.         j = i – 1;

7.         while (j>=0 && A[j]>a) {

8.             A[ j+1 ] = A[ j ];

9.             j- -;

10.         }

11.         A[ j+1 ] = a;

12.     }

13. }

合并两个有序的子数组

1. void merge(int A[ ],int p,int q,int r)

2. {

3.     int  *bp = new int[r-p+1];  // 分配缓冲区,存放被排序的元素

4.     int  i,j,k;

5.     i = p;   j = q + 1;   k = 0;

6.     while (i<=q && j<=r) {      //  逐一判断两子数组的元素

7.         if (A[ i ] <=A[ j ])            // 按两种情况,把小的元素拷贝到

8.            bp[ k++ ] = A[ i++ ];    // 缓冲区*/ 

9.         else

10.          bp[ k++ ] = A[ j++ ];

11.    }

12.     if (i==q+1)                    // 按两种情况,处理其余元素

13.         for (;j<=r;j++)

14.             bp[++] = A[j];           // 把A[ j ]~A[ r ]拷贝到缓冲区

15.     else

16.         for (;i<=q;i++)

17.             bp[++] = A[i];             // 把A[i]~A[q]拷贝到缓冲区

18.     k = 0;

19.     for (i=p;i<=r;i++)        // 最后,把数组bp的内容拷贝

20.         A[i++] = bp[k++];            // 到 A[p]~A[r]

21.     delete bp;

22. }

i:开始合并时第一个序列的起始位置

s:合并前序列的大小

t:合并后序列的大小

合并排序算法

1. template <class Type>

2. void merge_sort(Type A[ ],int n)

3. {   int  i, s, t = 1;            

5.     while (t<n) {            

6.         s = t; t = 2 * s; i = 0;       

7.         while (i+t<n) {

8.             merge(A,i,i+s-1,i+t-1);  //i,i+s-1,i+t-1定义被合并的两个序列的边界。

9.             i = i + t;                               

10.         }

11.         if (i+s<n)

12.             merge(A,i,i+s-1,n-1);

13.     }

14. }

1. 汉诺塔（Hanoi）问题：

void Hanoi (char a, char b, char c, int n)

{

        if ( n ==1 ) printf (“%c->%c”, a, b);

        else{

             Hanoi( a, c, b, n-1);

             printf( “%c->%c”,  a, b);

             Hanoi(c, b, a, n-1);

         }

}

    阶乘函数可归纳定义为:

    算法 计算阶乘函数 n!

    1. int factorial(int n)

    2. {

    3.     if (n==0)

    4.         return 1;

    5.     else

    6.         return n * factorial(n-1);

    7. }

整数划分问题

用一系列正整数之和的表达式来表示一个正整数，称为整数的划分。

     例：7 可划分为：

       7

       6 + 1

       5 + 2，5 + 1 + 1

       4 + 3，4 + 2 + 1，4 + 1 + 1 + 1

       3 + 3 + 1，3 + 2 + 2,  3 + 2 + 1 + 1，3 + 1 + 1 + 1 + 1

       2 + 2 + 2 + 1，2 + 2 + 1 + 1 + 1，2 + 1 + 1 + 1+ 1 + 1

       1 + 1 + 1+ 1 + 1 + 1 + 1

      上述任何一个表达式都称为整数 7 的一个划分。

2）正整数 n 的不同的划分个数称为正整数 n 的划分数，记为 p(n )；

3）求正整数 n 的划分数称为整数划分问题。

1）定义两个函数：

      r(n,m)：正整数 n 的划分中加数含 m 而不含大于 m 的所有划分数；

      q(n,m)：正整数 n 的划分中加数小于或等于 m 的所有划分数。

      例：在 7 的划分中：

           含 6 而不含大于 6 的划分有：

                 6 + 1，因此，r(7,6)=1；

            含 5 而不含大于 5 的划分有：

                 5 + 2，5 + 1 + 1，因此，r(7,5)=2；

            含 4 而不含大于 4 的划分有：

                 4 + 3，4 + 2 + 1，4 + 1 + 1 + 1，因此，r(7,4)=3；

            含 3 而不含大于 3 的划分有：

                3 + 3 + 1，3 + 2 + 2,  3 + 2 + 1 + 1，3 + 1 + 1 + 1 + 1

             因此，r(7,3)=4

4）递归式：

    ⑴ 由式 (4.1.1) 和式 (4.1.2) 可得下面递归关系：

    ⑵ 对所有的正整数  n，                     有：

    ⑶ n 的划分不可能包含大于 n 的加数

 

    ⑷ 整数 1 只有一个划分，而不管 m 有多大

    ⑸

分治策略

将要求解的较大规模问题分割成若干个更小规模的子问题；

对这些子问题分别求解，如果子问题的规模仍不够小，则再划分为更小的子问题，如此递归的进行下去，直到问题规模足够小、很容易求出其解为止。

将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

• 分治法所能解决的问题一般具有以下几个特征：
  1. 该问题的规模缩小到一定的程度就可以容易地解决；
  2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
  3. 利用该问题分解出的子问题的解可以合并为该问题的解；
  4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

快速排序的序列的划分算法

2. int split(Type A[ ], int low, int high)

 3. {   int k, i = low;

 5.     Type x = A[low];

 6.     for (k=low+1; k<=high; k++) {

 7.         if (A[k]<=x) {

 8.             i = i + 1;

 9.             if (i!=k)   swap(A[i], A[k]);

11.         }

12.     }

13.     swap(A[low], A[i]);

14.     return i;

15. }   

快速排序:

  1. template <class Type>

  2. void quick_sort(Type A[ ], int low, int high)

  3. {

  4.     int k;

  5.     if (low < high) {

  6.         k = split(A, low, high);

  7.         quick_sort(A, low, k-1);   //对左半段排序

  8.         quick_sort(A, k+1, high); //对右半段排序

  9.     }

10. }

贪婪法:

解向量：问题中n个元素的具体取值所构成的向量；

解空间：问题中n个元素的各种不同取值组合所构成的向量全体；

约束方程：问题中的限制条件所列出的方程；

目标函数：问题求解所要达到的目标；

可行解：满足约束方程的向量；

最优解：使目标函数达极值的向量。

性质: 最优子结构性质(动态规划也有该性质)  自顶向下

斐波那契

分治法: 优化原则或最优子结构性质, 自底向上, 划分子问题

• 分治法所能解决的问题一般具有以下几个特征：
  1. 该问题的规模缩小到一定的程度就可以容易地解决；
  2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
  3. 利用该问题分解出的子问题的解可以合并为该问题的解；
  4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

货郎担的动态规划函数

多段图动态规划函数:

资源分配问题

1. 回溯法
   1. 回溯法是一个既带有系统性又带有跳跃性的搜索算法；
   2. 它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。——系统性