求最大公约数和最小公倍数 - 中国DOS联盟论坛

　　看到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 ]

呵呵。纯支持一下。

兄的代码确实精彩，我有一点小疑问，两个数的最大公约数可以是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 ]

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 ]

谢谢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 ]

原来的帖

辗转相除法算是一种通用算法...

　　呵呵，原来已经有人做过了啊，没仔细搜索旧帖，造成了内容重复，罪过。

　　不过那个帖子是作为查错帖出现的，而这里提供的是另外的一种思路，合并主题似乎有点不合适，暂时不合并了，看看还有没有其他比较另类的算法或深入的分析出现。

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 ]

暂时还不能完全理解，先COPY下来慢慢看。

....


@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

第1楼　namejm	发表于 2007-01-24 13:35
荣誉版主　发帖 1,737　积分 5,226　来自成都
求最大公约数和最小公倍数　　看到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 ]

第2楼　willsion	发表于 2007-01-24 23:14
高级用户　发帖 312　积分 793
呵呵。纯支持一下。

第3楼　ccwan	发表于 2007-01-25 01:58
金牌会员　发帖 1,160　积分 2,725　来自河北廊坊
兄的代码确实精彩，我有一点小疑问，两个数的最大公约数可以是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* ]

第4楼　namejm	发表于 2007-01-25 03:08
荣誉版主　发帖 1,737　积分 5,226　来自成都
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 ]

第5楼　ccwan	发表于 2007-01-25 03:32
金牌会员　发帖 1,160　积分 2,725　来自河北廊坊
谢谢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 ]

第6楼　20080610	发表于 2007-01-25 04:05
初级用户　发帖 34　积分 83
原来的帖辗转相除法算是一种通用算法...

第7楼　namejm	发表于 2007-01-25 04:22
荣誉版主　发帖 1,737　积分 5,226　来自成都
呵呵，原来已经有人做过了啊，没仔细搜索旧帖，造成了内容重复，罪过。　　不过那个帖子是作为查错帖出现的，而这里提供的是另外的一种思路，合并主题似乎有点不合适，暂时不合并了，看看还有没有其他比较另类的算法或深入的分析出现。

第8楼　pengfei	发表于 2007-01-25 05:29
银牌会员　发帖 485　积分 1,218　来自湖南.娄底
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=mn,z=p/x echo %m% 和 %n%的最大公约数为:%x% echo %m% 和 %n%的最小公倍数为:%z% pause [ Last edited by pengfei on 2007-1-25 at 10:32 AM* ]

第9楼　lzmyst	发表于 2007-01-25 06:01
新手上路　发帖 10　积分 19
暂时还不能完全理解，先COPY下来慢慢看。

第10楼　tao0610	发表于 2007-01-25 06:07
高级用户　发帖 218　积分 579
.... @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