Skip to content

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){
   输出鸡和兔的只数;
  }
}

判断腿数
1341 * 2+34 * 4==94
2332 * 2+33 * 4==94
3323 * 2+32 * 4==94
...
js

#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则符合
}

穷举方法:

成人人数剩余金额方案是否可行?
140-1*8=3232不是3的倍数, 不可行
240-2*8=2424是3的倍数, 可行
...
js
#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
}

js
#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只小碗,即(总钱数-小碗数量*小碗单价)/大碗单价
   //看下剩余钱数刚好够买小碗,再看小碗数量是否为偶数,符合则输出
  }

js
#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就输出
}

js
#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分的,符合即统计
  }
}

js
#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   } }

js
#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;
}
   

七、作业

搬砖问题马克思手稿的问题桐桐的计算怎样种树?桐桐去购物

八、规律类穷举

四个人的年龄求解 姐妹数对纸盒的最大体积是多少?

九、可选作业

【基础】回文数 【入门】一个六位数