基本のアルゴリズム

組合せの数

 組合せの数nCr は,順列の数nPrr!で割って求められるが,その通りの順序で計算するとnCr はBASICで表現可能な範囲の数であるのに,nPr を計算する過程で桁あふれを生じることがある。
 nCrnCr-1・(n-r+1)/r と変形できることを利用して次のように計算すると,無駄に桁数を増やさずに計算できる。

10 INPUT n,r
20 LET C=1
30 FOR i=1 TO r
40    LET C=C*(n-i+1)/i
50 NEXT i
60 PRINT C
70 END

二項分布

 nCx px(1-p)n-x を計算する。
 nが大きい数であると,nCx がBASICで計算可能な最大の数を超えたり,px(1-p)n-x がBASICで扱うことのできる最小の正の数を下回ったりしてしまう。それを避けるために,対数をとって計算する。

10 INPUT p,n
20 INPUT x
30 LET u=x*LOG10(p)+(n-x)*LOG10(1-p)
40 FOR i=1 TO x
50    LET u=u+LOG10(n-i+1)-LOG10(i)
60 NEXT i
70 PRINT 10^u
80 END

素因数分解

 入力された自然数n を素因数分解する。
 n を小さい素数から順に割り切れるかぎり割る。最初,f=2として,n をf で割り切れるかぎり割る(130行〜160行のDO〜LOOP)。  f で割れなくなったら,f には次の素数を割り当てる必要があるが,170行のように 1を加算した数にしても支障はない。なぜなら,もし,それが素数でないなら,130行の条件に合わないから,130行からのDO〜LOOPは実行されずに,再度170行が実行されるから。この操作が,f がn の約数になるまで繰り返される。繰り返しが終わるのは,n の約数をすべて出力してn=1 になったときである。

100 INPUT n
110 LET f=2
120 DO UNTIL n=1
130    DO WHILE MOD(n,f)=0
140       PRINT f;
150       LET n=n/f
160    LOOP
170    LET f=f+1
180 LOOP
190 END


 f が√n より大きくなってしまったら, f はn の素因数にはなりえない。だから,終了条件を見直して,f を増加させる繰り返しを早く終了させることができる。
改良版

100 INPUT n
110 LET f=2
120 DO UNTIL f>SQR(n)
130    DO WHILE MOD(n,f)=0
140       PRINT f;
150       LET n=n/f
160    LOOP
170    LET f=f+1
180 LOOP
190 IF n>1 THEN PRINT n
200 END

<備考>有理数モードでは,SQR(n)の代わりにINTSQR(n)を用いる。

 偶数の素数は2だけだから,2のみを別に処理し,以後,奇数に限定すれば,少し速くなる。
 また,SQR(n)の計算を繰り返しのたびに行うのは無駄だから,nの値を変えたときにのみ計算することにする。

100 INPUT n
110 DO WHILE MOD(n,2)=0
120    PRINT 2;
130    LET n=n/2
140 LOOP
150 LET f=3
160 LET s=SQR(n)
170 DO UNTIL f>s
180    DO WHILE MOD(n,f)=0
190       PRINT f;
200       LET n=n/f
210       LET s=SQR(n)
220    LOOP
230    LET f=f+2
240 LOOP
250 IF n>1 THEN PRINT n
260 END


<注意>
 BASICではFOR文の限界(TOの次に書かれる数値)はFOR〜NEXTループに入るときにのみ評価されるので,上のプログラムをFOR〜NEXTを用いて次のように書き換えることはできない。

100 INPUT n
110 DO WHILE MOD(n,2)=0
120    PRINT 2;
130    LET n=n/2
140 LOOP
150 LET s=SQR(n)
160 FOR f=3 TO s STEP 2
170    DO WHILE MOD(n,f)=0
180       PRINT f;
190       LET n=n/f
200       LET s=SQR(n)
210    LOOP
220 NEXT f
230 IF n>1 THEN PRINT n
240 END


素数か合成数か判定する

 2以上の整数を入力すると,素数であるか,合成数であるか判定する。

100 INPUT n
110 LET s$="素数"
120 FOR f=2 TO SQR(n)
130    IF MOD(n,f)=0 THEN
140       LET s$="合成数"
150       EXIT FOR
160    END  IF
170 NEXT f
180 PRINT n;"は";s$
190 END

 1を入力すると誤判定するので注意(1は素数でも合成数でもない)。

 2より大きい偶数は合成数であり,奇数の約数は奇数しかないから,次のようにすると,判定に要する時間をおよそ半分に減らせる。

100 INPUT n
110 IF n=2 then
120    LET s$="素数"
130 ELSEIF MOD(n,2)=0 THEN 
140    LET s$="合成数"
150 ELSEIF n>1 THEN
160    LET s$="素数"
170    FOR f=3 TO SQR(n) STEP 2
180       IF MOD(n,f)=0 THEN
190          LET s$="合成数"
200          EXIT FOR
210       END  IF
220    NEXT f
230 END IF
240 PRINT n;"は";s$ 
250 END

<備考>有理数モードでは,SQR(n)の代わりにINTSQR(n)を用いる。

さらに速くしたければ,エラトステネスの篩法によりSQR(n)以下の素数のリストを用意し,それで順に割る。


最大公約数

 2数の最大公約数を求めるアルゴリズム(互除法)は,再帰を用いて次のように表現できる。

100 FUNCTION GCD(a,b)
110    IF b=0 THEN
120       LET GCD=a 
130    ELSE 
140       LET GCD=GCD(b, MOD(a,b))
150    END IF
160 END FUNCTION
170 INPUT a,b
180 PRINT GCD(a,b)
190 END


 これを再帰を使わずに書くこともできる。
 上のプログラムで,140行のLET文は,実質的に
 a←b
 b←MOD(a,b)
という代入になっている。
 この代入を
LET a=b
LET b=MOD(a,b)
としたら,後から実行するLET文の実行時には既にaの値が書き換わってしまっているので具合が悪い。
 この事情はLET文の実行順序を逆にしても変わらないから,もうひとつ別の変数tを用意して,
 LET t=b
 LET b=MOD(a,b)
 LET a=t
のように代入する。
 これをb=0になるまで繰り返せば,aが最大公約数である。

10 INPUT a,b
20 DO UNTIL b=0
30    LET t=b
40    LET b=MOD(a,b)
50    LET a=t
60 LOOP
70 PRINT a
80 END


 普通は,剰余を求める計算を先に実行して,次の形に書かれることが多いが,実質的には同じ。

10 INPUT a,b
20 DO UNTIL b=0
30    LET r=MOD(a,b)
40    LET a=b
50    LET b=r
60 LOOP
70 PRINT a
80 END

フィボナッチ数列

 フィボナッチ数列{fn}は,
 f1=1, f2=1, fn=fn-1+fn-2
により定められる数列である。

 再帰を利用して書いたプログラム

10 FUNCTION f(n)
20    IF n=1 OR n=2 THEN LET f=1 ELSE LET f=f(n-1)+f(n-2)
30 END FUNCTION
40 INPUT n
50 PRINT f(n)
60 END

は実行可能であるが,効率が悪い。 なぜかというと,f(n-2)の計算を実行するとき,f(n-1)の計算の途中結果を利用しないから。

 配列を使って

DIM f(1000)
LET f(1)=1
LET f(2)=1
INPUT n
FOR i=3 TO n
   LET f(i)=f(i-1)+f(i-2)
NEXT i
PRINT f(n)
END

とすれば,計算の無駄は省けるが,計算には直前の2項しか使わないから,メモリを無駄に使っている。

 そこで,直前2項をd,eとして変数値をシフトしながら計算することにすると,

100 LET d=1
110 LET e=1
120 INPUT n
130 FOR i=3 TO n
140    LET f=e+d
150    LET d=e
160    LET e=f
170 NEXT i
180 PRINT f
190 END

のように書ける。150行と160行は,次の繰り返しの回のための変数値の更新を意味する。

自然数を2進法で表す

 自然数を2進表記に変換する。
 ある数を2であると,その余りが2進法における1の位の数である。その商をさらに2で割ると,余りが2の位の数になる。さらに,その商を2で割ったときの余りが4の位の数になる。つまり,2で割り,余りを出力して,商を次の入力とする繰り返しを行えばよい。
 次のプログラムでは,結果は,通常の表記とは逆順に,すなわち,1の位から順に出力される。

10 INPUT n
20 DO UNTIL n=0
30    LET r=MOD(n,2)
40    PRINT r;
50    LET n=(n-r)/2
60 LOOP
70 END


 上位桁が左にくるように結果を表示したい場合は,文字列処理を利用すると簡単。

10 LET s$=""
20 INPUT n
30 DO UNTIL n=0
40    LET r=MOD(n,2)
50    LET s$=STR$(r)&s$
60    LET n=(n-r)/2
70 LOOP
80 PRINT s$
90 END



小数を2進法で表す

 0以上1未満の十進小数を2進小数で表す。
 上と逆に考えればよい。すなわち,2倍して1で割った商(つまり整数部分)をとれば,それが,2進法における0.1の位の数である。その余りを再度,2倍して1で割った商をとると,それが0.01の位の数になる。再度,その余りを2倍する。

10 OPTION ARITHMETIC DECIMAL
20 INPUT x
30 PRINT "0.";
40 DO UNTIL x=0
50    LET p=INT(2*x)
60    PRINT p;
70    LET x=2*x-p
80 LOOP
90 END

 Full BASICは十進小数を正確に扱うので,Full BASICで実行する限りにおいてこのプログラムは正しい。
 十進小数は2進小数に直すと無限小数になることがある。たとえば,0.1を入力すると,このプログラムは永久に停止しない。(メニューから中断を選んで停止させる)

高速な累乗計算

 累乗を計算するとき,指数が2のべきであれば,
 a2=a×a
 a4=a2×a2
 a8=a4×a4
 a16=a8×a8
のように少ない回数の掛け算で実行できる。
 さらに,たとえば,25=16+8+1だから,
 a25=a16×a8×a
のようにして指数が2のべきでなくても少ない回数の掛け算で計算できる。
 自然数を2のべきの和に直す計算は2進法に直す計算と同じであるから,anの計算が高速に実行できる。

100 INPUT a,n
110 LET p=1
120 LET b=a
130 DO UNTIL n=0
140    IF MOD(n,2)=1 THEN LET p=p*b
150    LET b=b*b
160    LET n=INT(n/2)
170 LOOP
180 PRINT p
190 END

 BASICにはべき乗演算が備わっているから,このプログラムに実用的価値はないが,このアルゴリズムは,剰余系における累乗や,行列の累乗の計算に応用される。

 次のプログラムは,2×2行列aのn乗を計算する。

100 DIM a(2,2),b(2,2),m(2,2)
110 MAT INPUT a
120 INPUT n
130 MAT m=IDN
140 MAT b=a
150 DO UNTIL n=0
160    IF MOD(n,2)=1 THEN MAT m=m*b
170    MAT b=b*b
180    LET n=INT(n/2)
190 LOOP
200 MAT PRINT m
210 END

 次のプログラムは,kを法とする剰余系においてanを計算する。

100 INPUT k
110 INPUT a,n
120 LET p=1
130 LET b=MOD(a,k)
140 DO UNTIL n=0
150    IF MOD(n,2)=1 THEN LET p=MOD(p*b,k)
160    LET b=MOD(b*b,k)
170    LET n=INT(n/2)
180 LOOP
190 PRINT p
200 END

フェルマー テスト

 フェルマーの小定理
 0<a<kのとき,kが素数であれば,ak-1≡1 (mod k)
を利用すると,kを法とする剰余系において,あるa(1<a<k)に対してak-1乗が1にならなければ,kは素数ではないと結論することができる。
 次のプログラムは,a=2に対して上のテストを実行する。他のaの値に対して実行したいときは,100行を変更する。

100 LET a=2
110 INPUT k
120 LET n=k-1
130 LET p=1
140 LET b=a
150 DO UNTIL n=0
160    IF MOD(n,2)=1 THEN LET p=MOD(p*b,k)
170    LET n=INT(n/2)
180    LET b=MOD(b*b,k)
190 LOOP
200 IF p<>1 AND k>a THEN PRINT k;"は素数ではない." 
210 END

 このプログラムのよい点(剰余系で計算する利点)は,(k-1)2までの数値が正確に扱えれば済むこと。
 (仮称)十進BASICの十進モードは,数値式の中では16桁を超える精度を持つから,8桁程度までのkについて判定が可能。それより桁数が大きいときは有理数モードを使う。
<注意>多数のa の値に対して素数でないと判定されなかったからといって,素数だと断定できるわけではない。

 
戻る inserted by FC2 system