GCD

タグ:

引数に指定した配列の最大公約数(Greatest Common Divisor)を求めます。

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

プログラム

//////////////////////////////////////////////////
// 【引数】
//   arr : 最大公約数を求める数値を格納した配列 
// 【戻値】
//   最大公約数 
//////////////////////////////////////////////////
FUNCTION GCD(arr[])
	DIM c = LENGTH(arr)
	DIM rem = arr[c-1] MOD arr[c-2]
	IFB rem = 0 THEN
		IFB LENGTH(arr) = 2 THEN
			RESULT = arr[c-2]
			EXIT
		ENDIF
		RESIZE(arr, c-2)
		RESULT = GCD(arr)
		EXIT
	ENDIF
	arr[c-1] = arr[c-2]
	arr[c-2] = rem
	RESULT = GCD(arr)
FEND

解説

  1. 2行目
    	DIM c = LENGTH(arr)
    変数arrの要素数を変数cに代入。
  2. 3行目
    	DIM rem = arr[c-1] MOD arr[c-2]
    arr[c-1]をarr[c-2]で割った余りを変数remに代入。
  3. 4,12行目
    	IFB rem = 0 THEN
    		…
    	ENDIF
    変数remの値が0ならば5行目>>>
  4. 5-11行目
    		IFB LENGTH(arr) = 2 THEN
    			RESULT = arr[c-2]
    			EXIT
    		ENDIF
    		RESIZE(arr, c-2)
    		RESULT = GCD(arr)
    		EXIT
    配列arrの要素数が2ならば、arr[c-2]を返して終了。
    配列の要素数をc-2にする。GCDを再帰呼び出し。
  5. 13-15行目
    	arr[c-1] = arr[c-2]
    	arr[c-2] = rem
    	RESULT = GCD(arr)

プログラム実行例

二次方程式を解く

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 : 要素を追加する配列(参照引数) 
//   str : 追加する要素 
// 【戻値】
//   処理後の配列の中の要素の数 
//////////////////////////////////////////////////
FUNCTION arrayPush(var arr[], str)
	DIM res = RESIZE(arr, UBound(arr) + 1)
	arr[res] = str
	RESULT = res + 1
FEND

//////////////////////////////////////////////////
// 【引数】
//   arr : 最大公約数を求める数値を格納した配列 
// 【戻値】
//   最大公約数 
//////////////////////////////////////////////////
FUNCTION GCD(arr[])
	DIM c = LENGTH(arr)
	DIM rem = arr[c-1] MOD arr[c-2]
	IFB rem = 0 THEN
		IFB LENGTH(arr) = 2 THEN
			RESULT = arr[c-2]
			EXIT
		ENDIF
		RESIZE(arr, c-2)
		RESULT = GCD(arr)
		EXIT
	ENDIF
	arr[c-1] = arr[c-2]
	arr[c-2] = rem
	RESULT = GCD(arr)
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]
	// 偶数なら2で割り続ける
	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

//////////////////////////////////////////////////
// 【引数】
//   配列 : 上限値を求める配列 
// 【戻値】
//   配列の上限値 
//////////////////////////////////////////////////
FUNCTION UBound(array[])
	RESULT = RESIZE(array)
FEND
  1. SPLIT
  2. INPUT
  3. EVAL
  4. GCD
  5. ABS
  6. arrayPush
  7. IIF
  8. ROUND
  9. REPLACE
結果
4x^2+5x+3
-----
-5/8+(√(23)i)/8
-5/8-(√(23)i)/8

最大公約数を求めます

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

DIM arr[] = 12, 18
PRINT GCD(arr)

//////////////////////////////////////////////////
// 【引数】
//   arr : 最大公約数を求める数値を格納した配列 
// 【戻値】
//   最大公約数 
//////////////////////////////////////////////////
FUNCTION GCD(arr[])
	DIM c = LENGTH(arr)
	DIM rem = arr[c-1] MOD arr[c-2]
	IFB rem = 0 THEN
		IFB LENGTH(arr) = 2 THEN
			RESULT = arr[c-2]
			EXIT
		ENDIF
		RESIZE(arr, c-2)
		RESULT = GCD(arr)
		EXIT
	ENDIF
	arr[c-1] = arr[c-2]
	arr[c-2] = rem
	RESULT = GCD(arr)
FEND
  1. GCD
結果
6
解説
  1. 1行目
    DIM arr[] = 12, 18
    最大公約数を求める数値を配列に格納します。
  2. 2行目
    PRINT GCD(arr)
    GCD関数で最大公約数を求めて出力します。

関連記事

ABS (スクリプト関数)
引数の絶対値を求めます。
ARCCOS (スクリプト関数)
引数の逆余弦を求めます。
ARCSIN (スクリプト関数)
引数の逆正弦を求めます。
ARCTAN (スクリプト関数)
引数の逆正接を求めます。
CEIL (スクリプト関数)
正の方向へ切り上げた数値を返します。
EXP (スクリプト関数)
自然指数関数を求めます。
LN (スクリプト関数)
自然対数を求めます。
LOGN (スクリプト関数)
常用対数を求めます。
ZCUT (スクリプト関数)
マイナス値を0にして返します。プラス値はそのままの値を返します。
INT (スクリプト関数)
小数点以下を切り捨てた値を返します。負の値の場合、正の値のようにより小さい値にではなく0に近い側に切り捨てされます。
POWER (スクリプト関数)
数値のべき乗を求めます。
RANDOM (スクリプト関数)
RANDOM関数は、0以上Range未満の範囲にある乱数(整数)を返します。引数を省略した場合は、0以上1未満の乱数(小数点以下15桁)を返します。
ROUND (スクリプト関数)
指定した位置で偶数丸めした値を返します。四捨五入する場合は、roundOff関数を使います。
isEven
引数に指定した数値が偶数かどうかを調べます。偶数ならばTrue、それ以外の数値はFalse、文字列はエラー値を返します。
isOdd
引数に指定した数値が奇数かどうかを調べます。奇数ならばTrue、それ以外の数値はFalse、文字列はエラー値を返します。
radToDeg
弧度法(Radian)を度数法(Degree)に変換します。度数法を弧度法に変換するにはDegToRad関数を使います。
SQRT (スクリプト関数)
引数の平方根を求めます。累乗根はPOWER関数を使います。
fact
引数に指定した自然数の階乗を求めます。再帰関数。二重階乗を求めるにはfactDouble関数を使います。
factDouble
引数に指定した自然数の二重階乗を求めます。戻値の型はDouble型です。再帰関数。階乗を求めるにはfact関数を使います。
degToRad
度数法(Degree)を弧度法(Radian)に変換します。弧度法を度数法に変換するにはRadToDeg関数を使います。
LCM
LCM関数は、引数に指定した配列の最小公倍数(Least Common Multiple)を求める関数です。最大公約数を求めるには、GMD関数を使います。
hexToDec
16進数を10進数に変換します。10進数を16進数に変換するにはdecToHex関数を使います。
decToHex
10進数を16進数に変換します。16進数を10進数に変換するにはhexToDec関数を使います。
binToDec
2進数を10進数に変換します。10進数を2進数に変換するにはdecToBin関数を使います。
binToHex
2進数を16進数に変換します。16進数を2進数に変換するにはhexToBin関数を使います。
hexToBin
16進数を2進数に変換します。2進数を16進数に変換するにはbinToHex関数を使います。
decToBin
10進数を2進数に変換します。2進数を10進数に変換するにはbinToDec関数を使います。
isPrime
引数に指定した数値が素数かどうかを調べます。素数の場合True、素数でない場合Falseを返します。
normalizeAngle
度単位の角度を0~360度に正規化します。
divisors
引数に指定した数値の約数をリストを配列で返します。
digitSum
引数に指定した数字和(数値の各桁を足した結果)を返します。正の整数以外を指定した場合は、エラー値を返します。
Collatz
コラッツ数列を求め結果を配列で返します。
Kaprekar
カプレカ数を求め結果を配列で返します。
ARABIC
ARABIC関数は、ローマ数字をアラビア数字に変換する関数です。アラビア数字をローマ数字に変換するには、ROMAN関数を使います。
ROMAN
ROMAN関数は、アラビア数字をローマ数字に変換する関数です。ローマ数字をアラビア数字に変換するには、ARABIC関数を使います。