題目一、jobdu1073：楊輝三角形
http://ac.jobdu.com/problem.php?pid=1073
- 題目描述： 輸入n值，使用遞歸函數，求楊輝三角形中各個位置上的值。
- 輸入： 一個大于等于2的整型數n
- 輸出：
-
題目可能有多組不同的測試資料，對于每組輸入資料，
按題目的要求輸出相應輸入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<iostream>
#include<cmath>
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<n;i++){//遞歸代碼
for(int j=0;j<i;j++){
cout<<YangHui(i,j)<<" ";
}
cout<<YangHui(i,i)<<endl;
}**/
for(int i=1;i<n;i++){//遞歸代碼
for(int j=0;j<i;j++){
cout<<a[i][j]<<" ";
}
cout<<a[i][i]<<endl;
}
}
return 0;
}
AC代碼(遞歸代碼)：
#include <iostream>
using namespace std;
int a[600][600],k=0;
int dfs(int i,int j){
if(i==0) return a[i][j]=1;
if(j==0||i==j) {
a[i][j]=1;
for(int k=2;k<j;k++){//搜尋最後一行的所有
dfs(i,k);
}
}
if(a[i][j]) return a[i][j];
return a[i][j]=dfs(i-1,j-1)+dfs(i-1,j);
}
int main()
{
dfs(400,400);
//cout<<a[6][6]<<endl;
int n;
while(cin>>n){
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
cout<<a[i][j]<<" ";
}
cout<<a[i][i]<<endl;
}
}
//cout << "Hello world!" << endl;
return 0;
}
題目二、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<iostream>
#include<cstdio>
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<a[j][i]){//找到最大數所在的行
ma=a[j][i]; k=j;
}
}
for(int c=1;c<=n;c++){//交換第i和第k行
int tmp=a[i][c];
a[i][c]=a[k][c];
a[k][c]=tmp;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<n;j++){
cout<<a[i][j]<<" ";
}
cout<<a[i][n]<<endl;
}
}
int main()
{
int n;
while(cin>>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<iostream>
#include<string>
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<s1.size()&&j>=0){
if(ok==0){//用ok控制添加那個字元
ok=1;
s+=s1[i++];
}
else{
ok=0;
s+=s2[j--];
}
}
//适合不相等的兩個字元串,對于本題可以去掉
while(i<s1.size()){
s+=s1[i++];
}
while(j>=0){
s+=s2[j--];
}
cout<<s<<endl;
}
return 0;
}
題目四、題目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<iostream>
#include<cstdio>
#include<cstring>
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<n;i++){
cin>>d>>p;
if(p>=0) a[p]=d;
else b[-p]=d;
}
cin>>m;
for(int i=0;i<m;i++){
cin>>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<<a[i]<<" "<<i;}
else cout<<" "<<a[i]<<" "<<i;
}
}
for(int i=1;i<=1000;i++){
if(b[i]) cout<<" "<<b[i]<<" "<<-i;
}
cout<<endl;
}
return 0;
}
![九度OJ 題目1085：求root(N, k)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)