10日連続投稿になるからといって、調子に乗って枠を確保。
しかし、うっかり今日中には間に合わなそうで、アドベントカレンダーに数日後に投稿したい記事を書くのに時間を使いすぎてしまう。
まだ今日の分を書いてないじゃないか……
今日の分にしようと思っていたネタを書けてないのに、書くための時間を失ってしまったぞ。
しょうがない、この枠はなんか軽めのネタで埋めよう……何をしよう……
今週分の note は月曜に投稿していて今日投稿する必要は無いが……
そうだ、またなでしこの記事からテーマをパクろう。(クズ)
今回やること
IchigoJam で、n と r を受け取って、nPr と nCr を求める。
※IchigoJamはjig.jpの登録商標です
nPr と nCr の求め方
nPr (n 個から r 個選ぶ順列) は、n 以下の整数を大きい順に r 個掛けることで求めることができる。
nCr (n 個から r 個選ぶ組み合わせ) は、nPr の値を r の階乗 (r!) で割ることで求めることができる。
r の階乗は、正の整数を小さい順に r 個掛けることで求めることができる。
これらは、0 ≦ r ≦ n の場合のみを考える。
また、nP0 = 1、0! = 1 である。(まず 1 があり、そこに条件を満たす数を 0 個掛けると考える)
実装方針
時間が少なくなってしまった中素早く実装するため、今回はマシン語を使わずに簡単に実装できる程度の多倍長演算を行う。
そのために、入力の範囲を 100 未満に制限し、1要素に十進数2桁を格納して計算を行う。
十進数2桁までであれば、32,767 までしか格納できない IchigoJam BASIC の変数でも普通に掛け算や割り算の計算を行うことができる。
入力が 100 未満なので、扱う数は高々 100! までであり、これは 100 の 100 乗より小さい。
よって、IchigoJam の配列の1要素に多倍長整数の1要素を格納することで、オーバーフローせずに計算を行うことができる。
一般の多倍長の掛け算や割り算には手間がかかるが、掛ける数や割る数が1要素の場合は、各桁との掛け算や割り算をしていけばいいだけなので、簡単である。
プログラム
※ DEC$ を使用しているので、DEC$ に対応した環境専用
10 ' nPr & nCr
20 ?"nPr ﾄ nCr ｦ ｹｲｻﾝ ｼﾏｽ"
30 ?"(0 <= r <= n <= 99)"
40 INPUT "n=",N
50 INPUT "r=",R
60 IF !(0<=R AND R<=N AND N<100) ?"ｼﾞｮｳｹﾝ ｦ ﾐﾀｼﾏｾﾝ!":GOTO 40
70 FOR I=0 TO 101:[I]=0:NEXT:[0]=1
80 IF R=0 GOTO 120
90 FOR I=N TO N-R+1 STEP -1
100 C=0:FOR J=0 TO 101:M=[J]*I+C:[J]=M%100:C=M/100:NEXT
110 NEXT
120 ?"nPr=";:GOSUB 190
130 IF R=0 GOTO 170
140 FOR I=1 TO R
150 C=0:FOR J=101 TO 0 STEP -1:M=C*100+[J]:[J]=M/I:C=M%I:NEXT
160 NEXT
170 ?"nCr=";:GOSUB 190
180 END
190 F=0:FOR I=101 TO 0 STEP -1
200 IF F ?DEC$([I]+100,2); ELSE IF [I] F=1:?[I];
210 NEXT:?CHR$(10);:RETURN
実行結果例
↓まずは変な入力をしてみる
↓最大の入力。この環境では約100秒で計算結果が出た
↓r を n-r にしても、nCr の値は変わらないことを確かめる
解説
入力の受け付け
10 ' nPr & nCr
20 ?"nPr ﾄ nCr ｦ ｹｲｻﾝ ｼﾏｽ"
30 ?"(0 <= r <= n <= 99)"
40 INPUT "n=",N
50 INPUT "r=",R
60 IF !(0<=R AND R<=N AND N<100) ?"ｼﾞｮｳｹﾝ ｦ ﾐﾀｼﾏｾﾝ!":GOTO 40
メッセージを出力し、n と r の値の入力を受け付ける。
入力が条件に合わない場合、やり直させる。
順列の計算
70 FOR I=0 TO 101:[I]=0:NEXT:[0]=1
80 IF R=0 GOTO 120
90 FOR I=N TO N-R+1 STEP -1
100 C=0:FOR J=0 TO 101:M=[J]*I+C:[J]=M%100:C=M/100:NEXT
110 NEXT
120 ?"nPr=";:GOSUB 190
多倍長整数を 1 に初期化し、順列の計算を行う。
n から大きい順に掛けていく。
掛け算は、下位から上位へ向かって行う。
計算が完了したら、結果を出力するサブルーチンを呼び出す。
組み合わせの計算
130 IF R=0 GOTO 170
140 FOR I=1 TO R
150 C=0:FOR J=101 TO 0 STEP -1:M=C*100+[J]:[J]=M/I:C=M%I:NEXT
160 NEXT
170 ?"nCr=";:GOSUB 190
180 END
順列の計算結果に対し割り算を行い、組み合わせを計算する。
1 から小さい順に割っていく。
割り算は、上位から下位に向かって行う。
計算が完了したら、再び結果を出力するサブルーチンを呼び出す。
多倍長整数の出力
190 F=0:FOR I=101 TO 0 STEP -1
200 IF F ?DEC$([I]+100,2); ELSE IF [I] F=1:?[I];
210 NEXT:?CHR$(10);:RETURN
上位から下位の順で、各要素を出力する。
上位の 0 ばかりの部分は出力しない。
最初に 0 以外の要素があったら、それをそのまま出力し、「0以外があったフラグ」を立てる。
それ以降、すなわち「0以外があったフラグ」が立っていたら、必要に応じて0埋めして要素を出力する。
おわりに
IchigoJam BASIC で、n が小さい範囲での nPr と nCr の値を計算することができた。
マシン語を使用してより大きい値を扱う乗除算を行うなど、まだ改良の余地は大きそうだ。
そして、進行中の記事や構想中の記事も、しっかり形にしていきたい。