数学の部屋へもどる◆東京都 明 さんからの解答
参考で、コメントなしですが手数、手順を求めるためのプログラムを添付します。
（10進ＢＡＳＩＣです。）
DECLARE EXTERNAL SUB serch
DECLARE EXTERNAL SUB proot
DECLARE EXTERNAL FUNCTION fkai
LET N=5
DIM L(N)
DIM R(N)
LET MSN=fkai(N)*(N+1)
DIM ST(MSN,4,0 TO 3)
FOR J=1 TO N
LET L(J)=N-J+1
NEXT J
MAT R=ZER
MAT ST=ZER
LET PN=1
LET ST(1,1,0)=1
DO
LET PN=PN+1
FOR J=1 TO MSN
IF ST(J,1,0)=1 THEN CALL serch(N,MSN,PN,ST,EM)
NEXT J
LOOP UNTIL EM=1
DIM BP(PN-1,2)
LET SN=fkai(N)
LET TC=0
PRINT "手数 : ";PN-1
CALL proot(N,MSN,PN,SN,ST,BP,TC)
PRINT "総数 : ";TC
END
EXTERNAL FUNCTION fkai(X)
LET M=1
FOR J=1 TO X
LET M=M*J
NEXT J
LET fkai=M
END FUNCTION
EXTERNAL SUB proot(N,MSN,PN,SN,ST(,,),BP(,),TC)
LET pPN=PN-1
IF pPN=0 THEN
LET pLC=0
FOR J=1 TO SIZE(BP,1)
LET pLC=MOD(pLC+1,10)
PRINT BP(J,1);"(";BP(J,2);"),";
IF pLC=0 THEN PRINT
NEXT J
PRINT
LET TC=TC+1
EXIT SUB
END IF
FOR J=1 TO 4
IF ST(SN,J,0)<>0 THEN
LET pSN=ST(SN,J,1)
LET BP(pPN,1)=ST(SN,J,2)
LET BP(pPN,2)=ST(SN,J,3)
CALL proot(N,MSN,pPN,pSN,ST,BP,TC)
END IF
NEXT J
END SUB
EXTERNAL SUB decarr(N,L(),R(),SN)
DECLARE EXTERNAL FUNCTION fkai
DIM B(N)
FOR J=1 TO N
LET B(J)=J
NEXT J
MAT L=ZER
MAT R=ZER
LET RN=INT((SN-1)/fkai(N))
LET sSN=MOD((SN-1),fkai(N))+1
FOR J=N-1 TO 1 STEP-1
LET P=N-J
LET BF=B(P)
LET stN=INT((sSN-1)/fkai(J))
IF stN<>0 THEN
LET sSN=MOD((sSN-1),fkai(J))+1
IF RN<>0 THEN
LET BF=B(P+stN)
FOR K=stN TO 1 STEP -1
LET B(P+K)=B(P+K-1)
NEXT K
ELSE
LET BF=B(P+stN)
FOR K=stN TO 1 STEP -1
LET B(P+K)=B(P+K-1)
NEXT K
LET L(N-P+1)=BF
LET B(P)=BF
END IF
END IF
LET B(P)=BF
IF RN<>0 THEN
LET R(P)=BF
LET RN=RN-1
ELSE
LET L(N-P+1)=BF
END IF
NEXT J
IF RN<>0 THEN LET R(N)=B(N) ELSE LET L(1)=B(N)
END SUB
EXTERNAL SUB encarr(N,L(),R(),SN)
DECLARE EXTERNAL FUNCTION fkai
DIM B(N)
LET P=1
LET RN=0
FOR J=1 TO N
IF R(J)=0 THEN EXIT FOR
LET B(P)=R(J)
LET P=P+1
LET RN=RN+1
NEXT J
FOR J=N TO 1 STEP -1
IF L(J)<>0 THEN
LET B(P)=L(J)
LET P=P+1
END IF
NEXT J
LET sSN=0
FOR J=1 TO N-1
LET stN=0
FOR K=J+1 TO N
IF B(J)>B(K) THEN LET stN=stN+1
NEXT K
LET sSN=sSN+stN*fkai(N-J)
NEXT J
LET SN=(sSN+1)+RN*fkai(N)
END SUB
EXTERNAL SUB serch(N,MSN,PN,ST(,,),EM)
DECLARE EXTERNAL SUB encarr
DECLARE EXTERNAL SUB decarr
DECLARE EXTERNAL FUNCTION fkai
DIM sL(N)
DIM sR(N)
DIM L(N)
DIM R(N)
LET EM=0
LET sPN=PN-1
FOR J=1 TO MSN
IF ST(J,1,0)=sPN THEN
CALL decarr(N,L,R,J)
LET sPC=1
DO
MAT sL=L
MAT sR=R
CALL nextp
IF sEM=1 THEN EXIT DO
CALL encarr(N,sL,sR,SN)
IF SN=fkai(N) THEN LET EM=1
IF ST(SN,1,0)=0 OR ST(SN,1,0)=PN THEN
FOR K=1 TO 4
IF ST(SN,K,0)=0 THEN
LET ST(SN,K,0)=PN
LET ST(SN,K,1)=J
LET ST(SN,K,2)=MN
LET ST(SN,K,3)=SD
EXIT FOR
END IF
NEXT K
END IF
LOOP
END IF
NEXT J
SUB nextp
LET sEM=0
SELECT CASE sPC
CASE 1
LET sPC=sPC+1
FOR nJ=N TO 2 STEP -1
IF sL(nJ)<>0 THEN
FOR nK=1 TO N-1
IF sR(nK)=0 THEN
LET sR(nK)=sL(nJ-1)
LET sR(nK+1)=sL(nJ)
LET MN=sL(nJ-1)
LET sL(nJ)=0
LET sL(nJ-1)=0
LET SD=2
EXIT SUB
END IF
NEXT nK
END IF
NEXT nJ
CASE 2
LET sPC=sPC+1
FOR nJ=N TO 2 STEP -1
IF sR(nJ)<>0 THEN
FOR nK=1 TO N-1
IF sL(nK)=0 THEN
LET sL(nK)=sR(nJ-1)
LET sL(nK+1)=sR(nJ)
LET MN=sR(nJ-1)
LET sR(nJ)=0
LET sR(nJ-1)=0
LET SD=2
EXIT SUB
END IF
NEXT nK
END IF
NEXT nJ
CASE 3
LET sPC=sPC+1
FOR nJ=N TO 1 STEP -1
IF sL(nJ)<>0 THEN
FOR nK=1 TO N
IF sR(nK)=0 THEN
LET sR(nK)=sL(nJ)
LET MN=sL(nJ)
LET sL(nJ)=0
LET SD=1
EXIT SUB
END IF
NEXT nK
END IF
NEXT nJ
CASE 4
LET sPC=sPC+1
FOR nJ=N TO 1 STEP -1
IF sR(nJ)<>0 THEN
FOR nK=1 TO N
IF sL(nK)=0 THEN
LET sL(nK)=sR(nJ)
LET MN=sR(nJ)
LET sR(nJ)=0
LET SD=1
EXIT SUB
END IF
NEXT nK
END IF
NEXT nJ
CASE 5
LET sEM=1
END SELECT
END SUB
END SUB◆ 問題へもどる
◆ 今週の問題へ