辞書式配列の問題を十進BASICで解いてみました。(^_^;
と、いうより、Javaから翻訳してみました。(^_^;
ABCDEFの6文字を全て使ってできる順列をABCDEFを1番目として、辞書式に並べる時、次の問いに答えよ。
(1)140番目の文字列を求めよ。
(2)FBCDAEは何番目の文字列か。
場合の数・確率の問題は、検算が難しいため、答えに確信が持てないことが多いですね。(^_^;
● DicPerm1.BAS
OPTION BASE 0 DECLARE EXTERNAL SUB toCharAr DECLARE EXTERNAL SUB Sort DECLARE EXTERNAL SUB genPerm DECLARE EXTERNAL FUNCTION Join$ LET s$="ABCDEF" LET N=LEN(s$) LET R=N DIM p$(N-1) ! 順列生成用 CALL toCharAr(p$,s$) ! //--- (1) ---// LET tm=TIME ! Timer Start CALL Sort(p$,0,N-1) ! 念のためのソート LET count=0 LET nextPerm=1 DO LET count=count+1 !PRINT Join$(p$) IF count=140 THEN EXIT DO CALL genPerm(p$,N,R,nextPerm) LOOP WHILE nextPerm=1 PRINT "(1)";Join$(p$) PRINT "Runtime :";ROUND(TIME-tm,3);"[sec]" ! //--- (2) ---// LET tm=TIME ! Timer Start CALL Sort(p$,0,N-1) ! 必須のソート LET count=0 LET nextPerm=1 DO LET count=count+1 !PRINT Join$(p$) IF Join$(p$)="FBCDAE" THEN EXIT DO CALL genPerm(p$,N,R,nextPerm) LOOP WHILE nextPerm=1 PRINT "(2)";count;"番目" PRINT "Runtime :";ROUND(TIME-tm,3);"[sec]" END EXTERNAL SUB toCharAr(a$(),s$) LET j=LBOUND(a$) FOR i=1 TO LEN(s$) LET a$(j)=s$(i:i) LET j=j+1 NEXT i END SUB EXTERNAL SUB Sort(a$(),f,t) FOR i = f + 1 TO t FOR j=i TO f+1 STEP -1 IF a$(j-1)<=a$(j) THEN EXIT FOR swap a$(j),a$(j-1) NEXT j NEXT i END SUB EXTERNAL SUB genPerm(p$(),n,r,nextPerm) LET nextPerm=0 IF r<=0 OR n<r THEN EXIT SUB FOR i=r+1 TO n-1 FOR j=i TO r+1 STEP -1 IF p$(j-1)>=p$(j) THEN EXIT FOR swap p$(j),p$(j-1) NEXT j NEXT i FOR i=n-1 TO 1 STEP -1 IF p$(i-1)< p$(i) THEN EXIT FOR NEXT i IF i=0 THEN EXIT SUB FOR j=n-1 TO i+1 STEP -1 IF p$(i-1)< p$(j) THEN EXIT FOR NEXT j swap p$(j),p$(i-1) FOR j=0 TO INT((n-1-i)/2) swap p$(i+j),p$(n-1-j) NEXT j LET nextPerm=1 END SUB EXTERNAL FUNCTION Join$(a$()) LET r$="" FOR i=LBOUND(a$) TO UBOUND(a$) LET r$=r$&a$(i) NEXT i LET Join$=r$ END FUNCTION
●実行結果
(1)BAFCED Runtime : .01 [sec] (2) 633 番目 Runtime : .02 [sec]
※参考URL
●特定の順列を見つける方法
●辞書式配列の問題をJavaで解いてみた。
●同じものを含む順列の問題を十進BASICで解いてみた。