|
目录
什么是枚举法？
枚举法的应用
1.鸡兔同笼
2.韩信点兵
3.年龄问题?
4.统计方形
1~5题为填空题
第1题较为简单，不用编程也能得出答案。
6~10题为编程题
重点算法:(1)枚举；(2)递推递归；(3)动态规划；(4)搜索；(5)回溯。
什么是枚举法？
暴力破解，最常用的是枚举法，也叫穷举法。
枚举法是在分析问题时，逐个列举出所有可能情况，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃，最后得出一般结论。主要利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检验，从中找出符合要求的答案，因此枚举法是通过牺牲时间来换取答案的全面性。
就是通过循环或者递归，把所有可能的情况过一遍，符合条件就留下，不符合继续找。
方法步骤：
1.确定枚举对象、枚举范围、判断条件。
2.循环验证每一个解。
枚举法的应用
1.鸡兔同笼
问题：有鸡兔共50头，共有脚120只。 问 ：鸡兔分别的数量？
public class Main {
public static void main(String[] args) {
for(int i=0;i<=50;i++) {//设鸡有i只
//最小是0，最大为50，在一个循环中一个一个的测试，看哪一个条件能够满足题目要求
int j=50-i;//设兔有j只
if(2*i + 4*j==120) {//鸡有2条腿，兔有4条腿
System.out.println("i="+i+" "+"j="+j);
}
}
}
}
【答案】i=40 j=10
2.韩信点兵
?问题：韩信知道部队人数大约1000人左右，具体数字不详，5人一组剩余1人，7个人一组还剩两个人，8个人一组还剩3个人，问：这支部队有多少人?
public class Main {
public static void main(String[] args) {
for(int i=0;i<2000;i++) {
if(i%5==1 && i%7==2 && i%8==3) {
System.out.println("i="+i);
}
}
}
}
【答案】i=51
i=331
i=611
i=891
i=1171
i=1451
i=1731
3.年龄问题?
美国数学家维纳(N.Wiener)智力早熟，11 岁就上了大学。他曾在 1935~1936 年应邀来中国清华大学讲学。一次，他参加某个重要会议，年轻的脸孔引人注目。于是有人询问他的年龄，他回答说：“我年龄的立方是个 4 位数。我年龄的 4 次方是个6 位数。这 10 个数字正好包含了从 0 到 9 这 10 个数字，每个都恰好出现 1 次。”
请你推算一下，他当时到底有多年轻。
【解析】界限 “我年龄的立方是个 4 位数。我年龄的 4 次方是个6 位数” 所以在 18和25 之间?
public class Main {
public static void main(String[] args) {
String sum;
for(int i=11;i<25;i++) {
sum=i*i*i+""+i*i*i*i;
int j=0;
while(sum.lastIndexOf(sum.charAt(j))==j) {
if(j==9) {
System.out.println(i);
return;
}
j++;
}
}
}
}
【答案】18
lastIndexOf()
返回指定元素在数组中的最后一个的索引，如果不存在则返回 -1 。
chatAt()
返回指定索引位置的char值。索引范围为0~length()-1。
如: str.charAt(0)检索str中的第一个字符,str.charAt(str.length()-1)检索最后一个字符。
4.统计方形
有一个n*m方格的棋盘，求其方格包含多少正方形、长方形
【输入格式】
n,m规定m小于等于5000，n小于等于5000
【输出格式】
方格包含多少正方形、长方形
输入输出样例
【输入】
2 3
【输出】
8 10
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int [][ ]map=new int[n][m];
long zsum=0,csum=0;//zsum是正方形，csum是长方形
long sum=0;//sum是所有矩形
for(int i=0;i<map.length;i++) {
for(int j=0;j<map[i].length;j++) {
sum+=(i+1)*(j+1);
zsum+=Math.min(i+1,j+1);
}
}
csum=sum-zsum;
System.out.println(zsum+" "+csum);
}
}
?
|