吾爱破解 - LCG - LSG |安卓破解|病毒分析|www.52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 4883|回复: 9
收起左侧

[其他原创] vb程序求最大公约数(更相减损术)

[复制链接]
望天hous 发表于 2018-10-17 22:41
本人写的刚接触 VB  自己写的一个求最大公约数(更相减损术)。 上传的有源码和程序   求大神指导   有什么意见可以提出啦


这里是度娘算法   自己只挑了其中的一种  有兴趣的可以试试

求法[url=]编辑[/url]

质因数分解法


质因数分解(9张)
质因数分解法:把每个数分别分解质因数,再把各数中的全部公有质因数提取出来连乘,所得的积就是这几个数的最大公约数
例如:求24和60的最大公约数,先分解质因数,得24=2×2×2×3,60=2×2×3×5,24与60的全部公有的质因数是2、2、3,它们的积是2×2×3=12,所以,(24,60)=12。
把几个数先分别分解质因数,再把各数中的全部公有的质因数和独有的质因数提取出来连乘,所得的积就是这几个数的最小公倍数
例如:求6和15的最小公倍数。先分解质因数,得6=2×3,15=3×5,6和15的全部公有的质因数是3,6独有质因数是2,15独有的质因数是5,2×3×5=30,30里面包含6的全部质因数2和3,还包含了15的全部质因数3和5,且30是6和15的公倍数中最小的一个,所以[6,15]=30。

短除法
短除法:短除法求最大公约数,先用这几个数的公约数连续去除,一直除到所有的商互质为止,然后把所有的除数连乘起来,所得的积就是这几个数的最大公约数。
短除法求最小公倍数,先用这几个数的公约数去除每个数,再用部分数的公约数去除,并把不能整除的数移下来,一直除到所有的商中每两个数都是互质的为止,然后把所有的除数和商连乘起来,所得的积就是这几个数的最小公倍数,例如,求12、15、18的最小公倍数。
短除法的本质就是质因数分解法,只是将质因数分解用短除符号来进行。
短除符号就是除号倒过来。短除就是在除法中写除数的地方写两个数共有的质因数,然后落下两个数被公有质因数整除的商,之后再除,以此类推,直到结果互质为止(两个数互质)。
而在用短除计算多个数时,对其中任意两个数存在的因数都要算出,其它没有这个因数的数则原样落下。直到剩下每两个都是互质关系。
求最大公因数便乘一边,求最小公倍数便乘一圈。
无论是短除法,还是分解质因数法,在质因数较大时,都会觉得困难。这时就需要用新的方法。

辗转相除法
辗转相除法:辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。
例如,求(319,377):
∵ 319÷377=0(余319)
∴(319,377)=(377,319);
∵ 377÷319=1(余58)
∴(377,319)=(319,58);
∵ 319÷58=5(余29)
∴ (319,58)=(58,29);
∵ 58÷29=2(余0)
∴ (58,29)= 29;
∴ (319,377)=29。
可以写成右边的格式。
用辗转相除法求几个数的最大公约数,可以先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。最后所得的那个最大公约数,就是所有这些数的最大公约数。

更相减损法
更相减损法:也叫更相减损术,是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。
《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”
翻译成现代语言如下:
第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法
例1.用更相减损术求98与63的最大公约数。
解:由于63不是偶数,把98和63以大数减小数,并辗转相减:
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以,98和63的最大公约数等于7。
这个过程可以简单的写为:
(98,63)=(35,63)=(35,28)=(7,28)=(7,21)=(7,14)=(7,7)=7.
例2.用更相减损术求260和104的最大公约数。
解:由于260和104均为偶数,首先用2约简得到130和52,再用2约简得到65和26。
此时65是奇数而26不是奇数,故把65和26辗转相减:
65-26=39
39-26=13
26-13=13
所以,260与104的最大公约数等于13乘以第一步中约掉的两个2,即13*2*2=52。
这个过程可以简单地写为:
(260,104)(/2/2) =>(65,26)=(39,26)=(13,26)=(13,13)=13. (*2*2) => 52[1][url=]好的   闲话少数。希望感兴趣的朋友可以一起学习共同进步[/url]

求最大公约数(更相减损术).rar

21.49 KB, 下载次数: 13, 下载积分: 吾爱币 -1 CB

求最大公约数(更相减损术)

免费评分

参与人数 2吾爱币 +3 热心值 +2 收起 理由
fch + 1 我很赞同!
wushaominkk + 3 + 1 感谢发布原创作品,吾爱破解论坛因你更精彩!

查看全部评分

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

A羽飞 发表于 2018-10-17 22:45
进来学习学习。。。
lizhirui 发表于 2018-10-17 22:49
头像被屏蔽
沐雨红尘 发表于 2018-10-17 22:51
 楼主| 望天hous 发表于 2018-10-18 07:19 来自手机
沐雨红尘 发表于 2018-10-17 22:51
辗转相除法,神奇的方法!

对(^o^)用辗转相除法,实现起来会相对简单点
tvc01 发表于 2018-10-18 11:40 来自手机
多谢分享
heang567 发表于 2018-10-19 12:03
学习了,收藏了
lsp87 发表于 2018-10-23 16:40
学习中,太多了。
 楼主| 望天hous 发表于 2018-11-17 17:41
lsp87 发表于 2018-10-23 16:40
学习中,太多了。

确实很多  目前正在学习API数据库链接   
maogui 发表于 2018-11-17 17:57
表示这次考到这个!
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则 警告:本版块禁止灌水或回复与主题无关内容,违者重罚!

快速回复 收藏帖子 返回列表 搜索

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2024-3-29 13:33

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表