九度oj 西北工業大學2011機試題目全解

九度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<