实验室新生娱乐赛题解

Acting2024-11-042024-11-04

新生娱乐赛题解

兹所呈现之本题解，仅为个人针对此题所持观点，其既非官方所颁布之标准答案，亦未必为最优之解法。若阁下持有更佳之思路，诚邀参与讨论。

需特此说明者，本题所标注之难度，乃基于本套试题所设定之相对难度，并非该题实际固有之难度层级。

再者，虑及多数人惯常使用之编程语言状况，本套题解特选用 C 语言予以编写。兹C水平如狗啃屎，若题解之中存在讹误之处，敬祈不吝指正。

废话不多说，开始看题：

Medium 7-5 字母直方图

题目：

读入一个字符串，对其中的字母按照不区分大小写的出现次数输出一个星号组成的直方图。

输入格式:

一行，一个不超过100字节的字符串，可能含有空格。

输出格式:

若干行，每行一个大写字母，空格后接着一排星号（*字符），星号数量与该字母的出现次数相同。为了保证图形的美观，只需要输出至少出现了2次的字母。如果字符串包含多个字母，那么按照字母首次出现的顺序输出。

输入样例:

在这里给出一组输入。例如：

Anika, buy a banana.

输出样例:

在这里给出相应的输出。例如：

A ******
N ***
B **

解析：

常规思路：遍历一遍字符串，使用有顺序的Map将出现的字符和出现的次数统计，然后顺序遍历Map，如果Map的key是字母并且value的数值大于等于2 输出。

当然，大多数同学使用C语言，LinkedHashMap 并不包含于C语言，所以我们需要换一种思路：使用二维数组存储字符的ASCII码和出现的频率。（感兴趣的同学可以提前了解）

遍历字符串，使用二维数组存储对应的字符的ASCII码和出现的次数。在遍历的同时需要判断该字符的大小写，可以规定为存储大写字母的ASCII码。
随后开始遍历数组，当某个字符的出现频率符合要求，输出。
输出：先将二维数组存储的ASCII码转化为大写字母然后使用循环输出 * 随后换行。

#include <stdio.h>
#include <string.h>
#include <ctype.h>  // 包含toupper函数的头文件  

#define MAX_INPUT_LEN 1000  // 定义输入字符串的最大长度  

int main() {
        char arr[MAX_INPUT_LEN];
    	scanf("%[^\n]",&arr);
        int n = strlen(arr);  // 计算字符串长度  
        int temp[n][2];       // 创建一个二维数组来存储字符和计数  
        int idx = 0;


        // 遍历字符串，统计字符出现次数  
        for (int i = 0; i < n; i++) {
            char x = arr[i];
            if (x == ' ') continue;  // 忽略空格  

            // 查找字符是否已经在 temp 数组中（这里为了简化，没有实现查找优化）  
            int found = 0;
            for (int j = 0; j < idx; j++) {
                if (temp[j][0] == x) {
                    temp[j][1]++;  // 如果字符已经在 temp 数组中，则增加计数  
                    found = 1;
                    break;
                }
            }

            // 如果字符不在 temp 数组中，则添加它  
            if (!found) {
                temp[idx][0] = x;
                // 如果字符是小写字母，则转换为大写字母  
                if (islower(x)) {
                    temp[idx][0] = (int)toupper(x);
                }
                temp[idx][1] = 1;
                idx++;
            }
        }

        // 打印出现次数大于或等于 2 的字符及其星号表示  
        for (int i = 0; i < idx; i++) {
            if (temp[i][1] >= 2) {
                printf("%c: ", temp[i][0]);
                for (int j = 0; j < temp[i][1]; j++) {
                    printf("*");
                }
                printf("\n");
            }
        }
    return 0;
    }

Medium 7-7 一元多项式的乘法与加法运算

原题：

设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1

输出样例:

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

解析

模拟。大部分同学可能没有理解

第一个多项式：

$$3x^{4}+(-5)x^{2}+6x^{11}+(-2)x^{0}$$

第二个多项式

$$5x^{20}+(-7)x^{4}+3x^{1}$$

根据本题的样例参考此公式。

得到的这两个多项式，先进行相乘，降序输出幂最高的系数和指数，例如以上两个多项式相乘的最高次幂的项分别相乘 3x^4 * 5x^20 结果中系数是15 幂指数是 24 所以第一行前两个输出的是 15 25

思路一：定义两个二维数组，分别存储两个多项式的指数和系数，乘法：使用嵌套循环系数相乘指数相加；加法：使用查找相同的指数，指数相同系数相加。来不及了上思路二。

思路二：定义一个结构体，存储每一项的系数和指数，使用结构体存储；同样的乘法是互相乘，所以使用嵌套循环，加法是只有相同次幂的项才可以过。

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int coef; //系数
    int exp;  //指数
} Term;

int main() {
    int n1, n2;

    // 读取第一个多项式
    scanf("%d", &n1);
    Term *poly1 = (Term *)malloc(n1 * sizeof(Term)); //开辟一个数组空间 数组的每个节点存储的是一个结构体
    for (int i = 0; i < n1; i++) {
        scanf("%d %d", &poly1[i].coef, &poly1[i].exp);
    }

    // 读取第二个多项式
    scanf("%d", &n2);
    Term *poly2 = (Term *)malloc(n2 * sizeof(Term));
    for (int i = 0; i < n2; i++) {
        scanf("%d %d", &poly2[i].coef, &poly2[i].exp);
    }

    // 计算乘积
    int maxExpMul = poly1[0].exp + poly2[0].exp;
    Term *mulResult = (Term *)calloc(maxExpMul + 1, sizeof(Term)); //开辟数组空间存储结果

    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < n2; j++) {
            int newExp = poly1[i].exp + poly2[j].exp;
            int newCoef = poly1[i].coef * poly2[j].coef;
            mulResult[newExp].coef += newCoef; //将新系数加到mulResult中相应指数的位置上。
            mulResult[newExp].exp = newExp;
        }
    }

    // 计算和
    int maxExpAdd = poly1[0].exp > poly2[0].exp ? poly1[0].exp : poly2[0].exp;
    Term *sumResult = (Term *)calloc(maxExpAdd + 1, sizeof(Term)); //开辟数组空间

    for (int i = 0; i < n1; i++) {
        sumResult[poly1[i].exp].coef += poly1[i].coef;
        sumResult[poly1[i].exp].exp = poly1[i].exp;
    }
    for (int i = 0; i < n2; i++) {
        sumResult[poly2[i].exp].coef += poly2[i].coef;
        sumResult[poly2[i].exp].exp = poly2[i].exp;
    }

    // 输出乘积
    int first = 1;
    for (int i = maxExpMul; i >= 0; i--) { 
        if (mulResult[i].coef != 0) {
            if (!first) {
                printf(" ");
            }
            printf("%d %d", mulResult[i].coef, mulResult[i].exp);
            first = 0;
        }
    }
    if (first) {
        printf("0 0");
    }
    printf("\n");

    // 输出和
    first = 1;
    for (int i = maxExpAdd; i >= 0; i--) {
        if (sumResult[i].coef != 0) {
            if (!first) {
                printf(" ");
            }
            printf("%d %d", sumResult[i].coef, sumResult[i].exp);
            first = 0;
        }
    }
    if (first) {
        printf("0 0");
    }
    printf("\n");

    // 释放内存
    free(poly1);
    free(poly2);
    free(mulResult);
    free(sumResult);

    return 0;
}

Hard 7-8 二分查找

题目：

利用二分查找找出所给出的数在数组中的下标

输入格式:

第一行输入n和m表示数组有n个数据，m表示要对m个数进行查找

输出格式:

所有输出在一行完成，行末没有多余空格和多余回车。

输入样例:

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

输出样例:

0 1 2 3 4

解析：

二分，经典算法。“二分查找只能用于有序数列，即有单调性的序列。二分查找的主要原理就是，不断通过取中间值，缩小范围，直到找到。其时间复杂度为O（logn）。” 题目没有直接说明给出的数组是有序的，是一个隐含条件；

既然是有序的数列，就不需要每次查找都从头开始遍历，只需要比对中间的值。以本题为例，给出一个升序的数组，查找x在数组中的位置，只需要每次用x比对一下中间的数，如果中间的数小于要找的x，那么x一定在中间的数的右边。反之，在左边。

大部分同学没通过的原因是时间超出范围。

#include<stdio.h>
//切记二分查找只能用于有序数列。
//二分查找的主要原理就是，不断通过取中间，缩小范围，直到找到。
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    int arr[n];//在这里设置数组，避免不必要的错误。
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    for(int j=0;j<m;j++){
        int value=0;
        scanf("%d",&value);
        int left=0;
        int right=n-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(arr[mid]>value){
                right=mid-1;//三个判断是核心。
            }
            if(arr[mid]<value){
                left=mid+1;
            }
            if(arr[mid]==value){
                if(j==m-1){
                    printf("%d",mid);//题目要求的是打印下标
                }else{//格式打印
                    printf("%d ",mid);
                }
                break;//找到直接跳出，否则无限循环，出现错误。
            }
        }
    }
    return 0;
}