标题: 求最大公约数和最小公倍数 [打印本页]
作者: namejm 时间: 2007-1-24 13:35 标题: 求最大公约数和最小公倍数
看到lxmxn在玩求素数的批处理，我也玩一个，不过这个难度要低得多，没有对输入作容错检查，不保证结果是否发生溢出错误，仅作为茶余饭后的无聊之作：
@echo off
setlocal enabledelayedexpansion
:begin
cls
set flag=
set num1=
set num2=
set /p num1= 请输入第一个数：
set /p num2= 请输入第二个数：
if %num1% leq %num2% (set min=%num1%) else set min=%num2%
:: 此 if 语句可以改为 if %num1% gtr %num2% set /a num1=%num2%,num2=%num1% ，
:: 以达到减少变量数目的目的，则下一句 for 中的 %min% 就得相应地修改为 %num1%
for /l %%i in (%min%,-1,2) do (
set GCD=%%i
set /a mod1=%num1%%%%%i
set /a mod2=%num2%%%%%i
if !mod1! equ 0 if !mod2! equ 0 set flag=1&goto end
)
:end
if defined flag (
set /a LCM=%num1%/%GCD%*%num2%
echo %num1% 和 %num2% 的最大公约数是 %GCD%，最小公倍数是 !LCM!
) else (
set /a LCM=%num1%*%num2%
echo %num1% 和 %num2% 最大公约数为1，最小公倍数是 !LCM!
)
pause
goto begin
[ Last edited by namejm on 2007-1-24 at 02:59 PM ]setlocal enabledelayedexpansion
:begin
cls
set flag=
set num1=
set num2=
set /p num1= 请输入第一个数：
set /p num2= 请输入第二个数：
if %num1% leq %num2% (set min=%num1%) else set min=%num2%
:: 此 if 语句可以改为 if %num1% gtr %num2% set /a num1=%num2%,num2=%num1% ，
:: 以达到减少变量数目的目的，则下一句 for 中的 %min% 就得相应地修改为 %num1%
for /l %%i in (%min%,-1,2) do (
set GCD=%%i
set /a mod1=%num1%%%%%i
set /a mod2=%num2%%%%%i
if !mod1! equ 0 if !mod2! equ 0 set flag=1&goto end
)
:end
if defined flag (
set /a LCM=%num1%/%GCD%*%num2%
echo %num1% 和 %num2% 的最大公约数是 %GCD%，最小公倍数是 !LCM!
) else (
set /a LCM=%num1%*%num2%
echo %num1% 和 %num2% 最大公约数为1，最小公倍数是 !LCM!
)
pause
goto begin
作者: willsion 时间: 2007-1-24 23:14
呵呵。纯支持一下。
作者: ccwan 时间: 2007-1-25 01:58
兄的代码确实精彩，我有一点小疑问，两个数的最大公约数可以是1啊，为什么要显示没有最大公约数呢？在数学中，如果两个数是互质数,那么，它们的最大公约数就是1。
附上一段不用for语句的代码
@echo off
set/p a=输入第一个数
set/p b=输入第二个数
set/a ab=%a%*%b%
cls&echo.&echo/&echo\
echo %a% 和 %b% 的 最大公约数 最小公倍数
if %a% lss %b% goto restart
:loop
set/a num_=%a%%%%b%
if %num_% gtr 0 set/a a=%b%&set/a b=%num_%&goto loop
goto show
:restart
set a=%b%&set b=%a%
goto :loop
:show
set/a num=%ab%/%b%
echo %b% %num%
pause>nul
[ Last edited by ccwan on 2007-1-25 at 06:38 AM ]set/p a=输入第一个数
set/p b=输入第二个数
set/a ab=%a%*%b%
cls&echo.&echo/&echo\
echo %a% 和 %b% 的 最大公约数 最小公倍数
if %a% lss %b% goto restart
:loop
set/a num_=%a%%%%b%
if %num_% gtr 0 set/a a=%b%&set/a b=%num_%&goto loop
goto show
:restart
set a=%b%&set b=%a%
goto :loop
:show
set/a num=%ab%/%b%
echo %b% %num%
pause>nul
作者: namejm 时间: 2007-1-25 03:08
Re ccwan 『第 3 楼』:
sorry，基本概念没有记好，犯了低级错误。
你的代码通过辗转求余的方法来计算最大公约数，确实是个比较好的思路，并且速度比我的要快得多，比如用52317和75569来测试，你的代码转瞬间就求出了最大公约数(虽然求最小公倍数的时候出错了)，而我的要跑上10S左右才能算出来。
不过我的代码在计算最小公倍数的时候，能处理的数字范围比你的要大一点(你的代码稍微修改一下就可以了)，因为你的是通过先把两个数字相乘然后再除以最大公约数来获得，而我的是先把两个数除以最大公约数之后再乘以最大公约数来获得——其实在计算最小公倍数的时候，我有点机械了，代码还可以精简一下，即先除以最大公约数之后再乘以另外一个数。
另外，你的 set/a num2=%a%%%b% 这条语句，其实是钻了set /a运算的空子，不知是你有意为之还是没注意到：在 set /a 运算中，参与运算的变量可以直接用变量名而无须使用百分号对来引用。如果按照一般的理解，这条语句的意思是 %a% 和 %b% 做 % 运算，可是批处理中的 set/a 并没有 % 这个运算符(虽然CMD下有 % 运算符号，但是批处理中的预处理机制并不会把单个的 % 识别为模运算符)，而实际上，运算是按照 %% 来操作的，可能的过程是：CMD预处理机制认为 %% 的优先级高于百分号对的引用，从而先扩展模运算符再处理变量的引用，而此时为 %a 模 b%，在 set /a 运算中，找不到变量 a 模 b，从而抛弃前后百分号，变成用 a的值 模 b的值。这个过程仅为推测，不一定正确。建议你把这条语句改成 set/a num2=a%%b 或者 set/a num2=%a%%%%b% ，以避免造成误解。
[ Last edited by namejm on 2007-1-24 at 04:00 PM ]
作者: ccwan 时间: 2007-1-25 03:32
谢谢jm兄的指点，我的考虑是:set/a num2=%a%%%b% 这条语句中若根据兄的意思，改为a%%b的话，cmd运算中会当作a%b,然后查找a,b的值去运算；而我的代码在cmd中会直接取a的值，然后模b，若a＝8，则运算式为set/a num2=8%b,这样减少了一个数值的查找，并不会出现错误。
这可以在cmd下通过实验看到。
对于兄的异议，这正是我知识匮乏的结果，不能从根本上了解它的运行机制。我还是在这里改为set/a num2=%a%%%%b%吧，这样比较好理解。
[ Last edited by ccwan on 2007-1-25 at 03:50 AM ]
作者: 20080610 时间: 2007-1-25 04:05
原来的帖
辗转相除法算是一种通用算法...
作者: namejm 时间: 2007-1-25 04:22
呵呵，原来已经有人做过了啊，没仔细搜索旧帖，造成了内容重复，罪过。
不过那个帖子是作为查错帖出现的，而这里提供的是另外的一种思路，合并主题似乎有点不合适，暂时不合并了，看看还有没有其他比较另类的算法或深入的分析出现。
作者: pengfei 时间: 2007-1-25 05:29
namejm兄和ccwan兄写的代码很不错, 辗转相除法的确是求最大公约数和公倍数的最佳算法, 也是平时最常采用的方法.
它在求公约数时, 将被除数和余数分别赋给下一步将要运算的除数和被除数, 直到余数为0止.
@echo off
set /p x=请输入第一个数:
set /p y=请输入第二个数:
set /a m=x,n=y
if %x% lss %y% set /a x=%y%,y=%x%
:go
set /a r=x%%y,x=y,y=r
if %y% neq 0 goto go
set /a p=m*n,z=p/x
echo %m% 和 %n%的最大公约数为:%x%
echo %m% 和 %n%的最小公倍数为:%z%
pause
[ Last edited by pengfei on 2007-1-25 at 10:32 AM ]set /p x=请输入第一个数:
set /p y=请输入第二个数:
set /a m=x,n=y
if %x% lss %y% set /a x=%y%,y=%x%
:go
set /a r=x%%y,x=y,y=r
if %y% neq 0 goto go
set /a p=m*n,z=p/x
echo %m% 和 %n%的最大公约数为:%x%
echo %m% 和 %n%的最小公倍数为:%z%
pause
作者: lzmyst 时间: 2007-1-25 06:01
暂时还不能完全理解，先COPY下来慢慢看。
作者: tao0610 时间: 2007-1-25 06:07
....
@echo off&setlocal enabledelayedexpansion
set /p num1= 请输入第一个数：
set /p num2= 请输入第二个数：
if %num1% geq %num2% (set g=%num1%&set l=%num2%) else set g=%num2%&set l=%num1%
:loop
set/a b+=g,mod=b%%l
if not %mod%==0 goto loop
set/a a=g*l/b
echo %num1% 和 %num2% 的最大公约数是 %a%，最小公倍数是 %b%
pause
set /p num1= 请输入第一个数：
set /p num2= 请输入第二个数：
if %num1% geq %num2% (set g=%num1%&set l=%num2%) else set g=%num2%&set l=%num1%
:loop
set/a b+=g,mod=b%%l
if not %mod%==0 goto loop
set/a a=g*l/b
echo %num1% 和 %num2% 的最大公约数是 %a%，最小公倍数是 %b%
pause