侯体宗的博客
  • 首页
  • Hyperf版
  • beego仿版
  • 人生(杂谈)
  • 技术
  • 关于我
  • 更多分类
    • 文件下载
    • 文字修仙
    • 群聊
    • 九宫格抽奖
    • 拼图
    • 消消乐
    • 相册

在go语言中实现欧几里德算法示例步骤详解

Go  /  管理员 发布于 2星期前   28

欧几里得算法是寻找两个整数的最大公约数 (GCD) 的一种众所周知且有效的方法。

GCD 是可以整除两个整数而不留余数的最大数。

该算法以古希腊数学家欧几里德的名字命名,欧几里德在公元前 300 年左右在他的《几何原本》一书中提出了该算法。


以下是对欧几里德算法的逐步解释:

从两个正整数 a 和 b 开始,其中 a >= b。如果 a < b,只需交换它们的值。

请注意,这是为了方便数学演示,因为该实现也适用于 a < b。

a 除以 b 并求余数 r(使用模运算,表示为 a % b)。如果 r 为 0,则 GCD 为 b,算法终止。

如果 r 不为 0,则将 a 设置为 b,将 b 设置为 r。然后,重复步骤 2。

算法不断迭代,直到余数为0。此时,最后一个非零余数就是原来两个数的GCD。

欧几里德算法之所以有效,是因为当较大的数字被较小的数字除以其余数替换时,
两个数字的 GCD 保持不变。

下面是一个例子来说明算法:

1.让我们找出 30 和 9 的 GCD:

a = 30, b = 9

2.计算余数:

r = a % b = 30 % 9 = 3(因为3不为0,继续第3步)

3.更新值:

a = 9, b = 3

4.计算新的余数:

r = a % b = 9 % 3 = 0(r 现在为 0)

5.30和9的GCD是3。


为什么它有效?

两个整数的最大公约数是将两个整数整除而不留余数的最大正整数;

因此该算法基于以下关键属性:

如果aand是两个整数,则andb的 GCD 与and的 GCD 相同,其中表示取模运算符(除法后的余数)abba % b%。


在数学上,算法的关键属性可以使用除法算法来证明:

让a和b是两个正整数,这样a >= b. 我们可以将除法算法写成:

a = bq + r, 其中q是商,r是余数。

现在,令成为和d的公约数。然后,对于一些整数和。我们可以将除法算法重写为:

aba = d * m1b = d * m2m1m2
d * m1 = (d * m2) * q + r.

重新排列等式,我们得到:

r = d * (m1 - m2 * q).

由于是和d的因数,也可以写成 的倍数,我们可以得出结论也是 的约数。

这意味着和的 GCD也是 的除数。因此,我们可以替换为并继续使用此算法找到 GCD,直到变为 0。abrddrabrbrb

欧几里得算法因其高效和简单性而特别有用,使其易于在计算机算法和编程语言中实现。


让我们看看在Go中实现它的一些不同方法:


递归实现

欧几里得算法在 Golang 中的实现是一个递归版本,可以找到两个整数的 GCD。

让我们一步步来了解它:

函数定义为GCD(a, b int) int。它需要两个整数输入,a和b,并返回一个整数输出。

递归的基本情况用 进行检查if b == 0。如果为 0,则函数返回作为 GCDb的值。a

如果b不为 0,tmp则创建一个临时变量并为其赋值a。这个临时变量用于a在下一步更新它的值之前存储它的值。


a和的值b更新如下:

a被赋予了 的当前值b。

btmp当(的先前值)除以(更新前的)a的新值时,被赋予余数的值。ab

a该函数使用和b作为输入的更新值递归调用自身return GCD(a, b)。


算法继续递归调用自身,直到到达base case,即b变为0。

此时,函数返回GCD,即 的值a。

// Recursive approach:
func GCD(a, b int) int {
    if b == 0 {
        return a
    }
    tmp := a
    a = b
    b = tmp % a
    return GCD(a, b)
}

例如,假设我们想要找到 56 和 48 的 GCD:

第一次调用:GCD(56, 48)

由于b(48) 不为 0,因此更新a并b:

a变成 48

b变成 56 % 48 = 8

该函数使用新值调用自身:GCD(48, 8)

第二次调用:GCD(48, 8)

由于b(8) 不为 0,因此更新a并b:

a变成 8

b变成 48% 8 = 0

该函数使用新值调用自身:GCD(8, 0)

第三次调用:GCD(8, 0)

现在,b(0) 是 0,所以函数返回a(8) 作为 GCD。


迭代实现

Golang 中欧几里德算法的这种实现是使用循环查找两个整数的 GCD 的迭代版本。让我们逐步查看代码:

函数定义为GCD(a, b int) int。它需要两个整数输入,a和b,并返回一个整数输出。

只要b不等于0,就使用循环进行迭代。循环条件为b != 0;

请注意,Go 中的这种for循环构造本质上是while许多其他语言中的循环。

在循环内部,使用元组赋值同时更新a和的值: 。

此行执行以下操作:

ba, b = b, a%b

a被赋予了 的当前值b。

ba被赋予除以时的余数b。

当循环退出时(即b变为 0), 的值a作为 GCD 返回。

算法迭代直到余数 ( b) 为 0,此时 GCD 是最后一个非零余数,即 的值a。

func GCD(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

例如,假设我们想要找到 100 和 64 的 GCD:

初始化a为 100 和b64。检查循环条件:b(64) 不为 0。

在循环内,更新a和b:

a变成 64

b变为 100 % 64 = 36 再次检查循环条件:b(36) 不为 0。

在循环内,更新a和b:

a变成 36

b变为 64 % 36 = 28 再次检查循环条件:b(28) 不为 0。

在循环内,更新a和b:

a变成 28

b变为 36 % 28 = 8 再次检查循环条件:b(8) 不为 0。

在循环内,更新a和b:

a变成 8

b变为 28 % 8 = 4 再次检查循环条件:b(4) 不为 0。

在循环内,更新a和b:

a变成 4

b变为 8 % 4 = 0 再次检查循环条件: 现在,b(0) 为 0,因此循环退出。

该函数返回 (4) 的值a作为 GCD。


有兴趣的可以自行测试一番


  • 上一条:
    在go语言中使用PostgreSQL实现一个简单的CRUD示例
    下一条:
    在mysql中查询一个表中1至10000当中不存在的id示例
  • 昵称:

    邮箱:

    0条评论 (评论内容有缓存机制,请悉知!)
    最新最热
    • 分类目录
    • 人生(杂谈)
    • 技术
    • linux
    • Java
    • php
    • 框架(架构)
    • 前端
    • ThinkPHP
    • 数据库
    • 微信(小程序)
    • Laravel
    • Redis
    • Docker
    • Go
    • swoole
    • Windows
    • Python
    • 苹果(mac/ios)
    • 相关文章
    • 在go语言中以邮件标题中获取SPF和DMARC,来判断是否为垃圾邮件之垃圾邮件过滤器功能实现(0个评论)
    • 在go语言中使用attr字段标签提取XML属性数据示例(0个评论)
    • 在go语言中如何记录每个HTTP请求到你的Web服务器、日志记录器?(0个评论)
    • 在Go语言中如何查找一个IP地址的网络地址?(0个评论)
    • 在go语言中使用gin框架-中间件gin.BasicAuth()实现账号密码方式认证示例(0个评论)
    • 近期文章
    • 在go语言中以邮件标题中获取SPF和DMARC,来判断是否为垃圾邮件之垃圾邮件过滤器功能实现(0个评论)
    • 在go语言中使用attr字段标签提取XML属性数据示例(0个评论)
    • 在laravel中介绍一个生成假数据的PHP库:FakerPHP(0个评论)
    • 在laravel框架中对环境配置文件的加载过程步骤浅析(0个评论)
    • Laravel 10.12版本发布(0个评论)
    • 在go语言中如何记录每个HTTP请求到你的Web服务器、日志记录器?(0个评论)
    • 在Go语言中如何查找一个IP地址的网络地址?(0个评论)
    • ELK + Filebeat 搭建日志系统流程步骤(0个评论)
    • 在laravel中以curl的方式请求京东联盟api获取数据流程步骤(0个评论)
    • 在go语言中使用gin框架-中间件gin.BasicAuth()实现账号密码方式认证示例(0个评论)
    • 近期评论
    • 博主 在

      2023年国务院办公厅春节放假通知:1月21日起休7天中评论 @ xiaoB 你只管努力,剩下的叫给天意;天若有情天亦老,..
    • xiaoB 在

      2023年国务院办公厅春节放假通知:1月21日起休7天中评论 会不会春节放假后又阳一次?..
    • BUG4 在

      你翻墙过吗?国内使用vpn翻墙可能会被网警抓,你需了解的事中评论 不是吧?..
    • 博主 在

      go语言+beego框架中获取get,post请求的所有参数中评论 @ t1  直接在router.go文件中配就ok..
    • Jade 在

      如何在MySQL查询中获得当月记录中评论 Dear zongscan.com team, We can skyroc..
    • 2016-10
    • 2017-09
    • 2020-03
    • 2020-05
    • 2020-06
    • 2020-07
    • 2020-12
    • 2021-01
    • 2021-05
    • 2021-06
    • 2021-07
    • 2021-08
    • 2021-10
    • 2021-11
    • 2021-12
    • 2022-01
    • 2022-02
    • 2022-03
    • 2022-04
    • 2022-05
    • 2022-06
    • 2022-07
    • 2022-08
    • 2022-09
    • 2022-10
    • 2022-11
    • 2022-12
    • 2023-01
    • 2023-02
    • 2023-03
    • 2023-04
    • 2023-05
    Top

    Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号 PHP交流群

    侯体宗的博客