登录
Bash 编程: 计算两个正整数的最大公约数/GCD
2025年6月19日 05:36
使用 Bash 脚本计算最大公约数（GCD）
什么是 GCD？
- GCD 是 最大公约数（Greatest Common Divisor） 的缩写。
- 它是能同时整除两个整数的最大正整数。
- 例如：
- 8 和 12 的 GCD 是 4
- 14 和 49 的 GCD 是 7
- GCD 常用于化简分数、密码算法以及数论中。
计算 GCD 的常见算法
1. 欧几里得算法
- 最常见且高效的算法。
- 基于这样一个原理：
gcd(a, b) = gcd(b, a % b) - 重复上述步骤直到
b为 0，此时a即为最大公约数。
2. 减法法
- 不断用较大的数减去较小的数，直到两个数相等。
- 结果就是它们的 GCD。
- 相比欧几里得算法，这种方法在处理大数时效率较低。
3. 二进制 GCD 算法（Stein 算法）
- 使用位运算代替除法运算。
- 在某些硬件中更高效，因为避免了除法和取模操作。
- 基于以下规则：
- 若两个数都为偶数：
gcd(a, b) = 2 * gcd(a/2, b/2) - 若其中一个是偶数，则将其除以 2
- 若两个数都为奇数，且
a > b，则gcd(a, b) = gcd((a - b)/2, b)
- 若两个数都为偶数：
功能概述
- 该脚本计算两个数字的最大公约数（GCD）
- 确保输入参数是正整数
- 当输入缺失或无效时，提供用法说明
脚本功能解释
gcd()函数： 使用循环和取模操作实现欧几里得算法。- 参数个数检查： 确保用户传入了两个参数，否则提示用法并退出。
- 正则校验： 使用 Bash 正则判断两个输入是否为纯数字。
- 范围校验： 确保两个数字都大于零。
- 函数调用： 调用
gcd函数并输出结果。
计算两正整数最大公约数GCD的BASH函数
以下是计算GCD的BASH代码。
#!/bin/bash
## 计算两个数的最大公约数
gcd() {
local a=$1
local b=$2
while [ $b -ne 0 ]; do
local temp=$b
b=$((a % b))
a=$temp
done
echo $a
}
# 检查是否传入了两个参数
if [ $# -ne 2 ]; then
echo "用法: $0 <number1> <number2>"
exit 1
fi
## 检查两个参数是否为正整数
if ! [[ $1 =~ ^[0-9]+$ ]] || ! [[ $2 =~ ^[0-9]+$ ]]; then
echo "两个参数必须为正整数。"
exit 1
fi
if [ $1 -le 0 ] || [ $2 -le 0 ]; then
echo "两个参数都必须大于零。"
exit 1
fi
# 调用 gcd 函数并打印结果
result=$(gcd "$1" "$2")
echo $result
输入校验流程
- 检查是否传入了两个参数
- 使用正则表达式确保输入为整数：=~ ^[0-9]+$
- 确保两个数都大于 0
使用示例
两个互质整数co-prime，它们的最大公约数为1。
| 命令 | 输出 |
|---|---|
./gcd.sh 24 36 |
12 |
./gcd.sh 7 13 |
1 |
小提示：
- 使用
chmod +x gcd.sh让脚本可执行 - 然后运行：
./gcd.sh 12 30
BASH小技巧
- Bash 编程: 计算两个正整数的最大公约数/GCD
- BASH: 如何使用 cURL 命令获取 HTTP 响应代码?
- 通过BASH脚本显示树莓PI的温度和频率
- 如何通过BASH命令把频繁访问服务器的IP找出来?
- BASH编程: 计算一个文本文件中每个单词的频率
- LINUX BASH下的 大括号数组
- BASH 脚本 防止 iptablex 攻击
- BASH 脚本匹配 IP 地址的 简单例子 (正则表达式)
- 如何在 Linux 下 列出最耗资源的进程 (BASH 脚本)
- BASH: 通过dd命令测试硬盘读写速度/性能
- 判断服务器的硬盘类型: 是否是固态硬盘/NVMe
- LINUX 命令 cowsay, cowthink 牛说/牛想
- BASH: 怎样通过curl命令查看服务器响应时间??
- BASH: LINUX 下竖中指
英文：Compute GCD in Bash with Input Validation
本文一共 599 个汉字, 你数一下对不对.扫描二维码，分享本文到微信朋友圈
The post Bash 编程: 计算两个正整数的最大公约数/GCD first appeared on 小赖子的英国生活和资讯.
相关文章：
- 步步高学生电脑上 Basic 编程语言 peek 用法示例 步步高学生电脑 是8位FC机的经典之作.它上面的BASIC有三个版本 1.0, 2.0 和 2.1 2.1 版本有个在线帮助,实际上是 help.cmd 1.0 是用 Esc 键退回到 DOS 的,...
- 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
- 穷举算法的应用 – 去除EXCEL文件中的保护 EXCEL 是可以用密码来保护的. 比如 这个EXCEL 就用了密码保护. 打开EXCEL文件 你会注意到 无法编辑 无法查看宏(VBA)的代码. 去除保护很简单 第一步先编辑宏 VBA 把下面的VBA代码拷贝到VBA编辑器里 并按下F5运行 1...
- 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
- 一张图告诉你北京的雾霾有多严重 一北京的朋友朋友圈发的: 左上为全新口罩;右上为全新口罩本周一到周五每天室外戴20分钟左右;左下为全新口罩今早室外+公交车戴一个半小时;右下为全新口罩今早开车戴一小时左右. 还有这图 空气污染 – 红色的是严重的.中国,尤其是华北地区,是全球最红的地区,没有”之一”. 本文一共 113 个汉字, 你数一下对不对. 一张图告诉你北京的雾霾有多严重. (AMP 移动加速版本) 赞赏我的几个理由. ¥...
- 世界再无OneKey币圈美元虚拟卡了 我前两年就了解到OneKey这个币圈虚拟货币出金卡，不过去年年底才注册使用的。当时还花了99美元一步升级到顶级黑卡。然后这一年陆陆续续用了这卡，但用得不多，主要就用于支持一些VPS主机费还有CloudFlare，ChatGPT Pro等。 这个卡是美国地址，卡号有两个段，Visa 和 Mastercard，不过由于地址是美国的，刷卡可能会有问题。比如我ChatGPT Pro注册帐号是英国的，然后用这卡支付了几个月，突然有一天帐号就被封，被告知：您的付款记录很可疑。 印象中，用这虚拟货币Crypto Card美元出金卡有手续费，但是并没有啥Cash Back返现卡，如果是非美元购物则会有另一笔手续费，所以我很少用这卡出金变现。 前两个月，OneKey宣布关闭： 关于 OneKey Card 服务停用通知 尊敬的用户，为提高服务质量和优化产品供应，我们将按照以下时间表停用...
- 英国房子的EPC节能报告(Energe/Efficiency Performance Certificate) EPC (Energe/Efficiency Performance Certificate) 是英国房子的节能报告, 法律上规定, 每个房子都必须要有一个EPC报告, 报告的有效期为十年. 房东在把房子出租或者想卖房的时候, 这个EPC就必须有效, 在一些情况下 比如出租房子的时候, 这个EPC报告还必须符合一些最低标准, 比如房子必须满足 F档(类似及格线)...
- WordPress 最简单的过滤垃圾评论的方法 WordPress 很多垃圾评论都是由程序直接调用访问 wp_comments.php 造成的. 所以我们可以在 functions.php 文件里加入以下代码 新增一个过滤 简单的检查是否是直接调用. 1 2 3 4 5 6...
