最大公約数（除算禁止）
Posted feedbacks - Smalltalk
Squeak Smalltalk で。
通常は無限倍精度整数に対応した #gcd: を使います。ちなみに、無限倍精度向けの Integer>>#gcd: および SmallInteger>>#gcd: に細工（グローバル変数 COUNT を用意して各々のループ内に COUNT := COUNT + 1 を挿入）をしてカウントをしてみたところ、fib1999 gcd: fib2000 では 1127 でした。
通常は無限倍精度整数に対応した #gcd: を使います。ちなみに、無限倍精度向けの Integer>>#gcd: および SmallInteger>>#gcd: に細工（グローバル変数 COUNT を用意して各々のループ内に COUNT := COUNT + 1 を挿入）をしてカウントをしてみたところ、fib1999 gcd: fib2000 では 1127 でした。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | | gcdNoDiv gcdNoDivCount fibMemo fib fib1999 fib2000 |
gcdNoDiv := [:pair |
[(pair sort; first) = pair second or: [pair last = 1]]
whileFalse: [pair at: 2 incrementBy: pair first negated].
pair last].
gcdNoDivCount := [:pair |
| count |
count := 0.
[(pair sort; first) = pair second or: [pair last = 1]] whileFalse: [
count := count + 1.
pair at: 2 incrementBy: pair first negated].
count].
fibMemo := Dictionary new.
fib := [:nth |
fibMemo at: nth ifAbsentPut: [
nth < 3 ifTrue: [1] ifFalse: [
(fib copy fixTemps value: nth-1) + (fib copy fixTemps value: nth-2)]]].
fib1999 := fib copy fixTemps value: 1999.
fib2000 := fib copy fixTemps value: 2000.
fib1999 gcd: fib2000. "=> 1 " " 組み込みの GCD "
gcdNoDiv value: {fib1999. fib2000}. "=> 1 "
gcdNoDivCount value: {fib1999. fib2000}. "=> 1998 "
|
186 #4590() Rating0/8=0.00
あなたが使っている言語で除算と剰余が使えなくなりました。
以下の条件のもと最大公約数を求めるプログラムを書いてください。
条件
1 reply [ reply ]