标题基本算法简介(一)

　　编者按：应广大读者要求，希望我们向大家讲解一些编程基础知识。从这期开始，我们将连续向大家介绍一些在程序设计方面的基本算法。
　　　用辗转相除法求最大公约数和最小公倍数
　　我们在程序设计中，经常会遇到一些在一大堆数据中，求这些数据共有特性的情况。下面我们以两个例子向大家介绍这种算法。
　　一般地说，求最小公倍数用两个数的积除以最大公约数即可，而求最大公约数有两种算法：
　　1.穷举法，从较小数由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数，
　　2.辗转相除法，又名欧几里德算法，是计算最大公约数和最小公倍数的重要方法，比穷举法简便得多。
　　主要过程是(设两数为a，b，a>b):
　　1)a除以b得余数c;
　　2)令a=c，b除以a得余数c;
　　3)如果a不等于b则跳回1)，否则结束，最后一次的余数就是两数的最大公约数。
　　下面我们用C语言(Turbo C 2.0)来分别演示这两种方法。
　　　程序一：
　　#include<stdio.h>
　　int max(a，b){
　　if(a>=b)
　　return(a)；
　　else
　　return(b);}
　　int zdgys(int a，int b){ 
　　int m；
　　for(m=max(a，b);m>0;m--)
　　if((a%m==0)&&(b%m==0))break；
　　return(m)；} 
　　int zxgbs(int a，int b，int y)
　　{return(a*b/y;}
　　main()
　　{int i，j，k，l；
　　scanf("%d，%d"，&i，&j)；
　　k=zdgys(i，j)；
　　l=zxgbs(i，j，k)；
　　printf("%d和%d的最大公约数是：%d，最小公倍数是：%d"，i，j，k，l) 
　　　程序二：
　　#include<stdio.h>
　　int zdgys(int a，int b)
　　 {
　　int c，d；
　　if(b>a)
　　{c=a;a=b;b=c;}
　　for(;;)} 
　　d=a%b；
　　if(d==0) break；
　　a=b；
　　b=d;} 
　　return(b);} 
　　int zxgbs(int a，int b，int y)
　　{return(a*b/y;}
　　main()
　　{int i，j，k，l；
　　scanf("%d，%d"，&i，&j)；
　　k=zdgys(i，j)；
　　l=zxgbs(i，j，k)；
　　printf("%d和%d的最大公约数是：%d，最小公倍数是：%d"，i，j，k，l);} 
　　源程序可以在http://go8.163.com/~betterprogram/下载。