给定两个不等于0的整数M和N,求M和N的最大公约数。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] params = br.readLine().trim().split(" "); int a = Integer.parseInt(params[0]), b = Integer.parseInt(params[1]); if(a < b){ int temp = a; a = b; b = temp; } int remain = a % b; while(remain > 0){ a = b; b = remain; remain = a % b; } System.out.println(b); } }根据代码中循环的自相似性,直接用递归函数实现,核心代码改成一行
import scala.io.StdIn object Main { def main(args: Array[String]): Unit = { val in = StdIn val params = in.readLine().split(" ") var a = params(0).toInt var b = params(1).toInt println(gcd(a, b)) } def gcd(a: Int, b: Int): Int = { if(b == 0) a else gcd(b, a % b) } }
import java.util.Scanner; public class Main{ public static void main(String []args){ Scanner sc = new Scanner(System.in); int m = sc.nextInt(), n = sc.nextInt(); sc.close(); System.out.println(mcd(m, n)); } public static int mcd(int i, int j){//初始要求i,j均大于0 return j == 0 ? i : mcd(j, i%j);//保证递归时第一个参数大于第二个参数,当第二个参数为0时i就是res。 } }
#include<iostream> using namespace std; //q,r是m,n的商、余数,m,n的最大公约数是n,r的最大公约数 int gcb(int m,int n){ return n==0?m:gcb(n,m%n); } int main(){ int M,N; cin>>M>>N; int res=gcb(M,N); cout<<res<<endl; return 0;
def maxCommonDivisor(m, n): if m == 1 or n == 1 or m == n: return m #调整m,n的顺序使得m<n if m > n: m, n = n, m if n % m == 0: return m for i in range(1, m): if m % i == 0 and n % i == 0: commonDivisor = i return commonDivisor m, n = map(int, input().split()) print(maxCommonDivisor(m, n))
def maxCommonDivisor(m, n): #辗转相除法 #调整m,n的顺序使得m<n if m > n: m, n = n, m if n % m == 0: return m else: return maxCommonDivisor(m, n%m) m, n = map(int, input().split()) print(maxCommonDivisor(m, n))调整m,n的顺序使用系统函数sorted,会大幅度节省运行的空间
m, n = sorted([m, n])