文章目录[隐藏]
第一周
第一周:1月28日-2月6日
T1:愤怒小鸟 来源:第七届蓝桥杯-决赛-Java-B组
X星球愤怒的小鸟喜欢撞火车! 一根平直的铁轨上两火车间相距1000米 两火车(不妨称A和B)以时速10米/秒相对行驶。 愤怒的小鸟从A车出发,时速50米/秒,撞向B车, 然后返回去撞A车,再返回去撞B车,如此往复.... 两火车在相距1米处停车。 问:这期间愤怒的小鸟撞B车多少次? 注意:需要提交的是一个整数(表示撞B车的次数),不要填写任何其它内容。
解题思路:
代码:
public class T1 { public static void main(String[] args) { double locateA = 0, locateB = 1000;//A的初始位置为0,B的初始位置为1000 double crashTime;//撞车时间 int count = 0;//撞B车的次数统计 boolean isCrashB = false;//撞的是否是B车 //两车距离大于1时执行循环 while (locateB - locateA > 1) { crashTime = (locateB - locateA) / 60; isCrashB = !isCrashB;//第奇数次循环撞的是B车,第偶数次循环撞的是A车 if (isCrashB) { count++; } locateA += 10 * crashTime;//小鸟撞车后A的位置 locateB -= 10 * crashTime;//小鸟撞车后B的位置 } System.out.println(count); } } 输出结果:9
T2:反幻方 来源:第七届蓝桥杯-决赛-Java-B组
我国古籍很早就记载着 2 9 4 7 5 3 6 1 8 这是一个三阶幻方。每行每列以及对角线上的数字相加都相等。 下面考虑一个相反的问题。 可不可以用 1~9 的数字填入九宫格。 使得:每行每列每个对角线上的数字和都互不相等呢? 这应该能做到。 比如: 9 1 2 8 4 3 7 5 6 你的任务是搜索所有的三阶反幻方。并统计出一共有多少种。 旋转或镜像算同一种。 比如: 9 1 2 8 4 3 7 5 6 7 8 9 5 4 1 6 3 2 2 1 9 3 4 8 6 5 7 等都算作同一种情况。 请提交三阶反幻方一共多少种。这是一个整数,不要填写任何多余内容。
解题思路:
1.为了求出有多少种三阶反幻方,需要先求出1-9九个数字的全排列,相当于每一种情况都要判断一遍。这里就要用到深度优先搜索(DFS)的思想。
2.每一种情况,都要判断三行三列以及两对角线相加是否都不同,那么一共可以得到8个值,这8个值都不相同,才满足题意。考虑到Java中的Set集合具有元素不会重复的特性,因此可以将这8个值存入一个Set集合,如果最终集合中有8个元素,说明满足题意,小于8个元素,说明有相同的情况存在,应当舍弃。统计有多少个方阵满足每行每列每个对角线上的数字和都互不相等。
3.因为旋转或镜像算同一种情况,观察一下可以发现,一个方阵通过旋转,可以得到4种不同的形态(旋转0度、90度、180度、270度),通过镜像,也可以得到4种形态(上下翻转、左右翻转)。因此,一个满足题意的方阵,通过旋转和镜像,会有8种不同的形态。而这8种形态,也必然会在全排列中出现,所以最终满足满足题意的方阵数目 = 每行每列每个对角线上的数字和都互不相等的数目 / 8
DFS三个重点:1.截止条件。2.候选结点。3.筛选。
public class T2 { private static int count = 0; public static void main(String[] args) { //Key:1-9 Value:是否被使用过 HashMap<Integer, Boolean> map = new HashMap<>(); for (int i = 1; i <= 9; i++) { map.put(i, false); } LinkedList<Integer> list = new LinkedList<>();//存储结果 dfs(map, 1, list);//深度优先搜索 System.out.println(count / 8);//旋转或镜像会有8种不同形态但算同一种情况 } public static void dfs(HashMap<Integer, Boolean> map, int level, LinkedList<Integer> result) { //1.截止条件 if (level > map.size()) { //截止后说明一个完整的排列已经生成,可以开始计算行、列、对角线的和 int row1 = result.get(0) + result.get(1) + result.get(2); int row2 = result.get(3) + result.get(4) + result.get(5); int row3 = result.get(6) + result.get(7) + result.get(8); int col1 = result.get(0) + result.get(3) + result.get(6); int col2 = result.get(1) + result.get(4) + result.get(7); int col3 = result.get(2) + result.get(5) + result.get(8); int diag1 = result.get(0) + result.get(4) + result.get(8); int diag2 = result.get(2) + result.get(4) + result.get(6); /** * 创建一个Set集合,将这些结果存入set中,如果最终set集合中的元素数量不是8,说明有重复的元素 */ HashSet<Integer> set = new HashSet<>(); Collections.addAll(set, row1, row2, row3, col1, col2, col3, diag1, diag2); if (set.size() == 8) { count++; } return; } //2.候选结点 for (int i = 1; i <= map.size(); i++) { //筛选 if (!map.get(i)) { result.push(i);//当前结点的值没有被使用过则可以加入结果集 map.put(i, true);//加入结果集后要改变状态 dfs(map, level + 1, result); result.pop();//通过出栈将结果集初始化 map.put(i, false);//将各个结点的使用状态初始化 } } } }
T3:打靶 来源:第七届蓝桥杯-决赛-Java-B组
小明参加X星球的打靶比赛。 比赛使用电子感应计分系统。其中有一局,小明得了96分。 这局小明共打了6发子弹,没有脱靶。 但望远镜看过去,只有3个弹孔。 显然,有些子弹准确地穿过了前边的弹孔。 不同环数得分是这样设置的: 1,2,3,5,10,20,25,50 那么小明的6发子弹得分都是多少呢?有哪些可能情况呢? 下面的程序解决了这个问题。 仔细阅读分析代码,填写划线部分缺失的内容。 public class Main { static void f(int[] ta, int[] da, int k, int ho, int bu, int sc) { if(ho<0 || bu<0 || sc<0) return; if(k==ta.length){ if(ho>0 || bu>0 || sc>0) return; for(int i=0; i<da.length; i++){ for(int j=0; j<da[i]; j++) System.out.print(ta[i] + " "); } System.out.println(); return; } for(int i=0; i<=bu; i++){ da[k] = i; f(ta, da, k+1, __________________ , bu-i, sc-ta[k]*i); // 填空位置 } da[k] = 0; } public static void main(String[] args) { int[] ta = {1,2,3,5,10,20,25,50}; int[] da = new int[8]; f(ta, da, 0, 3, 6, 96); } } 注意:只填写划线处缺少的内容,不要填写已有的代码或符号,也不要填写任何解释说明文字等。
解题思路:
1.经过分析代码,可以得出此题各个参数的含义如下:
数组ta中存放环数分值,数组da里面存放每个分值各打了多少次,k记录DFS中当前所在层数,ho记录还剩多少个弹孔没打,bu记录还剩多少颗子弹,sc记录还剩多少分没打。
2.填空位置是让我们填写递归调用DFS方法的参数ho,ho记录还剩多少个弹孔没有打,按理说此处应该填写ho - 1。但是从for循环中的参数i可以发现,i是从0开始的,当i = 0时,da[k] = i,则此时da[k] = 0,相当于打中da[k]的次数没有增加,则没有增加弹孔。而当i > 0时,则子弹是打在了靶子上的,产生弹孔且只产生一个弹孔。
因此此题答案为:
ho - (i == 0 ? 0 : 1)
2 Comments
嗯,好复杂
踩踩