本ページには広告が含まれています。
目次 [非表示]
引数に指定した配列の最大公約数（Greatest Common Divisor）を求めます。ユークリッドの互除法で最大公約数を求めています。
- 構文
- Double = GCD( array )
- 引数
- array 必須
- 最大公約数を求める数値を格納した配列
- 戻り値
- 最大公約数
プログラム
////////////////////////////////////////////////// // 【引数】 // array : 最大公約数を求める数値を格納した配列 // 【戻り値】 // 最大公約数 ////////////////////////////////////////////////// FUNCTION GCD(array[]) DIM c = LENGTH(array) DIM rem = array[c-1] MOD array[c-2] IFB rem = 0 THEN IFB LENGTH(array) = 2 THEN RESULT = array[c-2] EXIT ENDIF RESIZE(array, c-2) RESULT = GCD(array) EXIT ENDIF array[c-1] = array[c-2] array[c-2] = rem RESULT = GCD(array) FEND
解説
- 2行目
- arrayの要素数を変数cに代入。
DIM c = LENGTH(array)
- 3行目
- arrayのc-1番目をc-2番目で割った余りをremに代入。
DIM rem = array[c-1] MOD array[c-2]
- 4,12行目
- remの値が0ならば5行目>>>を実行。
IFB rem = 0 THEN … ENDIF
- 5-11行目
- arrayの要素数が2ならば、arrayのc-2番目を返して終了。
IFB LENGTH(array) = 2 THEN RESULT = array[c-2] EXIT ENDIF RESIZE(array, c-2) RESULT = GCD(array) EXIT
配列の要素数をc-2にする。GCDを再帰呼び出し。
- 13-15行目
array[c-1] = array[c-2] array[c-2] = rem RESULT = GCD(array)
公約数と最大公約数について
公約数とは
2つ以上の自然数についていずれの約数にもなることができる整数のことを公約数といいます。言い換えると、共通している約数のことを指します。例えば、8と12の公約数は、まず8の約数が1、2、4、8で、12の約数が1、2、3、4、6、12なので、共通している1、2、4となります。
最大公約数とは
最大公約数とは、共通する約数（公約数）のうち最大の整数のことです。8と12の最大公約数は約数のうちで最大の整数である4となります。
ユークリッドの互除法
ユークリッドの互除法とは2つの自然数の最大公約数を求める方法で、以下の性質を使って最大公約数を求めます。
POINT
2つの自然数a,b（a≥b）について、aをbで割ったときの商をq、余りをrとすると「aとbの最大公約数」は、「bとrの最大公約数」に等しい。
これらの性質を利用したユークリッドの互除法での手順は以下のようになります。
手順
- aをbで割り、余りrを求める。
- bを手順1の余りrで割り、その余りr1を求める。
- rを手順2の余りr1で割り、その余りr2を求める。
- r1を手順3の余りr2で割り、その余りr3を求める。
- 以降、rnをrn+1で割り、その余りrn+2を余りが0になるまで繰り返し求めていく。
これを式で表すと以下のようになります。
a÷b=qmodrb÷r=q1modr1r÷r1=q2modr2r1÷r2=q3modr3以下は1071と1029の最大公約数を求める例です。
1071÷1029=1mod421029÷42=24mod2142÷21=2mod0余りが0になったときの割る数である21が最大公約数です。
プログラム実行例
最大公約数を求めます
12と18の最大公約数を求めます。
DIM array[] = 12, 18 PRINT GCD(array) ////////////////////////////////////////////////// // 【引数】 // array : 最大公約数を求める数値を格納した配列 // 【戻り値】 // 最大公約数 ////////////////////////////////////////////////// FUNCTION GCD(array[]) DIM c = LENGTH(array) DIM rem = array[c-1] MOD array[c-2] IFB rem = 0 THEN IFB LENGTH(array) = 2 THEN RESULT = array[c-2] EXIT ENDIF RESIZE(array, c-2) RESULT = GCD(array) EXIT ENDIF array[c-1] = array[c-2] array[c-2] = rem RESULT = GCD(array) FEND
結果
6
使用関数
解説
二次方程式を解く
DIM frac[2] DIM coeff = SPLIT(INPUT("係数を入力してください。「ax^2+bx+c=0」の「a,b,c」を入力。"), ",") DIM a = coeff[0] DIM b = coeff[1] DIM c = coeff[2] // 判別式 DIM D = EVAL("POWER(b, 2) - 4 * a * c") DIM ans[-1] DIM digit = -3 SELECT TRUE CASE D > 0 IFB b = 0 THEN DIM root = simplifySqrt(D) frac[0] = root[0] frac[1] = EVAL("2 * a") num = GCD(frac) IFB frac[1] = ABS(num) THEN res = frac[0] / ABS(num) ELSE res = frac[0] + "/" + frac[1] ENDIF arrayPush(ans, (IIF(frac[0] / num <> 1, frac[0] / num, "") + IIF(root[1] <> 1, "√(" + root[1] + ")", ""))) arrayPush(ans, (IIF(frac[0] / num <> 1, -frac[0] / num, "") + IIF(root[1] <> 1, "√(" + root[1] + ")", ""))) ELSE // 約分する frac[0] = EVAL("-b") frac[1] = EVAL("2 * a") num = GCD(frac) IFB frac[1] = ABS(num) THEN res = frac[0] / ABS(num) ELSE res = frac[0] + "/" + frac[1] ENDIF // ルートの中から整数を外に出す root = simplifySqrt(D) frac[0] = root[0] num = GCD(frac) IFB frac[1] = num THEN arrayPush(ans, res + "+" + (IIF(frac[0] / num <> 1, frac[0] / num, "") + "√(" + root[1] + ")")) arrayPush(ans, res + "-" + (IIF(frac[0] / num <> 1, frac[0] / num, "") + "√(" + root[1] + ")")) ELSE arrayPush(ans, res + "+(" + (IIF(frac[0] / num <> 1, frac[0] / num, "") + "√(" + root[1] + "))/" + (frac[1] / num))) arrayPush(ans, res + "-(" + (IIF(frac[0] / num <> 1, frac[0] / num, "") + "√(" + root[1] + "))/" + (frac[1] / num))) ENDIF ENDIF CASE D = 0 arrayPush(ans, ROUND(EVAL("-b/(2*a)"), digit)) CASE D < 0 IFB b = 0 THEN root = simplifySqrt(D) frac[0] = root[0] frac[1] = EVAL("2 * a") num = GCD(frac) IFB frac[1] = ABS(num) THEN res = frac[0] / ABS(num) ELSE res = frac[0] + "/" + frac[1] ENDIF arrayPush(ans, (IIF(frac[0] / num <> 1, frac[0] / num, "") + IIF(root[1] <> 1, "√(" + root[1] + ")", ""))) arrayPush(ans, (IIF(frac[0] / num <> 1, -frac[0] / num, "") + IIF(root[1] <> 1, "√(" + root[1] + ")", ""))) ELSE frac[0] = EVAL("-b") frac[1] = EVAL("2 * a") num = GCD(frac) IFB frac[1] = ABS(num) THEN res = frac[0] / ABS(num) ELSE res = IIF(frac[0] * frac[1] < 0, "-", "") + ABS(frac[0] / num) + "/" + ABS(frac[1] / num) ENDIF // ルートの中から整数を外に出す root = simplifySqrt(ABS(D)) frac[0] = root[0] num = GCD(frac) IFB frac[1] = num THEN arrayPush(ans, res + "+" + (IIF(frac[0] / num <> 1, frac[0] / num, "") + "√(" + root[1] + ")i")) arrayPush(ans, res + "-" + (IIF(frac[0] / num <> 1, frac[0] / num, "") + "√(" + root[1] + ")i")) ELSE arrayPush(ans, res + "+(" + (IIF(frac[0] / num <> 1, frac[0] / num, "") + "√(" + root[1] + ")i)/" + (frac[1] / num))) arrayPush(ans, res + "-(" + (IIF(frac[0] / num <> 1, frac[0] / num, "") + "√(" + root[1] + ")i)/" + (frac[1] / num))) ENDIF ENDIF SELEND PRINT REPLACE(IIF(a <> 1, a, "") +"x^2+" + b + "x+" + c, "+-", "-") PRINT "-----" FOR item IN ans PRINT item NEXT ////////////////////////////////////////////////// // 【引数】 // num : ルートの中 // 【戻値】 // 整数を外に出す ////////////////////////////////////////////////// FUNCTION simplifySqrt(num) HASHTBL root DIM arr = primeFactorization(num) DIM a = 1, b = 1 FOR item IN arr root[item] = root[item] + 1 NEXT FOR n = 0 TO LENGTH(root) - 1 IF INT(root[n, HASH_VAL] / 2) <> 0 THEN a = a * POWER(root[n, HASH_KEY], INT(root[n, HASH_VAL] / 2)) IF (root[n, HASH_KEY] * (root[n, HASH_VAL] MOD 2)) <> 0 THEN b = b * (root[n, HASH_KEY] * (root[n, HASH_VAL] MOD 2)) NEXT DIM res[1] = a, b RESULT = SLICE(res) FEND ////////////////////////////////////////////////// // 【引数】 // array : 要素を追加する配列（参照引数） // values : 追加する要素をvalue1から指定 // 【戻り値】 // 処理後の配列の要素の数 ////////////////////////////////////////////////// FUNCTION arrayPush(var array[], value1 = EMPTY, value2 = EMPTY, value3 = EMPTY, value4 = EMPTY, value5 = EMPTY, value6 = EMPTY, value7 = EMPTY, value8 = EMPTY, value9 = EMPTY, value10 = EMPTY, value11 = EMPTY, value12 = EMPTY, value13 = EMPTY, value14 = EMPTY, value15 = EMPTY, value16 = EMPTY) DIM i = 1 WHILE EVAL("value" + i) <> EMPTY DIM res = RESIZE(array, UBound(array) + 1) array[res] = EVAL("value" + i) i = i + 1 WEND RESULT = LENGTH(array) FEND ////////////////////////////////////////////////// // 【引数】 // array : 最大公約数を求める数値を格納した配列 // 【戻り値】 // 最大公約数 ////////////////////////////////////////////////// FUNCTION GCD(array[]) DIM c = LENGTH(array) DIM rem = array[c-1] MOD array[c-2] IFB rem = 0 THEN IFB LENGTH(array) = 2 THEN RESULT = array[c-2] EXIT ENDIF RESIZE(array, c-2) RESULT = GCD(array) EXIT ENDIF array[c-1] = array[c-2] array[c-2] = rem RESULT = GCD(array) FEND ////////////////////////////////////////////////// // 【引数】 // expr : 評価する式 // truepart : 評価した式がTrueのときに返す値 // falsepart : 評価した式がFalseのときに返す値 // 【戻り値】 // truepart : 評価した式がTrueのとき、falsepart : 評価した式がFalseのとき ////////////////////////////////////////////////// FUNCTION IIF(expr, truepart, falsepart) IFB EVAL(expr) THEN RESULT = truepart ELSE RESULT = falsepart ENDIF FEND ////////////////////////////////////////////////// // 【引数】 // num : 素因数分解する数値 // 【戻り値】 // 素因数分解した数値を格納した配列 ////////////////////////////////////////////////// FUNCTION primeFactorization(num) DIM arr[-1] WHILE num MOD 2 = 0 arrayPush(arr, 2) num = num / 2 WEND FOR n = 3 TO num WHILE num MOD n = 0 arrayPush(arr, n) num = num / n WEND NEXT RESULT = SLICE(arr) FEND ////////////////////////////////////////////////// // 【引数】 // inputs : 繰り返す文字列 // multiplier : inputsを繰り返す回数 // 【戻り値】 // inputsをmultiplier回を繰り返した文字列を返します ////////////////////////////////////////////////// FUNCTION strRepeat(inputs, multiplier) DIM res = "" FOR n = 1 TO multiplier res = res + inputs NEXT RESULT = res FEND ////////////////////////////////////////////////// // 【引数】 // arrayname : 上限値を求める配列の名前 // dimension : 返す次元を示す整数 // 【戻り値】 // 配列の上限値 ////////////////////////////////////////////////// FUNCTION UBound(arrayname[], dimension = 1) RESULT = EVAL("RESIZE(arrayname" + strRepeat("[0]", dimension - 1) + ")") FEND
結果
4x^2+5x+3 ----- -5/8+(√(23)i)/8 -5/8-(√(23)i)/8
使用関数
関連記事
- fact関数 (自作関数)
- 引数に指定した数値の階乗を求めます。
- factDouble関数 (自作関数)
- 引数に指定した数値の二重階乗を求めます。
- ABS関数 (スクリプト関数)
- 引数の絶対値を求めます。
- ARCCOS関数 (スクリプト関数)
- 引数の逆余弦を求めます。
- CEIL関数 (スクリプト関数)
- 正の方向へ切り上げた数値を返します。
- LN関数 (スクリプト関数)
- 自然対数を求めます。
- LOGN関数 (スクリプト関数)
- 常用対数を求めます。
- ZCUT関数 (スクリプト関数)
- マイナス値を0にして返します。プラス値はそのままの値を返します。
- isOdd関数 (自作関数)
- 引数に指定した数値が奇数かどうかを調べます。奇数ならばTrue、それ以外の数値はFalse、文字列はエラー値を返します。
- radToDeg関数 (自作関数)
- 弧度法（Radian）を度数法（Degree）に変換します。度数法を弧度法に変換するにはDegToRad関数を使います。
