算法与算法类问题求解.PDF

算法与算法类问题求解 /~rxli/ Ruixuan Li School of Computer Science and Technology Huazhong University of Science and Technology Nov. 10, 2015 算法与算法类问题求解 (1)为什么算法很重要呢? 符号化, 再语 自然/社 计算化 执行化 义化 自然/社会 算法 算法的结果 问题的求 会问题 程序化 产生 解结果 高级语言程序 程序执行 编译 汇编语言程序 程序执行 汇编 执行化 机器级程序 运算器和控制 --机器指令 器(CPU)-执行 0/1化 信号化 用0/1编码：指 存储 存储器：0/1 令和数据 存与取 “是否会编程序”，本质上是“能否想出求解问题的算法”， 其次才是将算法用计算机可以识别的形式书写出来 1 算法与算法类问题求解 (2)什么是算法? 算法计算机与软件的灵魂。“算法”(Algorithm)一词源于数学家的名字：公 元825年，阿拉伯数学家阿科瓦里茨米(AlKhowarizmi)写了著名的 《波斯教科书》(Persian Textbook)，书中概括了进行四则算术运算的计算规则。 算法是一个有穷规则的集合，它用规则规定了解决某一特定 类型问题的运算序列，或者规定了任务执行或问题求解的一系 列步骤。 如音乐乐谱、太极拳谱等都可看作广义的算法 算法与算法类问题求解 (3)什么是计算学科中的算法? 算法 有穷性：一个算法在执行有穷步规则之后必 须结束。 确定性：算法的每一个步骤必须要确切地定 寻找两个正整数的最大 义，不得有歧义性。 公约数的欧几里德算法 输入：算法有零个或多个的输入。 输入：正整数M和正整数N 输出：算法有一个或多个的输出/ 结果，即与 输出：M和N的最大公约数(设MN) 输入有某个特定关系的量。 算法步骤： 能行性：算法中有待执行的运算和操作必须 Step 1. M除以N,记余数为R Step 2. 如果R不是0，将N的值赋给M, 是相当基本的(可以由机器自动完成)，并能在有限 R的值赋给N, 返回Step 1; 否则, 最大 时间内完成。 公约数是N, 输出N, 算法结束。 基本运算：除法、赋值、逻辑判断 典型的“重复/循环”与“迭代”