《C++之算法设计与实现ppt课件.pptx》由会员分享，可在线阅读，更多相关《C++之算法设计与实现ppt课件.pptx（11页珍藏版）》请在三一办公上搜索。
1、算法设计与实现构造算法解决问题按照自顶向下、逐步求精的方式进行使用程序设计语言编程实现典型示例素性判定问题最大公约数问题,判断给定的某个自然数 n（大于 2）是否为素数算法逻辑输入：大于 2 的正整数 n输出：该数是否为素数，若为素数返回 true，否则返回 false步骤 1：设除数 i 为 2步骤 2：判断除数 i 是否已为 n，若为真返回 true，否则继续步骤 3：判断 n % i 是否为 0，若为 0 返回 false，否则继续步骤 4：将除数 i 递增，重复步骤 2,验证其为算法：对照算法五个基本特征证明算法正确测试算法,bool IsPrime( unsigned int n )
2、 unsigned int i = 2; while( i n ) if( n % i = 0 ) return false; i+; return true;,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 为标准库中的求平方根函数,bool IsPrime( unsigned int n ) unsigned int i =
3、 3; if( n % 2 = 0 ) return false; while( i = (unsigned int)sqrt(n) ) if( n % i = 0 ) return false; i += 2; return true;,第三版有什么改进？,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;
4、,第四版有什么改进？,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;,第五版有什么改进？,算法选择的权衡指标正确性：算法是否完全正确？效率：在某些场合，对程序效率的追求具有重要意义可理解性：算法是否容易理解，也是必须要考虑的算法评估：衡量算法的好坏，主要是效率,求两个正整数 x 与 y 的最
5、大公约数函数原型设计unsigned int gcd( unsigned int x, unsigned int y );,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;,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，重复上述步骤,
