![Board logo](images/default/logo.gif)
标题: [数值计算] 批处理求最小共倍数和最大公约数 [打印本页]
作者: BatHome 时间: 2007-10-25 22:16 标题: 批处理求最小共倍数和最大公约数
- ::原理:展转相除法
- ::code by youxi01@bbs.bathome.net 2007-10-24
- @echo off & setlocal enabledelayedexpansion
- if "%1"=="" goto :help
- call :loop %1 %2
- echo.
- echo %1和%2之间的最大公约数为:!deno! 最小公倍数为:!multi!
- pause>nul
- :loop %1 %2
- set /a var=%1 %% %2,deno=%2
- if !var! neq 0 call :loop %2 !var!
- set /a multi=%1*%2/!deno!
- goto :eof
- :help
- echo.&echo ==========================求最大公约数和最小公倍数=================
- echo [使用格式] %~0 %1 %2
- echo [使用示例] %~0 12 42
- echo ============================--------=================================
- cmd /k
复制代码
作者: 516526966 时间: 2008-8-8 18:49
创办作品,值得支持。。
不过这个论坛的朋友们,看帖不回贴的现象太严重了,直接没有人气。
没有听说吗?灌水也是一种美德。这样人气才旺盛。。。。。。。。。。
建议管理员增加 hide 命令窗口。回复才可以看到。。。。。。
作者: 523066680 时间: 2008-8-10 20:25
对对!!!以后大家要多测试一下楼主们的代码哦 提出建议
讨论 让论坛的帖子热起来!
作者: lhjoanna 时间: 2008-11-7 18:22
恩,看过了。楼主是不断改变调用函数的参数来达到辗转取余,相当于高级语言中的深层递归了。奇怪,怎么去年写的到现在回帖这么少啊,个人觉得求公约数和公倍数很有代表性啊。说实话,当时在学C语言时一开始就碰到这道题了,也是思考好久才明白了其思想,现在我就写出来请大家一起讨论下吧!
例:a=384,b=216
【法一】
大家都知道最大公约数即为两个数的公约数中最大的那个,既然如此,穷举出两个数中所有的公约数,再找出最大的即可。思想很简单,但只能对付一般的数值,如果对于几十位或上百位的大整数,效率实在不敢恭维。在此就不做进一步介绍了,大家有兴趣可以写下代码。
【法二】辗转取余法(辗转相除法)
1.最大公约数
这种方法最早记载于公元前几百年欧几里得的《几何原本》中,这种方法不需要逐个求两数的约数。具体实现如下(省略号后为余数):
<1> 384/216=1......168
<2> 216/168=1......48
<3> 168/48=3........24
<4> 48/24=2..........0
聪明的你一定发现规律了吧,第一次对两个数取余,第二次用两个数中较小的与求得的余数再做取余运算,这样反复辗转取余,直到余数为0.不知道说清楚了没,大家对照下面表格再理解下。
a b a mod b
384 216 168
216 168 48
168 48 24
48 24 0
求到最后一步a mod b=0,中的b,即24即为最大公约数。为什么是这样就能得到结果呢,请大家参考下面的链接,这里我就不讲了。
http://www.cnblogs.com/erwin/articles/704399.html
2.最小公倍数
关于最小公倍数的求法就简单了,两数相乘a*b,再除以两个数的最大公约数即可,上例中,最小公倍数为384*216/24=3456
现在附上我的代码,请大家一起讨论:- @echo off&setlocal enabledelayedexpansion
- :begin
- echo====================
- set /p num1=第一个数:
- set /p num2=第二个数:
- call :gcd %num1% %num2%
- :gcd
- set a=%1
- set b=%2
- :start
- set /a num=a%%b
- if %num% gtr 0 (
- set /a b=!a!%%!b!
- set /a a=%b%
- goto start
- )else (
- echo 最大公约数:!b!
- set /a sum=%1*%2/!b!
- echo 最小公倍数:!sum!
- goto begin
- )
复制代码
我学批处理没多久,代码可能还可以精简,大家一起讨论,共同学习啊!
[ 本帖最后由 lhjoanna 于 2008-11-7 18:28 编辑 ]
作者: email10t 时间: 2015-3-6 21:11
这是第一个批处理程序?
作者: 老刘1号 时间: 2017-2-7 21:16
朋友拿C语言的题考我…还讲了辗转相除…没想到这个坑已经被填了……- echo off&cls
- set /p num1=输入第一个数:
- set /p num2=输入第二个数:
- if %num1% LSS %num2% ^
- set num1=%num2% & set num2=%num1%
- :LOOP
- set TMP=
- set /a tmp=%num1%%%num2%
- if %tmp% neq 0 (
- set /a num1=num2
- set /a num2=tmp
- ) else (
- call :end %num2%
- exit
- )
- goto loop
-
- :end
- echo 它们的最大公约数是%1。
- pause
复制代码
作者: 老刘1号 时间: 2022-7-1 18:58
本帖最后由 老刘1号 于 2022-7-1 19:13 编辑
一万年后学了数理逻辑+位运算+数字电路的我又回来了
可读性≈0- @echo off
-
- set /a a=%random%,b=%random%
-
- rem swap a & b to makes a >= b if nessary
- set /a "c=((a-b)>>31)+1"
- set /a "d=c*a+(1-c)*b"
- set /a "e=(1-c)*a+c*b"
- rem echo %a% %b% %c% %d% %e%
- set /a "a=d,b=e"
-
- rem get greatest common divisor of a & b into a
- :g0
- set /a "c=a%%b,a=b,b=c,gend=!c"
- rem echo %a% %b%
- goto g%gend%
-
- :g1
- echo %d% %e% -^> %a%
- pause
复制代码
论坛这个万年屏蔽词…幸好我又看了一眼
作者: yyz219 时间: 2022-7-1 19:06
虽然不怎么看得明白,但是,觉得很强大
作者: qixiaobin0715 时间: 2022-7-2 09:49
可读性≈0
真的好拽!!!
作者: czjt1234 时间: 2022-11-20 15:21
本帖最后由 czjt1234 于 2022-11-20 15:22 编辑
回复 8# yyz219
俗称不明觉厉![](images/smilies/default/smile.gif)
就是原理不懂,就烦这个位移
欢迎光临 批处理之家 (http://bathome.net./) |
Powered by Discuz! 7.2 |