'****************************************************************************************
'10を作る_分数版.xls
'-----------------------------------------------
'プロトタイプとの違い
'　分数で計算
'　答を保存しておき,文字列として同じものを排除
'                             2000.12.31
'  分数の除算のバグを取る     2001.1.4
'-----------------------------------------------
' "Bit" 1999.11月号, ナノピコ教室｢最も遊びがいのある数は？｣掲載
'綾木健一郎氏のプログラム"quad.c"で使われた
'4つの数に対して再帰呼び出しを使って演算を施していくアルゴリズムを採用.
'オリジナルは｢最もたくさんの正の整数を作ることができる４個の数字の組み合わせを求める｣ものである。
'この再帰関数を10を作る計算に援用した.
'****************************************************************************************
'----------分数型を定義--------------------------
Type FRACTION
        nominator As Long       '分子
        denominator As Long     '分母
End Type
'----------記録型を定義--------------------------
Type RECORD
    a As FRACTION               '第1項
    b As FRACTION               '第2項
    operation As Long           '演算
End Type
'----------定数----------------------------------
Const OFF = 0
Const MAX = 1000
Const CHECKOFF = "0"
'----------グローバル変数------------------------
Dim answer(MAX) As String
'------------------------------------------------

Sub main()
    Dim num(0 To 3) As FRACTION
    Dim result(0 To 4) As RECORD
    Dim status As Boolean
    Dim i As Long, line As Long
    
    '----------初期化----------------------------
    For i = 0 To 3 Step 1           'セルから初期値の入力
        num(i).nominator = Cells(i + 1, 3).Value
        num(i).denominator = 1
    Next i
    For i = 0 To 4                  '記録の初期化
        result(i).a.nominator = OFF
        result(i).a.denominator = OFF
        result(i).b.nominator = OFF
        result(i).b.denominator = OFF
        result(i).operation = OFF
    Next i
    For i = 0 To MAX Step 1         '答を初期化.　null文字が配列の終わりの番兵として使われる
        answer(i) = ""
    Next i
    '--------------------------------------------
    status = False                  '答がなかった場合を検出するための状態をセット
    
    Call calc_num(num(), 4, result(), status)       '計算の呼び出し
    
    If (status = False) Then                        '計算終了後のチェック.答がなかった場合
        Cells(6, 1).Value = "１０はできませんでした。"
    Else                                            '答があった場合.同じ答を排除.
        i = 0                                       '配列を一つずつ取り
        Do
            j = i + 1                               '後ろの配列と比較して同じならCHCKOFFをつける.
            Do
                If (answer(j) = answer(i)) Then     'answer(j)がCHECKOFFであっても,CHECKOFFにマッチして
                    answer(j) = CHECKOFF            'CHECKOFFをつけるだけなので,誤判断にはならない.
                End If
                j = j + 1
            Loop While (answer(j) <> "")            '配列の終わりに達した
            i = i + 1
        Loop While (answer(i) <> "")                '配列の終わりに達した
        i = 0           '配列をなめるための変数
        line = 0        'セルに表示するための変数
        Do
            If (answer(i) <> CHECKOFF) Then         'ユニークな答として残ったものだけを表示
                line = line + 1
                Cells(line + 5, 1).Value = answer(i)
            End If
            i = i + 1
        Loop While (answer(i) <> "")
    End If
        
    End     'END文がないと,enter_result()中のstatic変数が初期化されず,続けて実行する場合に変調をきたす.
End Sub

'-----------------------------------------------------------------------
'与えられた項数が1項なら,10ができたかどうか判定して,10ができていれば登録する.
'項数が2項以上ならば,四則計算を行って項の数を減らす.
'-----------------------------------------------------------------------
Sub calc_num(num() As FRACTION, num_count As Long, result() As RECORD, status As Boolean)
    Dim my_num(0 To 3) As FRACTION          '再帰呼び出しのために,ローカルなnum()を作る
    Dim i As Long, j As Long, k As Long, g As Long
    
    If (num_count = 1) Then
        If (num(0).denominator = 0) Then    '分母が0はダメ
            Exit Sub
        ElseIf ((num(0).nominator Mod num(0).denominator) <> 0) Then    '割り切れないものはダメ
            Exit Sub
        ElseIf ((num(0).nominator \ num(0).denominator) = 10) Then      '10ができた.
            Call enter_result(result())
            status = True       '10ができた場合は, statusはTRUEになる.
        End If
    Else
        For i = 0 To num_count - 1 Step 1
            For j = 1 To num_count - 1 Step 1
                If (i <> j) Then                            'i<>j であるnum(i), num(j)を選んで演算し,項の数を減らす.
                    g = 0
                    For k = 0 To num_count - 1 Step 1
                        If ((k <> i) And (k <> j)) Then     'それ以外の項はそのままコピーする
                            my_num(g) = num(k)
                            g = g + 1
                        End If
                    Next k
                    '再帰呼び出しに入る前に記録を残す
                    result(num_count).a.nominator = num(i).nominator
                    result(num_count).a.denominator = num(i).denominator
                    result(num_count).b.nominator = num(j).nominator
                    result(num_count).b.denominator = num(j).denominator
                    '----------------------------------------------------
                    '加減乗算の分母の計算
                    my_num(g).denominator = num(i).denominator * num(j).denominator
                    
                    '加算
                    my_num(g).nominator = num(i).nominator * num(j).denominator + num(j).nominator * num(i).denominator
                    result(num_count).operation = 1
                    Call calc_num(my_num(), num_count - 1, result(), status)
                    
                    '減算
                    my_num(g).nominator = num(i).nominator * num(j).denominator - num(j).nominator * num(i).denominator
                    result(num_count).operation = 2
                    Call calc_num(my_num(), num_count - 1, result(), status)
                    
                    '項を交換して減算
                    my_num(g).nominator = -my_num(g).nominator
                    result(num_count).operation = 3
                    Call calc_num(my_num(), num_count - 1, result(), status)
                    
                    '乗算
                    my_num(g).nominator = num(i).nominator * num(j).nominator
                    result(num_count).operation = 4
                    Call calc_num(my_num(), num_count - 1, result(), status)
                    
                    '除算の分母の計算
                    my_num(g).denominator = num(i).denominator * num(j).nominator
                    '除算
                    If (num(j).denominator <> 0) Then
                        my_num(g).nominator = num(i).nominator * num(j).denominator
                        result(num_count).operation = 5
                        Call calc_num(my_num(), num_count - 1, result(), status)
                    End If
                    
                    '項を交換して除算
                    my_num(g).denominator = num(j).denominator * num(i).nominator
                    If (num(i).denominator <> 0) Then
                        my_num(g).nominator = num(j).nominator * num(i).denominator
                        result(num_count).operation = 6
                        Call calc_num(my_num(), num_count - 1, result(), status)
                    End If
                    '再帰呼び出しから戻ってきたところで記録を消す
                    result(num_count).a.nominator = OFF
                    result(num_count).a.denominator = OFF
                    result(num_count).b.nominator = OFF
                    result(num_count).b.denominator = OFF
                    result(num_count).operation = OFF
                End If
            Next j
        Next i
    End If
End Sub

'------------------------------------------------
'10ができた時の記録を答として文字列に変換して登録する
'------------------------------------------------
Sub enter_result(result() As RECORD)
    Dim i As Long
    Dim m(0 To 4) As RECORD
    Dim op(1 To 6) As String
    Static count As Long    '答の数. static変数は０に初期化される.
    
    op(1) = "＋"
    op(2) = "－"
    op(3) = "－"
    op(4) = "×"
    op(5) = "÷"
    op(6) = "÷"
    
    For i = 4 To 2 Step -1
        '項を交換して演算した場合の処置
        If ((result(i).operation = 3) Or (result(i).operation = 6)) Then
            m(i).a.nominator = result(i).b.nominator
            m(i).a.denominator = result(i).b.denominator
            m(i).b.nominator = result(i).a.nominator
            m(i).b.denominator = result(i).a.denominator
            m(i).operation = result(i).operation
        Else
            m(i) = result(i)    '同じ型同士は一括代入できる
        End If
    Next i
    
    For i = 4 To 2 Step -1
        If (m(i).a.denominator <> 1) Then
            answer(count) = answer(count) + Left(CStr(m(i).a.nominator), 6) + "/" + Left(CStr(m(i).a.denominator), 6)
        Else
            answer(count) = answer(count) + Left(CStr(m(i).a.nominator), 6)
        End If
        answer(count) = answer(count) + "  " + op(m(i).operation) + "  "
        If (m(i).b.denominator <> 1) Then
            answer(count) = answer(count) + Left(CStr(m(i).b.nominator), 6) + "/" + Left(CStr(m(i).b.denominator), 6) + "      "
        Else
            answer(count) = answer(count) + Left(CStr(m(i).b.nominator), 6) + "      "
        End If
    Next i
    count = count + 1

End Sub
Sub clear()
    Columns("A:A").ClearContents
End Sub