综合练习问题集【续2】 课程安排介绍 ■图的所有点最短距离问题 ■前面以介绍设计方法为主 应用:纹理合成中的缝合法。 ■后面以解决问题为主 ■贪婪算法理论: Matroid、 Greedoid、 GreedSet ■旅行商问题【精确解、近似解】 ■背包问题【同上】 算法简介 本课程要回答算法的几个基本问题 ■什么是算法 一个定义好的用来计算,或者 会停下来吗? 駕过奚家最黑架过寯鳇锽焱踅聳榮蕈♂ 进制的加法来说明问题 它的结果正确吗? 1001101110 它运算快吗? +111011010001 它使用了多少内存? ■=1001110101110 进一步我们需要回答: ■i=0;计++;i< Length(第二个数) 它能够应用到那些领域? ■如果第二个数=1plus(第一个数,D) 利用不同语言实现需要那些技巧? ■plus(数,i): ∥在数的第位加1 ■如果数[]==1数=0plus(数,计+1) 算术 进制问题 ■历史上,算术运算是一件非常有意思的工作, ■中国一直使用十进制来表示数字,而通过算盘 见在看起来人人都会用的算术,其广泛应用也 这种2-5-10进制可以进行快速算术计算,宋 只是最近的事。算术的关键是表示,如十进 朝开始普及。 制、罗马进制。利用罗马进制进行算术运算并 不是一件轻松的事3 清华大学 宋斌恒 13 综合练习问题集【续2】 n 图的所有点最短距离问题 n 应用：纹理合成中的缝合法。 n 图的单源最短路径 n 贪婪算法理论：Matroid、Greedoid、GreedSet n 旅行商问题【精确解、近似解】 n 背包问题【同上】 n 自选 清华大学 宋斌恒 14 课程安排介绍 n 前面以介绍设计方法为主 n 后面以解决问题为主 清华大学 宋斌恒 15 算法简介 n 什么是算法：算法是一个定义好的用来计算，或者更 加一般地说，是用于把一定的输入转换成需要的输出 的过程。大家最熟悉不过的算法就是算术中的加法和 乘法。下面我们通过一个二进制的加法来说明问题： n 10011011101 n ＋ 111011010001 n ＝1001110101110 n 算法：一个循环： n i=0; i++; i<length(第二个数): n 如果第二个数[i]==1 plus(第一个数, i) n plus(数，i)： //在数的第i位加1 n 如果 数[i]==1 数[i]=0; plus（数，i＋1）； 清华大学 宋斌恒 16 本课程要回答算法的几个基本问题 n 它会停下来吗？ n 它的结果正确吗？ n 它运算快吗？ n 它使用了多少内存？ n 进一步我们需要回答： n 它能够应用到那些领域？ n 利用不同语言实现需要那些技巧? 清华大学 宋斌恒 17 算术 n 历史上，算术运算是一件非常有意思的工作， 现在看起来人人都会用的算术，其广泛应用也 只是最近的事。算术的关键是表示，如十进 制、罗马进制。利用罗马进制进行算术运算并 不是一件轻松的事。 清华大学 宋斌恒 18 进制问题 n 中国一直使用十进制来表示数字，而通过算盘 这种2－5－10进制可以进行快速算术计算，宋 朝开始普及