推荐订阅源

又是一个递归算法

问题:一个射击运动员打靶,靶一共有10环,连开10枪打中90环的可能行有多少种?

以下是解决这个问题的VB.NET代码

Module Module1

    '用来记录每次打几环的数组
    Dim fire(9) As Integer
    '用来记录当前打第几枪
    Dim num As Integer = 0
    '用来记录一共有多少种可能
    Dim count As Integer = 0

    Sub Main()

        '递归求解函数；参数：第num抢
        fireCount(num)
        '打印一共有多少种可能性
        Console.WriteLine("total count:" & count)

    End Sub

    '递归求解函数；参数：第num抢
    Sub fireCount(ByVal num As Integer)

        '当打第num抢的时候，共有11种环数的可能；这里从大到小循环
        For i As Integer = 10 To 0 Step -1
            '记录当前打了几环
            fire(num) = i
            '总环数记录
            Dim total As Integer = 0
            '算一下当前一共打了多少环
            For k As Integer = 0 To num
                total = total + fire(k)
            Next
            '如果剩下的都打10环也到不了90环，那么向下循环就更少了；也没有意义，
            '所以在这里退出函数, 而不是继续向下循环
            If total + (9 - num) * 10 < 90 Then
                '非常重要的，所谓“回溯”，当前的这条数据无法满足条件
                '所以要取消掉
                num = num - 1
                Return
            End If
            '如果打到90环则向外输入
            If total = 90 Then
                count = count + 1
                Console.Write(count & ":")
                '向外输出
                For k As Integer = 0 To 9
                    If k <= num Then
                        Console.Write(">" & fire(k))
                    Else
                        '如果不到10次，则后面的都应该是0环
                        Console.Write(">0")
                    End If
                Next
                Console.WriteLine()
                '继续循环
                Continue For
            End If
            '如果没有打到第10枪，继续递归
            If num < 9 Then
                fireCount(num + 1)
            End If
        Next
    End Sub

End Module

以下是部分输出结果：
1:>10>10>10>10>10>10>10>10>10>0
2:>10>10>10>10>10>10>10>10>9>1
3:>10>10>10>10>10>10>10>10>8>2
4:>10>10>10>10>10>10>10>10>7>3
5:>10>10>10>10>10>10>10>10>6>4
6:>10>10>10>10>10>10>10>10>5>5
7:>10>10>10>10>10>10>10>10>4>6
8:>10>10>10>10>10>10>10>10>3>7
9:>10>10>10>10>10>10>10>10>2>8
10:>10>10>10>10>10>10>10>10>1>9
11:>10>10>10>10>10>10>10>10>0>10

......

92364:>2>9>10>10>10>9>10>10>10>10
92365:>2>9>10>10>9>10>10>10>10>10
92366:>2>9>10>9>10>10>10>10>10>10
92367:>2>9>9>10>10>10>10>10>10>10
92368:>2>8>10>10>10>10>10>10>10>10
92369:>1>10>10>10>10>10>10>10>10>9
92370:>1>10>10>10>10>10>10>10>9>10
92371:>1>10>10>10>10>10>10>9>10>10
92372:>1>10>10>10>10>10>9>10>10>10
92373:>1>10>10>10>10>9>10>10>10>10
92374:>1>10>10>10>9>10>10>10>10>10
92375:>1>10>10>9>10>10>10>10>10>10
92376:>1>10>9>10>10>10>10>10>10>10
92377:>1>9>10>10>10>10>10>10>10>10
92378:>0>10>10>10>10>10>10>10>10>10
total count:92378