九度oj 西北工业大学2011机试题目全解

题目一、jobdu1073：杨辉三角形

?

题目可能有多组不同的测试数据，对于每组输入数据，
按题目的要求输出相应输入n的杨辉三角形。

6

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

题目分析：

可以用推和递归，题目要求递归但是好像超时了，只能递推了。简单题详见代码。

AC代码：

/**
 *西北工业大学2011研究生机试题
 */
#include
  
   
#include
   
     using namespace std; int a[105][105]; int YangHui(int x,int y){//题目要求用递归,不过在九度上测试超时,无奈只能用递推 if(x==y||y==0) return 1; else return YangHui(x-1,y)+YangHui(x-1,y-1); } int main() { for(int i=0;i<100;i++){ for(int j=0;j<100;j++){ if(i==j||j==0) a[i][j]=1; else a[i][j]=a[i-1][j]+a[i-1][j-1]; } } int n; while(cin>>n){ /** for(int i=1;i
     
     题目二、jobdu1470：调整方阵
     
?
     
http://ac.jobdu.com/problem.php?pid=1470
     
输入一个N（N<=10）阶方阵，按照如下方式调整方阵： 1.将第一列中最大数所在的行与第一行对调。 2.将第二列中从第二行到第N行最大数所在的行与第二行对调。 依此类推... N-1.将第N-1列中从第N-1行到第N行最大数所在的行与第N-1行对调。 N.输出这个方阵
 
     输入：
     
包含多组测试数据,每组测试数据第一行为一个整数N,表示方阵的阶数. 接下来输入这个N阶方阵.
 
     输出：
     
调整后的方阵
 
     样例输入：
     
4
3 6 8 7
6 7 5 3
8 6 5 3
9 8 7 2
 
     样例输出： 
     
9 8 7 2
6 7 5 3
3 6 8 7
8 6 5 3
 
     
 
     题目分析： 
     
?
 
     
简单的模拟题，注意控制下标的操作即可，见代码。
 
     
AC代码：
 
     
/**
 *西北工业大学2011研究生机试题
 */
#include
      
       
#include
       
         using namespace std; int a[12][12]; void TiaoZ(int n){ int ma,k; for(int i=1;i<=n;i++){ ma=a[i][i]; k=i; for(int j=i+1;j<=n;j++){//每次从第i行开始比较 if(ma
        
         >n){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; } } TiaoZ(n); } return 0; } 
        
       
      
 
     
 
     题目三、jobdu1471：合并符串 
     
?
 
     
http://ac.jobdu.com/problem.php?pid=1471
 
     
给定两个字符串S1和S2，合并成一个新的字符串S。
 合并规则为，S1的第一个字符为S的第一个字符，将S2的最后一个字符作为S的第二个字符；
 将S1的第二个字符作为S的第三个字符，将S2的倒数第二个字符作为S的第四个字符，以此类推。
 
     输入： 
     
包含多组测试数据，每组测试数据包含两行，代表长度相等的两个字符串S1和S2（仅由小写字母组成，长度不超过100）。





 
     输出： 
     
合并后的新字符串S
 
     样例输入： 
     
abc
def
 
     样例输出： 
     
afbecd
 
     题目分析： 
     
?
 
     
只需要用一个变量ok控制添加那个字符串的字符，用ok=0，ok=1表示。此题给出的字符串长度相等，代码中给出了不相等的代码。
 
     
AC代码：
 
     
?
 
     
#include
      
       
#include
       
         using namespace std; int main() { string s1,s2; while(cin>>s1>>s2){ int i,j,ok=0; i=0; j=s2.size()-1; string s; while(i
        
         =0){ if(ok==0){//用ok控制添加那个字符 ok=1; s+=s1[i++]; } else{ ok=0; s+=s2[j--]; } } //适合不相等的两个字符串,对于本题可以去掉 while(i
         
          =0){ s+=s2[j--]; } cout<
          
           
?
           
题目四、题目1472：求两个多项式的和 
           
http://ac.jobdu.com/problem.php?pid=1472 
 
           题目描述：
           
输入两个多项式，计算它们的和。 每个多项式有若干对整数表示，每组整数中，第一个整数表示系数（非0），第二个整数表示该项的次数。 如由3 3 5 -2 1 4 0表示3x^5 - 2 * x + 4其中第一个3表示该多项式由三个整数对表示。
 
           输入：
           
输入为两行，分别表示两个多项式。表示每项的整数对按照次数大小降序给出。(次数绝对值小于1000，系数绝对值小于10000)
 
           输出：
           
按照降次顺序输出表示和多项式的整数对（系数为0的整数对不用输出，整数对由空格分隔，最后一个整数对后不添加空格）
 
           样例输入：
           
3 3 5 -2 1 4 0
4 2 3 -1 2 1 1 3 0
 
           样例输出： 
           
3 5 2 3 -1 2 -1 1 7 0
 
           题目分析： 
           
?
 
           
此题的意思可能是要用链表进行编程的，由于数据太小小编没有用链表而是用两个数组a[],b[],进行编程实现的，用数组a表示指数p大于等于0的项，用数组b表示指数小于0的项。详见代码。
 
           
AC代码：
 
           
?
 
           
#include
            
             
#include
             
               #include
              
                using namespace std; int a[1005],b[1005];//a表示指数大于0,b表示指数小于0 int main() { int n,m,d,p; while(cin>>n){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(int i=0;i
               
                >d>>p; if(p>=0) a[p]=d; else b[-p]=d; } cin>>m; for(int i=0;i
                
                 >d>>p; if(p>=0) a[p]+=d; else b[-p]+=d; } int ok=1; for(int i=1000;i>=0;i--){ if(a[i]){//注意去掉末尾的空格 if(ok){ok=0; cout<
                 
                  
?