题目一

题目描述

愤怒小鸟

X星球愤怒的小鸟喜欢撞火车!

一根平直的铁轨上两火车间相距 1000 米
两火车 (不妨称A和B) 以时速 10米/秒 相对行驶。

愤怒的小鸟从A车出发,时速50米/秒,撞向B车,
然后返回去撞A车,再返回去撞B车,如此往复....
两火车在相距1米处停车。

问:这期间愤怒的小鸟撞 B 车多少次?

注意:需要提交的是一个整数(表示撞B车的次数),不要填写任何其它内容。

解题思路

  1. 首先初始化出A车、B车、鸟在坐标轴上的位置,次数,然后是鸟与每次与车碰撞的时间,注意:这里题目要求说提交的是整数,就需要对count设置int类型,还有可能出现在计算时间可能不是整数,因此位置和时间都需要设置为double类型进行计算
  2. 由于第一次鸟开始是向B出发,这里设置与B车相遇就是true,方便判断出鸟目前所处的位置。
  3. 第一次鸟遇见B车,计算从开始到相遇所用时间公式为:10 * time + 50 * time = (bLength - aLength),然后更新A车、B车、鸟它们在与车相遇的时间点所在的位置。进行count++。由于已经与B车相遇,那么就应该返回到与A车相遇,设置一个判断条件将与A车相遇设置为false
  4. 鸟与A车相遇的时候就进行与B相遇类似的处理情况,计算单次相遇时间、更新位置、在设置为true。
  5. 最后的判断条件就是当B车与A车相减比1大为判断结束。

所用方法

这个问题主要是使用了while循环判断进行操作

代码

public class Title01 {
    public static void main(String[] args) {
        // a的位置和b的位置
        double aLength = 0;
        double bLength = 1000;
        // 鸟的位置
        double bird = 0;
        // 表示次数
        int count = 0;
        // 表示时间,用于到一趟所用时间
        double time = 0;
        // 初始第一次遇见b
        boolean flag = true;
        // 判断条件为当b与a的距离为1米的时候就结束,小于一就不能满足
        while ((bLength - aLength) > 1) {

            if (flag) {
                // 遇到b时
                // 计算公式为:10 * time + 50 * time = (bLength - aLength)
                time = (bLength - aLength) / 60.00;
                aLength += 10 * time;
                bLength -= 10 * time;
                bird = bird + 50 * time;
                count++;
                flag = false;
            } else {
                // 遇到a时
                // 鸟的初始位置减去a的位置就是当前鸟与a相遇的时候,除以两者速度之和
                time = (bird - aLength) / 60.00;
                aLength += 10 * time;
                bLength -= 10 * time;
                bird = bird - 50 * time;
                flag = true;
            }
        }
        System.out.println(count);
    }
}

题目二

题目描述

反幻方

我国古籍很早就记载着

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个数字中进行全排列得到不同的一个9位数,相对于是将3 * 3的矩阵转换为一个9位数不重复的情况。
  2. 通过例子可以看出来美一个反幻方都有8种不通的心态,这些形态分别是对称、旋转、对角线对称。一共就是8种,可以通过计算所有的有多少个(包括重复的情况,然后总的除以8就能得到最后的结果)。
  3. 在进行比较每一个矩阵是否是有重复采用的是对这个矩阵每一行、列、对角线求和得到8个值,然后采用set接口创建集合,我采用的是HashSet集合,这样做的目的是由于set添加元素如果有重复的那么就就不会重复出现,也不用比较。最后判断将这8个值添加进去,最后判断一下这个集合的个数是否是8就ok了。如果有8个就返回ture。
  4. 全排列采用的是深度优先加交换的操作。

所用方法

一个集合,一维数组进行操作。

代码

import java.util.HashSet;
public class Title02 {
    // 全局计数
    static int count = 0;
    public static void main(String[] args) {
        int[] num = {1 , 2, 3, 4, 5, 6, 7, 8, 9};
        method(num, 0, num.length - 1);
        // 由于会有每一大类会重复出现8次的情况,也就是旋转,轴对称,对角线对称,加上本身一共8个
        System.out.println(count / 8);
    }
    // 全排列实现
    public static void method(int[] num, int start, int end) {
        if (start == end) {
            // 进行判断所得的数组,如果没有重复的就++操作
            if (bijiao(num)) {
                count++;
            }
        } else {
            for (int i = start; i <= end; i++) {
                swap(num, start, i);
                method(num, start + 1, end);
                swap(num, start, i);
            }
        }
    }
    // 数组的交换方法
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    // 比较求和方法,当出现重复返回false,没有重复返回true
    public static boolean bijiao(int[] arr) {
        int[] arr1 = new int[8];
        // 每行之和
        arr1[0] = arr[0] + arr[1] + arr[2];
        arr1[1] = arr[3] + arr[4] + arr[5];
        arr1[2] = arr[6] + arr[7] + arr[8];
        // 每列之和
        arr1[3] = arr[0] + arr[3] + arr[6];
        arr1[4] = arr[1] + arr[4] + arr[7];
        arr1[5] = arr[2] + arr[5] + arr[8];
        // 对角线
        arr1[6] = arr[0] + arr[4] + arr[8];
        arr1[7] = arr[2] + arr[4] + arr[6];

        // 每一对进行比较所有元素是否有相同的,根据题目条件可以看出来这8个数字不能存在有相同的情况
        /**
         * 通过set接口中的任何一个来创建一个集合,我采用HashSet,这里为什么要采用Set接口,
         * 那是因为在添加元素的时候如果有相同的值,那么集合的size就不为8就可以判断出是否是反幻方
         */
        HashSet hashSet = new HashSet();
        for (int i = 0; i < arr1.length; i++) {
            hashSet.add(arr1[i]);
        }

        if (hashSet.size() != 8) {
            return false;
        }
        return true;
    }

}

题目三

题目描述

打靶

小明参加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. 这种填空题通过源代码来看。首先从main方法开始分析,ta数组根据题目的要求对应的就是这个靶子上的得分分布情况。da表示打中那个靶子的下标。
  2. 在f方法中可以看得到ho、sc,分别表示打的弹孔剩余的个数,sc表示剩下的的分数。
  3. 根据天空的位置来看,i是从0开始的,不成立的初始情况,来推断出k环上是否是有多少个子弹数,没打中就不对ho进行操作,如果被打中就要少掉一个孔。

代码

public class Title03 {
    static void f(int[] ta, int[] da, int k, int ho, int bu, int sc) {
        // ta[i]表示靶子的得分情况,da[i]表示打中第i环的个数,k子弹打中的环数,ho表示子弹剩下的孔数,bu表示剩下多少枪,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,ho-((i ==0 )? 0 : 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);
    }
}

题目四

题目描述

路径之谜

小明冒充X星球的骑士,进入了一个奇怪的城堡。
城堡里边什么都没有,只有方形石头铺成的地面。

假设城堡地面是 n x n 个方格。【如图1.png】所示。

按习俗,骑士要从西北角走到东南角。
可以横向或纵向移动,但不能斜着走,也不能跳跃。
每走到一个新方格,就要向正北方和正西方各射一箭。
(城堡的西墙和北墙内各有 n 个靶子)

同一个方格只允许经过一次。但不必做完所有的方格。

如果只给出靶子上箭的数目,你能推断出骑士的行走路线吗?

有时是可以的,比如图1.png中的例子。

本题的要求就是已知箭靶数字,求骑士的行走路径(测试数据保证路径唯一)

输入:
第一行一个整数N(0<N<20),表示地面有 N x N 个方格
第二行N个整数,空格分开,表示北边的箭靶上的数字(自西向东)
第三行N个整数,空格分开,表示西边的箭靶上的数字(自北向南)

输出:
一行若干个整数,表示骑士路径。

为了方便表示,我们约定每个小格子用一个数字代表,从西北角开始编号: 0,1,2,3....
比如,图1.png中的方块编号为:

0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

示例:
用户输入:
4
2 4 3 4
4 3 3 3

程序应该输出:
0 4 5 1 2 3 7 11 10 9 13 14 15

资源约定:
峰值内存消耗 < 256M
CPU消耗 < 1000ms

请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。

所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意:不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意:主类的名字必须是:Main,否则按无效代码处理。

lanqiao01

解题思路

Q.E.D.


一个在读大学生