题目分析：
一百铜钱可以买一百只鸡。一只公鸡，5美元，一只母鸡，3美元，3个小的。一百只公鸡，母鸡，鸡，多少只?
分析：
way one：
我们直接三层暴力循环，因为不可能超过100只的同种鸡，那么三层循环，每层100次
PS：时间复杂度太高了，我们需要进一步优化
way two：
由于公鸡5元，那么不可能买20只公鸡，则公鸡循环层为20,同理，母鸡3元，循环层为33，小鸡就使其循环层为100
PS：循环次数下降了不少，但是有没有进一步的优化呢
way three：
我们有这两个方程组：
x+y+z=100------(1) 5x+3y+z/3=100------(2)
消去z后可得：7x+4y=100,进一步得：y=25-7x/4(x可取0,4,8,12)（因为y为整数）
那么，循环只用四次即可
代码如下：
#include <iostream> #include <Windows.h> using namespace std; int main() { LARGE_INTEGER freq, start, end; QueryPerformanceFrequency(&freq); cout << freq.QuadPart << endl; int count; //方法1： QueryPerformanceCounter(&start); count = 0; cout << "方法1：" << endl; for (int cock = 0; cock < 100; cock++) { for (int hen = 0; hen < 100; hen++) { for (int chick = 0; chick < 100; chick += 3) { count++; if (((cock + hen + chick) == 100) && ((5 * cock + 3 * hen + chick / 3) == 100)) { cout << cock << "," << hen << "," << chick << endl; } } } } cout << "Count:" << count << endl; QueryPerformanceCounter(&end); cout << "Duration:" << end.QuadPart - start.QuadPart << endl; //方法2： QueryPerformanceCounter(&start); count = 0; cout << "方法2：" << endl; for (int cock = 0; cock < 20; cock++) { for (int hen = 0; hen < 33; hen++) { for (int chick = 0; chick < 100; chick += 3) { count++; if (((cock + hen + chick) == 100) && ((5 * cock + 3 * hen + chick / 3) == 100)) { cout << cock << "," << hen << "," << chick << endl; } } } } cout << "Count:" << count << endl; QueryPerformanceCounter(&end); cout << "Duration:" << end.QuadPart - start.QuadPart << endl; //方法3： QueryPerformanceCounter(&start); count = 0; cout << "方法3：" << endl; for (int cock = 0; cock < 16; cock += 4) { count++; int hen = 25 - 7 * cock / 4; int chick = 100 - cock - hen; cout << cock << "," << hen << "," << chick << endl; } cout << "Count:" << count << endl; QueryPerformanceCounter(&end); cout << "Duration:" << end.QuadPart - start.QuadPart << endl; cout << endl; }
