C++枚举法（一）

学习目标理解枚举法使用循环枚举剪枝优化CPU的运算速度现代计算机可以以极高的速度执行计算任务,从每秒数十亿次到数亿亿次不等。个人电脑处理器(CPU)通常可以完成每秒十亿次运算。高性能的服务器CPU通常可以完成每秒万亿次运算。世界上最强大的超级计算机的运算速度可以达到每秒干万亿次,甚至百亿亿次运算。随着技术的发展而快速变化,处理器的运算能力还在不停提升中。你会怎么做?从一盒笔中挑出所有蓝色的笔准备好所有的笔将每一支笔拿起来检查是蓝色的就收起来不是就放另一边。忘记行李箱的密码确定所有密码的排列一个一个试验箱子打开了,停止试验否则继续试验1.枚举法将问题的所有可能的答案一一列举出来。根据条件判断此答案是否合适。合适就保留,不合适就舍弃。这种思路和方法就是枚举法因为通过列举所有可能性找到最终答案,枚举法也被称为暴力破解法、蛮力法。1.1枚举法的特点简单直观能够找出问题的所有解需要消耗大量的时间1.2枚举的原则:把所有可能全部列举到,不能有遗漏循环是最简单的枚举方案1.3循环枚举就是使用一重或多重循环枚举所有的情况简单,粗暴,有效!循环枚举怎么做?确定枚举量、枚举范围用循环实现枚举for循环、while循环、do-while循环在循环体中进行判断和筛选1.4小明的密码小明在某次出国旅行过程中忘记了行李箱的密码,它的行李箱是三位密码锁。小明只记得三位密码之和为19,其中第二位加1等于一三两位之和,第一位的1.5倍等于第三位。请帮助小明找出他的密码。【输入】无【输出】一行三个整数,用空格做间隔。题意理解程序分析代码编写#includebits/stdc.husingnamespacestd;intmain(){for(inti0;i9;i)for(intj0;j9;j)for(intk0;k9;k){if(ijk19j1iki*1.5k)coutijk;}return0;}确定枚举量、枚举范围用循环实现枚举在循环体中进行判断和筛选代码优化1.5剪枝优化法充分利用题目里的关键信息去掉不必要的分支提高算法效率三位密码之和为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个字符宽度,宽度不足的在左边填充空格)。题意理解#includebits/stdc.husingnamespacestd;intmain(){intn,i0;cinn;for(intc0;cn/5;c)//5角个数{for(intb0;bn/2;b)//2角个数{for(inta0;an;a)//11角个数{if(ab*2c*5n){i;printf(%03d%12d%12d%12d\n,i,a,b,c);}}}}return0;}进行优化输出格式分析代码编写#includebits/stdc.husingnamespacestd;intmain(){intn,i0,a;cinn;for(intc0;cn/5;c){for(intb0;b(n-c*5)/2;b){an-c*5-b*2;//次数 a(n/51)*(n/21)*(n1)i;printf(%03d%12d%12d%12d\n,i,a,b,c);}}return0;}4.不吉利日期在国外,每月的13号和每周的星期五都是不吉利的。特别是当13号那天恰好是星期五时,更不吉利。已知某年的一月一日是星期w,并且这一年一定不是闰年,求出这一年所有13号那天是星期五的月份,按从小到大的顺序输出月份数字。(w1 … 7)【输入】输入w,表示一月一日是星期几(w)。【输出】输出有一到多行,每行一个月份,表示该月的13日是星期五。【输入用例】7【输出用例】110确定枚举量、枚举范围用循环实现枚举intmain(){//1.确定枚举范围1年365天每一天都进行判断intw;cinw;//2.用循环实现枚举for(inti1;i12;i)//12个月{//这个月总天数d;for(intj1;jd;j)//每一天{//进行判断筛选w;//每过一天星期数w1;}}return0;}在循环体中进行判断和筛选如果是13号并且是星期5,输出月份信息;intmain(){//1.确定枚举范围1年365天每一天都进行判断intw;cinw;//2.用循环实现枚举for(inti1;i12;i)//12个月{//这个月总天数d;for(intj1;jd;j)//每一天{//进行判断筛选if(j13w%75)//输出月份信息w;//每过一天星期数w1;}}return0;}代码编写#includebits/stdc.husingnamespacestd;/*int main() { for(int i0;i9;i) for(int j0;j9;j) for(int k0;k9;k) { if(ijk19 j1ik i*1.5k) coutijk; } return 0; }*//*int main() { int n,i0,a; cinn; for(int c0;cn/5;c) { for(int b0;b(n-c*5)/2;b) { an-c*5-b*2; //次数 a(n/51)*(n/21)*(n1) i; printf(%03d%12d%12d%12d\n,i,a,b,c); } } return 0; }*/intmain(){//1.确定枚举范围1年365天每一天都进行判断intw,d;cinw;//2.用循环实现枚举for(inti1;i12;i)//12个月{//这个月总天数d;if(i1||i3||i5||i7||i8||i10||i12)d31;elseif(i2)d28;elsed30;for(intj1;jd;j)//每一天{//进行判断筛选if(j13w%75)coutiendl;//输出月份信息w;//每过一天星期数w1;}}return0;}本次课程的知识点理解枚举算法的概念循环枚举的用法学习用剪枝法优化枚举算法枚举法的练习:硬币组合、不吉利日期练一练交通方式【编程挑战】小明要从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#includebits/stdc.husingnamespacestd;intmain(){for(inti1;i2;i)for(intj3;j5;j)cout交通工具i交通工具jendl;return0;}