算法设计与分析

卢鹏丽 教授

目录

  • 1 概述
    • 1.1 概述-课件
    • 1.2 概述-视频
    • 1.3 MIT-概述-课件（1-2）
    • 1.4 MIT-概述-视频（1-2）
    • 1.5 MIT-概述-文本
  • 2 分治（DC）算法
    • 2.1 DC-最大连续子序列和
      • 2.1.1 最大连续子序列和-课件
      • 2.1.2 最大连续子序列和-视频
    • 2.2 DC-两个多项式相乘
      • 2.2.1 两个多项式相乘-课件
      • 2.2.2 两个多项式相乘-视频（1-2）
    • 2.3 大整数相乘+大矩阵相乘
    • 2.4 DC-线性时间选择+快速排序
      • 2.4.1 线性时间选择+快速排序-课件
      • 2.4.2 线性时间选择+快速排序-视频
    • 2.5 MIT-分治法1
      • 2.5.1 MIT-分治法1-课件
      • 2.5.2 MIT-分治法1-视频
      • 2.5.3 MIT-分治法1-文本
    • 2.6 MIT-分治法2
      • 2.6.1 MIT-分治法2-课件
      • 2.6.2 MIT-分治法2-视频-快排及随机化方法
      • 2.6.3 MIT-分治法2-视频-线性时间排序
      • 2.6.4 MIT-分治法2-视频-顺序统计+中值
      • 2.6.5 MIT-分治法2-文本
    • 2.7 分治法补充+总结
    • 2.8 分治算法C程序实现
      • 2.8.1 二分查找算法
      • 2.8.2 归并排序
      • 2.8.3 线性时间选择
      • 2.8.4 快速排序
      • 2.8.5 两个多项式相乘
      • 2.8.6 两个大整数相乘
      • 2.8.7 最大连续子序列和（MCS）
  • 3 动态规划（DP）算法
    • 3.1 DP-0-1背包问题
      • 3.1.1 0-1背包问题-课件
      • 3.1.2 0-1背包问题-视频（1-2）
    • 3.2 DP-矩阵链相乘
      • 3.2.1 矩阵链相乘-课件
      • 3.2.2 矩阵链相乘-视频 （1-4）
    • 3.3 DP-最长公共子序列 LCS 问题
      • 3.3.1 MIT-最长公共子序列-课件
      • 3.3.2 MIT-最长公共子序列-视频
      • 3.3.3 MIT-最长公共子序列-文本
    • 3.4 DP-凸多边形最优三角剖分
    • 3.5 凸多边形-作业证明
    • 3.6 DP-数字棋盘
    • 3.7 DP-数字三角形
    • 3.8 DP-所有点对间最短路径-Folyd算法
    • 3.9 动态规划算法C程序实现
      • 3.9.1 最长公共子序列（LCS）
      • 3.9.2 所有LCS序列
      • 3.9.3 矩阵链相乘
      • 3.9.4 数字棋盘
      • 3.9.5 数字三角形
      • 3.9.6 凸多边形最优三角剖分
      • 3.9.7 凸多边形-课后作业证明
      • 3.9.8 所有点对间最短路径
      • 3.9.9 0-1背包问题
      • 3.9.10 矩阵链相乘次数相差100倍
  • 4 贪心(Gleedy)算法
    • 4.1 分数背包问题
      • 4.1.1 分数背包-课件
      • 4.1.2 分数背包-视频
    • 4.2 单源最短路径问题-Dijkstra算法
      • 4.2.1 单源最短距离-课件
      • 4.2.2 单源最短路径-视频
    • 4.3 最短路径-MIT资料
      • 4.3.1 最短路径1-MIT-课件
      • 4.3.2 最短路径1-MIT-视频
      • 4.3.3 最短路径1-MIT-文本
      • 4.3.4 最短路径2-MIT-课件
      • 4.3.5 最短路径2-MIT-视频
      • 4.3.6 最短路径2-MIT-文本
      • 4.3.7 最短路径3-MIT-课件
      • 4.3.8 最短路径3-MIT视频
      • 4.3.9 最短路径3-MIT-文本
    • 4.4 最小生成树问题-Kruscal算法
      • 4.4.1 Kruscal-课件
      • 4.4.2 Kruscal-视频
    • 4.5 最小生成树-Prim算法
      • 4.5.1 Prim-课件
      • 4.5.2 Prim-视频
    • 4.6 最小生成树-MIT资料
      • 4.6.1 MIT-最小生成树-课件
      • 4.6.2 MIT-最小生成树-视频
      • 4.6.3 MIT-最小生成树-文本
    • 4.7 文件压缩问题-哈夫曼编码
      • 4.7.1 Huffman-课件
      • 4.7.2 Huffman-视频
    • 4.8 贪心算法C语言实现
      • 4.8.1 单源最短路径（Single Source shortest path）
      • 4.8.2 MST-Kruskal算法
      • 4.8.3 MST-Prim算法
      • 4.8.4 哈夫曼编码
      • 4.8.5 分数背包问题
      • 4.8.6 DFS
      • 4.8.7 BFS
  • 5 回溯法（BackTracking）
    • 5.1 回溯法-课件
    • 5.2 回溯法-介绍-视频
    • 5.3 回溯法-3着色问题-视频
    • 5.4 回溯法--8皇后问题-视频
    • 5.5 回溯法-总结-视频
    • 5.6 回溯法C程序实现
      • 5.6.1 3-着色问题
      • 5.6.2 4-皇后问题
      • 5.6.3 8-皇后问题
      • 5.6.4 迷宫问题
      • 5.6.5 子集和数问题
      • 5.6.6 旅行商问题
  • 6 NP问题
    • 6.1 NP
  • 7 数学知识补充
    • 7.1 数学知识
  • 8 归纳法
    • 8.1 常见的归纳算法
    • 8.2 归纳算法C程序实现
      • 8.2.1 基数排序
      • 8.2.2 生成排列
      • 8.2.3 寻找多数元素
  • 9 算法-课程思政
    • 9.1 思政1-大矩阵相乘-Matlab被禁事件
      • 9.1.1 思政-Matlab被禁事件及思考
      • 9.1.2 思政-学生演讲-MATLAB被禁
      • 9.1.3 学生演讲截屏-MATLAB
    • 9.2 思政2-最大子序列和问题
      • 9.2.1 思政-5个案例-匠精神
      • 9.2.2 思政-学生演讲-工匠精神
      • 9.2.3 学生演讲截屏-工匠精神
回溯法C程序实现

回溯算法（Backtrackingalgorithm）：3-着色问题、4-皇后问题、8-皇后问题、迷宫问题、自己和数问题

问题的描述、C语言实现程序、运行截图。