第七周习题

分手后的思念是犯贱 2023-01-13 11:59 220阅读 0赞

菜鸡记录站

  • A、Welcome
      • 代码
  • B、第K大元素
      • 代码
  • C、整数划分问题之备忘录法
      • 代码
  • D、数字三角形之备忘录法
      • 代码
  • E、数字三角形之动态规划法
      • 代码
  • F、滚球游戏
      • 代码

A、Welcome

题目描述

  • ”How happy we are, To meet friends from afar!” Welcome to Hunan University of Chinese Medicine! Hope all of you can enjoy the competition ^ v ^ Now your task is to read an integer w and output the character painting of ”HNUCM”, there are w space(s) (space are represented by dot) between two letters. Please refer to the sample for the specific format.

输入

  • There are several test files and each contains one case. The input contains only 1 integer w (1 ≤ w ≤ 2018).

输出

  • The output has 5 lines, each line has 25+4w characters which only contains ’o’(lowercase letter ’o’) and ’.’(English period ’.’)

样例输入 Copy

1
样例输出 Copy

  1. o...o.o...o.o...o.ooooo.o...o
  2. o...o.oo..o.o...o.o.....oo.oo
  3. ooooo.o.o.o.o...o.o.....o.o.o
  4. o...o.o..oo.o...o.o.....o...o
  5. o...o.o...o.ooooo.ooooo.o...o

代码

  1. import java.util.Scanner;
  3. public class Main {  
  4.     static int n = 0;
  5.     public static void output_dot(){ 
  6.         for (int i = 1; i <= n; i++)
  7.             System.out.print(".");
  8.     }
  9.     private static void output_letter(){ 
  10.         System.out.print("o...o");
  11.         output_dot();
  12.         System.out.print("o...o");
  13.         output_dot();
  14.         System.out.print("o...o");
  15.         output_dot();
  16.         System.out.print("ooooo");
  17.         output_dot();
  18.         System.out.print("o...o\n");
  20.         System.out.print("o...o");
  21.         output_dot();
  22.         System.out.print("oo..o");
  23.         output_dot();
  24.         System.out.print("o...o");
  25.         output_dot();
  26.         System.out.print("o....");
  27.         output_dot();
  28.         System.out.print("oo.oo\n");
  30.         System.out.print("ooooo");
  31.         output_dot();
  32.         System.out.print("o.o.o");
  33.         output_dot();
  34.         System.out.print("o...o");
  35.         output_dot();
  36.         System.out.print("o....");
  37.         output_dot();
  38.         System.out.print("o.o.o\n");
  40.         System.out.print("o...o");
  41.         output_dot();
  42.         System.out.print("o..oo");
  43.         output_dot();
  44.         System.out.print("o...o");
  45.         output_dot();
  46.         System.out.print("o....");
  47.         output_dot();
  48.         System.out.print("o...o\n");
  50.         System.out.print("o...o");
  51.         output_dot();
  52.         System.out.print("o...o");
  53.         output_dot();
  54.         System.out.print("ooooo");
  55.         output_dot();
  56.         System.out.print("ooooo");
  57.         output_dot();
  58.         System.out.print("o...o\n");
  59.     }
  60.     public static void main(String[]args){ 
  61.         Scanner sc = new Scanner(System.in);
  62.         n = sc.nextInt();
  63.         output_letter();
  64.     }
  65. }

链接：Welcome——记得戳我呀！

【我看了别人的文章看懂了题目的意思，可是我不会写啊，所以我把人家的代码直接拿过来了，别骂我，我会努力的，我只是修改了一些名称】

B、第K大元素

题目描述

  • 输入n个整数和一个正整数k(1<=k<=n)，输出这些整数从大到小排序后的第k个。（要求时间复杂度为O(n)，需使用随机化分区） 。

输入

  • 多组数据输入，每组第一个数字为数组的长度n, 然后接下输入n个整数，最后输入整数k(1<=k<=n)。

输出

  • 输出数组降序排序后的第k个整数。

样例输入 Copy

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

样例输出 Copy

  1. 3
  2. 6

代码

  1. import java.util.Random;
  2. import java.util.Scanner;
  4. public class Main { 
  6.     private static void swap(int[] shuzu, int i, int j) { 
  7.         int t=shuzu[i];
  8.         shuzu[i]=shuzu[j];
  9.         shuzu[j]=t;
  10.     }
  12.     private static int fenqu(int[] shuzu, int left, int right) { 
  13.         // TODO Auto-generated method stub
  14.         int r = random(left,right);
  15.         swap(shuzu,left,r);
  17.         int jizhun = shuzu[left];//基準
  19.         while (left < right) { // 最终使得枢纽之前（后）的记录均不大（小）于它
  21.             while (left < right && shuzu[right] >= jizhun)
  22.                 right--;
  24.             swap(shuzu, left, right);// 将比枢轴记录小的记录交换到低端
  26.             while (left < right && shuzu[left] <= jizhun)
  27.                 left++;
  29.             swap(shuzu, left, right); // 将比枢轴大的记录交换到高端
  30.         }
  31.         return left;
  32.     }
  34.     private static int kuaipai(int[] shuzu, int left, int right, int key) { 
  36.         if(left==right)
  37.             return shuzu[left];
  39.         int r = fenqu(shuzu,left,right);//p,q兩個端點，分區縮小範圍
  40.         int j = r-left+1;//基准前包括基准的个数，从第1小到第j小元素
  41.         if(key<=j)
  42.             return kuaipai(shuzu,left,r,key);
  43.         else
  44.             return kuaipai(shuzu,r+1,right,key-j);
  45.         }
  47.     private static int random(int a, int b) { //【a,b】
  48.         Random rand=new Random();
  49.         int k = rand.nextInt(b-a+1)+a;
  50.         return k;
  52.     }
  54.     public static void main(String[] args) { 
  55.         // TODO Auto-generated method stub
  56.         Scanner sc = new Scanner(System.in);
  58.         while (sc.hasNext()) { 
  60.             int n = sc.nextInt();
  61.                 int[] shuzu = new int[n];
  62.                 for (int i = 0; i < n; i++) { 
  63.                    shuzu[i]= sc.nextInt();
  64.                 }
  65.                 int shuju = sc.nextInt();
  66.                 int key = shuzu.length-shuju+1;
  67.                 System.out.println(kuaipai(shuzu,0,n-1,key);           
  68.         }
  69.     }
  70. }

链接：第K大元素——戳这里！

【这个题我刚开始不知道怎么做，然后就看了别人的代码，就是把求第K大元素变成了求第Z小元素，然后求出这个Z就OK，只是我懂了，但是我不会写啊，然后就把前几周写的代码拿过来，又看着别人的代码改啊】

C、整数划分问题之备忘录法

题目描述

  • 使用备忘录法编写一个程序，求一个正整数n的所有划分个数。 例如，输入3，输出3；输入4，输出5。

输入

  • 多组输入，每一组是一个正整数n。

输出

  • 输出划分数。

样例输入 Copy

  1. 3
  2. 4

样例输出 Copy

  1. 3
  2. 5

代码

  1. import java.util.Scanner;
  3. public class Main { 
  5.     static int shuzu[][]=new int[105][105];
  6.     static int n;
  7.     public static int memory(int n,int m) { 
  9.         if((n<1)||(m<1)) //小于0无意义
  10.             return 0;
  12.         if((n==1)||(m==1)) //其中一个为0, q(n,m)=0 n=1 || m=1
  13.             return 1;
  15.         if(n<m)     //q(n,m)=q(n,n)
  16.             return memory(n,n);
  18.         if(n==m){    //q(n,m)=q(n,n)=1+q(n,n-1)
  19.             if (shuzu[n-1][n-2]==0) { //数组中不存在已计算过的值
  20.                 shuzu[n-1][n-2] = memory(n,n-1);//记录下来
  21.             }
  22.             return 1 + shuzu[n-1][n-2];
  23.         }
  24.         if (n>m) {    //q(n,m)=q(n,m-1)+q(n-m,m)
  25.             if (shuzu[n-m-1][m-1]==0) { 
  26.                 shuzu[n-m-1][m-1]=memory(n-m,m);
  27.             }
  28.             if (shuzu[n-1][m-2]==0) { 
  29.                 shuzu[n-1][m-2] = memory(n,m-1);
  30.             }
  31.             return shuzu[n-1][m-2] + shuzu[n-m-1][m-1];
  32.         }
  33.         else
  34.             return 0;
  36.     }
  37.     public static void main(String[] args) {   
  38.         Scanner sc = new Scanner(System.in);  
  39.         while(sc.hasNext()) { 
  40.             n = sc.nextInt();
  41.             System.out.println(memory(n,n));  
  42.         }    
  43.     }     
  46. }

链接自取：整数划分之备忘录法——戳我戳我！

【冒个泡证明我还在~】

D、数字三角形之备忘录法

题目描述

  • 如下图所示的数字三角形，从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。编写一个程序求出最佳路径上的数字之和。
    【使用动态规划法实现】

    7 

    1.    3   8 
    2.  8   1   2

    2 7 4 4
    4 5 2 6 5

输入

  • 多组样例输入，每组第一行输入三角形的层数n，接下来n行输入三角形。

输出

  • 输出最佳路径上的数字之和。

样例输入 Copy

  1. 2
  2. 1
  3. 1 2
  4. 3
  5. 1
  6. 1 2
  7. 1 2 3

样例输出 Copy

  1. 3
  2. 6

提示

  • 路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。

代码

  1. import java.util.Scanner;
  3. public class Main {   
  4.     static int shuzu[][]=new int [105][105];
  5.     static int cbb[][]=new int[105][105];
  6.     static int n;
  7.     private static int solve(int i,int j) { 
  8.           //超出范围，结束递归
  10.           if(shuzu[i][j]>=0) 
  11.               return shuzu[i][j]; //引入备忘录保存子问题的解
  12.           if(i==n+1) 
  13.               return 0;
  14.           return shuzu[i][j]=cbb[i][j]+Math.max(solve(i+1,j),solve(i+1,j+1));
  16.           }
  18.     public static void main(String[] args) {   
  21.                 Scanner sc = new Scanner(System.in);  
  22.                 while(sc.hasNext()) { 
  23.                   n=sc.nextInt();     
  24.                           for(int i=1;i<=n;i++) { 
  25.                               for(int j=1;j<=i;j++) { 
  26.                                   cbb[i][j]=sc.nextInt();
  27.                                   shuzu[i][j]=-1;
  28.                               } 
  29.                           }
  30.                           System.out.println(solve(1,1));
  32.                       }              
  33.                 }               
  34.             }

放个链接：数字三角形之备忘录法

【希望我还能见到明天的太阳，哭晕在厕所~，一次次的失败和一次次的尝试，我麻木了，我先看个漫画】

E、数字三角形之动态规划法

题目描述

  • 如下图所示的数字三角形，从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。编写一个程序求出最佳路径上的数字之和。
    【使用动态规划法实现】

    7 

    1.    3   8 
    2.  8   1   2

    2 7 4 4
    4 5 2 6 5

输入

  • 多组样例输入，每组第一行输入三角形的层数n，接下来n行输入三角形。

输出

  • 输出最佳路径上的数字之和。

样例输入 Copy

  1. 2
  2. 1
  3. 1 2
  4. 3
  5. 1
  6. 1 2
  7. 1 2 3

样例输出 Copy

  1. 3
  2. 6

提示

  • 路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。

代码

  1. import java.util.Scanner;
  3. public class Main { 
  5.     public static void main(String[] args) { 
  6.         // TODO Auto-generated method stub
  8.             Scanner sc = new Scanner(System.in);  
  9.             while(sc.hasNext()) { 
  11.              int n = sc.nextInt();
  13.              int cbb[][] = new int[n+1][n+1];
  14.              int shuzu[][] = new int[n+1][n+1];
  16.              for(int i=1;i<=n;i++)
  17.                  for(int j=1;j<=i;j++)
  18.                     cbb[i][j] = sc.nextInt();
  21.              for(int i=1;i<=n;i++)
  22.                  shuzu[n][i] = cbb[n][i];//最后一行的每一列
  24.              for(int i=n-1;i>=1;i--)
  25.                  for(int j=1;j<=i;j++)   //自底向上DP
  26.                      shuzu[i][j]=cbb[i][j]+Math.max(shuzu[i+1][j],shuzu[i+1][j+1]);//对行遍历
  28.              System.out.println(shuzu[1][1]);
  29.             }
  30.         }

}
放个链接： 数字三角形之动态规划法

【我也不好意思说啥了，我觉得有CSDN这个地方挺好的，但是我养成了依赖性，不会做就立马搜题，也不会说自己去思考，反正我自己是深有体会的，而且最近几次上课也没有认真听讲，上课老神游，唉~觉得自己真是越来越丧了呢，得快点写了，该睡觉了】

F、滚球游戏

题目描述

  • 某滚球游戏规则如下：球从入口处（第一层）开始向下滚动，每次可向下滚动一层，直到滚至最下面一层为止。球每次可滚至左下、下方或右下三个方格中的任意一个，每个方格都有一个得分，如样例所示。第1层有1个方格，第2层有3个方格，……，以此类推，第n层有2*n-1个方格。设计一个算法，使得球从入口滚至最下面一层的总得分和最大。

输入

  • 对于每个样例，第1行的正整数n表示数字三角形的行数。（n<=100)
  • 接下来n行包含一个数字三角形，每一行包含2n-1个方格，对应有2n-1个表示得分的正整数（不超过10^5），每两个数字之间用空格隔开。
  • 每两组样例之间有一个空行。

输出

  • 球从入口（第一层）滚至最下面一层的最大得分和。

样例输入 Copy

  1. 2
  2.   3
  3. 2 1 3
  5. 3
  6.     1
  7.   2 1 2
  8. 3 4 2 1 3

样例输出 Copy

  1. 6
  2. 7

【这题我真是哭死QAQ~，我花了一天的时间在这个题目上，我起初CSDN,只找到了一个人的代码，然后我就复制过来了，结果不报错，运行不输出数据，我又去百度，我在那个preferences里勾选两个show的框，取消框里的√，我又重启又改代码，愣是没有输出，我整个人都傻了，然后我就放弃了，我想着等着我的大佬室友从自习教室回来帮我看看，然后一直等到了晚上11点多，我还在这个题目，而且提交时间快截止了，我的大佬室友之一说：“我不看JAVA代码，我比熟悉C语言”，是的没错，我又傻了，正如我现在写代码第一反应是java代码一样，看C语言我一脸懵逼，我又问了另一个大佬，好家伙，“我看不懂你的代码”，是我不配了，我自己来写吧，我把之前借鉴的那个代码的输入改了，不然它要我无限输入，我又新写了一个函数，来判断三个数的大小（得益于我的室友，她的指导还是有帮助的），然后直接用了数字三角形的那段动态规划的代码，终于，含泪告别第七周的习题了，有些时候，放手去写吧，相信自己，哭QAQ，终于可以休息会了，写个博客先！】

放个链接，就是我最初看到的那篇文章，其实不用切割空格，反正我写的代码就没用，不过还是可以看看啦：滚球游戏 ——DP

代码

  1. import java.util.Scanner;
  3. public class Main { 
  4.     public static int max_da(int i,int j,int t){ 
  5.         int a = Math.max(i, j);
  6.         int b = Math.max(j, t);
  7.         int c = Math.max(a, b);
  8.         return c;
  9.     }
  11.     public static void main(String[] args) { 
  12.         Scanner sc = new Scanner(System.in);
  13.         while(sc.hasNext()){ 
  14.             int n = sc.nextInt();
  15.             int a[][] = new int[n+1][2*n];
  16.             int p[][] = new int[n+1][2*n];
  18.                 for(int i=1;i<=n;i++)
  19.                     for(int j=1;j<=2*i-1;j++)
  20.                          a[i][j] = sc.nextInt();//每一行每一列
  22.                  for(int j=1;j<=2*n-1;j++)
  23.                      p[n][j] = a[n][j];//最后一行的每一列
  25.                  for(int i=n-1;i>=1;i--)
  26.                      for(int j=1;j<=2*i-1;j++)   //自底向上DP
  27.                          p[i][j]=a[i][j]+max_da(p[i+1][j],p[i+1][j+1],p[i+1][j+2]);//对行遍历
  29.                  System.out.println(p[1][1]);
  30.              }        
  31.         }  
  32.     }

【今天学习到的小技能：我真是好懒呀！
1、Ctrl + / 可以给选定的代码段加单行注释，取消也用这个快捷键
2、Ctrl + Shift + / 多行注释，取消也是这个，记得选中再按键哈
3、Ctrl + D 删除某一行，鼠标放在这一行
】

发表评论

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

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

相关阅读

    相关 第十七周

    一.学习 　　1.这一周基本上进入复习周了，大家都在备考当中，而我感觉这一周的效率不是很高，没有复习到多少东西，进度和16周的没有什么区别，所以自己内心还是有点小慌张 　　

    清疚清疚/ 0 赞/ 381 阅读