百钱百鸡问题算法(2) 百钱百鸡算法描述

找到原题答案：

今有鸡翁一，值钱伍；鸡母一，值钱三；鸡鶵三，值钱一。凡百钱买鸡百只，问鸡翁、母、鶵各几何？

答曰：鸡翁四，值钱二十；鸡母十八，值钱五十四；鸡鶵七十八，值钱二十六。

又答：鸡翁八，值钱四十；鸡 母十一，值钱三十三，鸡鶵八十一，值钱二十七。

又答：鸡翁十二，值钱六十；鸡母四、值钱十二；鸡鶵八十 四，值钱二十八。”

以上答案与我上期解答完全一致。

算法优化：

       Dim watch As New Diagnostics.Stopwatch
        watch.Start()     '启动
        Dim m, n, a, b, c As Integer
        For a = 0 To 19
            For b = 0 To 33
                c = 100 - a - b
                m = 5 * a + 3 * b + c / 3
                n = a + b + c
                If (m = 100) And (n = 100) Then
                    TextBox1.Text = TextBox1.Text + String.Format("a={0},b={1},c={2},钱数={3},鸡数={4}", a, b, c, m, n) + vbCrLf
                End If

            Next
        Next

        watch.Stop()
        TextBox1.Text = TextBox1.Text + String.Format("用时{0}毫秒", watch.Elapsed.TotalMilliseconds)
    End Sub

因为a最大不超过100/5＝19

b最大不超过100/3=33

只要限制了a,b的最大循环次数，第一层循环减少80次，第二层循环减少了67次。

第三层循环完全取消，直接c = 100 - a - b，由a,b计算而来，减少了100次循环

所以总循环由原来的100*100*100＝1000000次，减少为20*33＝660次。

优化前后对比，时间节省非常明显，原来可能要花费27ms,现在只要0.7ms