2020_java蓝桥_暑假训练_递归2

发表于 | 分类于 ， | 热度: ℃
字数统计: 2.3k | 阅读时长 ≈ 11

🌸递归训练

Traffic_Route

1、某城市经常在高峰时段发生交通拥堵，因此市政府决定采取管制措施：在高峰时段，车辆只能向东或北行驶。所有的街道都是东西走向或者南北走向，形成下图所示网络。

aLV5kV.png

假设我们我们已经知道了一辆车的初始位置和目标位置，那么有多少种可以到达目标位置的路径呢？起点位置为E 终点位置为F （选做利用递归解决）

🍁分析

普通的跳格子问题，直接递归，没啥好说的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Traffic_Route {
	private static int path = 0;
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int s_x = input.nextInt();
		int s_y = input.nextInt();
		int e_x = input.nextInt();
		int e_y = input.nextInt();
		fun(s_x, s_y, e_x, e_y);
		System.out.println(path);
		input.close();
		
	}
	private static void fun(int startX, int startY, int endX, int endY) {
		if(startX == endX && startY == endY) {
			path++;
		}
		if(startX > endX) {
			fun(startX - 1, startY, endX, endY);
		}
		if(startY < endY) {
			fun(startX, startY + 1, endX, endY);
		}
	}
}

🌸Building_Blocks

2、小明最近喜欢搭数字积木。一共有10块积木，每个积木上有一个数字，0~9。

搭积木规则：

每个积木放到其它两个积木的上面，并且一定比下面的两个积木数字小。

最后搭成4层的金字塔形，必须用完所有的积木。

下面是两种合格的搭法：

1
2
3
4
5
6
7
8
   0
  1 2
 3 4 5
6 7 8 9
   0
  3 1
 7 5 2
9 8 6 4

请你计算这样的搭法一共有多少种？

🍁分析

  • 1.用递归求出0-9的全排列
  • 2.对每个排列进行判断，满足条件+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Building_Blocks {
	private static int count;
	public static void main(String[] args) {
		int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
		dfs(arr, 0);
		System.out.println(count);
	}
	private static void dfs(int[] arr, int start) {
		if(start == arr.length - 1) {
			if(judge(arr)) {
				count++;
			}
			return;
		}
		for(int i = start; i < arr.length; i++) {
			swap(arr, start, i);
			dfs(arr, start + 1);
			swap(arr, start, i);
		}
	} 
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	private static boolean judge(int[] a) {
		if((a[0]<a[1]&&a[0]<a[2]) && (a[1]<a[3]&&a[1]<a[4]) && (a[2]<a[4]&&a[2]<a[5]) && (a[3]<a[6]&&a[3]<a[7]) && (a[4]<a[7]&&a[4]<a[8]) && (a[5]<a[8]&&a[5]<a[9])) {
			return true;
		}
		return false;
	}
}

🌸Mission_Mix

3、X星球要派出一个5人组成的观察团前往W星。

其中：

A国最多可以派出4人。

B国最多可以派出2人。

C国最多可以派出2人。

D国最多可以派出1人。

E国最多可以派出1人。

F国最多可以派出3人。

那么最终派往W星的观察团会有多少种国别的不同组合呢？

🍁分析

数组a是用来存储各个国家可以派遣的人数， 方法 func(int[] a, int k, int n, String s) 其中int[] a指代数组a，变量k 指代国家索引，变量n 指代当前已经选出的人数，变量str 指代 一个选出的用字符串表示的情况for循环，循环当前国家（a[k]）的情况，并用s2存下来，然后k+1递归进入下一个国家（索引值），n-i 表示还需要派遣的人数，s表示存储的当前情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Mission_Mix {
	private static int sum = 0;
	public static void main(String[] args) {
		int[] a = {4, 2, 2, 1, 1, 3};
		fun(a, 0, 5, "");
		System.out.println(sum);
	}
	private static void fun(int[] a, int k, int n, String str) {
		if(k == a.length) {
			if(n == 0) {
				System.out.println(str);
				sum++;
			}
			return;
		}
		
		if(n < 0) {
			return;
		}
		
		String s = str;
		for(int i = 0; i <= a[k]; i++) {
			fun(a, k + 1, n - i, s);
			s += (char)(k + 'A');
		}
	}
}

🌸Poker_Suquence

4、A A 2 2 3 3 4 4， 一共4对扑克牌。请你把它们排成一行。

要求：两个A中间有1张牌，两个2之间有2张牌，两个3之间有3张牌，两个4之间有4张牌。

请填写出所有符合要求的排列中，字典序最小的那个。

例如：22AA3344 比 A2A23344 字典序小。当然，它们都不是满足要求的答案。

🍁分析

这道题就这么看，确实懵了一阵，索性直接全排列，寻找满足条件的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Poker_Suquence {
	private static Set<String> set = new TreeSet<>();
	public static void main(String[] args) {
		String str = "AA223344";
		dfs(str.toCharArray(), 0);
		for(String s : set) {
			System.out.println(s);
		}
	}
	private static void dfs(char[] data, int k) {
		if(k == data.length) {
			judge(data);
			return;
		}
		
		for(int i = k; i < data.length; i++) {
			swap(data, i, k);
			dfs(data, k + 1);
			swap(data, i, k);
		}
	}
	private static void judge(char[] a) {
		String s = new String(a);
		if(s.lastIndexOf('A') - s.indexOf('A') != 2) {
			return;
		}
		if(s.lastIndexOf('2') - s.indexOf('2') != 3) {
			return;
		}
		if(s.lastIndexOf('3') - s.indexOf('3') != 4) {
			return;
		}
		if(s.lastIndexOf('4') - s.indexOf('4') != 5) {
			return;
		}
		set.add(s);
	}
	private static void swap(char[] a, int i, int j) {
		char temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

🍁全排列第二种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class Poker_Suquence {
	public static void main(String[] args) {
		System.out.println("-------------");
		char[] str2 = new char[8];
		dfs2(str2, 0);
	}
	/**
	 * 
	 * @param a
	 * @param k
	 */
	private static void dfs2(char[] a, int k) {
		if(k >= a.length) {
			if(judge2(a)) {
				show(a);
			}
		}else {
			for(int i = 1; i <= 4; i++) {
				a[k] = (char) (i + '0');
				dfs2(a, k + 1);
			}
		}
	}
	private static void show(char[] a) {
		for(int i = 0; i < a.length; i++) {
			if(a[i] == '1') {
				System.out.print('A');
			}else {
				System.out.print(a[i]);
			}
		}
		System.out.println();
	}
	private static boolean judge2(char[] a) {
		boolean[] bool = new boolean[5];
		int sizeA = 0, size2 = 0, size3 = 0, size4 = 0;
		for(int i = 0; i < a.length; i++) {
			if(a[i] == '1') {
				sizeA++;
				if(i + 2 < a.length && a[i] == a[i + 2] || i - 2 > 0 && a[i - 2] == a[i]) {
					bool[0] = true;
				}
			}

			if(a[i] == '2') {
				size2++;
				if(i + 3 < a.length && a[i] == a[i + 3] || i - 3 > 0 && a[i - 3] == a[i]) {
					bool[1] = true;
				}
			}

			if(a[i] == '3') {
				size3++;
				if(i + 4 < a.length && a[i] == a[i + 4] || i - 4 > 0 && a[i - 4] == a[i]) {
					bool[2] = true;
				}
			}

			if(a[i] == '4') {
				size4++;
				if(i + 5 < a.length && a[i] == a[i + 5] || i - 5 > 0 && a[i - 5] == a[i]) {
					bool[3] = true;
				}
			}

		}
		if(sizeA == 2 && size3 == 2 && size4 == 2 && size2 == 2) {
			bool[4] = true;
		}
		return bool[0] && bool[1] && bool[2] && bool[3] && bool[4];	
	}
}

🍁全排列第三种写法

将A当做1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Poker_Suquence {
    public static int a[]={1,2,3,4};
    public static int b[]=new int [8];
	public static void main(String[] args) {
		fun(0);
	}
	/**
	 * 
	 * @param n
	 */
    public static void fun(int n)
    {
        for(int i=0;i<8;i++)
        {
            if(b[i]==0&&(i+a[n]+1)<8&&b[i+a[n]+1]==0)
            {
                b[i]=b[i+a[n]+1]=a[n];
                if(n==3)
                {
                    for(int j=0;j<8;j++)
                    {
                    	if(b[j] == 1) {
                    		System.out.print('A');
                    	}else {                  		
                    		System.out.print(b[j]);
                    	}
                    }
                    System.out.println();
                }
                else fun(n+1);
                b[i]=b[i+a[n]+1]=0;
            }
        }
    }
}

🌸Full_Of_Permutation

5、已知不同字母构成的串，求它的全排列

例如“ABCD”的全排列？

🍁分析

直接进行全排列，也没什么好说的，分为字符串和字符数组的全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Full_Of_Permutation {
	public static void main(String[] args) {
		String str = "ABCD";
		System.out.println(dfs(str).toString());
	}
	//字符串
	private static List<String> dfs(String str){
		List<String> list = new Vector<String>();
		//出口
		if(str.length() == 1) {
			list.add(str);
			return list;
		}
		// 下面是递归的相似性
		/* Vector非常类似ArrayList，但是Vector是同步的。 */
		for(int i = 0; i < str.length(); i++) {
			char cur = str.charAt(i);
			 //用来临时存储 递归之后的全排列
			List<String> lis = new Vector<String>();
			//lis为递归s串中除去i之后的各个元素的全排列
			lis = dfs(str.substring(0, i) + str.substring(i + 1));
			//然后把i的加在lis的前边就行
			for(int k = 0; k < lis.size(); k++) {
				list.add("" + cur + lis.get(k));
			}
		}
		return list;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Full_Of_Permutation {
	public static void main(String[] args) {
		String str = "ABCD";
		
		dfs2(str.toCharArray(), 0);//k从第0个开始
	}
	//数组
	/**
	 * 
	 * @param a 待排列数组
	 * @param k 数组下表
	 */
	private static void dfs2(char[] a, int k) {
		//出口
		if(k == a.length - 1) {
			//把数组类型的aa强制转换成字符串类型,并输出
			System.out.println(String.valueOf(a));
			return;//K达到上线，不能继续递归，程序返回
		}
		//递归相似性
		//从第k个数开始，到数组中的最后一个数为止，依次进行交换（k从第一个数开始）
		for(int i = k; i < a.length; i++) {//i=k,即不能漏掉不交换的情况
			//试探
			swap(a, i, k);
			//调用K+1；递归后面的元素
			dfs2(a, k + 1);
			//回溯，再交换回来
			swap(a, i, k);
			 //做试探，递归之后立即回溯
		}
	}
	private static void swap(char[] a, int i, int j) {
		char temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

🌸Repeated_Letter_Combinations

6、有重复的字母中求取出m个所有组合

​ 例如： “AAABBCCCCCCDD” 中取3个字母的所有组合

🍁分析

无疑是从中拿出三个字母进行全排列，详情见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Repeated_Letter_Combinations {
	private static int sum = 0;
	public static void main(String[] args) {
		int[] data = {3, 2, 6, 2};//四种元素分别所占个数
		int[] x = new int[4];//每种元素取多少个
		dfs(data, x, 0, 3);
		System.out.println(sum);
	}
	private static void dfs(int[] data, int[] x, int loc, int goal) {
		if(loc == 4) {
			if(goal == 0) {
				sum++;
				print(x);
			}
			return;
		}
		//i 为第loc种元素所取得个数
		for(int i = 0; i <= (goal < data[loc] ? goal : data[loc]); i++) {
			x[loc] = i;
			dfs(data, x, loc + 1, goal - i);
		}
	}
	private static void print(int[] x) {
		for(int i = 0; i < 4; i++) {
			for(int j = 0; j < x[i]; j++) {
				System.out.print((char)('A' + i));
			}
		}
		System.out.println();
	}
}

最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！

-------------本文结束感谢您的阅读-------------
云澈 wechat
扫一扫，用手机访问哦
坚持原创技术分享，您的支持将鼓励我继续创作！
0%