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

﹏ヽ暗。殇╰゛Y 2022-12-27 01:52 141阅读 0赞

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

*   *   *  最小数
         *  求并集
         *  寻找素数对
         *  亲和数
         *  第几天
         *  前m大数
         *  展开字符串
         *  进制转换
         *  素数判断

### 最小数 ###

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

#include<iostream>
    #include<string>
    #include<algorithm>
    using namespace std;
    
    /* 对于该题的结果是存在数字字符串序列 a[0],a[1],....a[n] 使用拼接最小 即 相邻字符串之间 如a[0],a[1] a[0]+a[1] < a[1][0] C++的字符串比较，也是根据字符串的ascii 比较 */
    
    bool cmp(string A,string B){ 
      return A+B<B+A;
    }
    const int MAXN = 1e4+4;
    string num[MAXN];
    
    int main(){ 
      int n;
      cin>>n;
      for(int i=0;i<n;++i){ 
        cin>>num[i];
      }
      sort(num,num+n,cmp);
      for(int i=0;i<n;++i)cout<<num[i];
      return 0;
    }

测试数据

3
    3 32 321

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

### 求并集 ###

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

#include<iostream>
    #include<set>
    using namespace std;
    
    /* 利用c++ set 集合 排序，且不重复， 把数组A,B的元素直接插入集合中即可 或者 合并数组排序 去重 */
    
    int main(){ 
      int n,m,d;
      while(cin>>n>>m){ 
        set<int> s;
        for(int i=0;i<n+m;++i){ 
          cin>>d;
          s.insert(d);
        }
        for(set<int>::iterator iter=s.begin();iter!=s.end();++iter){ 
          cout<<*iter<<" ";
        }
        cout<<endl;
      }
      return 0;
    }

测试数据

1 2
    1 
    2 3
    1 2
    1 
    1 2

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

### 寻找素数对 ###

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

#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){ 
        for(int j=n/2-1;j>1;--j){  // -1 是例如 14 = 7+7 这种情况
          if (!number[j]&&!number[n-j]){ 
            cout<<j<<" "<<n-j<<endl;
            break;
          }
        }// 要寻找最近的素数，从中间值向两边搜索
      }
      return 0;
    }

测试数据

14 20 30

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

### 亲和数 ###

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

#include<iostream>
    using namespace std;
    
    int factorSum(int n){ 
      int sum = 1,j;
      for(j=2;j*j<=n;++j){  // 优化
        if(n%j==0)sum += j+n/j;
      }
      if(j*j==n) sum-=j; // 3*3 = 9 重复加了 需要减去
      return sum;
    }// 求数n的因数和
    
    int main(){ 
      int m,a,b;
      cin>>m;
      while(m--){ 
        cin>>a>>b;
        if (factorSum(a)==b&&factorSum(b)==a)cout<<"YES\n";
        else cout<<"NO\n";
      }
      return 0;
    }

测试数据

2
    220 284
    100 200

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

### 第几天 ###

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

#include<cstdio>
    using namespace std;
    
    bool isLeap(int n){ 
      return (n%400==0)||(n%100!=0&&n%4==0); 
    }
    
    int a[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31};// a[i] 表示平年第i月的天数
    
    int main(){ 
      int year,month,day;
      while(~scanf("%d/%d/%d",&year,&month,&day)){ //scanf 未读到数据时会返回-1 ，~ 表示按位取反 得到0 循环结束
        int sum = day;
        for(int i=1;i<month;++i)sum+=a[i];
        if (isLeap(year)&&month>2)sum++;
        printf("%d\n",sum);
      }
      return 0;
    }

测试数据

1985/1/20
    2006/3/12

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

### 前m大数 ###

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

#include<iostream>
    #include<algorithm>
    using namespace std;
    const int MAXN = 1e6+6;
    int a[MAXN];
    int sum[MAXN];
    
    bool cmp(int a,int b){ 
      return a>b;
    }// 从大到小排序
    
    int main(){ 
      int n,m;
      while(cin>>n>>m){ 
        for(int i=0;i<n;++i)cin>>a[i];
        sort(a,a+n,cmp);
        int cnt = 0, N = min(n,100);// 取一部分即可
        for(int i=0;i<N;++i){ 
          for(int j=i+1;j<N;++j)sum[cnt++]=a[i]+a[j];
        }
        sort(sum,sum+cnt,cmp);
        for(int i=0;i<m-1;++i)cout<<sum[i]<<" ";
        cout<<sum[m-1]<<endl;
      }
      return 0;
    }

测试数据

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

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

### 展开字符串 ###

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

#include<iostream>
    #include<string>
    #include<stack>
    using namespace std;
    
    bool isDigit(char c){ 
      return c>='0'&&c<='9';
    } // 判断字符c是否为数字
    
    bool isAlpha(char c){ 
      return (c>='A'&&c<='Z')||(c>='a'&&c<='z');
    } // 判断字符c是否为字母
    
    string exStr(string s){ 
      stack<char> res;
      int times;
      for(int i=0,len=s.size();i<len;++i){ 
        if(isDigit(s[i])||s[i]=='(')res.push(s[i]);
        else if(isAlpha(s[i])) { 
          if(isDigit(res.top())){  // 一个字符的重复
            times = res.top() - '0';
            res.pop();
            while(times--)res.push(s[i]);
          }else res.push(s[i]);
        }else if(s[i]==')'){ 
          string tmp;
          while(res.top()!='('){ 
            tmp.insert(tmp.begin(),res.top());
            res.pop();
          }
          res.pop();//弹出左括号
          if(res.empty()||!isDigit(res.top())) times=1; //省略1的写法
          else { 
            times = res.top() - '0';
            res.pop();
          }
          while(times--){ 
            for(int j=0,jlen=tmp.size();j<jlen;++j)res.push(tmp[j]);
          }
        }
      }
      string tmp;
      while(!res.empty()){ 
        tmp.insert(tmp.begin(),res.top());
        res.pop();
      }
      return tmp;
    }
    
    int main(){ 
      int n;
      cin>>n;
      string s;
      while(n--){ 
        cin>>s;
        cout<<exStr(s)<<endl;    
      }
      return 0;
    }

测试数据

2
    1(1a2b1(ab)1c)
    3(ab2(4ab))

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

### 进制转换 ###

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

#include<iostream>
    #include<string>
    using namespace std;
    
    string toRadix(int n,int r){ 
      if (n==0) return "0";
      string tmp = "";
      string flag = "";
      if (n<0){ 
        flag = "-";
        n*=-1;
      }
      while(n){ 
        int d = n%r;
        if (d<10) tmp = char('0'+d) + tmp;
        else tmp = char('A'+d-10)+tmp;
        n/=r;
      }
      return flag+tmp;
    }
    
    
    int main(){ 
      int n,r;
      while(cin>>n>>r){ 
        cout<<toRadix(n,r)<<endl;
      }
      return 0;
    }

测试数据

7 2
    23 12
    -4 3

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

### 素数判断 ###

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

#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 x,y;
      EratosthenesPrime();
      while(cin>>x>>y){ 
       if(x==0&&y==0)break;
       bool flag=true;
       for(int i=x;i<=y;++i){ 
         if(number[i*i+i+41]){ 
            flag = false;
            break;
         }
       }
       if (flag) cout<<"OK\n";
       else cout<<"Sorry\n";
      }
      return 0;
    }

测试数据

0 1
    0 0

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: /images/20221120/cb9dede380714098b8b915c2d3d3579f.png
[20201207131050385.png]: https://img-blog.csdnimg.cn/20201207131050385.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201207131230130.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[20201207151359894.png]: https://img-blog.csdnimg.cn/20201207151359894.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201207151438465.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[20201207153010659.png]: https://img-blog.csdnimg.cn/20201207153010659.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/202012071531354.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[20201207153639340.png]: https://img-blog.csdnimg.cn/20201207153639340.png
[20201207153733630.png]: https://img-blog.csdnimg.cn/20201207153733630.png
[20201207154518675.png]: https://img-blog.csdnimg.cn/20201207154518675.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201207173312730.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[20201207173243474.png]: https://img-blog.csdnimg.cn/20201207173243474.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201207173533650.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[20201207214521684.png]: https://img-blog.csdnimg.cn/20201207214521684.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201207174342924.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[20201207190726913.png]: https://img-blog.csdnimg.cn/20201207190726913.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20201207191007867.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[20201207193419381.png]: https://img-blog.csdnimg.cn/20201207193419381.png