[数值计算] 批处理求最小共倍数和最大公约数

BatHome

::原理：展转相除法
::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
复制代码

czjt1234

回复 8# yyz219


    俗称不明觉厉

就是原理不懂，就烦这个位移

qixiaobin0715

可读性≈0
真的好拽！！！

yyz219

虽然不怎么看得明白，但是，觉得很强大

老刘1号

一万年后学了数理逻辑+位运算+数字电路的我又回来了

可读性≈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
复制代码

论坛这个万年屏蔽词…幸好我又看了一眼

老刘1号

朋友拿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
复制代码

email10t

这是第一个批处理程序？

lhjoanna

恩，看过了。楼主是不断改变调用函数的参数来达到辗转取余，相当于高级语言中的深层递归了。奇怪，怎么去年写的到现在回帖这么少啊，个人觉得求公约数和公倍数很有代表性啊。说实话，当时在学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 编辑 ]

523066680

对对！！！以后大家要多测试一下楼主们的代码哦 提出建议
讨论 让论坛的帖子热起来！

516526966

创办作品，值得支持。。
不过这个论坛的朋友们，看帖不回贴的现象太严重了，直接没有人气。
没有听说吗？灌水也是一种美德。这样人气才旺盛。。。。。。。。。。
建议管理员增加 hide  命令窗口。回复才可以看到。。。。。。