九度OJ北京航空航天大学2009机试题题解

题目一、jobdu1166：迭代求立方根

?pid=1166

题目描述：

立方根的逼近迭代方程是 y(n+1) = y(n)*2/3 + x/(3*y(n)*y(n)),其中y0=x.求给定的x经过n次迭代后立方根的值。

输入：

输入有多组数据。
每组一行，输入x n。

输出：

迭代n次后的立方根，double精度,保留小数点后面六位。

样例输入： 3000000 28 样例输出： 144.224957 题目分析：

递归或者递推，个人感觉递推挺好，两个变量循环前进即可。

AC代码：

<span style="font-size:18px;">/** *@xiaoran *递推或者递归 */ #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<cstdlib> #include<cctype> #include<cmath> #define LL long long using namespace std; int main() { double y,x,yy; int n; while(cin>>x>>n){ y=x; for(int i=1;i<=n;i++){ yy=y*2/3+x/(3*y*y); y=yy; } printf("%.6lf\n",y); } return 0; } </span>

题目二、jobdu1167：数组排序

?pid=1167

题目描述：

输入一个数组的值,求出各个值从小到大排序后的次序。

输入：

输入有多组数据。
每组输入的第一个数为数组的长度n(1<=n<=10000),后面的数为数组中的值,以空格分割。

输出：

各输入的值按从小到大排列的次序(最后一个数字后面没有空格)。

样例输入： 4 -3 75 12 -3 样例输出： 1 3 2 1 题目分析：排序+哈希map即可，STL中map挺好用。排序的记录每个值的下标哦。

AC代码：

<span style="font-size:18px;">#include<iostream> #include<algorithm> #include<map> using namespace std; int a[10001],b[10001],cnt[10001]; int main() { int n; while(cin>>n){ for(int i=0;i<n;i++){ cin>>a[i]; b[i]=a[i]; } sort(a,a+n); cnt[0]=1; map<int,int> num; num[a[0]]=1; for(int i=1;i<n;i++){ if(a[i]==a[i-1]) num[a[i]]=num[a[i-1]]; else num[a[i]]=num[a[i-1]]+1; } for(int i=0;i<n-1;i++){ cout<<num[b[i]]<<" "; } cout<<num[b[n-1]]<<endl; } return 0; } </span>
题目三、jobdu1168：字符串的查找删除

?pid=1168

题目描述：

给定一个短字符串（不含空格），，再给定若干字符串，在这些字符串中删除所含有的短字符串。

输入：

输入只有1组数据。
输入一个短字符串（不含空格），再输入若干字符串直到文件结束为止。

输出：

删除输入的短字符串(不区分大小写)并去掉空格,输出。

样例输入： in #include int main() { printf(" Hi "); } 样例输出： #clude tma() { prtf("Hi"); } 题目分析：

不解释，看代码。不太懂的话，建议研究下C++中的库函数。

AC代码：<span style="font-size:18px;">/** *@xiaoran */ #include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<vector> #include<stack> #include<cstdlib> #include<cctype> #include<cmath> #define LL long long using namespace std; int main() { string s1,s,s2; getline(cin,s); for(int i=0;i<s.size();i++){ if(isalpha(s[i])) s[i]=tolower(s[i]); } int k=s.size(); while(getline(cin,s1)){ s2=s1; for(int i=0;i<s1.size();i++){ if(isalpha(s1[i])) s1[i]=tolower(s1[i]); } string::size_type pos=0; int ok=0; while((pos=s1.find(s,pos))!=string::npos){ //cout<<pos<<endl; s1.erase(pos,k); s2.erase(pos,k); ++pos; } for(int i=0;i<s2.size();i++){ if(s2[i]!=' ') cout<<s2[i]; } cout<<endl; } return 0; } </span>