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
  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)
  1. gcd
結果
6
解説
  1. 1行目
    DIM arr[] = 12, 18
    最大公約数を求める数値を配列に格納します。
  2. 2行目
    PRINT GCD(arr)
    GCD関数で最大公約数を求めて出力します。

Was this post helpful?

関連記事

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