第十二周

2024-01-17 21:24:04

课后练习题

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下载与安装