关于程序员:数据结构荣誉课第一次实验解题报告

一、反复计数
题目
在一个无限的正整数序列中，有些数会多次重复呈现。请你统计每个数的呈现次数，而后按数字在序列中第一次呈现的地位程序输入数及其次数。
输出格局:
第1行，1个整数N，示意整数的个数，(1≤N≤50000)。

第2行，N个正整数，每个整数x 都满足 1 ≤ x ≤2000000000。

输入格局:
若干行，每行两个用一个空格隔开的数，第一个是数列中呈现的数，第二个是该数在序列中呈现的次数。

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

12
8 2 8 2 2 11 1 1 8 1 13 13

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

解题思路
题目比较简单，我是先建设了一个构造体来示意这个数与它呈现的次数，想到的第一种办法就是每次读入一个数就对构造体数组进行遍历，如果存在该数count就+1否则就将这个数退出到构造体数组中，尽管我晓得这样很大概率会超时，但我还是吧这种办法打了下来碰碰运气（过后并不会map，呜呜呜）第一次并没有通过果然被卡了工夫，然而改了改代码就过了，哈哈哈。

参考代码

#include<stdio.h>
#define MAX 50001
 struct list{
    int num;
    int count;
};
int t=1;
int main(){
    struct list a[MAX];
    int N;
    scanf("%d",&N);
    int i,j;
    int x;
    scanf("%d",&x);
    a[0].num=x;
    a[0].count=1;
    for(i=1;i<N;i++)
    {
        scanf("%d",&x);
        for(j=0;j<t;j++)
        {
            if(a[j].num==x) { a[j].count++; break; } 
        }
        if(j==t)
        {
            t++;
            a[j].num=x;
            a[j].count=1;
        }
    }
    for(i=0;i<t;i++){
        printf("%d %d",a[i].num,a[i].count);
        if(i!=t-1) printf("\n");
    }
    return 0;
}

二、报数游戏
题目
n集体围成一圈，从1开始顺次编号，做报数游戏。现指定从第1集体开始报数，报数到第m集体时，该人出圈，而后从其下一个人从新开始报数，仍是报数到第m集体出圈，如此反复上来，直到所有人都出圈。总人数有余m时将循环报数。请输入所有人出圈的程序。
输出格局:
一行，两个整数n和m。n示意游戏的人数，m示意报数出圈的数字，1≤n≤50000，1≤m≤100.

输入格局:
一行，n个用空格分隔的整数，示意所有人出圈的程序

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

5 2

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

2 4 1 5 3

解题思路
这个题就是一个典型的约瑟夫环问题，在大一上初学C语言的时候在慕课上就做过相似的作业不过那个是叫猴子选大王。这个题的思路也很简略就是建设一个数组来保留每个人的编号，之后每次出队都将该编号输入并将其删除（就是把前面的所有编号顺次前移），这样最终数组中剩下的一个就是最初出圈的（也就是大王）。

参考代码

#include<stdio.h>
int main()
{
    int n;
    int m;
    int i,j=0;
    long N[500001];
    scanf("%d %d",&n,&m);
    for(i=0;i<n;i++)
    {
        N[i]=i+1;
    }
    while(n>1)
    {
        j=(j+m-1)%n;
        printf("%ld ",N[j]);
        for(i=j;i<n-1;i++)
        {
            N[i]=N[i+1];
        }
        n--;
    }
    printf("%ld\n",N[0]);
    return 0;
    
}

三、算数表达式计算
题目
工作: 计算算术表达式的值。

算术表达式按中断给出，以=号完结，包含+,-,/四种运算和(、)分隔符。运算数的范畴是非负整数，没有正负符号，小于等于109 。

计算过程中,如果呈现除数为0的状况,表达式的后果为”NaN” ; 如果两头后果超出32位有符号整型范畴,仍按整型计算，不用非凡解决。输出保障表达式正确。

输出格局:
一行，包含1个算术表达式。算术表达式的长度小于等于1000。

输入格局:
一行，算术表达式的值。

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

(1+30)/3=

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

解题思路
这个题是谷老师提前走漏给咱们的所以我也是提前打了一下这个题还去特意温习了一下中断表达式转后缀表达式，温习温习发现上课的时候讲的是变转后缀边计算，思路就是建设两个栈来保留操作数和操作符，开始时将中断表达式保留到一个字符串当中，因为题目曾经明确所输出的肯定是非法的所以不必思考别的接下来就是从左一次读表达式如果是操作数就入栈，如果是操作符就须要依据操作符栈来决定下一步的操作，如果栈空则入栈，否则判断栈顶元素与以后元素的优先级如果以后元素优先级高则入栈（‘(’的优先级最高），如果是‘)’则将元素安抚栈中的运算符一次出栈并计算操作数，直至遇到‘(’，如果以后运算符优先级小于等于栈顶运算符等级则先对该运算符进行运算（不入栈）。读完之后如果运算符栈不空则将其全副出栈并计算即可。

参考代码

#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<string.h>
#include<iostream>
#define L 1001
using namespace std;
stack<int> Stacknum;
stack<char> Stackchar;
void Fun(char e){
    int temp1,temp2;
    temp1=Stacknum.top(); Stacknum.pop();
    temp2=Stacknum.top(); Stacknum.pop();
    switch(e)
    {
        case '+' :  Stacknum.push(temp2+temp1); break;
        case '-' :  Stacknum.push(temp2-temp1); break;
        case '*' :  Stacknum.push(temp2*temp1); break;
        case '/' :  
            if(temp1==0) {printf("NaN");exit(0);}
            else
            Stacknum.push(temp2/temp1); break;
    }
} 
int main(){
    char str[L];
    scanf("%s",str);
    int i;
    int temp;
    for(i=0;str[i]!='=';i++)
    {
        if(str[i]>='0'&&str[i]<='9')
        {
            temp=str[i]-'0';
            while(str[i+1]!='=')
            {
                if(str[i+1]>='0'&&str[i]<='9')
                {
                    temp=temp*10+str[i+1]-'0';
                    i++;
                }
                else break;
            }
            Stacknum.push(temp);
        }
        else
        {
            char tmp;
            if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'||str[i]=='('||str[i]==')')
            {
                switch(str[i])
                {
                    case '+' :
                        if(Stackchar.empty()) {Stackchar.push('+');break;}
                        tmp=Stackchar.top();
                        if(tmp!='+'&&tmp!='-'&&tmp!='*'&&tmp!='/') Stackchar.push('+');
                        else
                        {
                            while(!Stackchar.empty()&&tmp!='(')
                            {
                                Stackchar.pop();
                                Fun(tmp);
                                if(Stackchar.empty()) break;
                                else tmp=Stackchar.top();
                            }
                            Stackchar.push('+');
                        }
                        break;
                    case '-' :
                        if(Stackchar.empty()) {Stackchar.push('-');break;}
                        tmp=Stackchar.top();
                        if(tmp!='+'&&tmp!='-'&&tmp!='*'&&tmp!='/') Stackchar.push('-');
                        else
                        {
                            while(!Stackchar.empty()&&tmp!='(')
                            {
                                Stackchar.pop();
                                Fun(tmp);
                                if(Stackchar.empty()) break;
                                else tmp=Stackchar.top();
                            }
                            Stackchar.push('-');
                        }
                        break;
                    case '*' :
                        if(Stackchar.empty()) {Stackchar.push('*');break;}
                        tmp=Stackchar.top();
                        if(tmp!='*'&&tmp!='/') Stackchar.push('*');
                        else
                        {
                            while((tmp=='*'||tmp=='/')&&tmp!='(')
                            {
                                Stackchar.pop();
                                Fun(tmp);
                                if(Stackchar.empty()) break;
                                else tmp=Stackchar.top();
                            }
                            Stackchar.push('*');
                        }
                        break;
                    case '/' :
                        if(Stackchar.empty()) {Stackchar.push('/');break;}
                        tmp=Stackchar.top();
                        if(tmp!='*'&&tmp!='/') Stackchar.push('/');
                        else
                        {
                            while((tmp=='*'||tmp=='/')&&tmp!='(')
                            {
                                Stackchar.pop();
                                Fun(tmp);
                                if(Stackchar.empty()) break;
                                else tmp=Stackchar.top();
                            }
                            Stackchar.push('/');
                        }
                        break;
                    case '(' :
                        Stackchar.push('(');
                        break;
                    case ')' :
                        tmp=Stackchar.top();
                        while(tmp!='(')
                        {
                            Stackchar.pop();
                            Fun(tmp);
                            tmp=Stackchar.top();
                        }
                        Stackchar.pop();
                        break;
                }
            }
        }
    }
    while(!Stackchar.empty())
    {
        char tmp=Stackchar.top();
        Stackchar.pop();
        Fun(tmp);
    }
    temp=Stacknum.top();
    printf("%d",temp);
    return 0;
}

四、最青睐的序列
题目
小唐这段时间在钻研序列。拿来N个整数的序列，他给序列中的每个整数都赋予一个青睐值。青睐值也是整数，有正有负，越大表明越喜爱。他想晓得，如何从序列中间断取最多m个数，他取得青睐值最大。1≤N≤500000，1≤m≤N。

输出格局:
第一行是两个整数N,m。别离代表序列中数的个数以及能取的最多个数。

第二行用空格隔开的N个整数，第i个整数Li代表他对第i个数的青睐值。│Li│≤1000

输入格局:
一行，三个数，示意取得最大青睐值，及第一个取最大青睐值的区间。

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

5 2
1 4 5 2 3

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

9 2 3

解题思路
因为在之前的分割中做过前缀和的题所以看到这道题首先想到了用前缀和来保留青睐值的和，这样能节俭一些工夫，第一次做的时候并没有看清楚题意，认为是找m个数的最大区间，还认为为啥这么简略就把代码实现了一遍，后果总是有几个测试点过不去，等到课后做题的时候才发现是最大m个，因为青睐值也可能是负值，在课上听了同学是用枯燥队列做的，谷老师心里的解法也是枯燥队列，而且枯燥队列就是用来解决求区间的最大最小值问题的，所以我学习了同学得思路与代码，创立了一个双端队列来实现，要实现枯燥队列须要保护它的枯燥性与区间长度。

参考代码

#include<stdio.h>
#include<iostream>
#include<deque> 
using namespace std;
deque<int> mon_deq;
int main(){
    long long sum[500000];
    int left,right;//左右端点
    long long max=0;//最大青睐值
    int N,m;
    scanf("%d%d",&N,&m);
    int i,j;
    sum[0]=0;
    for(i=1;i<=N;i++)
    {
        scanf("%lld",&sum[i]);
        sum[i]+=sum[i-1];
    }
    mon_deq.push_front(0);
    for(i=1;i<=N;i++)
    {
        while(!mon_deq.empty()&&sum[mon_deq.front()]>sum[i])
            mon_deq.pop_front();
        mon_deq.push_front(i);
        while(!mon_deq.empty()&&(i-mon_deq.back()>m))
            mon_deq.pop_back();
        if(max<sum[i]-sum[mon_deq.back()])
        {
            max=sum[i]-sum[mon_deq.back()];
            left=mon_deq.back()+1;
            right=i;
        }
    }
    printf("%lld %d %d",max,left,right);
    return 0;
}

关于程序员:数据结构荣誉课第一次实验解题报告

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于程序员:数据结构荣誉课第一次实验解题报告

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

发表回复取消回复