第十五周.

阅读量：3969 次

发布时间：2019-05-24

本文共 4153 字，大约阅读时间需要 13 分钟。

十五周

A、1的个数

题目描述

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

输入

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

输出

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

样例输入 Copy

样例输出 Copy

代码

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

代码

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)

C、又是一道简单题

题目描述

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

输入

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

输出

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

样例输入 Copy

278449121

样例输出 Copy

Case 1: 2Case 2: 0

代码

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 31 21 32 3

样例输出 Copy

1 2 31 3 22 1 32 3 13 1 23 2 1

代码

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后问题

输入

皇后的个数

输出

每一种方案及总方案数

样例输入 Copy

样例输出 Copy

0 1 0 00 0 0 23 0 0 00 0 4 0----------------0 0 1 02 0 0 00 0 0 30 4 0 0----------------总方案数为：2

代码

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

F、素数环

题目描述

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

输入

输入正整数n

输出

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

注：每一个环都从1开始。

样例输入 Copy

样例输出 Copy

1 4 3 2 5 61 6 5 2 3 4

代码

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