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

我会带着你远行 2022-12-27 01:22 149阅读 0赞

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

*   *   *  2013年
         *   *  交叉奇偶验证
             *  后序序列
         *  其他
         *   *  最大连续子序列
             *  回文数猜想
             *  18岁生日
             *  Sky 数
             *  统计难题

### 2013年 ###

#### 交叉奇偶验证 ####

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

#include<iostream>
    using namespace std;
    const int MAXN = 1e3+3;
    
    int matrix[MAXN][MAXN];
    
    int main(){ 
      int n;
      while(cin>>n){ 
        for(int i=0;i<n;++i){ 
          for(int j=0;j<n;++j){ 
            cin>>matrix[i][j];
          }
        }
        int rowCnt=0,colCnt=0,row,col;// 行列不为1的个数为奇数的个数，其最后出现的位置
        for(int i=0;i<n;++i){ 
          int sum = 0;
          for(int j=0;j<n;++j)sum+= matrix[i][j];
          if (sum%2) { 
            rowCnt ++;
            row = i+1;
          }
        }
        for(int j=0;j<n;++j){ 
          int sum = 0;
          for(int i=0;i<n;++i)sum+= matrix[i][j];
          if (sum%2) { 
            colCnt ++;
            col = j+1;
          }
        } // 当一个数出错会影响这行与这列
        if (colCnt==0&&rowCnt==0) cout<<"OK\n";
        else if (colCnt==1&&rowCnt==1) cout<<"Error In ("<<row<<","<<col<<")\n";
        else cout<<"Error\n"; 
      }
    }

测试数据

4
    1 0 1 0
    0 0 0 0 
    1 1 1 1
    0 1 0 1
    4
    1 0 1 0
    0 0 1 0 
    1 1 1 1
    0 1 0 1
    4
    1 0 1 0
    1 1 0 0 
    1 1 1 1
    0 1 0 1

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

#### 后序序列 ####

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

#include<iostream>
    using namespace std;
    
    struct Node{ 
      char val; //
      Node* left;
      Node* right;
      Node(){ left=right=NULL;} 
      Node(char x){ 
        left=right=NULL;
        val = x;
      }
    }; // 定义树的节点结构
    
    char preorder[30];//前序序列
    char inorder[30]; // 中序序列
    
    Node* makeTree(int L1,int R1,int L2,int R2){ 
      // 中序序列区间[L1,R1] 中序序列区间[L2,R2] 
      if (L1>R1) return NULL;
      char data = preorder[L2]; // 通过前序区间的第一关键字 是根 查找在 中序区间的位置 来划分区间
      Node* bt = new Node(data);
      int p = L1;
      while(inorder[p]!=data)p++;
      int nodeLen = p-L1; // 划分区间左边长度
      bt->left = makeTree(L1,p-1,L2+1,L2+nodeLen);
      bt->right = makeTree(p+1,R1,L2+nodeLen+1,R2);
      return bt;
    } // 递归建树
    
    void postOrder(Node * tree){ 
      if (tree==NULL) return ;
      postOrder(tree->left);
      postOrder(tree->right);
      cout<<tree->val;
    }
    
    int main(){ 
      int n;// 节点个数
      cin>>n;
      for(int i=0;i<n;++i)cin>>preorder[i];
      for(int i=0;i<n;++i)cin>>inorder[i];
      Node* tree = makeTree(0,n-1,0,n-1);
      postOrder(tree);
    }

测试数据

7
    DBACEGF
    ABCDEFG

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

### 其他 ###

#### 最大连续子序列 ####

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

#include<iostream>
    using namespace std;
    const int MAXN = 1e4+4;
    int a[MAXN];
    // 动态规划 dp[n] = max(0, dp[n-1]) + num[n] （dp[n]表示以第n个数结尾的最大连续子序列的和）
    
    int main(){ 
      int n;
      while(cin>>n){ 
        for(int i=0;i<n;++i)cin>>a[i];
        int sum = a[0],msum = a[0],tmp,start = 0, end = 0; // 求和，最大和 以及所在[start, end]
        for(int i=1;i<n;++i){ 
          if (sum>0) sum+=a[i];
          else sum = a[i],tmp = i; // 存起始位置
          if (sum > msum) { 
            msum = sum ;
            end = i;
            start = tmp;
          }
        }
        if (msum<0) cout<<0<<" "<<a[0]<<" "<<a[n-1]<<endl;
        else cout<<msum<<" "<<a[start]<<" "<<a[end]<<endl;
      }
      return 0;
    }

测试数据

6
    -2 11 -4 13 -5 -2
    3 
    -1 -5 -2

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

#### 回文数猜想 ####

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

#include<iostream>
    #include<vector>
    using namespace std;
    
    int a[10],cnt; //存放数的每位 长度 
    void itoa(int n){ 
      cnt = 0;
      while(n){ 
        a[cnt++] = n%10;
        n/=10;
      }
    } // 将数n 的每一位存放在数组里
    
    bool judge(int b[],int n){ 
      for(int i=0,j=n/2;i<j;++i){ 
        if(b[i]!=b[n-i-1])return false;
      }
      return true;
    }// 判断是否为回文数
    
    int atoi(int b[],int n){ 
      int sum = 0;
      for(int i=0;i<n;++i)sum=sum*10+a[i];
      return sum;
    }// 将数组转换为int 在这里求得是该数的倒序数
    
    int main(){ 
      int n;
      while(cin>>n){ 
        itoa(n);
        vector<int> tmp; // 缓存中间结果
        tmp.push_back(n);
        while(!judge(a,cnt)){ 
          n += atoi(a,cnt);
          tmp.push_back(n);
          itoa(n);
        }
        cout<<tmp.size()-1<<endl<<tmp[0];
        for(int i=1,len=tmp.size();i<len;++i){ 
          cout<<"--->"<<tmp[i];
        }
        cout<<endl;
      }
      return 0;
    }

测试数据

27228
    37649

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

#### 18岁生日 ####

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

#include<cstdio>
    using namespace std;
    
    bool isLeap(int n){ 
      return (n%400==0)||(n%100!=0&&n%4==0); 
    }
    
    int main(){ 
      int n,year,month,day;
      scanf("%d",&n);
      while(n--){ 
        scanf("%d-%d-%d",&year,&month,&day);
        if(month == 2 && day == 29) { 
          printf("-1\n");
          continue;
        }// 存在则是闰年，加上18后，不是4的倍数，也就不是闰年
        int y = year + 18;
        int ans = 0;
        // 出生年为闰年且，月份<3 
        if (isLeap(year)&&month<3) ans++; 
        if (isLeap(y)&&month>2) ans++;
        for(int i=year+1;i<y;++i){ 
          if(isLeap(i))ans++;
        }
        printf("%d\n",365*18+ans);
      }
      return 0;
    }

测试数据

1
    1988-03-07

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

#### Sky 数 ####

问题描述：对于四位数 2992，它的十进制表示的所有位数之和为 2+9+9+2=22、它的十六进制 BB0 的所有位数之和为 22、同时它的十二进制表示 1894 的四位数之和也为 22。  
Sky 数是指其十进制、十六进制、十二进制的所有位数之和均为 22 的数字。  
输入：输入含有一些十进制的四位正整数，如果输入0 则表示结束。  
输出：若n为 Sky 数，则输出“\#n is a Sky Number.”，否则输出“\#n is not a Sky Number.”。  
每个结果占一行。\#n 表示读入的 n 值。

#include<iostream>
    using namespace std;
    
    int sumRadix(int n,int radix){ 
      int sum = 0;
      while(n){ 
        sum += n%radix;
        n/=radix;
      }
      return sum;
    }// 把10进制数n 转换radix进制 并把位数求和
    
    int main(){ 
      int n;
      while(cin>>n&&n!=0){ 
        if(sumRadix(n,10)==22&&sumRadix(n,12)==22&&sumRadix(n,16)==22) 
          cout<<"#"<<n<<" is a Sky Number.\n";
        else cout<<"#"<<n<<" is not a Sky Number.\n";
       }
      return 0;
    }

测试数据

2992
    1234
    0

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

#### 统计难题 ####

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

#include<iostream>
    #include<string>
    #include<vector>
    using namespace std;
    
    vector<string> words;
    
    int main(){ 
      string s;
      while(getline(cin,s)){ 
        if(s.size()==0)break; // 单词表读取完毕
        words.push_back(s);
      }
      while(getline(cin,s)){ 
        int len = s.size(),ans=0;
        for(int i=0,slen=words.size();i<slen;++i){ 
          if(len<=words[i].size()&&words[i].substr(0,len)==s)ans++;
        }// 前缀的长度要小于字符串的长度，然后遍历单词表，截取前缀判断是否相等
        cout<<ans<<endl;
      }
      return 0;
    }

测试数据

banana
    band
    bee
    absolute
    acm
    
    ba
    b
    band
    abc

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: /images/20221120/7c6534674dfc445c9455c506255f6d3b.png
[20201206223419360.png]: /images/20221120/6c8451799a844097941bfe8f5ea031f6.png
[20201206223439839.png]: /images/20221120/cdf91280b18b4d23b625bfba52f19929.png
[20201207090626331.png]: https://img-blog.csdnimg.cn/20201207090626331.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201207091218465.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[2020120709545630.png]: https://img-blog.csdnimg.cn/2020120709545630.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201207095823800.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[20201207101849326.png]: https://img-blog.csdnimg.cn/20201207101849326.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201207101933620.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[20201207104157542.png]: https://img-blog.csdnimg.cn/20201207104157542.png
[20201207123952746.png]: https://img-blog.csdnimg.cn/20201207123952746.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201207124145799.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[20201207124925353.png]: https://img-blog.csdnimg.cn/20201207124925353.png