[已解决]a和b猜拳，谁先胜3局就获胜，有几种情形？

香川群子

输出结果：

局数  过程
3        bbb
4        bbab
5        bbaab
5        bbaaa
4        babb
5        babab
5        babaa
5        baabb
5        baaba
4        baaa
4        abbb
5        abbab
5        abbaa
5        ababb
5        ababa
4        abaa
5        aabbb
5        aabba
4        aaba
3        aaa

香川群子

爱疯 发表于 2016-9-13 18:01
因为我想学习"排列组合的通用方法"，所以问这个。
并不为解决实际的问题，只想来学习。

排列、组合的通用算法，目前没有人超过我。

方法最多。速度最快。

爱疯

  2016-9-14 08:33

'N
Sub test()
    [a1].CurrentRegion = ""
    Call dg("", 2, 0, 0, 0, 0, 0)
End Sub
'
'1s
'2n
'3k
'4a
'5b
'6c
'7
Sub dg(s, n, k, a, b, c, t)
    If a = n Or b = n Or c = n Then
        k = k + 1: Cells(k, 1) = s: Cells(k, 2) = t
    Else
        For i = 1 To 3
            Select Case i
            Case 1
                Call dg(s & "a", n, k, a + 1, b, c, t + 1)  'a
            Case 2
                Call dg(s & "b", n, k, a, b + 1, c, t + 1)  'b
            Case 3
                Call dg(s & "c", n, k, a, b, c + 1, t + 1)  'c
            End Select
        Next
    End If
End Sub






лл
10#32

1kn
棬Щ
棬
е

2бκ鷵Ρ
iffalsetrueΣ

香川群子

爱疯 发表于 2016-9-14 11:18
'N
Sub test()
    [a1].CurrentRegion = ""

呵呵，你这是3人猜拳比胜负吗？
那代码应该这样子：

1. Dim k, n
   
2. Sub test()
   
3.     [a1].CurrentRegion = ""
   
4.     n = 3  'abc3人猜拳、谁先得到3胜则为赢家。
   
5.     k = 0: Call dg("", 0, 0, 0, 0)
   
6. End Sub
   
7. Sub dg(s, a, b, c, t)
   
8.     If a = n Or b = n Or c = n Then k = k + 1: Cells(k, 1) = s: Cells(k, 2) = t: Exit Sub
   
9.     Call dg(s & "a", a + 1, b, c, t + 1)
   
10.     Call dg(s & "b", a, b + 1, c, t + 1)
    
11.     Call dg(s & "c", a, b, c + 1, t + 1)
    
12. End Sub
    

复制代码

香川群子

香川群子 发表于 2016-9-14 08:33
超级简单：

同理，原题目中ab2人比赛的递归部分改成这样更简洁：

1. Dim k, n
   
2. Sub test()
   
3.     [a1].CurrentRegion = ""
   
4.     n = 3  '2人之间比赛、谁先得到3胜即赢下这一局。
   
5.     k = 0: Call dg("", 0, 0, 0)
   
6. End Sub
   
7. 
   
8. Sub dg(s, a, b, t)
   
9.     If a = n Or b = n Then k = k + 1: Cells(k, 1) = s: Cells(k, 2) = t: Exit Sub
   
10.     Call dg(s & "a", a + 1, b, t + 1)
    
11.     Call dg(s & "b", a, b + 1, t + 1)
    
12. End Sub
    

复制代码

显然递归中不需使用循环，更简单更好。

香川群子

【QCW911 想法是怎么来的？常年的积累经验？】

呵呵，当然是经验积累。

我玩递归很熟了。

香川群子

介绍一下递归算法思路的要点：

1. 解决问题的方法简单有规律。
2. 上一步骤的输出解就是下一步骤的输入条件。
3. 存在一个特定的退出条件。（否则陷入死循环）

接下来，就是考虑递归计算过程中、需要递推下去的结果（条件）等参数了。

另外，为了高效处理递归，可以引入循环，或根据条件不同并列多个异参数条件的递归过程。

呵呵。

香川群子

本题目非常符合递归算法过程。

1. 每一步骤的处理很简单，比胜负得到0负、1胜的结果，并统计每个人的累计胜负总数
2. 胜负记录传递到下一步骤
3. 任意1人先达到3胜即可退出递归。

因此，很简单。

小新De和尚头

香川群子 发表于 2016-9-14 08:33
超级简单：

果然是很厉害~~
我的想法跟你相似，但是思路还是你的好~
值得学习

爱疯

想到3个判断题，来学习。


1）递归一定可转换为循环。【  】
只是觉得对，但说不出理由 。。。


2）递归一定可转换成，最外层是 IF 语句的形式。【对】因为看到百度说“当边界条件不满足时，递归前进；当边界条件满足时，递归返回。”
所以，我觉得是递归的思路，决定了最外层是 IF语句的结构（但不一定时最有效的，学习）


2）递归用到的变量，一定可转为参数。【  】
递归做的少，我还有很多不懂，所以不知道。
一方面，为更好阅读和理解，觉得应该尽可能只保留必要的参数。
另一方面，为保持（递归）功能的封装性，觉得变量应尽量封装在方法的内部。
也许是平时几乎不会遇到太复杂情况，所以可任选。