GCDジージーディー関数

本ページには広告が含まれています。

引数に指定した配列の最大公約数（Greatestグレイテスト Commonコモン Divisorディバイザー）を求めます。ユークリッドの互除法で最大公約数を求めています。

構文
  1. Double = GCD( array )
引数
array 必須
最大公約数を求める数値を格納した配列
戻り値
最大公約数

プログラム

UWSC
//////////////////////////////////////////////////
// 【引数】
//   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

解説

  1. 2行目
    UWSC
    	DIM c = LENGTH(array)
    arrayの要素数を変数cに代入。
  2. 3行目
    UWSC
    	DIM rem = array[c-1] MOD array[c-2]
    arrayのc-1番目をc-2番目で割った余りをremに代入。
  3. 4,12行目
    UWSC
    	IFB rem = 0 THEN
		…
	ENDIF
    remの値が0ならば5行目>>>を実行。
  4. 5-11行目
    UWSC
    		IFB LENGTH(array) = 2 THEN
			RESULT = array[c-2]
			EXIT
		ENDIF
		RESIZE(array, c-2)
		RESULT = GCD(array)
		EXIT
    arrayの要素数が2ならば、arrayのc-2番目を返して終了。
    配列の要素数をc-2にする。GCDを再帰呼び出し。
  5. 13-15行目
    UWSC
    	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 \ge b\)）について、\(a\)を\(b\)で割ったときの商を\(q\)、余りを\(r\)とすると「\(a\)と\(b\)の最大公約数」は、「\(b\)と\(r\)の最大公約数」に等しい。

これらの性質を利用したユークリッドの互除法での手順は以下のようになります。

手順
  1. \(a\)を\(b\)で割り、余り\(r\)を求める。
  2. \(b\)を手順1の余り\(r\)で割り、その余り\(r_{1}\)を求める。
  3. \(r\)を手順2の余り\(r_{1}\)で割り、その余り\(r_{2}\)を求める。
  4. \(r_{1}\)を手順3の余り\(r_{2}\)で割り、その余り\(r_{3}\)を求める。
  5. 以降、\(r_{n}\)を\(r_{n+1}\)で割り、その余り\(r_{n+2}\)を余りが0になるまで繰り返し求めていく。
余りが0になったときの割る数の値が最大公約数となります。

これを式で表すと以下のようになります。

\begin{eqnarray} a \; &\div& \; \color{blue}{b} \; &=& \; q \; &\mod& \; \color{red}{r} \\ \color{blue}{b} \; &\div& \; \color{red}{r} \; &=& \; q_{1} \; &\mod& \; \color{green}{r_{1}} \\ \color{red}{r} \; &\div& \; \color{green}{r_{1}} \; &=& \; q_{2} \; &\mod& \; \color{pink}{r_{2}} \\ \color{green}{r_{1}} \; &\div& \; \color{pink}{r_{2}} \; &=& \; q_{3} \; &\mod& \; r_{3} \\ \end{eqnarray}

以下は1071と1029の最大公約数を求める例です。

\[ \begin{eqnarray} 1071 \; &\div& \; \color{blue}{1029} \; &=& \; 1 \; &\mod& \; \color{red}{42} \\ \color{blue}{1029} \; &\div& \; \color{red}{42} \; &=& \; 24 \; &\mod& \; \color{green}{21} \\ \color{red}{42} \; &\div& \; \color{green}{21} \; &=& \; 2 \; &\mod& \; 0 \end{eqnarray} \]

余りが0になったときの割る数である21が最大公約数です。

プログラム実行例

最大公約数を求めます

12と18の最大公約数を求めます。

UWSC
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
使用関数
解説

二次方程式を解く

UWSC
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関数 (自作関数)
奇数かどうか調べます。
radToDeg関数 (自作関数)
弧度法から度数法に変換します。