覆面算、再考

 投稿者：山中和義  投稿日：2009年 9月 7日(月)11時18分38秒
  一般にｒ個の変数にｎ個の数を割り当てる「場合の数」は、perm(n,r)通り。
したがって、高々perm(10,10)=10!通りを検証すればよいことになるが、、、
実際、現状のパソコンでは負荷になるものでもない。
また、一度解答できればプログラムもそれっきりになる。（one write）

論理的要素を一部考慮して、
枝刈りをすること（バックトラック法）で「場合の数」を減らすことができる。

●アルゴリズムの概要
加算は、一の位から順に計算していくので、異なる文字を一の位から順に割り付ける。

一の位（E+O+R=N）を算出するには、
a(i):1234xxxxxx
c$="EORNWUTVFS"
まで数が埋まっていればよい。

そこで MOD(1+2+3,10)=4 ？ を確認して、不成立ならxxxxxxはどう組替えてもこの「順列」は成立しない。
したがって、6!（xの数）通りは検証する必要がないことになる。

一つ下の位が成立したなら上の位で同じことを行う。
!覆面算（nPr順列＋枝狩り）

DECLARE EXTERNAL SUB F.perm !外部手続き、変数を宣言する
DECLARE EXTERNAL NUMERIC F.ANSWER_COUNT

LET t0=TIME

CALL perm(0, 1) !キャリーは０、一の位から
IF ANSWER_COUNT=0 THEN PRINT "解なし"

PRINT "計算時間=";TIME-t0

END


MODULE F

SHARE STRING c$

!　 ONE ↓※一の位からa()に順に割り付ける
!   TWO ↓
!+ FOUR ↓
!------
! SEVEN ↓
LET c$="EORNWUTVFS" !異なる文字　←←←←←　※差し替え

IF LEN(c$)>10 THEN
   PRINT "指定できる文字は１０文字以内です。"
   STOP
END IF

SHARE NUMERIC a(10) !文字に設定した数値（０～９）
MAT a=ZER(LEN(c$)) !文字数と同数に調整する

SHARE NUMERIC f(0 TO 9) !文字に割り当てる数（０～９）フラグ用　※
MAT f=ZER

PUBLIC NUMERIC ANSWER_COUNT !解答数
LET ANSWER_COUNT=0


EXTERNAL FUNCTION fnVAL(w$) !文字表現の数を数値に換える
   LET v=0
   FOR i=1 TO LEN(w$)
      LET p=POS(c$,w$(i:i))
      LET v=v*10+a(p)
   NEXT i
   LET fnVAL=v
END FUNCTION

PUBLIC SUB perm
EXTERNAL SUB perm(cy, L) !nPr順列での数の組を生成する
   FOR nm=LBOUND(f) TO UBOUND(f) !重複を避けて、０～９の数字を割り当てる
      IF f(nm)=0 THEN
         LET f(nm)=1 !使用中フラグをONにする

         LET a(L)=nm !L番目を数nmとする

         !----- ↓↓↓↓↓ -----　※差し替え
         SELECT CASE c$(L:L)
         CASE "N" !一の位を確認する
            LET k=fnVAL("E")+fnVAL("O")+fnVAL("R")
            IF MOD(k,10)=fnVAL("N") THEN
               CALL perm(INT(k/10), L+1)
            END IF
         CASE "U" !十の位を確認する
            LET k=fnVAL("N")+fnVAL("W")+fnVAL("U") + cy
            IF MOD(k,10)=fnVAL("E") THEN
               CALL perm(INT(k/10), L+1)
            END IF
         CASE "V" !百の位を確認する
            LET k=fnVAL("O")+fnVAL("T")+fnVAL("O") + cy
            IF fnVAL("O")>0 AND fnVAL("T")>0 AND MOD(k,10)=fnVAL("V") THEN
               CALL perm(INT(k/10), L+1)
            END IF
         CASE "S" !万と千の位を確認する
            LET k=fnVAL("F") + cy
            IF fnVAL("F")>0 AND fnVAL("S")>0 AND k=fnVAL("SE") THEN

               LET ANSWER_COUNT=ANSWER_COUNT+1 !解答数
               PRINT ANSWER_COUNT

               PRINT USING "    ONE   ####":fnVAL("ONE") !結果の表示
               PRINT USING "    TWO   ####":fnVAL("TWO")
               PRINT USING "＋ FOUR   ####":fnVAL("FOUR")
               PRINT "-------"
               PRINT USING "  SEVEN  #####":fnVAL("SEVEN")
               PRINT

               !STOP !１つだけならコメントをはずす
            END IF
         CASE ELSE
            IF L<LEN(c$) THEN CALL perm((cy), L+1) !次の文字へ　※cyは値渡し
         END SELECT
         !----- ↑↑↑↑↑ -----

         LET f(nm)=0 !未使用
      END IF
   NEXT nm
END SUB

END MODULE
 

戻る