数の長方形問題考察（２）

　数の長方形問題考察（２）を紹介します。

考察（２）

　プログラムによる解の探索を考察する。

●プログラム（NT111.bas）

' << NT111.bas >>
' Tiny Basic
' 数の長方形問題を解くプログラム。
'
Public N:     ' nの値。
Public M:     ' 辺の合計値。
Public R:     ' rの値。
Public COUNT: ' 部分順列の個数。
Public P(10): ' 部分順列を保存する配列
'
' 初期設定。
N=10
R=10
'
Do
  ' 辺の合計値Mの読み込み。
  Read M
  If M <= 0 Then Exit Do
  '
  ' 初期設定。
  COUNT=0
  For I=1 To N: P(I)=I: Next I             
  '                                        
  ' 部分順列の生成。                       
  Call Perm (1)                            
  Print"辺の合計値=";M;"　解の個数：";COUNT            
  Print
Loop
End                                      
'
' 部分順列を生成する手続き。
' Kは部分順列K番目の要素を意味する。
Sub Perm(K)
  If K = 4 Then
    S=P(1)+P(2)+P(3)
    If S <> M Then Exit Sub
    ' 左右に対称の配置を同一視する。。
    If P(1) > P(3) Then Exit Sub
  End If
  '
  If K = 7 Then
    S=P(3)+P(4)+P(5)+P(6)
    If S <> M Then Exit Sub
    ' ④と⑤を交換したものを同一視する。
    If P(4) > P(5) Then Exit Sub
  End If
  '
  If K = 9 Then
    S=P(6)+P(7)+P(8)
    If S <> M Then Exit Sub
    ' 上下に対称の配置を同一視する。。
    If P(2) > P(7) Then Exit Sub
  End If

  If K > R Then
    S=P(8)+P(9)+P(10)+P(1)
    If S <> M Then Exit Sub
    ' ⑨と⑩を交換したものを同一視する。
    If P(9) > P(10) Then Exit Sub
    ' 解の表示。
    COUNT=COUNT+1                                
    Print Using"[##]";COUNT;                     
    ' 長方形の頂点をかっこで囲む。
    For I=1 To R                                 
      If (I = 1) Or (I = 3) or (I = 6) or (I = 8) Then
        Print" (";
      End If             
      Print Using"##";P(I);                      
      If (I = 1) Or (I = 3) or (I = 6) or (I = 8) Then 
         Print")";
      End If              
    Next I                                       
    Print                                        
    Exit Sub
  End If
  '
  ' つぎの位置の要素を指定する。
  For I=K To N
    W=P(K): P(K)=P(I): P(I)=W
    Call Perm(K+1)
    W=P(K): P(K)=P(I): P(I)=W
  Next I
End Sub
'
' データ。
Data 17, 18, 19, 20, 21, 22, 0

実行結果