C++之算法设计与实现

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