一路小说网

第七十二章 小组的深化与林薇薇的笔记(第2页)

天才一秒记住【一路小说网】地址:https://www.waynot.net

他在黑板上写下算法步骤:

1.用较大数除以较小数,得到余数。

2.用之前的除数除以这个余数,得到新的余数。

3.重复这个过程,首到余数为零。

4.此时,最后的除数就是最大公约数。

他以1071和462为例进行演示:

1071÷462=2…147

462÷147=3…21

147÷21=7…0

所以,GCD(1071,462)=21。

“哇!

这么快?”

林薇薇看着简洁的步骤,对比自己草稿纸上的分解过程,惊讶地睁大了眼睛。

张涛也挠头:“这么简单?为啥这样算出来就是对的了?”

李浩眼中闪过领悟的光芒:

“我明白了!

这个算法的核心在于GCD(a,b)=GCD(b,amodb)这个性质!

它把大问题转化成了更小的问题,递归进行!”

“没错!”

苏白赞赏地看了李浩一眼:

“这就是算法的‘高效’所在——它通过不断缩小问题的规模,避免了复杂的质因数分解。

我们可以试着证明一下这个关键性质…”

接下来的时间,苏白引导大家一步步推导这个性质的证明。

虽然涉及一些整数的带余除法性质,但在苏白清晰的讲解和李浩的补充下,林薇薇和张涛也勉强跟上了思路,感受到了数学逻辑的严谨之美。

“太神奇了……”

林薇薇看着最终的证明过程,喃喃道:

“感觉像是打开了一扇新窗户。”

张涛虽然有些步骤没完全吃透,但也咂咂嘴:

“反正比分解质因数快多了!

这算法牛逼!”

李浩则己经开始思考:

“这个算法的时间复杂度是多少?大概和位数的对数成正比吧?比指数级分解快太多了。”

本章未完,请点击下一章继续阅读!若浏览器显示没有新章节了,请尝试点击右上角↗️或右下角↘️的菜单,退出阅读模式即可,谢谢!

如遇章节错误,请点击报错(无需登陆)

新书推荐

灵动天魔心逍遥小贵婿众神世界从虫族开始崛起超神宠兽店诸天从流月城开始妙手小村医豪门后妈在娃综靠反向贴贴爆火了我在天庭做仙官五年县令,亿斤粮震惊李世民巫界术士全球灾变:我成了世界树道吟修仙男院来了个女学渣我的玄幻模拟器射雕之江湖科技炼器师吃鬼的男孩吞天帝尊长姐有灵泉,荒年吃喝不愁不计其庶斗罗之修罗天使神兽召唤师诸天谍影老祖宗她是真的狂最强炊事兵