求最大公约数 以你之姓@ 2022-03-10 04:23 232阅读 0赞 ## 求最大公约数 ## \*\*一.题目内容 \*\*运行最大公约数的常用算法,并进行程序的调式与测试,要求程序设计风格良好,并添加异常处理模块。 \*\*二.算法设计 \*\*四种函数效率比较 1.辗转相除法:函数非递归调用 前提:设两数为a,b设其中a 做被除数,b做除数,temp为余数 <1>大数放a中、小数放b中; <2>求a/b的余数; <3>若temp=0则b为最大公约数; <4>如果temp!=0则把b的值给a、temp的值给a; <6>返回第二步; 2.穷举法(利用数学定义) 穷举法(也叫枚举法)穷举法 求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数 。 定义:对两个正整数a,b如果能在区间\[a,0\]或\[b,0\]内能找到一个整数temp能同时被a和b所整除,则temp即为最大公约数。 3.更相减损法 第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。 第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。 4.Stein算法 对两个正整数 x>y : <1>均为偶数 gcd( x,y ) =2gcd( x/2,y/2 ); <2>均为奇数 gcd( x,y ) = gcd( (x+y)/2,(x-y)/2 ); <3>x奇y偶 gcd( x,y ) = gcd( x,y/2 ); 3.x偶y奇 gcd( x,y ) = gcd( x/2,y ) 或 gcd( x,y )=gcd( y,x/2 );现在已经有了递归式,还需要再找出一个退化情况。注意到 gcd( x,x ) = x ,就用这个。 **三.算法设计** 一.辗转相除法:函数非递归调用 流程图 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70] 二.穷举法 流程图 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 1] 三.更相减损法 流程图 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 2] 四.Stein算法:函数的非递归调用 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 3] 四.源代码 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 4] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 5] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 6] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 7] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 8] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 9] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 10] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 11] 五.运行和测试截图 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 12] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 13] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 14] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 15] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 16] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 17] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 18] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 19] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 20]调试截图: ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 21] 六.总结与心得 此次程序使用了多个函数代码块,也让我学会了如何合理的处理各个函数的穿插使用问题。这个程序用一个简单的问题对比了函数及其算法的效率,并使用了时间函数和随机函数,时期更具有客观性,也让我学到了简单算法的优劣性比较。 在程序中使用的四种函数算法都各有特点,一些有较强的逻辑性,一些则需要扎实的数学功底。再次自己动手做程序,从调试到流程图再到写成博客,相比较第一次的手忙脚乱,这次就线的熟练许多。希望自己以后能做的越来越好,质量和效率也越来越高。 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70]: /images/20220310/fc26833b2cac49f4bc4eed8e505f919b.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 1]: /images/20220310/c1506ccdc2cb41d7a930e06848282343.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 2]: /images/20220310/4b88db20546a4e07b6b7e78e344d305f.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 3]: /images/20220310/a0507d3073a94ea29db39056148f5ca6.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 4]: /images/20220310/83445c25588a4503865c654b15da9eaf.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 5]: /images/20220310/54414ee66cde45d8b9645f089257c63e.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 6]: /images/20220310/d33645d036c848708d02db65f9403ab3.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 7]: /images/20220310/a58d09ddd7c94df2a917f1ec2e47fbed.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 8]: /images/20220310/c45c5891d97d429088686082dde2bbbd.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 9]: /images/20220310/85ccd7e42af046ec862cb78a7602abe6.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 10]: /images/20220310/af66db7bbdd6459b9a240c297ba06309.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 11]: /images/20220310/1558b0cea23a43f3af92557a800b376f.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 12]: /images/20220310/3af88a2a9226491b82291fe6a6b6320a.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 13]: /images/20220310/5e790b02023e4ba1bff5e69eb7453b89.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 14]: /images/20220310/7043e9915930465b84c041705e1f7090.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 15]: /images/20220310/230b4d4fbec64fbdae0b37389b09a0f7.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 16]: /images/20220310/e60488384f8f432baaf27ceb94184d27.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 17]: /images/20220310/68a08f52ca654dd1a0e508556ad7f196.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 18]: /images/20220310/0a7074d8a45144dca7e44c9382677d7c.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 19]: /images/20220310/842c4559c40a416c94cc7d9cfdafe6db.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 20]: /images/20220310/0d5081689c7d4bb3a783cf29be7361ac.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ByYXllcl94_size_16_color_FFFFFF_t_70 21]: /images/20220310/83030fef6cc6423c945d5ffee8aeabfe.png
还没有评论,来说两句吧...