GCD ｜ UWSC辞典

Contents

1 プログラム
- 1.1 解説
2 プログラム実行例
- 2.1 二次方程式を解く
- 2.2 最大公約数を求めます
  - 2.2.1 解説

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

構文

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

解説

2行目
```
	DIM c = LENGTH(arr)
```
DIM c = LENGTH(arr)
変数arrの要素数を変数cに代入。
3行目
```
	DIM rem = arr[c-1] MOD arr[c-2]
```
DIM rem = arr[c-1] MOD arr[c-2]
arr[c-1]をarr[c-2]で割った余りを変数remに代入。
4行目
```
	IFB rem = 0 THEN
```
IFB rem = 0 THEN
変数remの値が0ならば5行目>>>
5-11行目
```
		IFB LENGTH(arr) = 2 THEN
			RESULT = arr[c-2]
			EXIT
		ENDIF
		RESIZE(arr, c-2)
		RESULT = GCD(arr)
		EXIT
```
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を再帰呼び出し。
13-15行目
```
	arr[c-1] = arr[c-2]
	arr[c-2] = rem
	RESULT = GCD(arr)
```
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

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

結果: 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

結果: 6

解説

1行目
```
DIM arr[] = 12, 18
```
DIM arr[] = 12, 18
最大公約数を求める数値を配列に格納します。
2行目
```
PRINT GCD(arr)
```
PRINT GCD(arr)
GCD関数で最大公約数を求めて出力します。

この記事は役に立ちましたか？

UWSC辞典

GCD

プログラム

解説

プログラム実行例

二次方程式を解く

最大公約数を求めます

解説

検索フォーム

PR

最近の投稿・更新

タグ一覧

アーカイブ

カテゴリー

メタ情報

このページを共有する

お問合せ先