pascal中级教程第九章数学问题

1 2 倾倒的方案为： 1、桶->B杯； 2、B杯->A杯； 3、桶->B杯； 4、B杯->A杯； 5、A杯->桶; 6、B杯->A杯； 【问题分析】 解模方程。

首先，c＝gcd(a, b)。写成模方程形式即为bx≡c(mod a)。

设Pa，Pb分别为从体积为a ml。的酒杯中倒出酒的次数和将酒倒入体积为b mL的酒杯 中的次数，则有c＝bPb-aPa。

用Euclid辗转相除法求出Pa，Pb即可。时间复杂度为O(log2n)。

9.9 班级聚会

源程序名 reunion.???（pas, c, cpp） 可执行文件名 reunion.exe 输入文件名 reunion.in 输出文件名 reunion.out 【问题描述】 毕业25年以后，我们的主人公开始准备同学聚会。打了无数电话后他终于搞到了所有同学的地址。他们有些人仍在本城市，但大多数人分散在其他的城市。不过，他发现一个巧合，所有地址都恰好分散在一条铁路线上。他准备出发邀请但无法决定应该在哪个地方举行宴会。最后他决定选择一个地点，使大家旅行的花费和最小。 不幸的是，我们的主人公既不擅长数学，也不擅长计算机。他请你帮忙写一个程序，根据他同学的地址，选择聚会的最佳地点。 【输入】 输入文件的每一行描述了一个城市的信息。 首先是城市里同学的个数，紧跟着是这个城市到Moscow（起点站）的距离（km），最后是城市的名称。最后一行描述的总是Moscow，它在铁路线的一端，距离为0。 【输出】 聚会地点城市名称和旅行费用（单程），两者之间用一空格隔开。每km花费一个卢布。 【样例】 reunion.in reunion.out 7 9289 Vladivostok Yalutorovsk 112125 5 8523 Chabarovsk 3 5184 Irkutsk 8 2213 Yalutorovsk 10 0 Moscow 【问题分析】 中位数问题。找这样一个点(城市)——它左边的人数与右边的人数差的绝对值最小。时间复杂度为O(n)。

本问题的参考程序作者特意不加注释，以考察读者能否根据以上问题分析，将程序看懂并理解。