第十二周

课后练习题

A、XP的素数

题目描述

  • XP最近对素数很痴迷,特别是那些特殊的素数,其中有一类素数被称为孪生素数。其定义如下:如果一个数k是素数,k+2也是素数,那么k和k+2成为一对孪生素数。请计算一个给定区间m和n(0<m<n)中孪生素数对的个数。

输入

  • 单组输入数据 m n (0<m<n<1000)

输出

  • 请输出一行结果:区间[m,n]中孪生素数对的个数

样例输入 Copy

1 999

样例输出 Copy

35

链接:XP的素数

代码

import java.util.Scanner;

public class Main {
	public static int prime(int n){
		
		if(n==1)
			return 0;  //1不是素数,返回0
		for(int i=2;i<n;i++){
			if(n%i==0)
				return 0;
			continue;
		}
			
		return 1;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int m = sc.nextInt();
			int n = sc.nextInt();
			int sum = 0;
			
			for(int i = m;i<=n-2;i++)
				if(prime(i)==1&&prime(i+2)==1)
					sum++;
			System.out.println(sum);
		}

	}

}

B、XP的点滴

题目描述

  • XP一不留神感冒了,于是跑到校医院打点滴。打点滴真是无聊啊,他看到盐水一滴一滴地滴下来,突然想到一个问题:如果盐水有规律地滴下,先滴一滴,停一下;然后滴二滴,停一下;再滴三滴,停一下…,假设这瓶盐水一共有n毫升,每一滴是y毫升,每一滴需要的时间是一秒(假设最后一滴不到y毫升,需花费的时间也算一秒),停一下的时间也是一秒。请问XP多久能挂完这瓶盐水呢?

输入

  • 单组输入数据 n y (0<n,y<=1000)

输出

  • 输出一行结果

样例输入 Copy

10 1

样例输出 Copy

13

链接:XP的点滴

代码

import java.util.Scanner;

public class Main {
	public static int count(int []c,int n,int y){
		int temp = 0;//记录每次滴落的滴数
		for(int i=0;i<c.length;i++)//i代表中间间隔几次
			c[i] = i+1;
		int sum = 0;//总量的滴数,几滴就几秒
		double x = n/(y*1.0);
		if(x>n/y)
			sum = n/y+1;
		else
			sum = n/y;
		int j = 0;
		for(int i=0;i<c.length;i++)
			if(n>0){
				n-=c[i]*y;//记录间断次数
				j = i;
			}
		temp = j+sum;
		
		return temp;
	}

	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 y = sc.nextInt();
			int []c = new int[105];
			System.out.println(count(c,n,y));
		}
	}
}

C、今年暑假不AC

题目描述

  • “今年暑假不AC?”
  • “是的。”
  • “那你干什么呢?”
  • “看世界杯呀,笨蛋!”
  • “@#$%^&*%…”

确实如此,世界杯来了,球迷的节日也来了,估计很多ACMer也会抛开电脑,奔向电视了。
作为球迷,一定想看尽量多的完整的比赛,当然,作为新时代的好青年,你一定还会看一些其它的节目,比如新闻联播(永远不要忘记关心国家大事)、非常6+7、超级女生,以及王小丫的《开心辞典》等等,假设你已经知道了所有你喜欢看的电视节目的转播时间表,你会合理安排吗?(目标是能看尽量多的完整节目)

输入

  • 输入数据包含多个测试实例,每个测试实例的第一行只有一个整数n(n<=100),表示你喜欢看的节目的总数,然后是n行数据,每行包括两个数据Ti_s,Ti_e
    (1<=i<=n),分别表示第i个节目的开始和结束时间,为了简化问题,每个时间都用一个正整数表示。n=0表示输入结束,不做处理。

输出

  • 对于每个测试实例,输出能完整看到的电视节目的个数,每个测试实例的输出占一行。

样例输入 Copy

12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0

样例输出 Copy

5

链接:今年暑假不AC

代码

import java.util.Scanner;

public class Main {
	
	public static void swap(int[][] a,int j){
		int temp = a[j][1];
		a[j][1] = a[j+1][1];
		a[j+1][1] = temp;
		
		temp = a[j][0];
		a[j][0] = a[j+1][0];
		a[j+1][0] = temp;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n = sc.nextInt();
			if(n<=0)
				break;
			
			int [][]a = new int[n][2];
			for(int i=0;i<n;i++){
				a[i][0] = sc.nextInt();
				a[i][1] = sc.nextInt();
			}
			
			for(int i=0;i<n-1;i++)
				for(int j=0;j<n-1-i;j++)
					if(a[j][1]>a[j+1][1])
						swap(a,j);
			
			int count = 1;
			int num = a[0][1];
			for(int i=1;i<n;i++)
				if(a[i][0]>=num){
					num = a[i][1];
					count++;
				}
			System.out.println(count);
		}
	}
}

D、最优装载

题目描述

  • 使用贪心算法求解最优装载问题。

输入

  • 每组输入包括两部分, 第一行包括集装箱个数n,以及船的装载量C。 接下来n行每行则输入集装箱编号以及其重量。

输出

  • 输出包括两行,第一行为最多可装载的集装箱数量 。 第二行则为最优装载方案对应的所有集装箱编号(按照装载次序输出,用空格隔开) 。

样例输入 Copy

5 10
1 1
2 2
3 3
4 4
5 5

样例输出 Copy

4
1 2 3 4

代码

链接:最优装载

import java.util.Scanner;

public class Main {
	
	public static void swap(int[][] a,int j){
		int temp = a[j][1];
		a[j][1] = a[j+1][1];
		a[j+1][1] = temp;
		
		temp = a[j][0];
		a[j][0] = a[j+1][0];
		a[j+1][0] = temp;
	}
	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 c = sc.nextInt();
			if(n<=0)
				break;
			
			int [][]a = new int[n][2];
			for(int i=0;i<n;i++){
				a[i][0] = sc.nextInt();//编号
				a[i][1] = sc.nextInt();//重量
			}
			
			for(int i=0;i<n-1;i++)
				for(int j=0;j<n-1-i;j++)
					if(a[j][1]>a[j+1][1])
						swap(a,j);
			
			int count = 0;
			int x[] = new int[n];
			for(int i=0;i<n;i++)
				if(a[i][1]<=c){
					c-=a[i][1];
					count++;
					x[i] = a[i][0];
				}
			System.out.println(count);
			for(int i=0;i<count;i++)
				System.out.print(x[i]+" ");
			System.out.println();
		}
	}
}

E、XP的小视频

题目描述

  • XP的表哥为他推荐了一些学习计算机编程的小视频,这些视频的播放时间长短不完全相同。现在给定一段时间,你能告诉XP他最多可以看多少个视频吗?每个视频的播放时间和给定的总时间均用分钟为单位。

输入

  • 单组输入数据 第一行为m n ,m为给定时间长度(分钟)(0<n,m<=1000) ,n表示视频个数 ,接下来是n个整数代表每个视频的播放时间(每个视频播放时间为不超过1000的正整数)

输出

  • 输出一个整数代表XP最多可以看的视频数。

样例输入 Copy

84 6
65 46 18 76 79 3

样例输出 Copy

3

代码

import java.util.Arrays;
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 m = sc.nextInt();//给定时间长度
			int n = sc.nextInt();//视频个数
			int a[] = new int[n];
			for(int i=0;i<n;i++)
				a[i] = sc.nextInt();
			Arrays.sort(a);//排序,按视频长度从小到大
			int count = 0;
			for (int i=0;i<n&&a[i]<=m;i++) {
	              m -= a[i];//更新总重量
	              ++count;
	        }
			System.out.println(count);
	   }
	}
}

F、最小生成树(Prim)

题目描述

  • 使用Prim算法求图的最小生成树(MST)

输入

  • 每组数据分为两个部分,第一部分为图的点数n,和边数m, 第二部分为m行,每一行输入三个数字,前两个为两个顶点的编号,第三个为边权重。

输出

  • 最小生成树,输出时按照边的两个端点的升序输出。(先看左端点,再看右端点,端点不换位置)

样例输入 Copy

3 3
0 1 10
0 2 15
1 2 50

样例输出 Copy

0 1 10
0 2 15

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1010;
const int INF = 0x3f3f3f3f;

int n,m;
int G[MAXN][MAXN];
int g[MAXN][MAXN];
void init(){
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            G[i][j]=INF;
}

struct Edge{
    int lp;
    int rp;
    int len;
};

int cmp(const Edge &a,const Edge &b){
    if(a.lp==b.lp) return a.rp<b.rp;
    return a.lp<b.lp;
}

int main(){
    while(cin>>n>>m){
        Edge edges[m];
        init();
        int x,y,z,cnt=0;
        for(int i=0;i<m;i++){
            cin>>x>>y>>z;
            G[y][x]=z;
            G[x][y]=z;
            g[x][y]=z;
        }
        int closeset[MAXN],lowcost[MAXN],used[MAXN];
        for(int i=0;i<n;i++){//初始化
            lowcost[i]=G[0][i];
            closeset[i]=0;
            used[i]=0;            
        }
        used[0]=1;
        for(int i=1;i<n;i++){//每一次循环,找出一个到S最近的顶点
            int j=0;
            for(int k=0;k<n;k++){
                if((!used[k])&&(lowcost[k]<lowcost[j]))//k点不在S里面
                    j=k;
            }
            if(g[closeset[j]][j]==lowcost[j]){
                edges[cnt].lp=closeset[j];
                edges[cnt].rp=j;
                edges[cnt].len=lowcost[j];
            }
            else{
                edges[cnt].lp=j;
                edges[cnt].rp=closeset[j];
                edges[cnt].len=lowcost[j];
            }
            cnt++;
            used[j]=1;
            for(int k=0;k<n;k++){
                if((!used[k])&&(G[j][k]<lowcost[k])){
                    lowcost[k]=G[j][k];
                    closeset[k]=j;
                }
            }
        }
        sort(edges,edges+cnt,cmp);
        for(int k=0;k<cnt;k++){
            printf("%d %d %d\n",edges[k].lp,edges[k].rp,edges[k].len);
        }
    }
    return 0;
}

【今天下午吃了广东鱼粉,学校食堂的,不知道正不正宗,反正我挺喜欢的,嘿嘿~】
句子君:

“这是一个长满了百合花的峡谷。百合花静静地开放着,水边、坡上、岩石旁、大树下,到处都有。它们不疯不闹,也无鲜艳的颜色,仿佛它们开放着,也就是开放着,全无一点别的心思。峡谷上空的阳光是明亮的,甚至是强烈的,但因为峡谷太深,阳光仿佛要走过漫长的时间。因此,照进峡谷,照到这些百合花时,阳光已经变得柔和了,柔和得像薄薄的、轻盈得能飘动起来的雨幕。”
——曹文轩《根鸟》

上一篇:Windows XP(64位)语言包安装图文教程


下一篇:PHPStudy下载与安装