百鸡问题
“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”
一、在不甚思考的情况下(每种鸡都可能有0-100只)凭直觉写出蛮力法求解百鸡问题的基本思路并编程实现，思考该算法复杂度的渐进表达式。
暴力法直接求xyz
#include<iostream>
#include<time.h>
usingnamespace std;
int main()
{
clock_t start_time=clock();
{
int x,y,z;
for(x=0;x<=20;x++){
for(y=0;y<34;y++){
for(z=0;z<=100;z++){
if(x+y+z==100 &&5*x+3*y+z/3==100 && z%3==0)
cout<<“鸡翁有”<<x<<“只，”<<“鸡母有”<<y<<“只，”<<“鸡雏有”<<z<<“只”<<endl;
}
}
}
}
clock_t end_time=clock();
cout<< “Running time is: “<<static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000<<“ms”<<endl;//输出运行时间
return 0;
}
该算法的时间复杂度为T(n)=O(n^3)
二、缩小三种鸡数量可能的范围，优化算法，减少计算量，此时算法复杂度是否减少？
先确定z的数量，去掉一个for循环
#include<iostream>
#include<time.h>
usingnamespace std;
int main()
{
clock_t start_time=clock();
{
int x,y,z;
for(x=0;x<=20;x++){
for(y=0;y<34;y++){
z=100-x-y;
if(5*x+3*y+z/3==100 &&z%3==0)
cout<<“鸡翁有”<<x<<“只，”<<“鸡母有”<<y<<“只，”<<“鸡雏有”<<z<<“只”<<endl;
}
}
}
clock_t end_time=clock();
cout<< “Running time is:”<<static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000<<“ms”<<endl;//输出运行时间
return 0;
}
该算法的时间复杂度减少为T(n)=O(n^2)
三、进一步优化算法，能否降低算法的复杂度？请写出思路并编程实现。
消元法消掉z
#include<iostream>
#include<time.h>
usingnamespace std;
int main()
{
clock_t start_time=clock();
{
intx,y,z;
for(x=0;x<=20;x++){
y=(200-14*x)/8;
z=100-x-y;
if(5*x+3*y+z/3==100 && z%3==0&& x>=0 && y>=0 && z>=0)
cout<<“鸡翁有”<<x<<“只，”<<“鸡母有”<<y<<“只，”<<“鸡雏有”<<z<<“只”<<endl;
}
}
clock_t end_time=clock();
cout<< “Running time is:”<<static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000<<“ms”<<endl;//输出运行时间
return 0;
}
只有一个for循环，该算法的时间复杂度减少为T(n)=O(n)
三段代码的运行截图不再一一展示，可根据需要自行调试。
四、理解时间复杂度
解决百钱百鸡问题，有助于：
-
掌握穷举法（枚举法）的基本思想和实现方法。
-
能够通过分析问题对穷举法（枚举法）进行优化减少解空间的搜索范围。
-
理解算法复杂度的概念，熟悉并体会常见的时间复杂度。