基本算法简介（一）

黄陀 
2001年 22期

　　编者按：应广大读者要求，希望我们向大家讲解一些编程基础知识。从这期开始，我们将连续向大家介绍一些在程序设计方面的基本算法。
　　#1　　用辗转相除法求最大公约数和最小公倍数
　　　　我们在程序设计中，经常会遇到一些在一大堆数据中，求这些数据共有特性的情况。下面我们以两个例子向大家介绍这种算法。
　　　　一般地说，求最小公倍数用两个数的积除以最大公约数即可，而求最大公约数有两种算法：
　　　　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）来分别演示这两种方法。
　　#2　　程序一：
　　　　#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）　 
　　#2　　程序二：
　　　　#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/下载。 
 