第十五周.

谁借莪１个温暖的怀抱￠ 2022-10-06 06:54 263阅读 0赞

### 十五周 ###

*  A、1的个数
 *   *  代码
 *  B、最小素数对
 *   *  代码
 *  C、又是一道简单题
 *   *  代码
 *  D、图的m着色问题
 *   *  代码
 *  E、N皇后
 *   *  代码
 *  F、素数环
 *   *  代码

# A、1的个数 #

**题目描述**

*  输入一个int型的正整数，计算出该int型数据在内存中存储时1的个数。

**输入**

*  输入一个整数（int类型）。

**输出**

*  这个数转换成2进制后，输出1的个数。

**样例输入 Copy**

**样例输出 Copy**

[1、戳我！输入一个int型的正整数，计算出该int型数据在内存中存储时1的个数，这里还有十进制和十六进制的哟！][1_int_int_1]  
2、比较简洁的代码，可以看这个哦~

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()) { 
    			int n = sc.nextInt();
    			int count = 0;
    			String s = Integer.toBinaryString(n); //将n转为二进制数，并赋给s
    			for (int i = 0; i < s.length(); i++) //进行循环
    			    if (s.charAt(i) == '1') //charAt(int index)的作用是检测当前索引下的值
    			       count++;
    			System.out.println(count);
    			
    		}
    
    	}
    
    }

# B、最小素数对 #

**题目描述**

*  任意一个偶数（大于2）都可以由2个素数组成，组成偶数的2个素数有很多种情况，本题目要求输出组成指定偶数的两个素数差值最小的素数对。

**输入**

*  输入一个偶数。

**输出**

*  输出两个素数。

**样例输入 Copy**

**样例输出 Copy**

7
    13

## 代码 ##

[戳我戳我！][Link 1]

import java.util.Scanner;
    
    public class Main { 
    	
    	static int prime(int num) { 
    		for(int i=2;i<=Math.sqrt(num);i++)
    			if(num%i==0)
    				return 0; //不是素数
    		return 1;  //是素数
    	}
    
    	static void solve(int num) { 
    		int dist = num;//记录两个素数之间的差距
    		int t1=0,t2=0;//两个素数
    		for(int i=2;i<=num/2;i++)
    			if(prime(i)==1&& prime(num-i)==1)
    				if(num-(2*i)<dist) { //更新素数之间的更短的距离
    					dist = num-(2*i);
    					t1 = i;
    					t2 = num-i;
    				}
    		System.out.println(t1+"\n"+t2);
    		
    	}
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()) { 
    			int n = sc.nextInt();
    			solve(n);
    		}
    
    	}
    
    }

# C、又是一道简单题 #

**题目描述**

*  输入一个四个数字组成的整数 n，你的任务是数一数有多少种方法，恰好修改一个数字，把它 变成一个完全平方数（不能把首位修改成 0）。比如  
    n=7844，有两种方法：3844=622 和 7744=882。

**输入**

*  输入第一行为整数 T (1<=T<=1000)，即测试数据的组数，以后每行包含一个整数 n (1000<=n<=9999)。

**输出**

*  对于每组数据，输出恰好修改一个数字，把 n变成完全平方数的方案数

**样例输入 Copy**

2
    7844
    9121

**样例输出 Copy**

Case 1: 2
    Case 2: 0

[戳他戳他！细节真就不想说了，评测了几次只是因为输出的格式不对，一就是因为冒号后面有空格，我没注意到！又是一个小细节~][Link 2]

## 代码 ##

import java.util.Scanner;
    
    public class Main { 
    	static int a[] = new int[105];
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()) { 
    			int T = sc.nextInt();
    			
    			for(int i=32;i<100;i++)
    				a[i] = i*i;//记录平方的值
    			for(int i=1;i<=T;i++) { 
    				int num = 0;
    				int count = 0;
    				int n = sc.nextInt();
    				
    				for(int k=32;k<100;k++) { 
    					int x = a[k];
    					int y = n;
    					for(int j=0;j<4;j++) { 
    						int w = x%10;
    						int z = y%10;
    						if(w!=z)
    							count++;
    						x/=10;
    						y/=10;
    					}
    					
    					if(count==1)
    						num++;
    					count=0;
    					
    				}
    				System.out.println("Case "+i+": "+num);
    			}
    			
    		}
    	}
    
    }

# D、图的m着色问题 #

**题目描述**

*  给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色，请输出着色方案。

**输入**

*  输入第一行包含n，m，k分别代表n个结点，m条边，k种颜色，接下来m行每行有2个数u，v表示u和v之间有一条无向边,可能出现自环边，所以请忽略自环边。

**输出**

*  输出所有不同的着色方案，且按照字典序从小到大输出方案。

**样例输入 Copy**

3 3 3
    1 2
    1 3
    2 3

**样例输出 Copy**

1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 1 2
    3 2 1

## 代码 ##

[戳我戳我！][Link 3]

import java.util.Scanner;
    
    public class Main { 
    	static int n,m,k,count=0;
    	static int graph[][] = new int[105][105];
    	static int color[] = new int[105];
    	
    	static boolean used(int t,int i) { 
    		for(int k=1;k<=n;k++)
    			if(graph[t][k]==1 && color[k]==i)
    				return false;
    		return true;
    	}
    	
    	static void backtrack(int t,int m) { 
    		if(t>n) { 
    			for(int i=1;i<=n;i++)
    				System.out.print(color[i]+" ");
    			count++;
    			System.out.println();
    		}
    		else { 
    			for(int i=1;i<=m;i++) { 
    				if(used(t,i)) { 
    					color[t] = i;
    					backtrack(t+1,m);
    				}
    				color[t] = 0;
    			}
    		}
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()) { 
    			n = sc.nextInt();//点
    			m = sc.nextInt();//边
    			k = sc.nextInt();//颜色
    			
    			for(int i=1;i<=m;i++) { 
    				int a = sc.nextInt();//开始的点
    				int b = sc.nextInt();//结束的点
    				if(a!=b) { 
    					graph[a][b] = 1;
    					graph[b][a] = 1;
    				}
    			}
    			
    			for(int i=1;i<=n;i++) 
    				color[i] = 0;
    			
    			backtrack(1,k);
    			
    		}
    
    	}
    
    }

# E、N皇后 #

**题目描述**

*  使用回溯法求解N后问题
 *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODIzMTE4_size_16_color_FFFFFF_t_70]

**输入**

*  皇后的个数

**输出**

*  每一种方案及总方案数

**样例输入 Copy**

**样例输出 Copy**

0 1 0 0
    0 0 0 2
    3 0 0 0
    0 0 4 0
    ----------------
    0 0 1 0
    2 0 0 0
    0 0 0 3
    0 4 0 0
    ----------------
    总方案数为：2

## 代码 ##

[戳我戳我！][Link 4]

import java.util.Scanner;
    
    public class Main { 
    	static int N;//皇后个数
    	static int m[];//同一列
    	static int l[];//左斜线
    	static int r[];//右斜线
    	static int A[][];
    	static int count = 0;//当前已找到的方案数
    	
    	static void queen(int i) { 
    		for(int j=0;j<N;j++) { 
    			if(A[i][j]==0 && r[i+j]==0 && m[j]==0 && l[i-j+N]==0) { 
    				A[i][j] = i+1;
    				r[i+j] = m[j] = l[i-j+N] = 1;
    				if(i==N-1) { 
    					count++;
    					print(A);
    				}else
    					queen(i+1);
    				A[i][j]=0;
    				r[i+j] = m[j] = l[i-j+N] = 0;
    			}
    		}
    	}
    	
    	static void print(int [][]A) { 
    		for(int i=0;i<N;i++) { 
    			for(int j=0;j<N;j++)
    				System.out.print(A[i][j]+" ");
    		    System.out.println();
    		}
    		System.out.println("----------------");	
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()) { 
    			N = sc.nextInt();
    			A = new int[N][N];
    			m = new int[2*N];
    			l = new int[2*N];
    			r = new int[2*N];
    			queen(0);
    			System.out.println("总方案数为："+count);
    			
    		}
    
    	}
    
    }

# F、素数环 #

**题目描述**

*  现有1,2,3…,n，要求用这些数组成一个环，使得相邻的两个整数之和均为素数，要求你求出这些可能的环。

**输入**

*  输入正整数n

**输出**

*  输出时从整数1开始逆时针输出，同一个环只输出一次,且满足条件的环应按照字典序从小到大输出。
 *  注：每一个环都从1开始。

**样例输入 Copy**

**样例输出 Copy**

1 4 3 2 5 6
    1 6 5 2 3 4

## 代码 ##

[戳我戳我!][Link 5]

import java.util.Scanner;
    
    public class Main { 
    	static int []A;
    	static int []prime;
    	static int n;
    	
    	static boolean isp(int a,int b) { 
    		int c = a+b;
    		for(int i=2;i<c;i++)
    			if(c%i==0)
    				return false;
    		return true;
    	}
    	static void solve(int cur) { 
    		if(cur==n && isp(A[0],A[n-1])) { 
    			for(int i=0;i<n;i++)
    				System.out.print(A[i]+" ");
    			System.out.println();
    		}
    		for(int i=2;i<=n;i++) { 
    			if(prime[i]==0 && isp(i,A[cur-1])) { 
    				A[cur] = i;
    				prime[i] = i;
    				solve(cur+1);
    				prime[i] = 0;
    			}
    		}
    	}
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()) { 
    			n = sc.nextInt();
    			A = new int[n];
    			A[0] = 1;
    			prime = new int[n+1];
    			solve(1);
    		}
    
    	}
    
    }

> 【小编要准备考六级了，期末考试又来了啊啊啊啊啊啊！好啦，复习去！】  
> “许多人都在等待一个安全的环境，他们希望等所有的绿灯都亮了以后再出门。抱持这种想法的人，一辈子也无法走出家门。”

[1_int_int_1]: https://blog.csdn.net/weixin_43835284/article/details/105104764
[Link 1]: https://blog.csdn.net/tingzhiyi/article/details/52218302
[Link 2]: https://blog.csdn.net/qq_41529799/article/details/81029882
[Link 3]: https://blog.csdn.net/weixin_43927892/article/details/93382446
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODIzMTE4_size_16_color_FFFFFF_t_70]: /images/20221005/c9e410c305de44d798354d8483a3cefc.png
[Link 4]: https://blog.csdn.net/weixin_43927892/article/details/93418264
[Link 5]: https://blog.csdn.net/qq_45287265/article/details/104582108