天大计算机算法程序题（一）

素颜马尾好姑娘i 2022-12-26 13:28 73阅读 0赞

### 天大计算机算法程序题（一） ###

*   *   *  2019年
         *   *  完全数
             *  出勤记录
             *  双向起泡排序算法
         *  2018年
         *   *  排序
             *  简单计算器
         *  2017
         *   *  偶数拆分
             *  密码判断

### 2019年 ###

#### 完全数 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]

#include<iostream>
    using namespace std;
    const int MAXN = 1e4+4;
    bool flag[MAXN] ; // 标记一个数是否为完全数
    
    void init(){ 
      int i,sum,j;
      for(i=2;i<MAXN;i+=2){  // 现无发现奇完全数，直接i++也行
        sum = 1;
        for(j=2;j*j<=i;++j){  // 优化
          if(i%j==0)sum += j+i/j;
        }
        if(j*j==i) sum-=j; // 3*3 = 9 重复加了 需要减去
        if(sum==i){ 
          flag[i] = true;
          cout<<i<<endl;
        }// 是完全数
      }
    }
    
    int ans[MAXN]; // a[i] 表示 [0,i] 之间的完全数
    
    void solve(){ 
      init();
      for(int i=2;i<MAXN;++i){ 
        ans[i] = flag[i]?ans[i-1]+1:ans[i-1];
      } // 类似前缀和的思想
    }
    
    int main(){ 
      solve();
      int n; // 组数
      cin>>n;
      while(n--){ 
        int num1,num2;
        cin>>num1>>num2;
        cout<<ans[num2]-ans[num1]<<endl;
      }
      return 0;
    }

测试数据

3
    1 5
    2 7
    7 500

![在这里插入图片描述][20201205215214221.png]

#### 出勤记录 ####

问题描述：给定办公室的出勤记录，输出第一个到达的人和最后一个离开的人。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 1]

#include<cstdio>
    using namespace std;
    
    int copyChar(char src[],char desc[]){ 
      int i;
      for(i=0;src[i];++i)desc[i]=src[i];
      desc[i]=0;// 占位符
    }// 将src复制到desc
    
    int main(){ 
      int t,n; // 组数，数据量
      scanf("%d",&t);
      int h,m,s; // 分别表示小时 分钟 秒钟 
      char c[18],cmax[18],cmin[18];// 证件号码 
      while(t--){ 
        scanf("%d",&n);
        int hmax=-1,hmin=999999,tmp;// 分别表示最晚离开，最早到达
        while (n--){ 
          scanf("%s %d:%d:%d",c,&h,&m,&s); // 这里输入有格式，通过scanf 方便
          tmp = h*10000 + m *100 +s; // 比时间先比小时，再比分钟，最后比秒，可以直接拼接一起比字符串，这里转换数字比也行
          if (tmp<hmin) { 
            hmin = tmp;
            copyChar(c,cmin);
          }
          scanf("%d:%d:%d",&h,&m,&s);
          tmp = h*10000 + m *100 +s;
          if (tmp>hmax){ 
            hmax = tmp;
            copyChar(c,cmax);
          } 
        }
        printf("%s,%s\n",cmin,cmax);
      }
    }

数据案例

3
    1
    ME 00:00:00 23:59:59
    2
    EE 08:05:35 20:56:35
    MA 12:35:45 21:40:42
    3
    CS 15:30:28 17:00:10
    SC 08:00:00 11:25:25
    CT 21:45:00 21:58:40

![在这里插入图片描述][20201205221806840.png]

#### 双向起泡排序算法 ####

试编写一个双向起泡排序算法，要求相邻两趟向相反方向起泡。

### 2018年 ###

#### 排序 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 2]

#include<iostream>
    #include<string>
    #include<algorithm>
    using namespace std;
    const int MAXN = 1e3+3;
    
    string num[MAXN]; // 分割后的字符串
    
    string dealZero(string tmp){ 
      int i;
      for(i=0;i<tmp.size();++i){ 
        if(tmp[i]!='0')break;
      }
      string result = tmp.substr(i);
      if (result == "") return "0";
      return result;
    }// 处理字符串多余的前导0
    
    bool cmp(string A, string B){ 
      if (A.size()!=B.size())return A.size()<B.size();
      return A<B;
    } // 自定义排序规则 当字符串长的数大，同等长度直接一个个字符的比（C++ 重载了<）
    
    int main(){ 
      string s,tmp;
      getline(cin,s);// 读取一行字符串
      int ans = 0,len = s.size();
      for(int i=0;i<len;++i){ 
        if (s[i]=='5') { 
          if (tmp == "") continue; // 空串不处理
          num[ans++] = dealZero(tmp);
          tmp = "";
        }else { 
          tmp += s[i];
        }
      }
      if (tmp!="")  num[ans++] = dealZero(tmp);
      sort(num,num+ans,cmp);//排序
      for(int i=0;i<ans-1;++i){ 
        cout<<num[i]<<" ";
      }
      if (ans>0) cout<<num[ans-1]; // 末尾不多一个空格
      return 0;
    }

测试数据

00512312320507751

![在这里插入图片描述][20201206095236406.png]

#### 简单计算器 ####

问题描述：读入一个只包含+、-、\*、/的非负整数计算表达式，计算该表达式的值。  
输入：输入测试数据有若干，每个测试用例占一行，每行不超过 200 个字符，整数和运算符之间用一个空格分隔。当一行中只输入0时表示结束。  
输出：对每个测试用例输出一行，即该表达式的值，精确到小数点后 2 位。

#include<iostream>
    #include<string>
    #include<algorithm>
    #include<vector>
    #include<queue>
    #include<map>
    #include<stack>
    #include<iomanip>
    using namespace std;
    
    vector<string> split(string src, char seq){ 
      vector<string> result;
      int len = src.size(),i;
      string tmp;
      for(i=0;i<len;++i){ 
        if(src[i]==seq){ 
          if(tmp=="")continue;
          result.push_back(tmp);
          tmp = "";
        }else { 
          tmp += src[i];
        }
      }
      if (tmp != "" ) result.push_back(tmp);
      return result;
    } // 把 字符串src 根据字符seq进行分割
    
    int s2i(string src){ 
      int sum = 0, len = src.length();
      for(int i=0;i<len;++i){ 
        sum = sum*10 + src[i] - '0';
      }
      return  sum;
    }// 把字符串src转换为整形
    
    
    map<string, int> op; // 定义操作符的优先级，数大优先级大
    
    queue<string> postfixExp(string src){ 
      op["("]=op[")"]=1; // 通用处理
      op["+"]=op["-"]=2;
      op["*"]=op["/"]=3;
      vector<string> exps = split(src,' ');
      queue<string> result; // 后缀表达式结果
      stack<string> tmp ; // 中间结果
      int len = exps.size();
      for(int i=0;i<len;++i){ 
        if (exps[i][0]>='0'&&exps[i][0]<='9') {  // 表示为数字 直接入队列
          result.push(exps[i]);
        }else if (exps[i]=="("){  // 左括号直接入栈
          tmp.push(exps[i]);
        }else if (exps[i]==")") { 
          while(tmp.top()!="("){  // 将栈里面的操作符弹出到后缀表达式中，直到碰到了左括号 
            result.push(tmp.top());
            tmp.pop();
          }
          tmp.pop();// 扔掉左括号 
        }else {  // 操作符
          while(!tmp.empty()&&op[exps[i]]<=op[tmp.top()]){  // 只有当该操作符的优先级高于栈顶元素的优先级，才压入栈内 
            result.push(tmp.top());
            tmp.pop();
          }
          tmp.push(exps[i]);
        }
      }
      while(!tmp.empty()){  // 最后如果操作符栈还不空的话。依次弹出压入到队列中 
        result.push(tmp.top());
        tmp.pop();   
      }
      return result;
    }//将中缀表达式转化为后缀表达式
    
    double calc(string src){ 
      double tmp1,tmp2; // 第一操作数，第二操作数 
      queue<string> result = postfixExp(src);
      stack<double> tmp;
      string cur; // 队首元素
      while(!result.empty()){ 
        cur = result.front();
        result.pop();
        if (cur[0]>='0'&&cur[0]<='9'){ 
          tmp.push(0.0+s2i(cur));
        } else { 
          tmp2 = tmp.top();
          tmp.pop();
          tmp1 = tmp.top();
          tmp.pop();
          if (cur == "+") tmp1 += tmp2;
          else if (cur=="-") tmp1 -= tmp2;
          else if (cur =="*") tmp1 *= tmp2;
          else if (cur == "/") tmp1 /= tmp2;
          tmp.push(tmp1);
        }
      }
      return tmp.top();
    }
    
    int main(){ 
      string exp ;
      while(getline(cin,exp)){ 
        if(exp=="0")break; // 输入结束
         cout<<fixed<<setprecision(2)<<calc(exp)<<endl;
      }
      return 0;
    }

测试数据

1 + 2
    4 + 2 * 5 - 7 / 11
    4 * ( 1 + 2 )
    0

![在这里插入图片描述][20201206112721710.png]

### 2017 ###

#### 偶数拆分 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70_pic_center]

#include<iostream>
    using namespace std;
    const int MAXN = 1e4+4;
    bool number[MAXN]; // number[i] = true 表示 不是素数 这里主要是全局变量有默认初始值，bool 为false 
    
    void EratosthenesPrime(){ 
      for(int i=2;i*i<MAXN;++i){ 
        if(!number[i]){ 
          for(int j=i*i;j<MAXN;j+=i)number[j]=true;
        }
      }
    } // 埃拉托斯特尼筛法 
    
    int main(){ 
      int n;
      EratosthenesPrime();
      while(cin>>n&&n!=0){ 
        int ans = 0;
        for(int i=2,j=n/2;i<j;++i){ 
          if(!number[i]&&!number[n-i])ans++;
        }
        cout<<ans<<endl;
      }
      return 0;
    }

测试数据

30
    26
    0

![在这里插入图片描述][20201206114111757.png]

#### 密码判断 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 3]

#include<iostream>
    #include<string>
    using namespace std;
    
    bool judge(string s){ 
      int cnt1=0,cnt2=0,cnt3=0,cnt4=0;// 分别是否存在 大写字母 小写字母 数字 特殊符合 1 表示存在
      int len = s.size();
      if (len<8||len>16) return false;
      for(int i=0;i<len;++i){ 
        if (s[i]>='A'&&s[i]<='Z') cnt1 = 1;
        else if (s[i]>='a'&&s[i]<='z') cnt2 = 1;
        else if (s[i]>='0'&&s[i]<='9') cnt3 = 1;
        else if (s[i]=='`'||s[i]=='!'||s[i]=='@') cnt4 = 1;
        else if (s[i]=='#'||s[i]=='$'||s[i]=='%'||s[i]=='^') cnt4 = 1;
      }
      if (cnt1+cnt2+cnt3+cnt4>=3) return true;  
      return false;
    }
    
    int main(){ 
      int m;
      cin>>m;
      string s;
      while(m--){ 
        cin>>s;
        if (judge(s)) cout<<"YES\n";
        else cout<<"NO\n";
      }
    }

测试数据

3
    aI123d133
    Lin1@acm
    !~@@^^%1

![在这里插入图片描述][2020120612054234.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: /images/20221120/b779fd82f2804e058c85c74993aa01d0.png
[20201205215214221.png]: https://img-blog.csdnimg.cn/20201205215214221.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020120521554254.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[20201205221806840.png]: https://img-blog.csdnimg.cn/20201205221806840.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201205222318257.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[20201206095236406.png]: https://img-blog.csdnimg.cn/20201206095236406.png
[20201206112721710.png]: https://img-blog.csdnimg.cn/20201206112721710.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201206112848577.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70#pic_center
[20201206114111757.png]: https://img-blog.csdnimg.cn/20201206114111757.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201206114316941.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[2020120612054234.png]: https://img-blog.csdnimg.cn/2020120612054234.png