首页 > 代码库 > 求两个正整数的最大公约数——辗转相减法
求两个正整数的最大公约数——辗转相减法
问题：求解两个正整数的最大公约数
今天第一节形式化方法课，举了一个简单的例子——辗转相减法求解两个正整数的最大公约数，来讲解形式化方法的基本内容，让我们有感性的认识。其基本思路如下：
1.任意给定两个正整数a和b；
2.若a和b不相等，则执行第3步；
3.选择a、b中较大者，将较大者与较小者的差赋值给较大者；
4.判断重新赋值后的a和b是否相等，若不相等则继续执行第3步，否则执行第5步；
5.返回a或b。
程序如下（Java编写）。 程序中前断言和后断言是形式化方法中的内容，前断言判断用于计算的数据是否符合要求，后断言确保程序执行的结果是正确的。第一次接触形式化方法，不是太懂，感觉还是蛮有趣的。
1 package com.luop.algorithm; 2 3 /** 4 * 求解两个正整数的最大公约数 5 * @author LuoPeng 6 * 7 */ 8 public class GreatestCommonDivisor { 9 10 /**11 * 辗转相减法求最大公约数12 * @param first 第一个正整数13 * @param second 第二个正整数14 * @return 0：first或second中有非正整数；-1：出错，返回的正整数不是最大公约数；否则，返回的是first和second的最大公约数15 */16 public int continuousMinus (final int first, final int second) {17 18 /*19 * 前断言：判断输入是否有非正整数20 */21 if ( (first <= 0) ||22 (second <= 0) ) {23 return 0;24 }25 26 /*27 * 辗转相减法求最大公约数我们28 */29 int temp1 = first;30 int temp2 = second;31 while ( temp1 != temp2 ) {32 if ( temp1 > temp2) {33 temp1 = temp1 - temp2;34 } else {35 temp2 = temp2 - temp1;36 }37 }38 39 /*40 * 后断言：确保程序结果的正确性41 * 对于任意一个正整数a，如果a满足(first%a==0)&&(second%a==0)，则都有temp1>=a42 */43 int count = (first < second)?first:second;//取first和second中较小的数44 for (int i = 1; i <= count; i++) {45 if ( (first % i == 0) && 46 (second % i == 0) ) {47 /*48 * 如果temp1小于first和second的某个公约数，则说明求得的结果不正确49 */50 if ( temp1 < i ) {51 return -1;52 }53 }54 }55 56 /*57 * 返回结果58 */59 return temp1;60 61 }62 63 }
求两个正整数的最大公约数——辗转相减法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。