2006 交大考研上机题目&&题解(转载交大blog 诺曼狗狗)

2006 交大考研上机题目 + 题解

编程环境：VC++6
考试时间：3小时

Problem A.Fibonacci
Input: fib.in
Output: Standard Output
Time limit: 5 second
Memory limit: 64 megabytes
Offerd by ： http://spaces.msn.com/davidblogs/

The Fibonacci Numbers{0,1,1,2,3,5,8,13,21,34,55...} are defined by the recurrence:
F0=0 F1=1 Fn=Fn-1+Fn-2,n>=2
Write a program to calculate the Fibonacci Numbers.

Input
The input file contains a number n and you are expected to calculate Fn.(0<=n<=30)

Output
Print a number Fn on a separate line,which means the nth Fibonacci Number.

Example
fib.in Standard Output
1 1
2 1
3 2
4 3
5 5
6 8


Problem B.WERTYU
Input: wertyu.in
Output: Standard Output
Time limit: 5 second
Memory limit: 64 megabytes
Offerd by ： http://spaces.msn.com/davidblogs/

A common typing error is to place the hands on the keyboard one row to the right of the correct position.So "Q" is typed as "W" and "J" is typed as "K" and so on.You are to decode a message typed in this manner.

` 1 2 3 4 5 6 7 8 9 0 - = BackSp
Tab Q W E R T Y U I O P [ ]
A S D F G H J K L ; ' Enter
Z X C V B N M , . /
Control Alt Space Alt Control

Input
The input file consist of several lines of text.Each line may contain digits,spaces,upper case letters(except Q,A,Z),or punctuation shown above(except back-quote(') which is left to the key "1").Keys labelled with words [Tab,BackSp,Control,etc.] are not represented in the input.

Output
You are to replace each letter or punctuation symbol by the one immediately to its left on the QWERTY keyboard shown above.Spaces in the input should be echoed in the output.

Example
wertyu.in Standard Output
O S, GOMR YPFSU/ I AM FINE TODAY.


Problem C.String Matching
Input: matching.in
Output: Standard Output
Time limit: 5 second
Memory limit: 64 megabytes
Offerd by ： http://spaces.msn.com/davidblogs/

Finding all occurrences of a pattern in a text is a problem that arises frequently in text-editing programs.Typically,the text is a document being edited,and the pattern searched for is a particular word supplied by the user.

We assume that the text is an array T[1..n] of length n and that the pattern is an array P[1..m] of length m<=n.We further assume that the elements of P and T are all alphabets(∑={a,b...,z}).The character arrays P and T are often called strings of characters.

We say that pattern P occurs with shift s in the text T if 0<=s<=n and T[s+1..s+m] = P[1..m](that is if T[s+j]=P[j],for 1<=j<=m).

If P occurs with shift s in T,then we call s a valid shift;otherwise,we call s a invalid shift.
Your task is to calculate the number of vald shifts for the given text T and pattern P.

Input
In the input file,there are two strings T and P on a line,separated by a single space.You may assume both the length of T and P will not exceed 10^6.

Output
You should output a number on a separate line,which indicates the number of valid shifts for the given text T and pattern P.

Example
matching.in Standard Output
aaaaaa a 6
abababab abab 3
abcdabc abdc 0

Problem D.Exponential Form
Input: form.in
Output: Standard Output
Time limit: 5 second
Memory limit: 64 megabytes
Offerd by ： http://spaces.msn.com/davidblogs/

Every positive number can be presented by the exponential form.For example,
137 = 2^7 + 2^3 + 2^0
Let's present a^b by the form a(b).Then 137 is presented by 2(7)+2(3)+2(0).
Since 7 = 2^2 + 2 + 2^0 and 3 = 2 + 2^0 , 137 is finally presented by 2(2(2)+2+2(0))+2(2+2(0))+2(0).

Given a positive number n,your task is to present n with the exponential form which only contains the digits 0 and 2.

Input
The input file contains a positive integer n (n<=20000).

Output
You should output the exponential form of n an a single line.Note that,there should not be any additional white spaces in the line.

Example
form.in
137
Stardard Output
2(2(2)+2+2(0))+2(2+2(0))+2(0)
form.in
1315
Stardard Output
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

第一题
题目A 斐波拉契数列
输入文件: fib.in
输出文件: Standard Output
时间限制: 5 second
内存限制: 64 megabytes
翻译: RomanGol.SJTU

斐波拉契数列由如下方式定义
F0=0 F1=1 Fn=Fn-1+Fn-2,n>=2
写一个程序来计算斐波拉契数列

输入
输入文件包含了一个数字n，你用它来计算Fn.(0<=n<=30)

输出
在一行上输出一个数字，表示第n个斐波拉契数

范例
fib.in Standard Output
1 1
2 1
3 2
4 3
5 5
6 8

代码 Coded by RomanGol

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <string>

using std::cout;
using std::cin;
using std::endl;
using std::ifstream;
using std::ios;
using std::cerr;
using std::stringstream;
using std::string;
using std::vector;

int main(int argc, char *argv[])
{
ifstream in("fib.in", ios::in);
string fib_str;
int fib_num;
stringstream trsf;
vector<long> fibonacci;

fibonacci.push_back(0);
fibonacci.push_back(1);

getline(in, fib_str);

trsf << fib_str;
trsf >> fib_num;

cout << "num: " << fib_num << endl;

in.close();

if (fib_num < 0 || fib_num > 30)
{
cerr << "range overflown";
return -1;
}

for (int i = 2; i <= fib_num; ++i)
fibonacci = fibonacci[i - 1] + fibonacci[i - 2];

cout <<"fibonacci num: " << fibonacci[fib_num];
cin.ignore();
return 0;
}


第二题
题目B.WERTYU
输入: wertyu.in
输出: Standard Output
时间限制: 5 second
内存限制: 64 megabytes
翻译: RomanGol.SJTU

典型的输入错误是将要输入的字符错误的输入成了键盘上对应字符右边的那个字符，于是 "Q" 被错误的输入 "W" 而 "J" 错误的输入为 "K" 。你的任务是要纠正这种错误.

键盘：
` 1 2 3 4 5 6 7 8 9 0 - = BackSp
Tab Q W E R T Y U I O P [ ]
A S D F G H J K L ; ' Enter
Z X C V B N M , . /
Control Alt Space Alt Control

输入
输入文件包含了数行文本，每一行可能包含数字，空格，大写字母(除了 Q,A,Z),或者上面出现的标点符号(除了键盘上数字1左边的(')).功能键[Tab,BackSp,Control,etc.] 不会出现在输入中.

输出
你的任务就是要把每一个字符都按照 QWERTY 键盘上的位置，将它替换成它左边的那个字符。而空格应该被保留并且输出。

样例
wertyu.in Standard Output
O S, GOMR YPFSU/ I AM FINE TODAY.

#include <iostream>

#include <vector>
#include <string>

#include <fstream>
#include <sstream>

using std::cout;
using std::cin;
using std::cerr;
using std::endl;

using std::string;
using std::vector;

using std::ifstream;
using std::ios;

using std::stringstream;


int main(int argc, char *argv[])
{
string keyboard = "1234567890-=QWERTYUIOP[]ASDFGHJKL;'ZXCVBNM,./";

ifstream in("wertyu.in", ios::in);

string to_transform;
string transformed;

while( getline(in, to_transform))
{
for (string::iterator i = to_transform.begin(); i!= to_transform.end(); ++i)
{
if (*i == ' ')
transformed += ' ';
else
transformed += keyboard[keyboard.find(*i, 0) - 1];
}
cout << transformed << endl;
transformed.clear();

}

in.close();
cin.ignore();
return 0;
}

第三题
问题 C.字符串匹配
输入: matching.in
输出: Standard Output
时间限制: 5 second
内存限制: 64 megabytes
翻译: RomanGol.SJTU

在文本编辑程序中，寻找一个 pattern 的所有出现是一个经常遇到的问题，通常该文本是一个正在被编辑的文档，而要查找的 pattern 由用户来提供。

我们假设该文本是一个长度为n的数组 T[1..n] 而 pattern 是一个长度为m的数组 P[1..m] ， m<=n
我们进一步假设 P 和 T 中都是字母(∑={a,b...,z}).字符数组 P 和 T 通常被称作 strings of characters.

我们定义，如果 pattern P 出现在文本 T 中离开头字符 s 的位置上，如果 0<=s<=n 并且 T[s+1..s+m] = P[1..m](也就是说如果T[s+j]=P[j]，对于 1<=j<=m)，那么这是一个 P 在 T 中偏移为 s 的出现

如果 P 出现在 T 的偏移为 s 的位置，我们称 s 为一个有效偏移；否则，我们称s为一个无效偏移。
你的任务是在给定的文本 T 和 pattern P 中计算有效偏移的数量

输入
在输入文件中有两个字符串 T 和 P ， 它们在同一行，由一个空格分隔开。你可以假设这两个字符串的长度不会超过 10^6.

输出
你应该在单独的一行输出一个数字，表示在给定的文本 T 和 pattern P 中有效偏移的数量。

样例
matching.in Standard Output
aaaaaa a 6
abababab abab 3
abcdabc abdc 0


coded by RomanGol

#include <iostream>

#include <vector>
#include <string>

#include <fstream>
#include <sstream>

using std::cout;
using std::cin;
using std::cerr;
using std::endl;

using std::string;
using std::vector;

using std::ifstream;
using std::ios;

using std::stringstream;


int main(int argc, char *argv[])
{

ifstream in ("matching.in", ios::in);

string text;
string pattern;

getline(in, text, ' ');
getline(in, pattern, ' ');

cout << text << endl;
cout << pattern;

int pos;
int counter = 0;

while( (pos = text.find(pattern, 0)) >= 0)
{
++counter;
text = text.substr(pos + 1, text.size() - pos - 1);
}

cout << counter;

in.close();
cin.ignore();
return 0;
}


第四题
问题 D.指数形式
输入: form.in
输出: Standard Output
时间限制: 5 second
内存限制: 64 megabytes
翻译: RomanGol.SJTU

每个正整数都可以表示为2的幂次相加的格式，例如
137 = 2^7 + 2^3 + 2^0

这里我们用 a(b) 的格式来表示 a^b 。因此 137 被表示为 2(7)+2(3)+2(0).
因为 7 = 2^2 + 2 + 2^0 而 3 = 2 + 2^0 ，137 最终被表示为 2(2(2)+2+2(0))+2(2+2(0))+2(0).

给定一个正整数 n ，你的任务是将它表示为只用 0 和 2 来表示的指数格式

输入
输入文件包含一个正整数 n (n<=20000).

输出
你应该在单独的一行上输出一个 n 的指数形式。注意到不应该有额外的空白字符出现。

样例
form.in
137
Stardard Output
2(2(2)+2+2(0))+2(2+2(0))+2(0)
form.in
1315
Stardard Output
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

coded by RomanGol

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <sstream>

using std::cout;
using std::cin;
using std::cerr;
using std::endl;

using std::string;
using std::vector;

using std::ifstream;
using std::ios;

using std::stringstream;

string to_form(int, int);

int main(int argc, char *argv[])
{
ifstream in("form.in", ios::in);
string str;
stringstream tsf;
int n;

getline(in, str);
tsf << str;
tsf >> n;

str = to_form(n, 15);

in.close();

cout << str;

cin.ignore();
return 0;
}

string to_form(int num, int max)
{
static stringstream tsf;
string form;
string power;
const static int exp[15] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384 };

for (int i = max; i >=0; --i)
{
if ( num >= exp )
{
num -= exp;

if (i != 2 && i != 0)
power = to_form(i, i);
else
{
tsf.clear();
tsf << i;
tsf >> power;
}

if (num)
form += "2(" + power + ")+";
else
form += "2(" + power + ")";
}
}

return form;
}