12775: 【设计型】第7章:函数7.7(3) 递归法求最大公约数
Memory Limit:256 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:7
Solved:1
Description
两个正整数的最大公约数是能够整除这两个整数的最大整数。采用递归方法编写计算最大公约数的函数Gcd(),在主函数中调用该函数计算并输出从键盘任意输入的两整数的最大公约数。
递归方法:对正整数a和b,当a>b时,若a中含有与b相同的公约数,则a中去掉b后剩余的部分a-b中也应含有与b相同的公约数,对a-b和b计算公约数就相当于对a和b计算公约数。反复使用最大公约数的如下3条性质,直到a和b相等为止,这时,a或b就是它们的最大公约数。
性质1:如果a>b,则a和b与a-b和b的最大公约数相同,即Gcd(a,b)=Gcd(a-b,b)
性质2:如果b>a,则a和b与a和b-a的最大公约数相同,即Gcd(a,b)=Gcd(a,b-a)
性质3:如果a=b,则a和b的最大公约数与a值和b值相同,即Gcd(a,b)=a=b
Input
2个正整数。两数之间用逗号隔开。
Output
1个数。这个数是最大公约数。
Sample Input Copy
50,15
Sample Output Copy
5