枚举算法在生活当中是运用的比较常见的,不管是在scratch中,还是在c++中,枚举算法都是常用到的。今天我们来就以scratch编程举例(白鸡问题)来充分的了解下枚举算法。
什么是枚举算法?
枚举算法又叫穷举,指有序的、不重复不遗漏把所有可能的情况列举出来,并逐一验证是否满足给定的条件,直到找出问题的答案。
在枚举算法中,把问题分解两个部分:
1、列举:列举所有可能的情况,这个就需要用到重复循环,要考虑的问题是如何设计循环变量、初值、终值、递增值和几重循环。
2、检验:一般是分支结构,要考虑的问题是检验对象是谁?逻辑判断后的两个结果如何处理。
scratch编程枚举算法案例:(百鸡问题)
案例题意思:
一只公鸡值5元,一只母鸡值3元,而1元可买3只小鸡。现有n元钱,想买n只鸡。问有多少种买法?(钱要用完,某种鸡可以不买。)
举例百鸡问题,scratch枚举算法
解题思路分析:
1、设n元可以买x只鸡,y只母鸡,根据题意得出不等式为:5x+3y+(n-x-y)/3=n;其中5x是表示买x只鸡的费用,3y是指的买y只鸡的费用,(n-x-y)/3是表示买n-x-y只小鸡的费用。题目要求买n只鸡,所以小鸡的数量等于n-x-y;
2、某种鸡可以不买,也就是说,x、y、n-x-y可以为0;也就是x、y、n-x-y的最小值可以为0;
3、x可能最大值是多少?
x最大,那么y肯定是最小的,y最小为0;那么5x+3*0+(n-x-0)/3=n;得出x的最大值是x=n/7;
4、y可能最大值是多少?
y最大,那么x肯定是最小,x最小为0;那么5*0+3y+(n-0-y)/3=n;得出y的最大值是y=n/4;
5、两个循环进行嵌套,得出满足5x+3y+(n-x-y)/3=n的组合的可能。
最后,我们是要从这些数据组合中把满足5x+3y+(n-x-y)/3=n,条件的有多少种? 代码如下:
scratch枚举算法“白鸡问题”案例完整代码
总言之,在使用枚举算法的时候,一般需要两个方面的考虑:
1、确定枚举范围
2、找到吻合的条件
scratch算法相关重要知识点:
scratch堆栈算法题目,字符括号匹配
scratch递归算法,阶乘求积举例
欧几里德算法求最大公约数