深度优先

这个家伙好懒，除了文章什么都没留下

0%

发表于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

老师在群里发的题，就发了提干，不知道名字我就自己给它命名吧。

题干：从某数的最后一位开始数，这个数是几位就能被几整除，

然后依次从这个数最后一位开始删除数字，然后剩下的n-1位数字可以被（n-1）整除，

比如10245就满足条件，10245能被5整除，1024能被4整除，102能被3整除。。。。，

任意输入n，求所有满足条件的数，并探求n的最大值

几行代码就基本解决了，吓我一跳，小小得意，这么6，hhhh。

代码：

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
public class 数 {

	static int[] data=new int[50];
	static boolean fal=false;
	
	public static void main(String[] args) {
		long t1=System.nanoTime();
		dfs(0,1);
		long t2=System.nanoTime();
		System.out.println(t2-t1+"纳秒");
	}
	private static void dfs(long num,int k) {
		
		if(fal)return;
		
		if(k==19){
			System.out.println(num);
			fal=true;
			return;
		}
		
		for (int j = 9; j >= 0; j--) {
			if((num*10+j)%k==0){
				dfs(num*10+j,k+1);
			}
		}
	}
}

当时用long到达18位后结果就溢出了，所以没推出n最长是多少。其实当时知道换成BigInteger就可以解决

只是当时不知道BigInteger有直接取模的函数，以为蛮难的，其实不然。

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
import java.math.BigInteger;

public class 数 {

	static int[] data=new int[50];
	static boolean fal=false;
	
	public static void main(String[] args) {
		long t1=System.nanoTime();
		BigInteger num=BigInteger.ZERO;
		for (int i = 1; i < 30; i++) {			
			dfs(num,1,i);
			data=new int[50];
			fal=false;
		}
		long t2=System.nanoTime();
		System.out.println(t2-t1+"纳秒");
	}
	private static void dfs(BigInteger num,int k,int l) {
		
		if(fal)return;

		if(k>l){
			System.out.println(l+":"+num);
			fal=true;
			return;
		}
		
		for (int j = 9; j >= 0; j--) {
			
			BigInteger t=(num.multiply(BigInteger.valueOf(10)).add(BigInteger.valueOf(j)));

			if(t.mod(BigInteger.valueOf(k)).toString().equals("0")){//(num*10+j)%k==0)
				dfs(t,k+1,l);//dfs(num*10+j,k+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
1:9
2:98
3:987
4:9876
5:98765
6:987654
7:9876545
8:98765456
9:987654564
10:9876545640
11:98765456405
12:987606963096
13:9876069630960
14:98760696309604
15:987606963096045
16:9876062430364208
17:98485872309636009
18:984450645096105672
19:9812523240364656789
20:96685896604836004260
21:966858966048360042609
22:9668589660483600426096
23:72645656402410567240820
24:402852168072900828009216
25:3608528850368400786036725
26:0
27:0
28:0
29:0
783320379纳秒

发表于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

情侣啊，怎么刷个题都要虐狗呢，太没人性了。

编号分别为1，2，…，n的n对情侣参加聚会后拍照主持人要求这n对情侣中的所有人排成一横排，

别出心裁的规定每对情侣男左女右且不得相邻；编号为1的情侣之间有1个人，

编号为2的情路之间有2个人，…，编号为8的情侣之间有8个人，

并且规定左端编号小于右端编号，问所有满足以上要求的不同拍照排队方式共有多少，

输出其中排左端为1同时排右端n的排队方式。试对一般n对情侣拍照进行设计。

例如n=3时的一种拍照排队为“231213”

轻松的解决了，让你们虐狗的：

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
import java.util.Scanner;

public class 照相 {

	/*题意：有n*2个坑，要将1~n个数放到这些坑中，并且有那个关系
	 *
	 * 分析：第一个坑可以放1~n,所以遍历k，范围是（1~n）试探着入坑，
	 * 因为那个关系可知，data[k]=data[k+i+1],
	 * 并且将放进去的k，在数组中标记为已经使用的
	 * 
	 * 然后同样的道理放第二个坑，第三个坑。。。所以递归出来了
	 * 
	 * */
	static int n;
	static boolean[] vis;
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		vis=new boolean[n+1];
		int[] data=new int[n*2];
		f(0,data);

	}

	private static void f(int k, int[] data) {
		
		if(k==n*2-1){
			for (int i = 0; i < data.length; i++) {
				System.out.print(data[i]);
			}
			System.out.println();
			return;
		}
		
		for (int i = 1; i <= n; i++) {
			
			if(data[k]!=0){
				f(k+1,data);
				return;
			}	
			else if(!vis[i]&&(k+i+1)<n*2&&(data[k]==0&&data[k+i+1]==0)){
				
				data[k]=i;
				data[k+i+1]=i;
				vis[i]=true;
				
				f(k+1,data);
				
				vis[i]=false;
				data[k+i+1]=0;
				data[k]=0;
			}
		}
	}
}

发表于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

转自：http://blog.csdn.net/qq_34594236/article/details/61209276

这个题有几个地方可以借鉴，给格子的编号，判断连通性等地方。

题目描述：

如【图1.jpg】, 有12张连在一起的12生肖的邮票。

现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。


请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

题目答案：

116

题目思路：

枚举五种数的所有组合然后判断这五个数是否连通即可。判断连通性可以用DFS来判断，上下左右四个方向可以将题目中的1，2，3，4，5，6，7，8，9，10数字进行转换，4和5是无法连通的，可以将其变为1，2，3，4，6，7，8，9，11，12，13，14如图，这样我就可以实现左右分别+1和-1，上下分别+5和-5来实现。

题目JAVA代码:

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
public class 剪邮票
{  
	static int[] data=new int[]{1,2,3,4,6,7,8,9,11,12,13,14};
	static int[] arr=new int[5];
	static int[] vis=new int[5];
	static int[] dir=new int[]{1,-1,5,-5};
	static int ans=0;
	
	public static void main(String[] args) {
		for (int a = 0; a < data.length; a++) {
			for (int b = a+1; b < data.length; b++) {
				for (int c = b+1; c < data.length; c++) {
					for (int d = c+1; d < data.length; d++) {
						for (int e = d+1; e < data.length; e++) {
							arr[0]=data[a];
							arr[1]=data[b];
							arr[2]=data[c];
							arr[3]=data[d];
							arr[4]=data[e];
							vis=new int[5];
							vis[0]=1;
							dfs(0);
							boolean fal=true;
							for (int i = 0; i < 5; i++) {
								if(vis[i]==0)
									fal=false;
							}
							if(fal){
								ans++;
//								for (int i = 0; i < arr.length; i++) {
//									System.out.print(arr[i]+" ");
//								}
//								System.out.println();
//								for (int i = 0; i < arr.length; i++) {
//									System.out.print(vis[i]+" ");
//								}
//								System.out.println();
							}
						}
					}
				}
			}
		}
		System.out.println(ans);
	}

	//判断连通性
	private static void dfs(int u) {
	    for(int i=0 ;i<4 ;i++){  
	        int t = arr[u]+dir[i];  
	        if(t>=1&&t<=14){  
	            for(int j=0 ;j<5 ;j++)  
	                if(t==arr[j]&&vis[j]==0){  
	                    vis[j]=1;  
	                    dfs(j);  
	                }             
	        }  
	    }
	}
}