注意：需要提交的是一个整数（表示撞B车的次数），不要填写任何其它内容
思路:算出每次撞击后两车相距多远，每一次都为前一次的2/3
答案:9
public class 愤怒小鸟 { static int count; static void ff(double k){ if(k>1){ count++; k=k*2/3; ff(k); } else{ return; } } public static void main(String[] args) { ff(1000); if(count%2==0){ System.out.println(count/2); } else{ System.out.println(count/2+1); } } } 二、反幻方 我国古籍很早就记载着 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 等都算作同一种情况。 请提交三阶反幻方一共多少种。这是一个整数，不要填写任何多余内容。全排列问题
答案:3120
public class 反幻方 { static int count; static void admit(int []a){ int q=a[0]+a[1]+a[2]; int w=a[3]+a[4]+a[5]; int e=a[6]+a[7]+a[8]; int r=a[0]+a[3]+a[6]; int y=a[1]+a[4]+a[7]; int u=a[2]+a[5]+a[8]; int i=a[0]+a[4]+a[8]; int o=a[2]+a[4]+a[6]; if(q!=w&&q!=e&&q!=r&&q!=r&&q!=y&&q!=u&&q!=i&&q!=o&&w!=e&&w!=r &&w!=y&&w!=u&&w!=i&&w!=o&&e!=r&&e!=y&&e!=u&&e!=i&&e!=o &&r!=y&&r!=u&&r!=i&&r!=o&&y!=u&&y!=i&&y!=o &&u!=i&&u!=o&&i!=o){ count++; } } static void dfs(int []a,int k){ if(k>=a.length){ admit(a); } else for(int i=k;i<a.length;i++){ {int t=a[k];a[k]=a[i];a[i]=t;} dfs(a,k+1); {int t=a[k];a[k]=a[i];a[i]=t;} } } public static void main(String[] args) { int []a={1,2,3,4,5,6,7,8,9}; dfs(a,0); System.out.println(count/8); } }三、打靶 小明参加X星球的打靶比赛。 比赛使用电子感应计分系统。其中有一局，小明得了96分。 这局小明共打了6发子弹，没有脱靶。 但望远镜看过去，只有3个弹孔。 显然，有些子弹准确地穿过了前边的弹孔。 不同环数得分是这样设置的： 1,2,3,5,10,20,25,50 那么小明的6发子弹得分都是多少呢？有哪些可能情况呢？ 下面的程序解决了这个问题。 仔细阅读分析代码，填写划线部分缺失的内容。 public class 打靶 { 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, ho-(i>0?1:0), 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 思路:深度遍历
import java.util.Arrays; import java.util.Scanner; public class 路径之谜 { static int N; static int []north;//正北方靶数 static int []west;//正西方靶数 static int[][]direction={{0,-1},{0,1},{-1,0},{1,0}};//上下左右移动方向 static int[][]mark;//用来标记是否经过某块石头，0为未经过，1为经过 static int x,y;//石头坐标，正东方向为x轴正方向，正南方向为y轴正方向 static void dfs(String str){ if(x>=N-1&&y>=N-1){ int []north_Count=new int [N]; int []west_Count=new int [N]; for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ north_Count[i]+=mark[j][i];//每列耙总数 west_Count[i]+=mark[i][j];//每行耙总数 } } if(Arrays.equals(north, north_Count)&&Arrays.equals(west, west_Count)){//判断是否符合给出耙数的要求 System.out.println(str); return; } } for(int i=0;i<4;i++){ x+=direction[i][0]; y+=direction[i][1]; int position=x+N*y;//石头编号 String s=str+" "+position; if(x>=0&&x<N&&y>=0&&y<N&&mark[y][x]==0){ mark[y][x]=1; dfs(s); mark[y][x]=0;//回溯 } x-=direction[i][0]; y-=direction[i][1]; } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner input=new Scanner(System.in); N=input.nextInt(); mark=new int[N][N]; north=new int[N]; west=new int[N]; for(int i=0;i<north.length;i++){ north[i]=input.nextInt(); } for(int i=0;i<west.length;i++){ west[i]=input.nextInt(); } mark[0][0]=1; dfs("0"); } }
