最大公約数（除算禁止）
Posted feedbacks - Batchfile
silverwire
#5899()
[
Batchfile
]
バッチは多倍長演算をサポートしていないため、図らずも #4841の「条件(易)」を選択。
除算・余剰については、「除算・余剰を使わずに閏年」で回答したものを流用しました。
e.g.
C:>gcd.bat 1975 1225
25
遅延環境変数展開を利用しているので、Windows NTでは動作しません。Windows XPで動作
を確認。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | :: gcd.bat
@echo off
setlocal
set n=0
echo %1%2|findstr /r "[^0-9]" >NUL 2>&1
if %ERRORLEVEL% equ 0 (echo %~n0 [NUMBER] [NUMBER]) & goto :EOF
call :gcd %1 %2 n
endlocal & echo %n%
goto :EOF
:gcd
setlocal enabledelayedexpansion
set a=%1
set b=%2
set m=0
set q=0
if %a% lss %b% (
set /a a=%b%-%a%
set /a b-=!a!
set /a a+=!b!
)
:loop_gcd
call :mod %a% %b% m
if %m% equ 0 (endlocal & set %3=%b%) & goto :EOF
:: 剰余を除数の半分未満にして演算効率を向上
call :div %b% 2 q
if %q% lss %m% set /a m=%b%-%m%
set a=%b%
set b=%m%
goto loop_gcd
endlocal
goto :EOF
:mod
setlocal
set m=0
set q=0
call :div %1 %2 q
set /a m=%2*%q%
endlocal & set /a %3=%1-%m%
goto :EOF
:div
setlocal enabledelayedexpansion
set i=0
set m=%1
set m_=0
set n=%2
set n_=0
set q=0
if %n% gtr %m% (endlocal & set %3=%q%) & goto :EOF
call :msb %m% m_
call :msb %n% n_
set /a i=%m_%-%n_%
:loop_div
if %i% lss 0 (endlocal & set %3=%q%) & goto :EOF
set /a "q<<=1"
set /a "m_=%m%>>%i%"
if %m_% geq %n% (
set /a "n_=%n%<<%i%"
set /a m-=!n_!
set /a q+=1
)
set /a i-=1
goto loop_div
endlocal
goto :EOF
:: 最上位ビットを取得(most significant bit)
:msb
setlocal
set i=%1
set n=0
:loop_msb
set /a "i>>=1"
set /a n+=1
if %i% neq 0 goto loop_msb
endlocal & set %2=%n%
goto :EOF
|
186 #4590() Rating0/8=0.00
あなたが使っている言語で除算と剰余が使えなくなりました。
以下の条件のもと最大公約数を求めるプログラムを書いてください。
条件
1 reply [ reply ]