Pascal言語で小町算

質問

Pascal言語で、『１～９の順に数字を並べ、＋、－を補い式を作り、 値が１００になる組み合わせをすべて出力するプログラムを作成せよ（例：12 - 3 - 4 + 5 - 6 + 7 + 89 = 100）。』

という課題が出ました。自分なりに組んでみたのですが、
１２個あると聞いたのに、４個しか出力されません＞＜；

どこが間違っているのかご教授いただけると幸いですっ

-------------------------------------------------------
program KomachiZan(output);
var i,s:integer;
var sign:array[1..9] of integer;
var x,n:longint;

begin
writeln('< 小町算 -Komachi Zan- >');

for i:=1 to 9 do sign[i]:=-1;

repeat
x:=0;
n:=0;
s:=1;

for i:=1 to 9 do begin
if sign[i]=0 then n:=10*n+1
else begin
x:=x+s*n;
s:=sign[i];
n:=i;
end;
end;

x:=x+s*n;

if x=100 then begin
for i:=1 to 9 do begin
if sign[i]=1 then write(' + ')
else if sign[i]=-1 then write(' - ');

write(i);
end;

writeln(' = 100');
end;

i:=9;
s:=sign[i]+1;

while s>1 do begin
sign[i]:=-1;
i:=i-1;
s:=sign[i]+1;
end;

sign[i]:=s;
until sign[1]>=1;
end.
-------------------------------------------------------

回答No.2

nag0720 · ベストアンサー

１箇所だけ間違えています。

if sign[i]=0 then n:=10*n+1
↓
if sign[i]=0 then n:=10*n+i

お礼

ありがとうございます！ちゃんと動くようになりましたー^^！

回答No.1

digh

Pascal は大学時代に学びましたが、細かい文法を忘れてしまいましたので、
ポイントだけ書きたいと思います。
文字数オーバーして全部消えてしまったので書き直しました。
（最後にVB.NETのコードも書いておきました。）

ポイント
１．まず、一番最初の数字の符号は必ず＋だとすると、
　符号が入る場所は全部で 8 箇所あって、下の図のようになります。

　＋1□2□3□4□5□6□7□8□9　…(1)

　（…□の中に符号が入ります）

　１か所につき、３通りの符号（－、符号なし、＋）の入り方があって、それが８カ所あるので、
　符号の入り方は全部で( 3 の 8乗 )通りあります。

２．全てのパターンを走査するために、パターンを表す変数 p を
　for p:=0 to ( 3 の 8 乗) -1 do begin　～ というようにループさせます。
　こうすることで、全てのパターンを漏れなく調べることができます。

　(1)の図の符号部分だけを抜き出して、番号を振ると下の図のようになります。

　　[1][2][3][4][5][6][7][8]　…(2)

　ここで、各箱に入る符号「－」「符号なし」「＋」を
　それぞれ数字「0」「1」「2」で表すことにします。
　こうすることによって、各桁の数が 0 ～ 2 である 8 桁の数、として考えることができます。

３．p の値とパターンの形を結びつける方法。
　例えば、p=0 の時は、00000000 を表していると考えます。
　p=1 の時は、00000001 を表していると考えます。p=2 の時は、00000002 を表しています。
　p=3 の時は、00000003 とはなりません。一つの桁には 0,1,2 のどれかしか入らないので、
　p=3 の時は、00000010 を表していると考えます。
　つまり 3 進数の考え方になります。
　こうやって考えていくと、3 の 8 乗通りの全てのパターンを表せることがわかります。
　p=(3 の 8 乗) -1 の時、22222222 です。

　では、p の値を元にして、パターンの各桁の値（各箱の符号）を求めるためには具体的にどうすればよいでしょうか。
　例えば、一番右の値は、p を 3 で割った時の余りになります。(0,1,2 のどれか）
　右から2番目の値は、（[p を 3 で割った答え]の少数を切り捨てた値）を 3 で割った時の余りです。
　右から3番目の値は、（[p を 3 の 2 乗で割った答え]の少数を切り捨てた値）を 3 で割った時の余りです。
　よって任意の位置、右から k 番目の値は、（[p を 3 の (k-1) 乗で割った答え]の少数を切り捨てた値）を 3 で割った時の余りであるとわかります。

４．以上の方法で、全てのパターンについて、符号の並び方を調べることができます。
　次に考えることは、「符号なし」の時は、隣同士の数字がくっついて一つの数字になる、ということです。このひとまとまりの数字を「項」とします。
　例えば、1 + 2 - 3 と並んでいる場合、項は 1,2,3 の三つですが、
　1 + 2 [符号なし] 3 と並んでいる場合、1 + 23 となるため、項は 1,23 の二つです。

　つまり「＋」か「－」の符号が現れると、項が区切れます。
　各パターン毎に、符号の位置で項を区切り、全ての項を洗い出します。
　そして全ての項と符号を取得したら、各項を符号に従って計算します。
　計算結果が 100 になった場合は、符号を表示します。

ひとまず、上記の前提条件で VB.NET でコーディングすると、
以下のようになります。

|　' 小町算を行う
|
|　For p As Long = 0 To (3 ^ 8) - 1 ' <-- 3 ^ 8 は、3 の 8 乗
|　　' 各パターン毎に処理を行う
|
|　　' 各項の値を保持する配列
|　　Dim kous As New List(Of Long)
|　　kous.Add(1)
|　　' 各項の符号を保持する配列
|　　Dim signs As New List(Of Integer)
|　　signs.Add(2)
|　　' 項の要素数
|　　Dim kx As Integer = 0
|
|　　' 各桁の符号を判断して項目を区切る
|　　For k = 1 To 8
|　　　' k 桁目（ k と k + 1 の間の符号を調べる）
|　　　Dim sign As Integer = Fix(p / Math.Pow(3, k - 1)) Mod 3 ' <-- Pow(3,k-1)は、3 の k-1 乗
|　　　If sign = 1 Then
|　　　　' 符号なしの場合
|　　　　' 今の項目を10倍した後、1 の位の数を k + 1 とする。
|　　　　kous(kx) = kous(kx) * 10 + k + 1
|　　　Else
|　　　　' 符号がある場合
|　　　　' 項の要素数が一つ増える
|　　　　kx += 1
|　　　　' 新たな項として k + 1 を追加する
|　　　　kous.Add(k + 1)
|　　　　' 符号を追加する
|　　　　signs.Add(sign)
|　　　End If
|　　Next k
|
|　　' 100 になるか計算する
|　　Dim x As Long = 0
|　　For i = 0 To kx
|　　　' 各項の値に符号（ 0 はプラス、2 はマイナス）をかけて加算する
|　　　x = x + kous(i) * (signs(i) - 1)
|　　Next i
|　　If x = 100 Then
|　　　' 100 になった場合
|　　　' 符号を表示する
|　　　Dim s As String = ""
|　　　For i = 0 To kx
|　　　　Select Case signs(i)
|　　　　　Case 0
|　　　　　　' マイナス
|　　　　　　s += " - "
|　　　　　Case 1
|　　　　　　' 符号なし
|　　　　　Case 2
|　　　　　　' プラス
|　　　　　　s += " + "
|　　　　End Select
|　　　　s += Str(kous(i))
|　　　Next i
|　　　s += " = 100 !"
|　　　writeline( s ) ' 表示
|　　End If
|
|　Next p

結果は11通りになります。

小町算
+ 1 + 23 - 4 + 5 + 6 + 78 - 9 = 100
+ 123 - 4 - 5 - 6 - 7 + 8 - 9 = 100
+ 123 + 45 - 67 + 8 - 9 = 100
+ 123 + 4 - 5 + 67 - 89 = 100
+ 12 + 3 + 4 + 5 - 6 - 7 + 89 = 100
+ 123 - 45 - 67 + 89 = 100
+ 12 - 3 - 4 + 5 - 6 + 7 + 89 = 100
+ 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100
+ 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
+ 12 + 3 - 4 + 5 + 67 + 8 + 9 = 100
+ 1 + 23 - 4 + 56 + 7 + 8 + 9 = 100

お礼

長文ご教授いただき，ほんとうにありがとうございます！
ただ，私の脳では説明がちんぷんかんぷんでした・・・私の理解能力がないだけです，ごめんなさい＞＜
でも，勉強になりました！