蓝桥杯练习

文章目录[隐藏]

第一周

第一周: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) 

 

AnonyEast

一个爱折腾的技术萌新

2 Comments

  • 嗯,好复杂

  • 踩踩

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

相关推荐