中国DOS联盟论坛

中国DOS联盟

-- 联合DOS 推动DOS 发展DOS --

联盟域名:www.cn-dos.net  论坛域名:www.cn-dos.net/forum
DOS,代表着自由开放与发展,我们努力起来,学习FreeDOS和Linux的自由开放与GNU精神,共同创造和发展美好的自由与GNU GPL世界吧!

游客:  注册 | 登录 | 命令行 | 会员 | 搜索 | 上传 | 帮助 »
作者:
标题: 求最大公约数和最小公倍数 上一主题 | 下一主题
namejm
荣誉版主

batch fan


积分 5226
发帖 1737
注册 2006-3-10
来自 成都
状态 离线
『楼 主』:  求最大公约数和最小公倍数

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



尺有所短,寸有所长,学好CMD没商量。
考虑问题复杂化,解决问题简洁化。
2007-1-24 13:35
查看资料  发短消息 网志   编辑帖子  回复  引用回复
willsion
高级用户




积分 789
发帖 310
注册 2004-9-2
状态 离线
『第 2 楼』:  

呵呵。纯支持一下。

2007-1-24 23:14
查看资料  发送邮件  发短消息 网志   编辑帖子  回复  引用回复
ccwan
金牌会员




积分 2725
发帖 1160
注册 2006-9-23
来自 河北廊坊
状态 离线
『第 3 楼』:  

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



三人行,必有吾师焉。   学然后知不足,教然后知困,然后能自强也。
2007-1-25 01:58
查看资料  发送邮件  发短消息 网志   编辑帖子  回复  引用回复
namejm
荣誉版主

batch fan


积分 5226
发帖 1737
注册 2006-3-10
来自 成都
状态 离线
『第 4 楼』:  

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 ]



尺有所短,寸有所长,学好CMD没商量。
考虑问题复杂化,解决问题简洁化。
2007-1-25 03:08
查看资料  发短消息 网志   编辑帖子  回复  引用回复
ccwan
金牌会员




积分 2725
发帖 1160
注册 2006-9-23
来自 河北廊坊
状态 离线
『第 5 楼』:  

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



三人行,必有吾师焉。   学然后知不足,教然后知困,然后能自强也。
2007-1-25 03:32
查看资料  发送邮件  发短消息 网志   编辑帖子  回复  引用回复
20080610
初级用户





积分 83
发帖 34
注册 2006-11-24
状态 离线
『第 6 楼』:  

原来的帖

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

2007-1-25 04:05
查看资料  发短消息 网志   编辑帖子  回复  引用回复
namejm
荣誉版主

batch fan


积分 5226
发帖 1737
注册 2006-3-10
来自 成都
状态 离线
『第 7 楼』:  

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

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



尺有所短,寸有所长,学好CMD没商量。
考虑问题复杂化,解决问题简洁化。
2007-1-25 04:22
查看资料  发短消息 网志   编辑帖子  回复  引用回复
pengfei
银牌会员




积分 1218
发帖 485
注册 2006-7-21
来自 湖南.娄底
状态 离线
『第 8 楼』:  

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 ]



业精于勤而荒于嬉,形成于思而毁于随。
2007-1-25 05:29
查看资料  发送邮件  发短消息 网志  OICQ (573381312)  编辑帖子  回复  引用回复
lzmyst
新手上路





积分 19
发帖 10
注册 2005-12-13
状态 离线
『第 9 楼』:  

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

2007-1-25 06:01
查看资料  发短消息 网志   编辑帖子  回复  引用回复
tao0610
高级用户

朦胧的世界


积分 579
发帖 218
注册 2006-10-24
状态 离线
『第 10 楼』:  

....
@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





认识自己,降伏自己,改变自己
,才能改变别人!
2007-1-25 06:07
查看资料  发短消息 网志   编辑帖子  回复  引用回复

请注意:您目前尚未注册或登录,请您注册登录以使用论坛的各项功能,例如发表和回复帖子等。


可打印版本 | 推荐给朋友 | 订阅主题 | 收藏主题



论坛跳转: