7. 算法-枚举法√
发布时间:
一、什么是枚举(穷举)
枚举:列举所有的可能的数据,判断哪些数满足条件!
为什么会有穷举算法:因为有些情况我们无法通过数据规则或者直接计算得到答案,需要遍历所有可能并判断是否符合要求的处理方法
想一想,输出下列最小值,哪个需要用到穷举:
有序数组:[1,2,3,4,5,6,7,8,9]
无序数组:[8,6,4,8,2,1,3,9,7]
二、单循环穷举
【例1】 鸡兔同笼问题
思路:循环鸡,得到兔子数,核对总脚数
for(鸡的只数范围i = 1~34){
如果(有 i 只鸡, 有 35-i只兔, 腿的总数满足 94){
输出鸡和兔的只数;
}
}
鸡 | 兔 | 判断腿数 |
---|---|---|
1 | 34 | 1 * 2+34 * 4==94 |
2 | 33 | 2 * 2+33 * 4==94 |
3 | 32 | 3 * 2+32 * 4==94 |
... |
#include <iostream>
using namespace std;
int main(){
int i;//鸡的只数
//循环鸡可能的只数范围
for(i = 1;i <= 34;i++){
//i只鸡, 有35-i只兔, 判断总腿数是否为94
if(i * 2 + (35 - i) * 4 == 94){
cout<<i<<" "<<35 - i;
}
}
}
【例2】买公园门票
思路:循环成人,核对剩余钱是否刚好购买儿童票。
for(成人i=1;i<=最大成人数){//最大成人数即总钱数去掉一个儿童的再除8元
//得到剩余钱数,能整除3则符合
}
穷举方法:
成人人数 | 剩余金额 | 方案是否可行? |
---|---|---|
1 | 40-1*8=32 | 32不是3的倍数, 不可行 |
2 | 40-2*8=24 | 24是3的倍数, 可行 |
... |
#include <iostream>
using namespace std;
int main(){
/*成人票8元/张,儿童票3元/张 成人和儿童都有 共花了 40元
思路:
i = 循环成人票可能的范围1 ~ (40-3) / 8
买了 i张成人票的情况下,剩余的钱必须是儿童票单价的倍数
*/
//i代表成人票的购买数量,x代表买了i张成人票剩余的金额
int i,x;
//成人票最少1张,最多(40-3)/8张(因为至少留下买1张儿童票的钱)
for(i = 1;i <= (40 - 3) / 8;i++){
//计算剩余金额
x = 40 - i * 8;
if(x % 3 == 0){
cout<<i<<" "<<x / 3;
}
}
}
【例3】 买小猫小狗
思路:循环小狗数,核对剩余钱是否刚好买小猫。
for(小狗数量){ //从1到至少一个猫的数量大小,最大总钱数减去一只小猫的钱数/狗的单价
//判断剩下的钱是不是刚好买小猫,是则方案+1
}
#include <iostream>
using namespace std;
int main(){
/*
共x元,小狗a元/只,小猫b元/只
至少猫狗各一,正好用完
*/
int x,a,b,y,i;//y代表买了i只小狗剩余的钱
int c = 0;//计数的变量(count)
cin>>x>>a>>b;
//循环小狗可能的只数范围
for(i = 1;i <= (x - b) / a;i++){
//计算买了 i只小狗剩余的金额
y = x - i * a;
//如果剩余的金额是小猫单价的倍数,则方案成立
if(y % b == 0){
//cout<<i<<" "<<y / b<<endl;
c = c + 1;
}
}
cout << c << endl;
}
【例4】阿凡提的难题
条件一:钱要花完
条件二:两种碗都要买
条件三:两种碗的数量都得是偶数
思路:循环大碗数,核对剩余钱是否刚好买小碗以及小碗数量是否是偶数
都是偶数,那循环得从2开始,递增也是+2
for(大碗数量){//范围是小于至少2只小碗,即(总钱数-小碗数量*小碗单价)/大碗单价
//看下剩余钱数刚好够买小碗,再看小碗数量是否为偶数,符合则输出
}
#include <iostream>
using namespace std;
int main(){
//花完所有的钱,两种碗都要买,两种碗的数量都是偶数
//n:阿凡提的总金额,x代表买了i 只大碗剩余的钱
int n,a,b,x,i;
cin>>n>>a>>b;
//循环大碗可能的只数范围(1~(n-2*b)/a)
for(i = 2;i <= (n - 2 * b) / a;i = i + 2){
//计算买了 i只大碗剩余的钱
x = n - i * a;
//如果剩余的钱是小碗单价的倍数,且买到小碗的数量是偶数
if(x% b == 0 && x / b % 2 == 0){
cout<<i<<" "<<x / b<<endl;
}
}
}
三、可选作业
植树的人数 | 开学大采购 | 恐龙园买玩具 | 买糕点 |
---|
四、嵌套循环穷举
【例5】 百钱买百鸡
我国古代数学家张丘建在《算经》中提出了著名的“百钱百鸡问题”:“鸡翁一,值钱五;鸡母一,值钱三;鸡雏三,值钱一;百钱买百鸡,翁、母、雏各几何?”意思是说:一只公鸡卖5枚钱,一只母鸡卖3枚钱,三只小鸡卖1枚钱,用100枚钱买100只鸡,能买到公鸡、母鸡、小鸡各多少只?
思路:循环公鸡,再循环母鸡,得到小鸡数,核对总数是否为100
for(公鸡i = 1;小于100块买母鸡和小鸡后的数量;公鸡++){//100刨去一只母鸡和一只小鸡的/公鸡单价
//买公鸡剩余的钱知道了,这里再继续分母鸡和小鸡的情况
for(母鸡j = 1;小于母鸡最多数量;公鸡++){//剩余钱刨去一只小鸡的/母鸡单价
//又买母鸡剩余钱也知道了,判断总数量是否等于100
i只公鸡+j只母鸡+小鸡为剩余钱*3 =100就输出
}
#include <bits/stdc++.h>
using namespace std;
int main(){
int i,j,x,y;
//公鸡可能的只数范围
for(i = 1;i <= (100 - 3 - 1) / 5;i++){
x = 100 - i * 5;//买完公鸡剩余的钱
//循环x元能买到的母鸡的范围
for(j = 1;j <= (x - 1) / 3;j++){
y = x - j * 3;//买完i 只公鸡, j 只母鸡剩余的钱
//如果够100只
if(i + j + y * 3 == 100){
cout<<i<<" "<<j<<" "<<y * 3<<endl;
}
}
}
}
六、课堂练习
【例6】 兑换硬币题
思路:循环1分,再循环2分,核对剩余钱是否刚好兑换5分
for(1分的开始循环,数量限制刨去至少要有的2分和5分的){
//剩余的钱得到了
for(2分的开始循环;数量限制剩余的钱刨去至少的一个5分的){
//剩余的钱又得到了
判断是否能刚好兑换5分的,符合即统计
}
}
#include <iostream>
using namespace std;
int main(){
/*
一张一元票换1分、2分和5分的硬币,
每种至少一枚,问有几种换法?
1元 = 10角 = 100分
循环1分可能的数量范围,用剩余的钱去换2分(循环2分数量范围)
*/
int i,j,x,y;
int c = 0;//计数器
//循环1分可能的数量范围
for(i = 1;i <= 100 - 2 - 5;i++){
//换完1分剩余的钱
x = 100 - i;
//用x分去换2分
for(j = 1;j <= (x- 5) / 2;j++){
//计算换完1分和2分剩余的钱
y = x - j * 2;
//用y分去换5分
if(y % 5 == 0){
c++;
}
}
}
cout<<c<<endl;
}
【例7】 购买文具
思路:循环圆珠笔,再循环铅笔,核对总数是否大于30 for(圆珠笔){ //得到剩余钱 for(铅笔){ //得到剩余钱 //判断所有数量是否>30 } }
#include <iostream>
using namespace std;
int main(){
/*
N元钱 每样至少买一支 总数要超过30支 而且钱要全部花完
圆珠笔8角钱一支、铅笔2角钱一支、铅笔芯1角钱一支
*/
int n,i,j,x,y;
int c = 0;//方案总数
cin>>n;
n=n*10;//将单位元换算为角//循环圆珠笔可能的购头数量范围
//将单位元换算为角
//循环圆珠笔可能的购头数量范围
for(i=1;i<=(n-2-1)/8;i++){
//计算买完圆珠笔剩余的钱
x=n-i*8;
//用x角去购买铅笔
for(j=1;j<=(x-1)/2;j++){
//计算买完圆珠笔和铅笔剩余的钱
y=x-j*2;
//如果圆珠笔+铅笔+铅笔芯总数超过30支、
if(i +j+y> 30){
c++;
}
}
}
cout<<c<<endl;
}
七、作业
搬砖问题 | 马克思手稿的问题 | 桐桐的计算 | 怎样种树? | 桐桐去购物 |
---|
八、规律类穷举
四个人的年龄求解 | 姐妹数对 | 纸盒的最大体积是多少? |
---|
九、可选作业
【基础】回文数 | 【入门】一个六位数 |
---|