【新手进阶】之四：基础算法（四）

roych

现在，来介绍一下求最大公约数的一个算法——欧几里得相除法。欧几里得相除法定理如下：已知整数X和Y（X≥Y），X除以Y的余数为R，X和Y的最大公约数等于Y和R的最大公约数。X和0的最大公约数为X。

据此可以进行以下迭代：X mod Y=R→Y mod R=R1→R Mod R1=R2……Rn -1 mod Rn=0。最后得到的Rn便是最大公约数了。原理讲清楚了，接下来，老规矩，先贴算法：

• 先排序，使得lngN>=lngM。
• 对lngN求模，x=lngN mod lngM。
• 当x不等于0时，重复执行步骤4~6。
• 将lngM代入lngN中。
• 将x代入lngM中。
• 对lngN求模，x=lngN mod lngM。
• 当x=0时，lngN即是最大公约数。
  

1. Function getEuclid(ByVal lngN As Long, ByVal lngM As Long) As Long
   
2. Dim x As Long
   
3. If lngN < lngM Then x = lngN: lngN = lngM: lngM = x
   
4. x = lngN Mod lngM
   
5. Do Until x = 0
   
6.             lngN = lngM
   
7.             lngM = x
   
8.             x = lngN Mod lngM
   
9. Loop
   
10. getEuclid = lngM
    
11. End Function

复制代码

基础算法到此结束。
【新手入门】之一：If分支语句
【新手入门】之二：分支语句总结
【新手入门】之三：循环语句For
【新手入门】之四：循环语句Do和死循环
【新手入门】之五：公共变量与传址过程、传值过程
【新手入门】之六：“悲欢离合总无情”——浅谈Split和Join
【新手入门】之七：嵌套与并列——再谈If流程问题
【新手入门】之八：“连就连”——浅谈“&”和“+”连接符的区别
【新手入门】之九：从百钱百鸡谈起——浅谈“规划求解”兼答lingjiang问
【新手入门】之十：书到用时方恨少——自定义菜单（Access 2003）的制作
【新手入门】之十一：浅谈ADO之序言
【新手入门】之十二：浅谈ADO之Connection
【新手入门】之十三：浅谈ADO之Conmmand（上）
【新手入门】之十四：浅谈ADO之Command（下）
【新手入门】之十五：浅谈ADO之Recordset（上）
【新手入门】之十六：浅谈ADO之Recordset（下）
【新手入门】之十七：浅谈列表框的使用
【新手入门】之十八：双击列表框修改数据
【新手入门】之十九：从“书与女友恕不外借”谈起——浅谈“Bookmark”的使用
【新手入门】之二十：“书与书签”——bookmark属性答疑
【新手入门】之二十一：记录集的“凌迟”——逐条导出记录集

【新手进阶】之一：基础算法（一）
【新手进阶】之二：基础算法（二）
【新手进阶】之三：基础算法（三）
【新手进阶】之四：基础算法（四）
【新手进阶】之五：排序搜索（一）
【新手进阶】之六：排序搜索（二）
【新手进阶】之七：递归算法
【新手进阶】之八：冒泡排序
【新手进阶】之九：浅谈不绑定数据源操作记录
【新手进阶】之十：工作日的计算
【新手进阶】之十一：“庖丁解牛”和“纪昌学射”——浅谈表格式文本数据的导入
【新手进阶】之十二：从四脚腾空的奔马谈起——原来界面可以这样设计
【新手进阶】之十三：Outlook风格导航界面
【新手进阶】之十四：仓库管理系统

WFH6898

学习了，谢谢

today_suny

谢谢版主！！