画出求2个正整数a,b相除所得商q和余数r的流程图

Question

画出求2个正整数a,b相除所得商q和余数r的流程图

Answer 1

辗转相除法 百科名片 欧几里德辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法.它是已知最古老的算法, 其可追溯至3000年前.简单的想法 　　设两数为a、b(b＜a),求它们最大公约数(a、b)的步骤如下：用b除a,得a＝bq.r 1(0≤r).若r1=0,则(a,b)＝b；若r1≠0,则再用r1除b,得b＝r1q.r2 (0≤r2).若r2＝0,则(a,b)＝r1,若r2≠0,则继续用r2除r1,……如此下去,直到能整除为止.其最后一个非零余数即为(a,b). 原理及其详细证明 　　在介绍这个方法之前,先说明整除性的一些特点（下文的所有数都是正整数,不再重覆）,我们可以这样给出整除性的定义： 　　对于二个自然数a和b,若存在正整数q,使a=bq,则a能被b整除,b为a的因子,a为b的倍数. 　　如果a能被c整除,并且b也能被c整除,则c为a、b的公因数（公有因数）. 　　由此我们可以得出以下推论： 　　推论1、如果a能被b整除（a=qb）,若k为正整数,则ka也能被b整除（ka=kqb） 　　推论2、如果a能被c整除（a=hc）,b也能被c整除（b=tc）,则(a±b)也能被c整除 　　因为：将二式相加：a+b=hc+tc=(h+t)c 同理二式相减：a－b=hc－tc=(h－t)c 　　所以：(a±b)也能被c整除 　　推论3、如果a能被b整除（a=qb）,b也能被a整除（b=ta）,则a=b 　　因为：a=qb　b=ta　a=qta qt=1 因为q、t均为正整数,所以t=q=1 　　所以：a=b 　　辗转相除法是用来计算两个数的最大公因数,在数值很大时尤其有用,而且应用在电脑程式上也十分简单.其理论如下: 　　如果 q 和 r 是 m 除以 n 的商及余数,即 m=nq+r,则 gcd(m,n)=gcd(n,r). 　　证明是这样的: 设 a=gcd(m,n),b=gcd(n,r) 　　证明： 　　∵a为m,n的最大公约数, 　　∴m能被a整除,且n也能被a整除, 　　∴由推论1得：qn也能被a整除, 　　∴ 由推论2得：m-qn也能被a整除, 　　又 ∵m-qn=r, 　　∴r也能被a整除,即a为n和r的公约数（注意：还不是最大公约数） 　　∵b为n和r的最大公约数,a为n和r的公约数 　　∴a≤b, 　　同理 　　∵b为n, r的最大公约数, 　　∴n能被b整除,且r也能被b整除, 　　∴由推论1得：qn也能被b整除, 　　∴由推论2得：qn+r也能被b整除, 　　又∵m=qn+r, 　　∴m也能被b整除,即b为m和n的公约数,（注意：还不是最大公约数） 　　∵a为m,n的最大公约数,b为m和n的公约数, 　　∴b≤a, 　　由以上可知： 　　a≤b与b≤a同时成立, 　　故可得 　　a=b, 　　证毕. 　　例如计算 gcd(546, 429) 　　gcd(546, 429) 546=1*429+117 　　=gcd(429, 117) 429=3*117+78 　　=gcd(117, 78) 117=1*78+39 　　=gcd(78, 39) 78=2*39 　　=39 [编辑本段]计算机算法自然语言描述 　　辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的： 　　1. 若 r 是 a ÷ b 的余数, 则 　　gcd(a,b) = gcd(b,r) 　　2. a 和其倍数之最大公因子为 a. 　　另一种写法是： 　　1. a ÷ b,令r为所得余数（0≤r＜b） 　　若 r = 0,算法结束；b 即为答案. 　　2. 互换：置 a←b,b←r,并返回第一步. 流程图 　　 流程图(当型) 伪代码 　　这个算法可以用递归写成如下: 　　function gcd(a, b) c语言实现 　　/* 辗转相除法（递归）*/ 　　#include 　　int Gcd(int a,int b); 　　int main(void ) 　　 　　int Gcd(int m,int n)//最大公约数 　　 　　if(n == 0) return m; 　　else return Gcd(n,m%