前言
枚举,是一种最基本的算法思想,通过穷举枚举出所有的可能,再加以比较。
枚举算法适用于问题规模较小、解空间可穷举的情况。它的优点是简单直观,不需要复杂的数学推导,易于实现。但是,对于问题规模较大的情况,枚举算法的时间复杂度可能会非常高,效率较低。
接下来会介绍两个百钱白鸡的经典问题,解释枚举算法的意义。
题目示例
示例1:百钱白鸡1
题目描述
中国数学家张邱建(公元五世纪,其它资料不详)在他的《算经》中提出了著名的“百钱买百鸡”问题:
鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一。
百钱买百鸡,问翁、母、雏各几何?
你的任务:输出所有可行的方案。
无
输出共有若干行:
每行三个整数,相互之间用1个空格隔开,依次为公鸡、母鸡、小鸡的数量。
所有方案,第一优先级按公鸡的数量从小到大排列。
(无)
(无)
方法1:
推荐指数:⭐
先按照暴力枚举的方法写一个三重循环(位置数有三个,所以是三重循环)
代码:
#include<bits/stdc++.h>
#define in int
using namespace std;
in main()
{
for(in i=0;i<=100;i++)
{
for(in j=0;j<=100;j++)
{
for(in k=0;k<=100;k++)
{
//从所有可能解中找可行解
//常数写前面
if(k%3==0&&100==i+j+k&&100==i*5+j*3+k/3)
{
cout<<i<<" "<<j<<" "<<k<<endl;
}
}
}
}
return 0;
}
提交上去,会发现TLE爆了0分(如果OJ严)
所以,我们还需要简化:
方法2:
推荐指数:⭐⭐
我们可以进行枚举范围的缩减,也就是for循环范围的缩减。根据等式
公鸡+母鸡+小鸡=100
可得出以下范围:
公鸡:0~20
母鸡:0~33
小鸡:0~100//最多买到300只,但题目只让买100只
缩减后代码:
#include<bits/stdc++.h>
#define in int
using namespace std;
in main()
{
for(in i=0;i<=20;i++)
{
for(in j=0;j<=33;j++)
{
for(in k=0;k<=100;k++)
{
if(k%3==0&&100==i+j+k&&100==i*5+j*3+k/3)
{
cout<<i<<" "<<j<<" "<<k<<endl;
}
}
}
}
return 0;
}
成功AC了,但是还可以进一步简化:
方法3:
推荐指数:⭐⭐⭐⭐
三种鸡加起来=100,知二求一,可以省去最内层(其他两层也可以)的求小鸡的循环,通过
100-公鸡-母鸡=小鸡
的等式求出小鸡。
代码:
#include<bits/stdc++.h>
#define in int
using namespace std;
in main()
{
for(in i=0;i<=20;i++)
{
for(in j=0;j<=33;j++)
{
int k=100-i-j; //小鸡
if(k%3==0&&100==i+j+k&&100==i*5+j*3+k/3)
{
cout<<i<<" "<<j<<" "<<k<<endl;
}
}
}
return 0;
}
以上是最优方法
示例2:百钱白鸡2
题目描述
中国数学家张邱建(公元五世纪,其它资料不详),在他的《算经》中提出了著名的“百钱买百鸡”问题:鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一。百钱买百鸡,问翁、母、雏各几何?
你的任务是:根据给定的钱数 m,和买到的鸡数 n ,输出所有的方案。如果没有可行方案,输出 None
。
只有两个整数 m,n(0<m,n<10000)
若干行,每行 3 个数,表示一种可行方案,分别表示鸡翁、鸡母、鸡雏的数量。
100 100
0 25 75
4 18 78
8 11 81
12 4 84
100 10
None
跟百钱白鸡1差不多,只不过加了输入输出。
代码:
#include<bits/stdc++.h>
#define in int
#define bl bool
using namespace std;
in main()
{
in m,n;
bl f=0;
cin>>m>>n;
for(in i=0;i<=n;i++)
{
for(in j=0;j<=n;j++)
{
in k=n-i-j;
if(k%3==0&&n==i+j+k&&m==i*5+j*3+k/3)
{
cout<<i<<" "<<j<<" "<<k<<endl;
f=1;
}
}
}
if(f==0)
{
cout<<"None";
}
return 0;
}
标签:输出,百钱,样例,c++,枚举,白鸡,100 From: https://blog.csdn.net/FHY_pp/article/details/142414646