算法题--百钱白鸡

古代数学家 张丘建 算经 百钱百鸡
题目：公鸡5钱一只 母鸡3钱一只 小鸡1钱三只 现在需要用百钱买百鸡
100 买公鸡 20只
100 买母鸡 33只
100 买小鸡 100只

最暴力算法

func main() {
    count := 0
    for i := 0; i <= 20; i++ {
        for j := 0; j <= 33; j++ {
            for k := 0; k <= 100; k++ {
                count++
                if k%3 == 0 && i+j+k == 100 && i*5+j*3+k/3 == 100 {
                    fmt.Println("公鸡：", i, "母鸡：", j, "小鸡：", k)
                }
            }
        }
    }
    fmt.Println(count) //72114
}

优化一：
小鸡必须为3的倍数，所以k的步长可以改为3

func main() {
    count := 0
    for i := 0; i <= 20; i++ {
        for j := 0; j <= 33; j++ {
            for k := 0; k <= 100; k += 3 {
                count++
                if i+j+k == 100 && i*5+j*3+k/3 == 100 {
                    fmt.Println("公鸡：", i, "母鸡：", j, "小鸡：", k)
                }
            }
        }
    }
    fmt.Println(count) //24276
}

优化二：
当知道了公鸡和母鸡的只数后，小鸡的只数可以算出来（100 - i - j)，因此可以去掉一层for循环

func main() {
    count := 0
    for i := 0; i <= 20; i++ {
        for j := 0; j <= 33; j++ {
            count++
            //小鸡个数 100-公鸡-母鸡
            k := 100 - i - j
            if k%3 == 0 && i*5+j*3+k/3 == 100 {
                fmt.Println("公鸡：", i, "母鸡：", j, "小鸡：", k)
            }
        }
    }
    fmt.Println(count) //714
}

优化三：
母鸡和小鸡都跟3有关系，所以公鸡只能为2的倍数

func main() {
    count := 0
    for i := 0; i <= 20; i += 2 {
        for j := 0; j <= 33; j++ {
            count++
            //小鸡个数 100-公鸡-母鸡
            k := 100 - i - j
            if k%3 == 0 && i*5+j*3+k/3 == 100 {
                fmt.Println("公鸡：", i, "母鸡：", j, "小鸡：", k)
            }
        }
    }
    fmt.Println(count) //374
}