ACM初步练习

一、阅读程序，回答问题
void f1(int a[], int n){
int i, j;
i=0; j=n-1;
while(i<=j){
a[i] = a[i]+a[j];
a[j] = a[i]-a[j];
a[i] = a[i]-a[j];
++i; –j;
}
}
void main(){
int ar[4]={1,2,3,4};
f1(ar, 4);
}
1、此程序运行后ar中的结果是什么？
2、推测和描述函数f1的功能。
3、对于各种合理的输入，函数f1是否都能得到2问中你所描述的结果？

二、阅读程序，回答问题
int f2(int a[], int n){
// n是数组长度
int i,j,s;
for(i=0; i s=0;
for(j=0; j if (a[j] < a[i])
++s;
if (s==n/2)
return a[i];
}
}

1、推测和描述此函数的功能。
2、使用者反映，此函数在数据量很大的情况下，运行速度较慢，你能否设计出一
个更快的方法？说明思路即可。

三、使用C语言编制一个函数，使用辗转相除法计算两个整数的最大公因数。你的
程序对数据输入是否有要求？（即，是否在所有可能输入情况下都能得到正确结果
？）

四、使用组合数递推公式C(m,n)=C(m-1,n-1)+C(m-1,n) ，编制递归函数计算组合数。
此函数的计算效率能否改进？

五、你第一次进入一幢楼，设计非常复杂（如环行走廊，套间，错层楼梯等），试
设计一个方案，统计楼内共有多少个房间。

六、描述你的个人情况，你的学习成绩如何？你对ACM/ICPC有多少了解？你对自己
的程序设计能力有信心么？对于上面五个题目，你对自己的回答有多少把握？

附加题：实现Dijkstra算法