学习目标

1. 理解枚举法
2. 使用循环枚举
3. 剪枝优化
   CPU的运算速度

现代计算机可以以极高的速度执行计算任务,从每秒数十亿次到数亿亿次不等。个人电脑处理器(CPU)通常可以完成每秒十亿次运算。高性能的服务器CPU通常可以完成每秒万亿次运算。世界上最强大的超级计算机的运算速度可以达到每秒干万亿次,甚至百亿亿次运算。随着技术的发展而快速变化,处理器的运算能力还在不停提升中。

你会怎么做?

1. 从一盒笔中挑出所有蓝色的笔，准备好所有的笔，将每一支笔拿起来检查，是蓝色的就收起来，不是就放另一边。
2. 忘记行李箱的密码确定所有密码的排列，一个一个试验，箱子打开了,停止试验，否则继续试验

1.枚举法

1. 将问题的所有可能的答案一一列举出来。
2. 根据条件判断此答案是否合适。
3. 合适就保留,不合适就舍弃。

这种思路和方法就是枚举法
因为通过列举所有可能性找到最终答案,枚举法也被称为暴力破解法、蛮力法。

1.1枚举法的特点

1. 简单直观
2. 能够找出问题的所有解
3. 需要消耗大量的时间

1.2枚举的原则:

把所有可能全部列举到,不能有遗漏
循环是最简单的枚举方案

1.3循环枚举

就是使用一重或多重循环枚举所有的情况
简单,粗暴,有效!

循环枚举怎么做?

确定枚举量、枚举范围
用循环实现枚举for循环、while循环、do-while循环
在循环体中进行判断和筛选

1.4小明的密码

小明在某次出国旅行过程中忘记了行李箱的密码,它的行李箱是三位密码锁。小明只记得三位密码之和为19,其中第二位加1等于一三两位之和,第一位的1.5倍等于第三位。请帮助小明找出他的密码。
【输入】无
【输出】一行三个整数,用空格做间隔。

题意理解

程序分析

代码编写

#include<bits/stdc++.h>
using namespace std;
int main()
{
	for(int i=0;i<=9;i++) 
		for(int j=0;j<=9;j++)
			for(int k=0;k<=9;k++)
			{
				if(i+j+k==19 && j+1==i+k &&i*1.5==k)
					cout<<i<<j<<k;
			}
	return 0;
}

1. 确定枚举量、枚举范围
2. 用循环实现枚举
3. 在循环体中进行判断和筛选

代码优化

1.5剪枝优化法

4. 充分利用题目里的关键信息
5. 去掉不必要的分支
6. 提高算法效率

三位密码之和为19

其中第二位加1等于一三两位之和

第一位的1.5倍等于第三位

2.枚举法(小结)

将所有可能的答案一一列举出来再进行判断的方法叫枚举法
要点:

· 要把所有可能全部列举到,不能有遗漏

· 枚举过程中需要进行判断,选出符合条件的组合

枚举法几乎都要使用循环来实现

2.1枚举的意义:

1 可以充分利用计算机的速度
2 常用于解决“是否存在”或“有多少种可能”等问题
3 枚举可作为某类问题时间性能的底线,用来引出同样问题的更高效率的算法

当问题规模变大时,枚举法的执行效率低,最好进行优化。

2.2剪枝优化:

● 通过去掉不必要的分支,优化算法效率,就像我们修剪树木一样
● 是常见的一种算法优化方式

3.硬币面值组合

使用a个1角、b个2角、c个5角硬币组成n角钱。列出所有可能的a,b,c组合
【输入】一个整数n(1 <= n <= 100),代表需要组成的钱的角数。
【输出】输出有若干行。每行的形式为:ia bc。第1列i代表当前行数,从001开始,固定3个字符宽度,宽度不足3的用0填充;后面3列a,b,c分别代表1角、2角、5角硬币的个数(每个数字固定12个字符宽度,宽度不足的在左边填充空格)。

题意理解

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n,i=0;
	cin>>n;
	for(int c=0;c<=n/5;c++)//5角个数
	{
		for(int b=0;b<=n/2;b++)//2角个数
		{
			for(int a=0;a<=n;a++)//11角个数
			{
				if(a+b*2+c*5==n)
				{
					i++;
					printf("%03d%12d%12d%12d\n",i,a,b,c);
				}
					
			}
		}
	}
	return 0;
}

进行优化

输出格式分析

代码编写

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n,i=0,a;
	cin>>n;
	for(int c=0;c<=n/5;c++)
	{
		for(int b=0;b<=(n-c*5)/2;b++)
		{
				a=n-c*5-b*2; //次数 a=(n/5+1)*(n/2+1)*(n+1)
				i++;
				printf("%03d%12d%12d%12d\n",i,a,b,c);	
			
		}
	}
	return 0;
}

4.不吉利日期

在国外,每月的13号和每周的星期五都是不吉利的。特别是当13号那天恰好是星期五时,更不吉利。已知某年的一月一日是星期w,并且这一年一定不是闰年,求出这一年所有13号那天是星期五的月份,按从小到大的顺序输出月份数字。(w=1 … 7)
【输入】输入w,表示一月一日是星期几(w)。
【输出】输出有一到多行,每行一个月份,表示该月的13日是星期五。
【输入用例】7
【输出用例】1
10

确定枚举量、枚举范围

用循环实现枚举

int main()
{
	//1.确定枚举范围（1年365天每一天都进行判断） 
	int w;
	cin>>w;
	//2.用循环实现枚举
	for(int i=1;i<=12;i++) //12个月 
	{
		//这个月总天数d;
		 
		for(int j=1;j<=d;j++)//每一天 
		{
			//进行判断筛选
			w++;//每过一天，星期数w+1; 
		}
	}
	return 0;
}

在循环体中进行判断和筛选

如果是13号并且是星期5,输出月份信息;

int main()
{
	//1.确定枚举范围（1年365天每一天都进行判断） 
	int w;
	cin>>w;
	//2.用循环实现枚举
	for(int i=1;i<=12;i++) //12个月 
	{
		//这个月总天数d;
		 
		for(int j=1;j<=d;j++)//每一天 
		{
			//进行判断筛选
			if(j==13 && w%7==5)
				//输出月份信息 
			w++;//每过一天，星期数w+1; 
		}
	}
	return 0;
}

代码编写

#include<bits/stdc++.h>
using namespace std;
/*int main()
{
	for(int i=0;i<=9;i++) 
		for(int j=0;j<=9;j++)
			for(int k=0;k<=9;k++)
			{
				if(i+j+k==19 && j+1==i+k &&i*1.5==k)
					cout<<i<<j<<k;
			}
	return 0;
}*/
/*int main()
{
	int n,i=0,a;
	cin>>n;
	for(int c=0;c<=n/5;c++)
	{
		for(int b=0;b<=(n-c*5)/2;b++)
		{
				a=n-c*5-b*2; //次数 a=(n/5+1)*(n/2+1)*(n+1)
				i++;
				printf("%03d%12d%12d%12d\n",i,a,b,c);	
			
		}
	}
	return 0;
}*/
int main()
{
	//1.确定枚举范围（1年365天每一天都进行判断） 
	int w,d;
	cin>>w;
	//2.用循环实现枚举
	for(int i=1;i<=12;i++) //12个月 
	{
		//这个月总天数d;
		if(i==1 || i==3 || i==5 || i==7 || i==8 || i==10 || i==12) 
			d=31;
		else if(i==2)
			d=28;
		else
			d=30;
		for(int j=1;j<=d;j++)//每一天 
		{
			//进行判断筛选
			if(j==13 && w%7==5)
				cout<<i<<endl;//输出月份信息 
			w++;//每过一天，星期数w+1; 
		}
	}
	return 0;
}

本次课程的知识点

1. 理解枚举算法的概念
2. 循环枚举的用法
3. 学习用剪枝法优化枚举算法
4. 枚举法的练习:硬币组合、不吉利日期

练一练

交通方式

【编程挑战】小明要从A城市->C城市(必须途径B城市)。已知A市->B市有2种交通工具:“交通工具1”、“交通工具2”,B市->C市有3种交通工具:“交通工具3”、“交通工具4”、“交通工具5”。请你帮小明列出A市->C市的所有交通方式。
【输入】无
【输出】所有可能的交通方式的组合,一行一种组合。
【输出示例】交通工具1+交通工具3
交通工具1+交通工具4
交通工具1+交通工具5
交通工具2+交通工具3
交通工具2+交通工具4
交通工具2+交通工具5

#include<bits/stdc++.h>
using namespace std;

int main()
{
	for(int i=1;i<=2;i++)
		for(int j=3;j<=5;j++)
			cout<<"交通工具"<<i<<"+交通工具"<<j<<endl; 
	return 0;
}