|
|
四則演算ゲーム
4つの1桁の数に対して、四則（+,-,×,÷）、括弧、べき乗、平方根を使って、
ある数Nを求める式をつくる。
例
1,3,4,6から24を表す計算式は、6÷(1-3÷4)=24 ※難問
●四則演算、括弧、べき乗による場合
通常の式の表現（中置表現）では、括弧の組合せを考えるのは容易ではありません。
この場合は数が４つなので何とかなると思います。
そこで、一部の電卓やプログラム言語の数式処理で採用されている後置表記（逆ポーランド表記）を使ってみます。
後置表記（逆ポーランド表記）による数式
例
(1+2)*3-4 → 12+3*4-
利点
括弧を使わずにすべての式を表現できる。
数式を計算するプログラムが容易に作れる。
場合の数
4つの数の並びは、4!通り
式「12A3B4C」のABCの位置に入る演算子（四則、べき乗）の並びは、5^3通り
式「12A3B4C」のABCの位置に入る演算子の個数 0≦A≦1, 0≦B≦2-A, C=3-(A+B)
これらに注意して、コーディングしてみます。
1000 !四則演算ゲーム
1010 DATA 1,3,4,6 !4つの数
1020 DIM X(4)
1030 MAT READ X
1040
1050
1060 FOR N=0 TO 100 !求める数
1070 !!PRINT "N=";N
1080
1090
1100 DIM idx(4) !参照位置
1110 LET h=0
1120 DO WHILE h<FACT(4) !数字の並びは、4!通り
1130 CALL Num2PermFactorial(h, idx,4)
1140 !!!MAT PRINT idx; !debug
1150
1160
1170 LET OP$="+-*/^" !演算子
1180 LET L=LEN(OP$)
1190
1200 FOR i=0 TO L^3-1 !L進法による「演算子の並び」のパターンを生成する
1210 !!!PRINT i !debug
1220
1230 LET P$="" !演算子の並び
1240 LET t=i
1250 FOR k=1 TO 3 !個数は3個 ※進数変換
1260 LET w=MOD(t,L)+1
1270 LET P$=P$&OP$(w:w)
1280 LET t=INT(t/L)
1290 NEXT k
1300 !!!PRINT P$ !debug
1310
1320 FOR A=0 TO 1 !式「12A3B4C」に入る演算子の個数
1330 FOR B=0 TO 2-A
1340 LET C=3-(A+B) !残り
1350 !!!PRINT A;B;C !debug
1360
1370 !パターンから必要な個数だけ切り出して、式をつくる
1380 LET s$=STR$(X(idx(1))) !1番目の数
1390 LET s$=s$&STR$(X(idx(2))) !2番目の数
1400 LET s$=s$&P$(1:A)
1410 LET s$=s$&STR$(X(idx(3))) !3番目の数
1420 LET s$=s$&P$(1+A:A+B)
1430 LET s$=s$&STR$(X(idx(4))) !4番目の数
1440 LET s$=s$&P$(1+A+B:A+B+C)
1450 !!!PRINT s$ !debug
1460
1470 CALL calc(s$,X, v) !式を計算する
1480 IF ABS(v-N)<=1E-12 THEN !該当するなら、解となる
1490 PRINT s$;"=";v
1500
1510 EXIT DO !※最初に見つかった１つのみ
1520 END IF
1530
1540 NEXT B
1550 NEXT A
1560
1570 NEXT i
1580
1590 LET h=h+1 !次の並びへ
1600 LOOP
1610
1620 NEXT N
1630
1640 END
1650
1660
1670 EXTERNAL SUB calc(s$,X(), v) !後置表記の式を計算する
1680 DIM STK(4) !スタック
1690 LET SP=0 !スタックポインタ
1700 LET v=-99999999 !エラーの場合の値
1710 FOR i=1 TO LEN(s$) !式を計算する
1720 SELECT CASE s$(i:i)
1730 CASE "+","＋" !加算
1740 LET STK(SP-1)=STK(SP-1)+STK(SP)
1750 LET SP=SP-1
1760 CASE "-","－" !減算
1770 LET STK(SP-1)=STK(SP-1)-STK(SP)
1780 LET SP=SP-1
1790 CASE "*","×" !乗算
1800 LET STK(SP-1)=STK(SP-1)*STK(SP)
1810 LET SP=SP-1
1820 CASE "/","÷" !除算
1830 IF STK(SP)=0 THEN EXIT SUB !0による割り算
1840 LET STK(SP-1)=STK(SP-1)/STK(SP)
1850 LET SP=SP-1
1860
1870 CASE "^" !べき乗
1880 IF STK(SP-1)=0 AND STK(SP)<=0 THEN EXIT SUB !0の負数乗、0の0乗
1890 IF STK(SP-1)<0 AND STK(SP)<>INT(STK(SP)) THEN EXIT SUB !負数の非整数乗
1900 WHEN EXCEPTION IN
1910 LET STK(SP-1)=STK(SP-1)^STK(SP)
1920 LET SP=SP-1
1930 USE
1940 EXIT SUB !オーバーフロー、アンダーフロー
1950 END WHEN
1960
1970 CASE "√" !平方根
1980 IF STK(SP)<0 THEN EXIT SUB !負数
1990 LET STK(SP)=SQR(STK(SP))
2000
2010 CASE " "
2020 !nop
2030
2040 CASE IS >="0", IS <="9" !1桁の数値
2050 LET SP=SP+1
2060 LET STK(SP)=VAL(s$(i:i))
2070
2080 CASE ELSE
2090 END SELECT
2100 NEXT i
2110 IF SP<>1 THEN PRINT "error!!!"
2120 LET v=STK(1) !結果
2130 END SUB
2140
2150
2160 EXTERNAL SUB Num2PermFactorial(h, A(),N) !番号から順列パターンを生成する ※辞書式順序
2170 LET v=h !非負の10進数整数を階乗進数へ
2180 FOR j=1 TO N
2190 LET t=INT(v/j)
2200 LET A(N-j+1)=v-t*j +1 !階乗進数の各桁の値＋１ A[1..N]=(N-1)! … 3! 2! 1! 0!
2210 LET v=t
2220 NEXT j
2230 FOR j=N-1 TO 1 STEP -1 !順列パターンへ
2240 FOR k=j+1 TO N
2250 IF A(k)>=A(j) THEN LET A(k)=A(k)+1
2260 NEXT k
2270 NEXT j
2280 END SUB
●べき乗を含まない場合
1170 LET OP$="+-*/" !演算子
と変更（べき乗演算子を削除）してください。
●平方根を含む場合
式を計算する部分は既に組み込んでいますので、後は式の生成のみです。
同様に、組合せを考えればよいのですが、組合せの階層が増えてプログラムが複雑になります。
そこで、手動で切り抜ける方法を紹介します。
(√1)+2+3+4型
1380 LET s$=STR$(X(idx(1)))&"√" !1番目の数
1390 LET s$=s$&STR$(X(idx(2))) !2番目の数
1400 LET s$=s$&P$(1:A)
1410 LET s$=s$&STR$(X(idx(3))) !3番目の数
1420 LET s$=s$&P$(1+A:A+B)
1430 LET s$=s$&STR$(X(idx(4))) !4番目の数
1440 LET s$=s$&P$(1+A+B:A+B+C)
√(1+2+3)+4型
1380 LET s$=STR$(X(idx(1))) !1番目の数
1390 LET s$=s$&STR$(X(idx(2))) !2番目の数
1400 LET s$=s$&P$(1:A)
1410 LET s$=s$&STR$(X(idx(3))) !3番目の数
1420 LET s$=s$&P$(1+A:A+B)&"√"
1430 LET s$=s$&STR$(X(idx(4))) !4番目の数
1440 LET s$=s$&P$(1+A+B:A+B+C)
のように平方根を各数の後や演算子の後に組み合わせて追加すればよいと思います。
|
|