【思特奇杯.云上蓝桥-算法训练营】第2周

本文主要是介绍【思特奇杯.云上蓝桥-算法训练营】第2周，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.带分数

100 可以表示为带分数的形式：100 = 3 + 69258 / 714

还可以表示为：100 = 82 + 3546 / 197

注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。

类似这样的带分数，100 有 11 种表示法。

题目要求： 从标准输入读入一个正整数N (N<1000*1000) 程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！

例如： 用户输入： 100 程序输出： 11

再例如： 用户输入： 105 程序输出： 6

利用回溯法，先将所有的可能列出1~9的排列，然后再根据加号和除号的位置筛选出所有的合适方案。

package com.test;import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;public class DaiFen {static LinkedList<Integer> paths = new LinkedList<Integer>();static int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };static int result = 0;public static void main(String[] args) {Scanner scan = new Scanner(System.in);int N = scan.nextInt();dfs(paths, N);System.out.println(result);}public static void dfs(LinkedList<Integer> paths, int N) {if (paths.size() == 9) {accordWith(paths, N);return;}for (int i = 0; i < nums.length; i++) {if (paths.contains(nums[i])) {continue;}paths.add(nums[i]);dfs(paths, N);paths.removeLast();}}public static int calculateNumber(int start, int end) {int num = 0;for (int i = start; i <= end; i++) {num = num * 10 + paths.get(i);}return num;}public static void accordWith(List<Integer> list, int N) {for (int i = 0; i < 7; i++) {int intNum = calculateNumber(0, i);if (intNum >= N)break;for (int j = i + 1; j < 8; j++) {int child = calculateNumber(i + 1, j);int parent = calculateNumber(j + 1, 8);int temp = intNum + child / parent;if (child % parent == 0 && temp == N) {result++;}}}}}

2.李白打酒

话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。
像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。
注意：通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。

①回溯法，有两种选择。一个是遇到酒店，酒*2;一个是遇到花，酒-1。然后再筛选出最后是遇到花的情况的，即sum=1;

package com.test;public class LiBai {static int k, jiu = 2, hua = 0, dian = 0;public static void main(String[] args) {dfs(1);System.out.println(k);}private static void dfs(int n) {if (n == 15) {if (jiu == 1 && hua == 9 && dian == 5)k++;return;}for (int i = 1; i <= 2; i++) {//酒馆加酒if (i == 1) {jiu = jiu * 2;dian++;dfs(n + 1);jiu = jiu / 2;dian--;}//看花减酒if (i == 2) {jiu = jiu - 1;hua++;dfs(n + 1);jiu = jiu + 1;hua--;}}}}

②递归法
有两种情况选择，一种是遇到酒店*2，一种是遇到花+1；并且保证一种的次数是5 次，一种的次数是10次。终点是最后次数用尽，酒=0.

package com.test;public class LiBai2 {static int sum=0;public static void main(String[] args) {recur(5, 10, 2);System.out.println(sum);}public static void recur(int a,int b,int c) {if(a==0&&b==1&&c==1) {sum++;return;}//到酒馆if(a>0) recur(a-1, b, c*2);//到花if(b>0) recur(a, b-1, c-1);}
}

3.第39级台阶

小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!站在台阶前，他突然又想着一个问题：如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？

①回溯算法

package com.test;public class Steps {static int count;static int sum;public static void main(String[] args) {dfs(0);System.out.println(sum);}public static void dfs(int steps) {if(steps>39) return;if (steps == 39) {if (count % 2 == 0) {sum++;}return;}for(int i=1;i<=2;i++) {count++;steps+=i;dfs(steps);steps-=i;count--;}}
}

② 递归算法

package com.test;public class Steps2 {static int sum=0;public static void main(String[] args) {recur(0, 0);System.out.println(sum);}public static void recur(int steps,int count) {if(steps>39) return;if(steps==39) {if(count%2==0) {sum++;return;}}recur(steps+1, count+1);recur(steps+2, count+1);}
}

4.穿越雷区

X星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。
某坦克需要从A区到B区去（A，B区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？

已知的地图是一个方阵，上面用字母标出了A，B区，其它区都标了正号或负号分别表示正负能量辐射区。

思路：BFS算法

package com.test;import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;public class LeiQu {static int step = 0;public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();String[][] strs = new String[n][n];Node start = new Node("A", 0, 0);Node end = new Node("B", 4, 0);Scanner scan2 = new Scanner(System.in);for (int i = 0; i < n; i++) {String line = scan2.nextLine();strs[i] = line.split(" ");}scan.close();scan2.close();DFS(start, end, strs);System.out.println(step);}public static int DFS(Node start, Node end, String[][] strs) {int p_x;int p_y;Queue<Node> queue = new LinkedList<>();Set<Node> visited = new HashSet<>();// 将起点加入到队列queue.add(start);visited.add(start);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {Node cur = queue.poll();if (end.equals(cur))return step;p_x = cur.x;p_y = cur.y;for (Node item : findAdj(p_x, p_y, strs)) {if (!visited.contains(item)) {if (!cur.val.equals(item.val)) {queue.offer(item);visited.add(item);}}}}step++;}return -1;}public static List<Node> findAdj(int x, int y, String[][] strs) {int n = strs[0].length;List<Node> list = new ArrayList<>();if (x + 1 < n) {list.add(new Node(strs[x + 1][y], x + 1, y));}if (y + 1 < n) {list.add(new Node(strs[x][y + 1], x, y + 1));}if (x - 1 >= 0) {list.add(new Node(strs[x - 1][y], x - 1, y));}if (y - 1 >= 0) {list.add(new Node(strs[x][y - 1], x, y - 1));}return list;}
}class Node {String val;int x;int y;public Node() {}public Node(String val) {this.val = val;}public Node(String val, int x, int y) {this.val = val;this.x = x;this.y = y;}@Overridepublic int hashCode() {final int prime = 31;int result = 1;result = prime * result + ((val == null) ? 0 : val.hashCode());result = prime * result + x;result = prime * result + y;return result;}@Overridepublic boolean equals(Object obj) {if (this == obj)return true;if (obj == null)return false;if (getClass() != obj.getClass())return false;Node other = (Node) obj;if (val == null) {if (other.val != null)return false;} else if (!val.equals(other.val))return false;if (x != other.x)return false;if (y != other.y)return false;return true;}}5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
10

5. 迷宫

【问题描述】

下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可 以通行的地方。

010000
000100
001001
110000

迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。

对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。

对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。 请注意在字典序中D<L<R<U。（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 maze.txt，内容与下面的文本相同）

01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个字符串，包含四种字母 D、U、L、R，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

package com.test1;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class Puzzle {public static void main(String[] args) {String str = "";try {str = "01010101001011001001010110010110100100001000101010"+ "00001000100000101010010000100000001001100110100101"+ "01111011010010001000001101001011100011000000010000"+ "01000000001010100011010000101000001010101011001011"+ "00011111000000101000010010100010100000101100000000"+ "11001000110101000010101100011010011010101011110111"+ "00011011010101001001001010000001000101001110000000"+ "10100000101000100110101010111110011000010000111010"+ "00111000001010100001100010000001000101001100001001"+ "11000110100001110010001001010101010101010001101000"+ "00010000100100000101001010101110100010101010000101"+ "11100100101001001000010000010101010100100100010100"+ "00000010000000101011001111010001100000101010100011"+ "10101010011100001000011000010110011110110100001000"+ "10101010100001101010100101000010100000111011101001"+ "10000000101100010000101100101101001011100000000100"+ "10101001000000010100100001000100000100011110101001"+ "00101001010101101001010100011010101101110000110101"+ "11001010000100001100000010100101000001000111000010"+ "00001000110000110101101000000100101001001000011101"+ "10100101000101000000001110110010110101101010100001"+ "00101000010000110101010000100010001001000100010101"+ "10100001000110010001000010101001010101011111010010"+ "00000100101000000110010100101001000001000000000010"+ "11010000001001110111001001000011101001011011101000"+ "00000110100010001000100000001000011101000000110011"+ "10101000101000100010001111100010101001010000001000"+ "10000010100101001010110000000100101010001011101000"+ "00111100001000010000000110111000000001000000001011"+ "10000001100111010111010001000110111010101101111000";int[][] strToInt = new int[30][50];for (int i = 0; i < 30; i++) {for (int j = 0; j < 50; j++) {strToInt[i][j] = str.charAt(50 * i + j) - '0';}}Node start = new Node(0, 0, "", null);System.out.println(bfs(start, strToInt)); } catch (Exception e) {e.printStackTrace();}}public static String bfs(Node start, int[][] strToInt) {Queue<Node> queue = new LinkedList<Node>();int [][]visited=new int [30][50];queue.offer(start);visited[0][0]=1;while (!queue.isEmpty()) {int size = queue.size();Node cur = queue.poll();int p_x = cur.x;int p_y = cur.y;for (int i = 0; i < size; i++) {if (p_x == 49 && p_y == 29 && strToInt[cur.y][cur.x] == 0) {// 打印路径StringBuilder sb=new StringBuilder(cur.direct);while (cur.parentNode != null) {sb.append(cur.parentNode.direct);cur = cur.parentNode;}return sb.reverse().toString();}for (Node itemNode : findAdjNode(p_x, p_y, strToInt, queue)) {if (visited[itemNode.y][itemNode.x]!=1) {itemNode.parentNode = cur;queue.offer(itemNode);visited[itemNode.y][itemNode.x]=1;}}}}return null;}public static List<Node> findAdjNode(int x, int y, int[][] arr, Queue<Node> queue) {int ylen = arr.length;int xlen = arr[0].length;List<Node> list = new ArrayList<Node>();if (x + 1 < xlen && arr[y][x + 1] == 0) {list.add(new Node(x + 1, y, "R"));}if (x - 1 >= 0 && arr[y][x - 1] == 0) {list.add(new Node(x - 1, y, "L"));}if (y - 1 >= 0 && arr[y - 1][x] == 0) {list.add(new Node(x, y - 1, "U"));}if (y + 1 < ylen && arr[y + 1][x] == 0) {list.add(new Node(x, y + 1, "D"));}return list;}}class Node {int x;int y;String direct;Node parentNode;public Node() {super();}public Node(int x, int y, String direct) {super();this.x = x;this.y = y;this.direct = direct;}public Node(int x, int y, String direct, Node parentNode) {super();this.x = x;this.y = y;this.direct = direct;this.parentNode = parentNode;}}DDDDRRURRRRRRRDRRRDDDLDDRDDDDDDDDDDDDRDRDRRURRUURRDDDDRDRRRRRRURRDRRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDRDRRRRDRDRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR

6.跳马问题

题目描述
中国象棋半张棋盘如图1所示。马自左下角(0,0)向右上角（m，n）跳。规定只能往右跳，不准往左跳。比如图1中所示为一种跳行路线，并将路径总数打印出来。

输入格式：

只有一行：两个数n，m

输出格式：

只有一个数：总方案数total。

package com.test1;import java.util.Scanner;public class TiaoMa {static int[][] options={{1,2},{2,1},{2,-1},{1,-2}};static int x=0; static int y=0;static int count=0;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int n = scanner.nextInt();int m=scanner.nextInt();dfs(0, 0,m,n);System.out.println(count);}public static void dfs(int x,int y,int m,int n) {if(x>m||y>n) return;if(y<0) return;if(x==m&&y==n) {count++;return;}for(int[] items:options) {x+=items[0];y+=items[1];dfs(x, y,m,n);x-=items[0];y-=items[1];}}
}4 8
37

7.路径之谜

小明冒充X星球的骑士，进入了一个奇怪的城堡。
城堡里边什么都没有，只有方形石头铺成的地面。
假设城堡地面是 n x n 个方格。【如图1.png】所示。
按习俗，骑士要从西北角走到东南角。
可以横向或纵向移动，但不能斜着走，也不能跳跃。
每走到一个新方格，就要向正北方和正西方各射一箭。
（城堡的西墙和北墙内各有 n 个靶子）
同一个方格只允许经过一次。但不必走完所有的方格。
如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？
有时是可以的，比如图1.png中的例子。

package com.test1;
import java.util.Arrays;
import java.util.Scanner;  public class PathOfSecret {  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轴正方向    public static void main(String[] args) {  Scanner console = new Scanner(System.in);  //地面有N*N个方格  N = console.nextInt();  //北边以及西边箭靶上的数字  north = new int[N];  west = new int[N];mark = new int[N][N];  for(int i = 0; i < N;i++){  north[i] = console.nextInt();  }  for(int i = 0; i < N; i++){  west[i] = console.nextInt();  }  mark[0][0]=1;  dfs("0");  }  public static void dfs(String s){  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[i][j];//每列靶子上的箭数  west_count[i] += mark[j][i];//每行靶子上的箭数  }  }if(Arrays.equals(north, north_count)&&Arrays.equals(west, west_count)){  System.out.println(s);  return;  }}  //朝四个方向走  for(int i = 0; i < 4; i++){  x += direction[i][0];  y += direction[i][1];  int position;  position = x+N*y;//石头编号  String str = s + " "+position;  if(x>=0 && y>=0 && x<N && y<N &&mark[x][y]==0){  mark[x][y]=1;  dfs(str);  mark[x][y]=0;}  x -= direction[i][0];  y-= direction[i][1];//回溯  }  }  }  

这篇关于【思特奇杯.云上蓝桥-算法训练营】第2周的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---