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

桃扇骨 2022-12-26 15:27 173阅读 0赞

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

*   *   *  2016年
         *   *  统计
             *  最长回文子串长度
         *  2015年
         *   *  求正整数的根
             *  单词反转
         *  2014年
         *   *  解方程
             *  判断子串

### 2016年 ###

#### 统计 ####

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

#include<iostream>
    #include<string>
    using namespace std;
    
    int main(){ 
      int m,n;
      cin>>m;
      string s;
      for(int i=1;i<=m;++i){ 
        cin>>n;
        int cnt=0;
        while(n--){ 
          cin>>s;
          if (s=="sheep")cnt++;
        }
        cout<<"case"<<i<<":this list contains "<<cnt<<" sheep\n";
      }
      return 0;
    }

测试数据

3
    5
    sheep sheeps shep shepr shepp
    7
    sheep SHEEP Sheep sheep shepr sheer sherp
    3
    sheep sheep sheep.....

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

#### 最长回文子串长度 ####

给出一个只由小写英文字符 a,b,c…y,z 组成的字符串 S,求 S 中最长回文串的长度，回文就是正反读都是一样的字符串,如 aba, abba 等

#include<iostream>
    #include<string>
    #include<vector>
    using namespace std;
    
    string longestPalindrome(string s){ 
      string tmp = "$#";
      for (int i=0;i<s.size();i++){  //首先构造出新的字符串
        tmp += s[i];
        tmp += '#';
      }
        //cout<<tmp<<endl;
      vector<int> rd(tmp.size(), 0);//用一个辅助数组来记录最大的回文串长度，注意这里记录的是新串的长度，原串的长度要减去1
      int pos = 0, mx = 0;
      int start = 0, maxLen = 0;
      for (int i = 1; i < tmp.size(); i++) { 
        rd[i] = i < mx ? min(rd[2 * pos - i], mx - i) : 1;
        while (i+rd[i]<tmp.size() && i-rd[i]>0 && tmp[i + rd[i]] == tmp[i - rd[i]])//这里要注意数组越界的判断，源代码没有注意，release下没有报错
            rd[i]++;
        if (i + rd[i] > mx) { //如果新计算的最右侧端点大于mx,则更新pos和mx
          pos = i;
          mx = i + rd[i];
        }
        if (rd[i] - 1 > maxLen) { 
          start = (i - rd[i]) / 2;
          maxLen = rd[i] - 1;
        }
      }
      return s.substr(start, maxLen);
    }
    
    int main(){ 
      int n;
      cin>>n;
      string s;
      while(n--){ 
        cin>>s;
        cout<<longestPalindrome(s).size()<<endl;
      }
      return 0;
    }

测试数据

2
    aaaa
    abac

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

### 2015年 ###

#### 求正整数的根 ####

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

#include<iostream>
    using namespace std;
    
    int getBitSum(int n){ 
      int sum = 0;
      while(n){ 
        sum += n%10;
        n/=10;
      }
      return sum;
    }
    
    int main(){ 
      int n;
      while(cin>>n&&n!=0){ 
        while(n/10 != 0){ 
          n = getBitSum(n);
        }
        cout<<n<<endl;
      }
      return 0;
    }

测试数据

24
    39
    2
    0

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

#### 单词反转 ####

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

#include<iostream>
    #include<string>
    #include<vector>
    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进行分割
    
    string reverse(string s){ 
      string tmp;
      for(int i=s.length()-1;i>=0;--i)tmp += s[i];
      return tmp;
    }
    
    int main(){ 
      int n,len;
      cin>>n;
      cin.ignore();// 读取第一行后面的换行符 不然getline会读取到
      string s;
      while(n--){ 
        getline(cin,s);
        vector<string> result = split(s,' ');
        len = result.size()-1;
        for(int i=0;i<len;++i){ 
          cout<<reverse(result[i])<<" ";
        }
        if (len>=0) cout<<reverse(result[len])<<endl;
      }
      return 0;
    }

测试数据

3
    I am happy today
    To be or not to be
    I want to win the practice contest

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

### 2014年 ###

#### 解方程 ####

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

#include<iostream>
    using namespace std;
    
    int main(){ 
      int n,a,b;
      cin>>n;
      while(n--){ 
        cin>>a>>b;
        cout<<(a+b)/2<<" "<<(a-b)/2<<endl;
      }
      return 0;
    }

测试数据

2
    5 1
    48 22

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

#### 判断子串 ####

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

#include<iostream>
    using namespace std;
    
    int main(){ 
      int n;
      cin>>n;
      string sub,str;
      while(n--){ 
        cin>>sub>>str;
        int i=0,j=0,sublen = sub.length(),strlen =  str.length();
        while(i<sublen&&j<strlen){ 
          if(sub[i]==str[j]) { 
            i++;
            j++;
          }else { 
            j++;
          }
        }
        if (i==sublen) cout<<"Yes\n";
        else cout<<"No\n";
      }
      return 0;
    }

测试数据

2
    sequence subsequence
    person compression

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: /images/20221120/340074da4d2249f3a274046c232e44d3.png
[20201206125352677.png]: /images/20221120/0ce350d9c2294f59bda7fda360525dc7.png
[20201206190917955.png]: /images/20221120/966f2bbb6b9346a88f8861ba123035a3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 1]: /images/20221120/466f1c9a159d47f3b7a5a7e81fdc3b85.png
[20201206191755595.png]: /images/20221120/77d59f35db9447cbbeae1dc24602bdd0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 2]: /images/20221120/f9456fc947b34f98b6320d5fb93e8684.png
[20201206193448231.png]: /images/20221120/715549c75df349a6b06827a8eaba59ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201206193652111.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[20201206194050290.png]: https://img-blog.csdnimg.cn/20201206194050290.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020120619415372.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[20201206204101615.png]: https://img-blog.csdnimg.cn/20201206204101615.png