平方小町算

 投稿者:山中和義  投稿日:2009年11月 5日(木)08時43分58秒
  1~9の数の順列だから、9!通り。これはパソコンでも、あまり無理のない計算回数である。
場合の数を減らして、マシンパワーに頼らない、負荷の少ない処理を検討してみよう。

●平方小町
 □□□^2=□□□□□□  ただし、□は1~9が1個ずつ
LET t0=TIME


DEF fnFIG(x,n)=MOD(INT(x/10^n),10) !n桁目の数を得る ※0:一の位、1:十の位、2:百の位、…

LET N=9 !1~9の数字
LET R=3 !左辺の桁数

DIM P(R),NM(0 TO 9)
FOR i=0 TO perm(N,R)-1
   CALL Num2Perm(i, P,N,R) !左辺を算出する
   LET x=0
   FOR k=1 TO R !ホーナー法
      LET x=x*10+P(k)
   NEXT k

   LET y=x*x !右辺を算出する ※x^2=yより

   MAT NM=ZER !重複していないか確認する
   LET NM(0)=1 !0
   FOR k=1 TO R !左辺側
      LET NM(P(k))=1 !使用中
   NEXT k
   FOR k=0 TO N-R-1 !右辺側
      LET t=fnFIG(y,k)
      IF NM(t)=1 THEN EXIT FOR !重複!
      LET NM(t)=1
   NEXT k
   IF k>N-R-1 THEN PRINT x;"^ 2 =";y !結果を表示する

NEXT i


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

END


EXTERNAL SUB Num2Perm(h, A(),N,R) !番号から順列パターンを生成する ※辞書式順序
LET v=h
FOR j=1 TO R
   LET fac=PERM(N-j,R-j)
   LET t=INT(v/fac)
   LET A(j)=t+1 !1~N
   LET v=v-fac*t
NEXT j
FOR j=R-1 TO 1 STEP -1
   FOR k=j+1 TO R
      IF A(j)<=A(k) THEN LET A(k)=A(k)+1
   NEXT k
NEXT j
END SUB

その他の例
 分数小町
  □□□□/□□□□□=1/○  ただし、□は1~9が1個ずつ、○は2~9

 ヒント 9! → 4!。 分母=○×分子。


●平方小町
 □□□□□□□□□=○○○○○^2  ただし、□は1~9が1個ずつ、○は0~9
LET t0=TIME


DEF fnFIG(x,n)=MOD(INT(x/10^n),10) !n桁目の数を得る ※0:一の位、1:十の位、2:百の位、…

LET N=9 !1~9の数字

DIM NM(0 TO 9)
FOR i=INT(SQR(123456789)) TO INT(SQR(987654321))
   LET x=i*i !右辺を算出する ※x=i^2より

   MAT NM=ZER !重複していないか確認する
   LET NM(0)=1
   FOR k=1 TO N !左辺側
      LET t=fnFIG(x,k-1)
      IF NM(t)=1 THEN EXIT FOR !重複!
      LET NM(t)=1
   NEXT k
   IF k>N THEN PRINT x;"=";i;"^ 2" !結果を表示する

NEXT i


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

END
 

戻る