第十二周

末蓝、 2022-10-15 04:53 279阅读 0赞

课后练习题

  • A、XP的素数
    • 代码
  • B、XP的点滴
    • 代码
  • C、今年暑假不AC
    • 代码
  • D、最优装载
    • 代码
  • E、XP的小视频
    • 代码
  • F、最小生成树（Prim）
    • 代码

A、XP的素数

题目描述

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

输入

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

输出

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

样例输入 Copy

  1. 1 999

样例输出 Copy

  1. 35

链接：XP的素数

代码

  1. import java.util.Scanner;
  3. public class Main { 
  4.     public static int prime(int n){ 
  6.         if(n==1)
  7.             return 0;  //1不是素数，返回0
  8.         for(int i=2;i<n;i++){ 
  9.             if(n%i==0)
  10.                 return 0;
  11.             continue;
  12.         }
  14.         return 1;
  15.     }
  17.     public static void main(String[] args) { 
  18.         // TODO Auto-generated method stub
  19.         Scanner sc = new Scanner(System.in);
  20.         while(sc.hasNext()){ 
  21.             int m = sc.nextInt();
  22.             int n = sc.nextInt();
  23.             int sum = 0;
  25.             for(int i = m;i<=n-2;i++)
  26.                 if(prime(i)==1&&prime(i+2)==1)
  27.                     sum++;
  28.             System.out.println(sum);
  29.         }
  31.     }
  33. }

B、XP的点滴

题目描述

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

输入

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

输出

  • 输出一行结果

样例输入 Copy

  1. 10 1

样例输出 Copy

  1. 13

链接：XP的点滴

代码

  1. import java.util.Scanner;
  3. public class Main { 
  4.     public static int count(int []c,int n,int y){ 
  5.         int temp = 0;//记录每次滴落的滴数
  6.         for(int i=0;i<c.length;i++)//i代表中间间隔几次
  7.             c[i] = i+1;
  8.         int sum = 0;//总量的滴数，几滴就几秒
  9.         double x = n/(y*1.0);
  10.         if(x>n/y)
  11.             sum = n/y+1;
  12.         else
  13.             sum = n/y;
  14.         int j = 0;
  15.         for(int i=0;i<c.length;i++)
  16.             if(n>0){ 
  17.                 n-=c[i]*y;//记录间断次数
  18.                 j = i;
  19.             }
  20.         temp = j+sum;
  22.         return temp;
  23.     }
  25.     public static void main(String[] args) { 
  26.         // TODO Auto-generated method stub
  27.         Scanner sc = new Scanner(System.in);
  28.         while(sc.hasNext()){ 
  29.             int n = sc.nextInt();
  30.             int y = sc.nextInt();
  31.             int []c = new int[105];
  32.             System.out.println(count(c,n,y));
  33.         }
  34.     }
  35. }

C、今年暑假不AC

题目描述

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

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

输入

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

输出

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

样例输入 Copy

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

样例输出 Copy

  1. 5

链接：今年暑假不AC

代码

  1. import java.util.Scanner;
  3. public class Main { 
  5.     public static void swap(int[][] a,int j){ 
  6.         int temp = a[j][1];
  7.         a[j][1] = a[j+1][1];
  8.         a[j+1][1] = temp;
  10.         temp = a[j][0];
  11.         a[j][0] = a[j+1][0];
  12.         a[j+1][0] = temp;
  13.     }
  14.     public static void main(String[] args) { 
  15.         // TODO Auto-generated method stub
  16.         Scanner sc = new Scanner(System.in);
  17.         while(sc.hasNext()){ 
  18.             int n = sc.nextInt();
  19.             if(n<=0)
  20.                 break;
  22.             int [][]a = new int[n][2];
  23.             for(int i=0;i<n;i++){ 
  24.                 a[i][0] = sc.nextInt();
  25.                 a[i][1] = sc.nextInt();
  26.             }
  28.             for(int i=0;i<n-1;i++)
  29.                 for(int j=0;j<n-1-i;j++)
  30.                     if(a[j][1]>a[j+1][1])
  31.                         swap(a,j);
  33.             int count = 1;
  34.             int num = a[0][1];
  35.             for(int i=1;i<n;i++)
  36.                 if(a[i][0]>=num){ 
  37.                     num = a[i][1];
  38.                     count++;
  39.                 }
  40.             System.out.println(count);
  41.         }
  42.     }
  43. }

D、最优装载

题目描述

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

输入

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

输出

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

样例输入 Copy

  1. 5 10
  2. 1 1
  3. 2 2
  4. 3 3
  5. 4 4
  6. 5 5

样例输出 Copy

  1. 4
  2. 1 2 3 4

代码

链接：最优装载

  1. import java.util.Scanner;
  3. public class Main { 
  5.     public static void swap(int[][] a,int j){ 
  6.         int temp = a[j][1];
  7.         a[j][1] = a[j+1][1];
  8.         a[j+1][1] = temp;
  10.         temp = a[j][0];
  11.         a[j][0] = a[j+1][0];
  12.         a[j+1][0] = temp;
  13.     }
  14.     public static void main(String[] args) { 
  15.         // TODO Auto-generated method stub
  16.         Scanner sc = new Scanner(System.in);
  17.         while(sc.hasNext()){ 
  18.             int n = sc.nextInt();
  19.             int c = sc.nextInt();
  20.             if(n<=0)
  21.                 break;
  23.             int [][]a = new int[n][2];
  24.             for(int i=0;i<n;i++){ 
  25.                 a[i][0] = sc.nextInt();//编号
  26.                 a[i][1] = sc.nextInt();//重量
  27.             }
  29.             for(int i=0;i<n-1;i++)
  30.                 for(int j=0;j<n-1-i;j++)
  31.                     if(a[j][1]>a[j+1][1])
  32.                         swap(a,j);
  34.             int count = 0;
  35.             int x[] = new int[n];
  36.             for(int i=0;i<n;i++)
  37.                 if(a[i][1]<=c){ 
  38.                     c-=a[i][1];
  39.                     count++;
  40.                     x[i] = a[i][0];
  41.                 }
  42.             System.out.println(count);
  43.             for(int i=0;i<count;i++)
  44.                 System.out.print(x[i]+" ");
  45.             System.out.println();
  46.         }
  47.     }
  48. }

E、XP的小视频

题目描述

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

输入

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

输出

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

样例输入 Copy

  1. 84 6
  2. 65 46 18 76 79 3

样例输出 Copy

  1. 3

代码

  1. import java.util.Arrays;
  2. import java.util.Scanner;
  4. public class Main { 
  6.     public static void main(String[] args) { 
  7.         // TODO Auto-generated method stub
  8.         Scanner sc = new Scanner(System.in);
  9.         while(sc.hasNext()){ 
  10.             int m = sc.nextInt();//给定时间长度
  11.             int n = sc.nextInt();//视频个数
  12.             int a[] = new int[n];
  13.             for(int i=0;i<n;i++)
  14.                 a[i] = sc.nextInt();
  15.             Arrays.sort(a);//排序，按视频长度从小到大
  16.             int count = 0;
  17.             for (int i=0;i<n&&a[i]<=m;i++) { 
  18.                   m -= a[i];//更新总重量
  19.                   ++count;
  20.             }
  21.             System.out.println(count);
  22.        }
  23.     }
  24. }

F、最小生成树（Prim）

题目描述

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

输入

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

输出

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

样例输入 Copy

  1. 3 3
  2. 0 1 10
  3. 0 2 15
  4. 1 2 50

样例输出 Copy

  1. 0 1 10
  2. 0 2 15

代码

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const int MAXN = 1010;
  5. const int INF = 0x3f3f3f3f;
  7. int n,m;
  8. int G[MAXN][MAXN];
  9. int g[MAXN][MAXN];
  10. void init(){ 
  11.     for(int i=0;i<n;i++)
  12.         for(int j=0;j<n;j++)
  13.             G[i][j]=INF;
  14. }
  16. struct Edge{ 
  17.     int lp;
  18.     int rp;
  19.     int len;
  20. };
  22. int cmp(const Edge &a,const Edge &b){ 
  23.     if(a.lp==b.lp) return a.rp<b.rp;
  24.     return a.lp<b.lp;
  25. }
  27. int main(){ 
  28.     while(cin>>n>>m){ 
  29.         Edge edges[m];
  30.         init();
  31.         int x,y,z,cnt=0;
  32.         for(int i=0;i<m;i++){ 
  33.             cin>>x>>y>>z;
  34.             G[y][x]=z;
  35.             G[x][y]=z;
  36.             g[x][y]=z;
  37.         }
  38.         int closeset[MAXN],lowcost[MAXN],used[MAXN];
  39.         for(int i=0;i<n;i++){ //初始化
  40.             lowcost[i]=G[0][i];
  41.             closeset[i]=0;
  42.             used[i]=0;            
  43.         }
  44.         used[0]=1;
  45.         for(int i=1;i<n;i++){ //每一次循环，找出一个到S最近的顶点
  46.             int j=0;
  47.             for(int k=0;k<n;k++){ 
  48.                 if((!used[k])&&(lowcost[k]<lowcost[j]))//k点不在S里面
  49.                     j=k;
  50.             }
  51.             if(g[closeset[j]][j]==lowcost[j]){ 
  52.                 edges[cnt].lp=closeset[j];
  53.                 edges[cnt].rp=j;
  54.                 edges[cnt].len=lowcost[j];
  55.             }
  56.             else{ 
  57.                 edges[cnt].lp=j;
  58.                 edges[cnt].rp=closeset[j];
  59.                 edges[cnt].len=lowcost[j];
  60.             }
  61.             cnt++;
  62.             used[j]=1;
  63.             for(int k=0;k<n;k++){ 
  64.                 if((!used[k])&&(G[j][k]<lowcost[k])){ 
  65.                     lowcost[k]=G[j][k];
  66.                     closeset[k]=j;
  67.                 }
  68.             }
  69.         }
  70.         sort(edges,edges+cnt,cmp);
  71.         for(int k=0;k<cnt;k++){ 
  72.             printf("%d %d %d\n",edges[k].lp,edges[k].rp,edges[k].len);
  73.         }
  74.     }
  75.     return 0;
  76. }

Java代码：

  1. import java.util.Arrays;
  2. import java.util.Scanner;
  4. public class Main { 
  5.     public static int n;
  6.     public static int [][]c = new int[1000][1000];
  8.     public static void prim(int n){ 
  9.         class Edge implements Comparable{ 
  10.             int u,v,w;//这个类用来存边
  11.             public Edge(int u,int v,int w){ 
  12.                 this.u = u;
  13.                 this.v = v;
  14.                 this.w = w;
  15.             }
  17.             @Override
  18.             public int compareTo(Object o) { //重写排序规则
  19.                 // TODO Auto-generated method stub
  20.                 Edge edge = (Edge)o;
  21.                 if(edge.u!=this.u)
  22.                     return this.u-edge.u;
  23.                 return this.v-edge.v;
  24.             }
  26.         }
  27.         Edge e[] = new Edge[n-1];
  28.         float []lowcost = new float[n+1];//最短距离
  29.         int []closest = new int[n+1];//邻居
  30.         boolean []s = new boolean[n+1];//顶点是否被访问
  32.         s[1] = true;
  33.         for(int i=2;i<=n;i++){ 
  34.             lowcost[i] = c[1][i];
  35.             closest[i] = 1;
  36.             s[i] = false;
  37.         }
  39.         for(int i=1;i<n;i++){ 
  40.             float min = Float.MAX_VALUE;
  41.             int j = 1;
  42.             for(int k=2;k<=n;k++)
  43.                 if((lowcost[k]<min)&&(!s[k])){ 
  44.                     min = lowcost[k];
  45.                     j = k;
  46.                 }
  47.             if(c[closest[j]][j]>0)//先存下来
  48.                 e[i-1] = new Edge((closest[j]-1),(j-1),c[closest[j]][j]);
  49.             else
  50.                 e[i-1] = new Edge((j-1),(closest[j]-1),(-1)*c[closest[j]][j]);
  52.             s[j] = true;
  53.             for(int k=2;k<=n;k++)
  54.                 if((c[j][k]<lowcost[k])&&(!s[k])){ 
  55.                     lowcost[k] = Math.abs(c[j][k]);
  56.                     closest[k] = j;
  57.                 }
  59.         }
  60.         //开始处理结果集
  61.         Arrays.sort(e);
  62.         for(int i=0;i<n-1;i++){ 
  63.             Edge x = e[i];
  64.             System.out.println(x.u+" "+x.v+" "+x.w);
  65.         }
  66.     }
  68.     public static void main(String[] args) { 
  69.         // TODO Auto-generated method stub
  70.         Scanner sc = new Scanner(System.in);
  71.         while(sc.hasNext()){ 
  72.             int n = sc.nextInt();//点数
  73.             int m = sc.nextInt();//边数
  74.             for(int i=1;i<=n;i++)
  75.                 for(int j=1;j<=n;j++)
  76.                     c[i][j] = 10000;
  78.             for(int i=1;i<=m;i++){ 
  79.                 int x = sc.nextInt();
  80.                 int y = sc.nextInt();
  81.                 int z = sc.nextInt();
  82.                 ++x;
  83.                 ++y;
  84.                 c[x][y]=z;
  85.                 c[y][x]=-1*z;
  86.             }
  87.             prim(n);
  88.         }
  89.     }
  90. }

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

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

发表评论

表情：
评论列表 （有 0 条评论，279人围观）

还没有评论，来说两句吧...

相关阅读

    相关 第十周 任务二

    实验目的：学会使用循环控制语句解决实际问题 实验内容：编写多分支选择结构程序，根据个人月收入总额，计算出应缴税款和税后收入。 include <iostrea

    以你之姓@以你之姓@/ 0 赞/ 315 阅读

    相关 第十二周 任务一

    /【任务1】理解基类中成员的访问限定符和派生类的继承方式 由下面派生类Student1对基类Student的继承…… （1）请修改基类中成员的访问限

    清疚清疚/ 0 赞/ 385 阅读