C++之算法设计与实现ppt课件.pptx
TSINGHUA UNIVERSITY算法设计与实现算法设计与实现构造算法解决问题按照自顶向下、逐步求精的方式进行使用程序设计语言编程实现典型示例素性判定问题最大公约数问题TSINGHUA UNIVERSITY素性判定问题判断给定的某个自然数 n（大于 2）是否为素数算法逻辑输入：大于 2 的正整数 n输出：该数是否为素数，若为素数返回 true，否则返回 false步骤 1：设除数 i 为 2步骤 2：判断除数 i 是否已为 n，若为真返回 true，否则继续步骤 3：判断 n%i 是否为 0，若为 0 返回 false，否则继续步骤 4：将除数 i 递增，重复步骤 2TSINGHUA UNIVERSITY素性判定函数第一版验证其为算法：对照算法五个基本特征证明算法正确测试算法bool IsPrime(unsigned int n)unsigned int i=2;while(i n)if(n%i=0)return false;i+;return true;TSINGHUA UNIVERSITY素性判定函数第二版bool IsPrime(unsigned int n)unsigned int i=2;while(i=(unsigned int)sqrt(n)if(n%i=0)return false;i+;return true;为什么可以使用 sqrt(n)代替 n？sqrt 为标准库中的求平方根函数TSINGHUA UNIVERSITY素性判定函数第三版bool IsPrime(unsigned int n)unsigned int i=3;if(n%2=0)return false;while(i=(unsigned int)sqrt(n)if(n%i=0)return false;i+=2;return true;第三版有什么改进？TSINGHUA UNIVERSITY素性判定函数第四版bool IsPrime(unsigned int n)unsigned int i=3;if(n%2=0)return false;while(i=(unsigned int)sqrt(n)+1)if(n%i=0)return false;i+=2;return true;第四版有什么改进？TSINGHUA UNIVERSITY素性判定函数第五版bool IsPrime(unsigned int n)unsigned int i=3,t=(unsigned int)sqrt(n)+1;if(n%2=0)return false;while(i=t)if(n%i=0)return false;i+=2;return true;第五版有什么改进？TSINGHUA UNIVERSITY算法选择算法选择的权衡指标正确性：算法是否完全正确？效率：在某些场合，对程序效率的追求具有重要意义可理解性：算法是否容易理解，也是必须要考虑的算法评估：衡量算法的好坏，主要是效率TSINGHUA UNIVERSITY最大公约数问题求两个正整数 x 与 y 的最大公约数函数原型设计unsigned int gcd(unsigned int x,unsigned int y);TSINGHUA UNIVERSITY最大公约数函数：穷举法unsigned int gcd(unsigned int x,unsigned int y)unsigned int t;t=x y?x:y;while(x%t!=0|y%t!=0)t-;return t;TSINGHUA UNIVERSITY最大公约数函数：欧氏算法unsigned int gcd(unsigned int x,unsigned int y)unsigned int r;while(true)r=x%y;if(r=0)return y;x=y;y=r;输入：正整数 x、y输出：最大公约数步骤 1：x 整除以 y，记余数为 r步骤 2：若 r 为 0，则最大公约数即为 y，算法结束步骤 3：否则将 y 作为新 x，将 r 作为新 y，重复上述步骤
