Skip to content

algorithm-skill/AlgorithmAnalysisAndDesignTutorial

Repository files navigation

AlgorithmAnalysisAndDesignTutorial

《算法分析与设计教程》 秦明 阅读记录

目录

知识点

//快速排序
#include <stdio.h>

void swap(int arr[], int x, int y)
{
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

int partition(int arr[], int low, int high)
{
    int pivot = arr[low];
    while(low < high)
    {
        while((low < high) && (arr[high] > pivot))
            high--;
        swap(arr, low, high);
        while((low < high) && (arr[low] < pivot))
            low++;
        swap(arr, low, high);
    }
    return low;
}

void quickSort(int arr[], int low, int high)
{
    if(low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot-1);
        quickSort(arr, pivot+1, high);
    }    
}

void main()
{
    int arr[] = {100, 300, 20, 99, 85, 66, 879, 489, 512, 31};
    quickSort(arr, 0, 9);
    for(int i = 0; i <= 9; i++)
    {
        printf("%d\t",arr[i]);
    }
    
}
//图的递归后序遍历

#include <stdio.h>

typedef struct {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void PostOrderTraverse(BiTree tree)
{
    if(tree == NULL)
        return;
    
    PostOrderTraverse(tree->lchild);
    PostOrderTraverse(tree->rchild);
    printf("%d ", tree->data);
}

Chapter 1

总结

课后习题代码

第1章

  1. 解释下列名词:

    · 算法:笼统的将算法定义为解决某个确定问题的任意一种特殊方法。

    算法就是一组有穷的规则,它规定了解决某一类型问题的一系列计算方法

    · 频率计数:算法分析而论,一条语句的数量级指的是执行它的频率;对于一个算法而言,它的数量级指的是所有语句频率之和

    · 多项式时间算法:凡可用多项式来对其计算时间限界的算法,称为多项式时间算法。

    · 指数时间算法:计算时间只能用指数函数限界的算法称为指数时间算法

  2. 算法分析的目的:

    1. 可以充分发挥人类的聪明才智
    2. 想方设法设计一些好的算法,可以达到少花钱多办事、办好事的经济效果
  3. · 事前分析:求得一个算法的时间限界函数

    · 事后测试:确定程序所耗费的精确时间和空间

  4. 评价一个算法应从哪几个方面进行考虑

    1. 5个特性,确定性,有穷性,输入,输出,能行性
    2. 时间复杂度,空间复杂度
  5. 对于下列函数,求使得第二个函数比第一个函数小的n的最小值(n为自然数)

    1. $n^2$, $10n$ n = 0时
    2. $2^n$,$2n^3$ n = 1时
    3. $n^2/log_2n​$, $n(log_2n)^2​$ n = 10时
    4. $n^3/2, n ^ 2.81$ $n^{0.19} &gt; 2$

第3章

1,2 题目比较简单,自己做

3 活动安排问题

4 区间覆盖问题(思路)

4 区间覆盖问题(思路)

4 区间覆盖问题(思路 PPT 10页)

4 区间覆盖问题(代码)

5 带有限期作业排序问题(思路)

5 带有限期作业排序问题(代码)

6 删数字游戏

7 雷达安装问题

第4章

1,2,3,4 是小题,没有找,自己做吧

5 旅游城市

6 字符串编辑距离

7 正则括号序列(分析)

7 正则括号序列(代码)

8 n个颜色方格(POJ 1390)

第5章

第8题 宝石游戏没有找到答案

1 批处理作业调度

2 图着色问题

3 连续邮资问题

4 n皇后问题

5 子集和问题(分析)

5 子集和问题(核心代码)

6 相异数字序列(分析)

6 相异数字序列(代码)

7 集合分解

第6章

1 计算π

2 整数因子分解

3 数组主元素问题

4 n皇后问题

第7章

第1题没有找到答案

2 住宿安排

3 课程安排

4 小行星问题

5 运动员最佳匹配

6 排水沟问题

6 排水沟问题(代码)

7 海上开采站

参考教材

《趣学算法》 陈小玉

《算法设计与分析》 王晓东

About

《算法分析与设计教程》 秦明 阅读记录

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published