整数の和問題（７）考察

整数の和問題（７）考察を示します。

　整数の和が0となる式をすべて求めるプログラムをTiny Basicで示す。

●プログラム(SW111.bas)

' << SW111.bas >>
' 整数の和が0となる式をすべて求めるプログラム。
'
Public SUM(20): ' SUM(i)は、1～iまでの部分和。
Public C(20):   ' 符号を記憶する配列。
                ' C(i)は、i-1とiの間の符号を意味する。
                ' C(i)=1は"＋"、C(i)=0は"－"。
Public COUNT,N
'
Do
  ' 要素数の読み込み。
  Read N
  If (N <= 0) or (N > 20) Then Exit Do

  ' 初期設定。
  COUNT=0 
  SUM(1)=1
  '
  ' 樹形図の生成。
  Call S(2)
  Print"N=";N;" COUNT=";COUNT
  Print
Loop
End
'
Sub S(K)
  If K > N Then
    If SUM(K-1) = 0 Then
      COUNT=COUNT+1
      Print Using"####: ";COUNT;
      Print"1";
      For I=2 To N
        If C(I) = 0 Then Print"-"; Else Print"+";
        Print I;
      Next I
      Print
    End If
    Exit Sub
  End If
  '
  ' +を指定する場合。
  C(K)=1: SUM(K)=SUM(K-1)+K
  Call S(K+1)
  ' -を指定する場合。
  C(K)=0: SUM(K)=SUM(K-1)-K
  Call S(K+1)
End Sub
'
' データ。
Data 3,4,5,6,7,8,9,10,0

実行結果

1: 1+ 2- 3
N= 3 COUNT= 1

1: 1- 2- 3+ 4
N= 4 COUNT= 1

N= 5 COUNT= 0

N= 6 COUNT= 0

1: 1+ 2- 3+ 4- 5- 6+ 7
2: 1+ 2- 3- 4+ 5+ 6- 7
3: 1- 2+ 3+ 4- 5+ 6- 7
4: 1- 2- 3- 4- 5+ 6+ 7
N= 7 COUNT= 4

1: 1+ 2+ 3+ 4- 5- 6- 7+ 8
2: 1+ 2+ 3- 4+ 5- 6+ 7- 8
3: 1+ 2- 3+ 4+ 5+ 6- 7- 8
4: 1+ 2- 3- 4- 5- 6+ 7+ 8
5: 1- 2+ 3- 4- 5+ 6- 7+ 8
6: 1- 2- 3+ 4+ 5- 6- 7+ 8
7: 1- 2- 3+ 4- 5+ 6+ 7- 8
N= 8 COUNT= 7

N= 9 COUNT= 0

N= 10 COUNT= 0

OK