猫史档案馆

hello大家好！半年没有发过教程帖的梓树星辰，我来发教程啦！！！

————————————不咋优美的分界线————————————

众所不周知，做运算作品时运算时间是个重要的东西，所以本帖来教大家优化自己作品的运行时间

也叫算法优化

话不多说直接上题：

百钱买百鸡问题：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？（题目来源：《信息学奥赛一本通（C++版）》配套题库）

这种题我们最容易想到的就是遍历算法

遍历算法：把所有可能性都尝试一遍，找出符合条件的数据

OK直接上代码

//这是C++代码
#include<iostream>
#include<ctime>
using namespace std;
int main()
{
	int a=0,b=0,c=0;//a是鸡翁数，b是鸡母数，c是鸡雏数 
	while (a<=100)//遍历 a的所有可能性
	{
		a++;
		while (b<=100)//遍历 b的所有可能性
		{
			b++;
			while (c<=100)//遍历 c的所有可能性
			{
				c++;
				if (a*5+b*3+c/3.0==100&&a+b+c==100)//用if判断是否符合条件 
					cout<<a<<' '<<b<<' '<<c<<endl;
			}
			c=0;//每次遍历完后将值归零 
		}
		b=0;//每次遍历完后将值归零 
	}
		cout<<"运行用时："<<(double)(1.0*clock()/CLOCKS_PER_SEC)<<"秒";
	return 0;
}

看不懂的看kitten

好，我们看看结果和最重要的运行时间

C++的：

只用了0.011秒

 

kitten的：

23.163秒

同样的代码差距这么大的原因是C++的运行帧率（运行速度）比kitten快得多

 

这种效率，要是数据大了，就要很久才能得出结果

那如何优化？

优化方案：

1.钱只有100，最多买20只鸡翁或33只鸡母，可以减少循环次数

2.我们知道一共有100只鸡，在第二层遍历鸡母的循环里，已知了鸡翁和鸡母的数量，就可以用100-鸡翁-鸡母=鸡雏的数量，就不用遍历鸡雏了。

优化后的代码：

//这是C++代码
#include<iostream>
#include<ctime>
using namespace std;
int main()
{
	int a=0,b=0,c=0;//a是鸡翁数，b是鸡母数，c是鸡雏数 
	while (a<=20)//遍历 a的所有可能性 ，由于钱只有100，最多买20只，只需要遍历20次 
	{
		a++;
		while (b<=33)//遍历 b的所有可能性 ，由于钱只有100，最多买33只，只需要遍历33次 
		{
			b++;
			c=100-a-b;//已知a、b的值，且总数为100，就可以用100-a-b得出c的值 
			if (a*5+b*3+c/3.0==100&&a+b+c==100)//用if判断是否符合条件 
				cout<<a<<' '<<b<<' '<<c<<endl;
		}
		b=0;//每次遍历完后将值归零 
	}
	cout<<"运行用时："<<(double)(1.0*clock()/CLOCKS_PER_SEC)<<"秒";
	return 0;
}

kitten：

运行结果：

C++：

用了0.002秒

 

kitten：

用了0.084秒

 

这就是算法优化的好处和效果

 

 

 

彩蛋：

《千钱买千鸡》

（下面都是优化过的算法哦~）

//这是C++代码
#include<iostream>
#include<ctime>
using namespace std;
int main()
{
	int a=0,b=0,c=0;//a是鸡翁数，b是鸡母数，c是鸡雏数 
	while (a<=200)//遍历 a的所有可能性 ，由于钱只有1000，最多买200只，只需要遍历200次 
	{
		a++;
		while (b<=333)//遍历 b的所有可能性 ，由于钱只有1000，最多买333只，只需要遍历333次 
		{
			b++;
			c=1000-a-b;//已知a、b的值，且总数为1000，就可以用1000-a-b得出c的值 
			if (a*5+b*3+c/3.0==1000&&a+b+c==1000)//用if判断是否符合条件 
				cout<<a<<' '<<b<<' '<<c<<endl;
		}
		b=0;//每次遍历完后将值归零 
	}
	cout<<"运行用时："<<(double)(1.0*clock()/CLOCKS_PER_SEC)<<"秒";
	return 0;
}

 

运行结果：

 

好啦~下课！