计算机编程能力培养课程设计题目_2014.pdfVIP

2014 年通信工程学院计算机能力培养课程设计题目 题目一：计算圆周率 读懂下面著名的 C 语言“天书”，这段代码只用了四行代码（include 预编译命令不算） 就计算了 800 位圆周率，其算法自有其高明这处，所以本题更重要的是要论述清楚背后的数 学原理。 #includestdio.h long a = 10000,b,c=2800,d,e,f[2801],g; void main(){for(;b-c;)f[b++]=a/5; for(;d=0,g=c*2;c-=14,printf(%.4d,e+d/a),e=d%a) for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);scanf(%s);return;} 题目二：稳定伴侣问题 有 n 个男孩 m1，m2，…，mn 与 n 个女孩 w1，w2，wn。每一个男孩 mi 都依照喜爱这 n 个女孩的程度列成一张表，最喜欢的女孩排在第 1 位，最不喜爱的女孩排在第 n 位；同样地， 每一个女孩 wi 也依照她喜爱 n 个男孩的程度列成一张表。请写一个???序，把每一个男孩与 女孩的喜爱表格读入，并且把男孩与女孩一一配对，使得：如果 mp 与 wq 是一对的话，那么 第一：对 mp 的喜爱表格中排在 wq 之前的女孩而言，她的伴侣在她的表格中一定排在 mp 之 前；第二：对 wq 的喜爱表格中排在 mp 之前的男孩而言，他的伴侣在他的表格中一定排在 wq 之前。这就是稳定伴侣（Stable Marriage）问题。 【说明】 这个问题恐怕要多说一些才能讲得明白。先讲不稳定（Unstable）的情况；如果 m 的女 伴记成 PM（m），而 w 的男伴记成 PW（w）。如果有一对男孩与女孩 m 与 w，他们不是伴侣 （用上面的记号，m 的伴侣是 PM（m），w 的伴侣是 PW（w）），但 m 比较中意 w 而不是 PM （m），则同时 w 比较中意 m 而不是 PW（w）的时候，m 与 w 就一定心不甘情不愿了。例 如，如果 A 与 B 是男孩，X 与 Y 是女孩，A 比较中意 X，B 比较中意 Y，A 与 Y、B 与 X 结伴，那么 A 与 Y 心目中的情人都不是对方，B 与 X 亦然，这就是不稳定的状况。稳定伴 侣的问题，就是要在喜爱的表格中配出最合适、稳定的伴侣，而不是“乔太守乱点鸳鸯谱” 制造对对怨偶。 看一个完整的例子。假设男孩与女孩都用编号 1,2,3,4，其喜爱表格如表 1 所示。 表 1 男 孩 女 孩 1： 2 4 1 3 1： 2 1 4 3 2： 3 1 4 2 2： 4 3 1 2 3： 2 3 1 4 3： 1 4 3 2 4： 4 1 3 2 4： 2 1 4 3 1 表格中指出，男孩 1 最中意的女孩是 2，其次是 4 与 1，最后是 3；对于女孩 3 而言， 她最中意 1，其次是 4 与 3，最后是 2，对于这两份喜欢