文档介绍：算法的基础
*
第1页，共60页，编辑于2022年，星期一
1974年图灵奖获得者Donald Ervin Knuth:
计算机科学就是算法的研究
The Art of Computer Programming
算 n)
{ int r;
do
{ r = m % n;
m = n;
n = r;
} while(r);
return m;
}
算法的描述
[例题]利用C语言描述欧几里得算法。
*
第13页，共60页，编辑于2022年，星期一
算法是解决问题的方案，由于实际问题千奇百怪，因而制定出的解决方案也将千差万别。
算法的设计
算法设计的一般步骤：
①理解待求解问题
解决问题是设计算法的最终目标。除了需要分析问题的求解目标、输入数据和限制条件外，还要判断清楚待求解问题的种类，是否有现成的算法可以直接应用。
②确定算法运行的环境
了解算法的运行环境，才能设计出可行且高效的算法。比如在小型的嵌入式环境中只能运行需要较小内存的算法，而对于并行分布式的运行环境，则要设计高效的并行算法。
*
第14页，共60页，编辑于2022年，星期一
③设计算法
设计算法是将算法具体化，即设计出算法的详细规格说明。也就是，首先确定算法所需要的数据结构，然后结合具体问题的特性来选择算法的设计策略，最后根据算法设计技术的原理描述算法的具体流程(流程图、伪代码和程序设计语言等)。
④分析算法
对所设计出的算法进行复杂性分析，考察其在时间和空间方面的计算开销。若算法在某些环节的计算开销较大，可有针对性地改进该环节，若整个算法的计算开销太大，则需要返回第③步重新考虑采用新的算法设计技术来求解该问题。
⑤编程实现
采用某种程序设计语言将设计好的算法实现出来。
算法的设计
*
第15页，共60页，编辑于2022年，星期一
算法分类：
①数值算法 求解线性方程组、数值积分等，有特定的计算步骤 数值计算方法课程
②非数值算法 求解判定问题、最优化问题等，需要掌握算法设计技术 算法设计与分析课程
③软计算方法 遗传算法、粒子群算法、蚁群算法、人工神经网络等 计算智能课程
算法的设计
*
第16页，共60页，编辑于2022年，星期一
一、穷举法(又称蛮力算法)
穷举法指在问题的解空间范围内逐一测试，找出问题的解。它是一种简单而有效的算法设计策略同时也是一种很容易应用的方法。
算法的设计
穷举法的应用
国王的婚姻中国王使用的算法
旅行商问题中逐条路线计算
密码学中的***法
图论中四色定理的证明
百钱买百鸡问题
*
第17页，共60页，编辑于2022年，星期一
[案例一]***法是一种用穷举法实现的密码破译方法。
算法的设计
最原始、最基本的攻击方式，对密码进行逐一测试直到找到真正的密码。
原则上可以破译所有密码，但费时费力。
密码***软件：89Winrar QQ密码***软件
*
第18页，共60页，编辑于2022年，星期一
[案例二]四色定理(又称四色问题或四色猜想)。
算法的设计
四色问题描述：任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。
数学语言表示：将平面任意地细分为不相重叠的区域，每一个区域总可以用1、2、3、4这四个数字之一来标记，而不会使相邻的有公共边界的两个区域得到相同的数字。
证明四色定理(穷举法)：
①利用数学理论推出证明所有例子可以归约到证明有限个特例上；
②利用计算机程序产生了所有特例(大约1700个例子)，通过穷举发现所有特例都是四着色的。
*
第19页，共60页，编辑于2022年，星期一
[案例三]百钱买百鸡问题
百钱买百鸡：鸡翁一，值钱五
鸡母一，值钱三
鸡雏三，值钱一
问翁、母、雏各几何？
算法的设计
意思是：公鸡每只5元、母鸡每只3元、小鸡3只1元，用100元钱买100只鸡，求公鸡、母鸡、小鸡的只数。
*
第20页，共60页，编辑于2022年，星期一
设鸡翁、鸡母、鸡雏的个数分别为x、y、z，根据题意可得如下方程组：
5x＋3y＋z/3＝100
x＋y＋z＝100
1≤x＜20, 1≤y＜33, 3≤z＜100, z mod 3＝0
测试集合：1≤x＜20, 1≤y＜33