小町算(+,-のみ)のトレースです。

質問

小町算(+,-のみ)のトレースです。
宜しくお願いします。

アルゴリズム自体はIPAのソフトウェア開発を取得した時に
類似例をやったのでわかるのですが、設問の意図が分かりずらいです。

(１)プログラムで何種類のs(i)（i=1,2,・・・,9）について調べていますか。

　■１□２□３□４□５□６□７□８□９の小町算で、
　□には＋ならば(1)、空白ならば(0)、－ならば(－1)のいずれかが入る。
　ただし、■だけは＋(1)、空白(0)、に差異がない(例：＋12＝12)ので、
　空白(0)、－(－1)のいずれかが入る。

　下記プログラムを見ると最後から2行目のLOOP WHILE ( s(1) < 1)
　で最後の処理が終わっている。つまりs(1)の配列の中は１に対する■
　の部分であり、s(1)は空白(0)、－(－1)までしか処理されていない。

　こう考えると解答は2^1*3^8である。

　単純に考えると3^9ですが、この場合はどちらが正答なのでしょうか？
　私は2^1*3^8だと思うのですが…

　何と、此処には載せませんが(３)でLOOP WHILE ( s(1) < 1)についての説明を
　求められるのです。出題の順番が間違ってませんか？(１)が正解すれば、(３)
　は考えるまでも無い気がします。

(２)(１)による総当たりを樹形図で示せ。

　2^1*3^8の樹形図を書けとおっしゃるのですか…orz　　無理です。
　とりあえず、■１□２□３にコンパクト化します。(でも最終的に2^1*3^2=18)ですが…

　簡素化して考えて良いのでしょうか？

以下プログラムです

DIM s(9)
FOR i=1 TO 9
LET s(i)=-1
NEXT i
DO
LET SUM=0
LET NUM=0
LET SIGN=1
FOR i=1 TO 9
IF s(i)<>0 THEN
LET SUM=SUM+SIGN*NUM
LET SIGN=s(i)
LET NUM=i
ELSE
LET NUM=10*NUM+i
END IF
NEXT i
LET SUM=SUM+SIGN*NUM
IF SUN=100 THEN
FOR i=1 TO 9
IF s(i)= +1 THEN PRINT" + ";
IF s(i)= -1 THEN PRINT" - ";
PRINT i;
NEXT i
PRINT " = 100"
END IF
LET i=9
LET SIGN=s(i)+1
DO WHILE (SIGN > 1 )
LET s(i)=-1
LET i=i-1
LET SIGN=s(i)+1
LOOP
LET s(i)=SIGN
LOOP WHILE ( s(1) < 1)
END

回答No.1

ShowMeHow · ベストアンサー

アルゴリズムの「ア」も知らない私ですので間違っているかもしれませんが、

DO
　’計算
　’判定
　’印刷
　LET i=9
　LET SIGN=s(i)+1
　DO WHILE (SIGN > 1 )
　　LET s(i)=-1
　　LET i=i-1
　　LET SIGN=s(i)+1
　LOOP
LET s(i)=SIGN
LOOP WHILE ( s(1) < 1)
で繰り返されるループは（書きにくいので「-1」を「-」、「+1」を「+」と書きますが）
---------
--------0
--------+
-------0-
-------00
-------0+
------0--
・・・・
0++++++++
なので、おっしゃるとおり2^1*3^8です。
（なんかマイナスがくっついちゃいますが、意味はわかるでしょうから放って起きます。）
（2）については、設問者の意図はわかりません。

お礼

先ずは書き込み、有難うございます。

(2)に関してですが、一般化して記号のみで3層目まで示して最後に再帰させれば奇麗な樹形図が掛けました。