数据结构编程实验（第3版）
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

1.2　正确处理多个测试用例

【1.1.1 Financial Management】仅给出了一个测试用例，该测试用例中的数据个数是已知的（12个月的收入），且运算十分简单（累加月收入，计算月平均值）。但在通常情况下，为了全面检验程序的正确性，大多数试题都要求测试多个测试用例，只有通过所有测试用例，程序才算正确。如果测试用例的个数或每个测试用例中数据的个数是预先确定的，则处理多个测试用例的循环结构比较简单；若测试用例的个数或每组测试用例中数据的个数未知，仅知测试用例内数据的结束标志和整个输入的结束标志，应如何处理呢？在数据量较大、所有测试用例都采用同一运算且数据范围已知的情况下，有无提高计算时效的办法呢？对于这两个问题，在本节中先给出两个实例。

【1.2.1　Doubles】

给出2～15个不同的正整数，计算这些数中有多少个数对满足一个数是另一个数的两倍。比如，有下列正整数

1　4　3　2　9　7　18　22

那么符合要求的数对有3个，因为2是1的两倍、4是2的两倍、18是9的两倍。

输入

输入包括多个测试用例。每个测试用例一行，给出2～15个两两不同且小于100的正整数。每一行的最后一个数是0，表示这一行的结束，这个数不属于那2～15个给定的正整数。输入的最后一行仅给出整数-1，这一行表示测试用例的输入结束，不用进行处理。

输出

对每个测试用例，输出一行，给出有多少对数满足其中一个数是另一个数的两倍。

试题来源：ACM Mid-Central USA 2003

在线测试：POJ 1552，ZOJ 1760，UVA 2787

试题解析

本题包含多个测试用例，因此需要循环处理每个测试用例，整个输入的结束标志是当前测试用例的第一个数是-1。在循环体内做两项工作：

1）通过一重循环读入当前测试用例的数组a，并累计数据元素个数n。当前测试用例的结束标志是读入数据0。

2）通过两重循环结构枚举a[]的所有数据对a[i]和a[j]（0≤i<n-1，i+1≤j<n），判断a[i]和a[j]是否呈两倍关系（a[i]*2==a[j]||a[j]*2==a[i]）。

参考程序

#include <iostream>                             //预编译命令
using namespace std;                            //使用 C++标准程序库中的所有标识符
int main()                                      //主函数
{                                               //主函数开始
    int i, j, n, count, a[20];                  //声明整型变量i、j、n、count和整型
                                                //数组a
    cin>>a[0];                                  //输入第1个测试用例的首个数据
    while(a[0]!=-1)                             //若输入未结束，则输入下一个测试用例
    {  n=1;                                     //读入当前数据组
        for( ; ; n++)
            {
                cin>>a[n];
                if (a[n]==0) break;
            }
        count=0;                                //处理：计算当前测试用例中有多少数对满
                                                //足一个数是另一个数的2倍
        for (i=0; i<n-1; i++)                   //枚举所有数对
        {
            for (j=i+1; j<n; j++)
            {
                if (a[i]*2==a[j] || a[j]*2==a[i])//若当前数对满足2倍关系，则累计
                    count++;
            }
        }
        cout<<count<<endl;                      //输出当前测试用例中满足2倍关系的数对
        cin>>a[0];                              //输入下一个测试用例的首个数据
    }
    return 0;
}

本题的测试用例数和测试用例长度都是未知的，其求解程序采用双重循环结构。

·外循环：枚举各组测试用例，结束标志为输入结束符（本题的输入结束符为-1）。

·内循环：输入和处理当前测试用例中的数据，输入的结束标志为测试用例的结束符（本题的测试用例以0为结束符）。

在处理多个测试用例的过程中，可能会遇到这样一种情况：数据量较大，所有测试用例都采用同一运算，并且数据范围已知。在这种情况下，为了提高计算效率，可以采用离线计算方法：预先计算出指定范围内的所有解，存入某个常量数组；以后每测试一个测试用例，直接从常量数组中引用相关数据就可以了，这样就避免了重复运算。

【1.2.2　Sum of Consecutive Prime Numbers】

一些正整数能够表示为一个或多个连续素数的和。给出一个正整数，有多少个这样的表示？例如，整数53有两个表示，即5+7+11+13+17和53；整数41有三个表示，即2+3+5+7+11+13、11+13+17和41；整数3只有一个表示，即3；整数20没有这样的表示。注意，加法操作数必须是连续的素数，因此，对于整数20，7+13和3+5+5+7都不是有效的表示。

请写一个程序，对于一个给出的正整数，程序给出连续素数的和的表示数。

输入

输入一个正整数序列，每个数一行，在2～10 000之间取值。输入以0表示结束。

输出

除了最后的0，输出的每一行对应输入的每一行。对于一个输入的正整数，输出的每一行给出连续素数的和的表示数。输出中没有其他字符。

试题来源：ACM Japan 2005

在线测试：POJ 2739，UVA 3399

试题解析

由于每个测试用例都要计算素数，且素数上限为10 000，因此：

1）首先，离线计算出[2..10001]内的所有素数，按照递增顺序存入数组prime[1..total]。

2）然后，依次处理每个测试用例：

设当前测试用例的输入为n，连续素数的和为cnt，n的表示数为ans。

采用双重循环计算n的表示数ans：

·外循环i：枚举所有可能的最小素数prime[i]（for(int i=0;n>=prime[i];i++)）。

·内循环j：枚举由prime[i]开始的连续素数的和cnt，条件是所有素数在prime[]中且cnt不大于n（for(int j=i;j<total & & cnt<n;j++)cnt+=prime[j]）。内循环结束后，若cnt==n，则ans++。

外循环结束后得出的ans即问题解。

参考程序

#include <iostream>                    //预编译命令
using namespace std;                    //使用 C++标准程序库中的所有标识符
const int maxp = 2000, n = 10000;               //设定素数表长和输入值的上限
int prime[maxp], total = 0;               //素数表和表长初始化为0
bool isprime(int k)                    //判定k是否为素数
{
    for (int i = 0; i < total; i++)
        if (k % prime[i] == 0)
            return false;
    return true;
}
int main(void)                         //主函数
{                                 
    for (int i = 2; i <= n; i++)               // 预先建立素数表
        if (isprime(i))
                prime[total++] = i;
    prime[total] = n + 1;
    int m;
    cin >> m;                         //输入第1个正整数
    while (m) {                         //循环，直到输入正整数0为止
        int ans = 0;                    //和初始化为0
        for (int i = 0; m >= prime[i]; i++) {     // 枚举最小素数
            int cnt = 0;                    //求连续素数的和
            for (int j = i; j < total && cnt < m; j++)
                cnt += prime[j];
            if (cnt == m)                    // 若和恰好等于m，则累计答案数
                ++ans;
        }
        cout << ans << endl;               //输出答案数
        cin >> m;                         //输入下一个正整数
    }
    return 0;
}

所谓算法就是编程解决问题的方法。有些“输入–处理–输出”的计算题，尽管学过程序设计语言的读者能够解决，但“处理”这一环节的算法比较复杂，要求读者对于问题描述进行分析，推导出解题的算法。

【1.2.3　Game of Flying Circus】

反重力技术的发现改变了世界。反重力鞋（Grav鞋）的发明使人们能够在空中自由飞翔，从而催生了一项新的空中运动：“飞行马戏（Flying Circus）”。

参赛者穿着反重力鞋和飞行服进行比赛。比赛在一个特定的场地内进行，并要求参赛者在特定的时间内争取得分。比赛场地是一个边长为300米的正方形，正方形的四个角上都漂浮着浮标，这四个浮标按顺时针顺序编号为1、2、3、4，如图1.2-1所示。

图　1.2-1

两名选手将浮标#1作为比赛起点。比赛开始后，他们按顺时针顺序触碰四个浮标。（因为浮标#1是起点，所以他们要触碰的第一个浮标是浮标#2，此后，他们要按顺序触碰浮标#3、#4、和#1。）这里要注意，他们可以在比赛场地内自由飞行，甚至可以在正方形场地的中央飞行。

在以下两种情况下，选手可以得一分。

1）如果你比你的对手先触碰到浮标，你得一分。例如，在比赛开始后，如果对手比你先触碰了浮标#2，那么他得一分；而你触碰到浮标#2的时候，你就不会得分。还要注意，在触碰浮标#2之前，你不能触碰浮标#3或其他浮标。

2）不考虑浮标得分，而是靠格斗得分。如果你和对手在同一位置相遇，你可以和对手进行一场格斗，如胜利则得一分。考虑到游戏的平衡性，在浮标#2被触碰之前，两名选手不得格斗。

通常，有三种类型的选手：

1）Speeder：这类选手擅长高速运动，他们会通过触碰浮标来得分，尽量避免格斗。

2）Fighter：这类选手擅长格斗，他们会尽量通过和对手格斗来得分，因为Fighter的速度比Speeder慢，所以如果对手是一个Speeder，则Fighter很难通过触摸浮标来得分。

3）All-Rounder：综合了Fighter和Speeder的平衡型选手。

现在，在Asuka（All-Rounder选手）和Shion（Speeder选手）之间将进行一场训练赛。由于这场比赛只是一场训练赛，因此规则很简单：任何人触碰到浮标#1后，比赛结束。Shion是Speeder选手，他的策略非常简单：沿最短路径触碰浮标#2、#3、#4、#1。

Asuka擅长格斗，所以她和Shion格斗就会得1分，而对手在格斗之后会昏迷T秒。由于Asuka的速度比Shion慢，她决定在比赛中只和Shion格斗一次。本题设定，如果Asuka和Shion同时触碰浮标，则Asuka得分，并且Asuka还可以与Shion在浮标处格斗。在这种情况下，格斗发生在浮标被Asuka或Shion触碰之后。

Asuka的速度是V1米/秒，Shion的速度是V2米/秒。请问Asuka是否有赢的可能？

输入

输入的第一行给出整数t（0<t≤10000），然后给出t行，每行给出3个双精度变量T、V1和V2（0≤V1≤V2，T≥0），表示一个测试用例。

输出

如果存在Asuka赢得比赛的策略，则输出“Yes”，否则输出“No”。

提示

Asuka可以飞到连接浮标#2和浮标#3的边的中点，然后在那里等待Shion到来。当他们相遇时，Asuka和Shion格斗。此时，Shion会被击昏（这意味着Shion在100秒内不能移动），Asuka会飞回浮标#2，因为浮标#2已经被触碰了，她触碰浮标#2不会得分。但在那之后，她可以沿连接浮标的边飞到浮标#3、浮标#4、浮标#1，得3分。

试题来源：2015 ACM-ICPC Asia Shenyang Regional Contest

在线测试：HDOJ 5515，UVA 7244

试题解析

在Asuka和Shion之间进行的训练赛一共有5分可得：触碰4个浮标的4分和一场格斗的1分。

对于Asuka，要赢得比赛，可能有如下3种情况：

情况1：Asuka和Shion的速度一样（V1=V2），则Asuka和Shion同时到达浮标#2；然后Asuka和Shion进行一场格斗，Shion会被击昏；Asuka沿正方形场地的边到达浮标#3、浮标#4、浮标#1，赢得比赛。

情况2：Asuka的速度使得她在浮标#2和浮标#3之间的连线上的某点（未到浮标#3）和Shion相遇，即Shion沿正方形场地的边触碰浮标#2，然后沿连接浮标#2和浮标#3之间的连线向浮标#3飞行，Asuka则走直线，从浮标#1飞向该点。如图1.2-2所示。

Asuka和Shion在浮标#2与浮标#3间相遇的条件为。

设Asuka和Shion的相遇点与浮标#2的距离是x。在该点Asuka和Shion进行一场格斗，Shion会被击昏；然后Asuka沿直线飞到浮标#2，再飞向浮标#3和浮标#4。显然，相遇后，Asuka花费时间到达浮标#4，而Shion花费时间到达浮标#4。所以，如果Asuka能够先于Shion到达浮标#4，或者Asuka和Shion同时到达浮标#4，即，则Asuka获胜。

情况3：Asuka的速度使得她在浮标#3和浮标#4之间的连线上的某点（包括浮标#3，未到浮标#4）和Shion相遇，设该点与#4的距离为x，即Shion沿正方形场地的边已经触碰浮标#2和浮标#3；Asuka则走直线，从浮标#1飞向该点。如图1.2-3所示。在该点Asuka和Shion进行一场格斗，Shion会被击昏；然后Asuka沿直线飞到浮标#2，再沿正方形场地的边飞向浮标#3、浮标#4、浮标#1。也就是说，相遇后Asuka花费时间到达浮标#1，Shion花费时间到达浮标#1。如果Asuka能比Shion先到达浮标#1，或者Asuka和Shion同时到达浮标#1，则Asuka获胜。也就是说，如果，则Asuka获胜。

图　1.2-2

图　1.2-3

对于上述情况，如果Asuka能够获胜，则输出“Yes”，否则输出“No”。

参考程序

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PI;
const int N=1e5;
const double eps=1e-5;
const LL mod=1e9+7;
int main()
{
    int t, ca=1;                          //测试用例编号初始化
    scanf("%d", &t);                      //输入测试用例数
    while(t--)                            //依次处理每个测试用例
    {
        double t, v1, v2;                 // Shion格斗之后的昏迷时间为t，Asuka和
                                          // Shion的速度分别为v1、v2
        scanf("%lf%lf%lf", &t, &v1, &v2); //输入Shion格斗之后的昏迷时间
        printf("Case #%d: ", ca++);       //输出测试用例编号，计算下一个测试用例编号
                                          //分析Asuka赢得比赛的第一种情况
        if(v1==v2)                      
        {
            puts("Yes");
            continue;
        }
        //分析Asuka赢得比赛的第二种情况
        double tt1=300*sqrt(2.0)/v1;      // 计算Asuka从浮标#1沿对角线至浮标#3所用
                                          // 的时间
        double tt2=600.0/v2;              // 计算Shion走浮标#1-浮标#2-浮标#3所用
                                          // 的时间
        double v12=v1*v1, v22=v2*v2;      // 计算两者速度的平方
        double t1=300.0/v1;               // 计算Asuka走浮标#1-浮标#4所用的时间t1
        double t2=900.0/v2;               // 计算Shion走浮标#1-浮标#2-浮标#3-浮标
                                          // #4所用的时间
        if(t1>=t2)                        // 若在两者都走连线情况下，Asuka未先到达浮标
                                          // #4，则Asuka失败
        {
            puts("No");
            continue;
        }
        if(tt1<=tt2)                      // 若Asuka和Shion在浮标#2与浮标#3之间相
                                          // 遇，则计算相遇点与浮标#2的距离x
        {
            double dt=(600*v12)*(600*v12)-4*(v12-v22)*(v12*90000-90000*v22);
            double x=(-600.0*v12+sqrt(dt))/2.0/(v12-v22); 
            if((x+600)/v1<=t+(600-x)/v2)  //若Asuka先于Shion到达浮标#4，则获胜
            {
                puts("Yes");
                continue;
            }
        }
        //分析Asuka赢得比赛的第三种情况
        //计算Asuka和Shion在浮标#3与浮标#4之间的相遇点与浮标#4的距离x
            double dt=(1800*v12)*(1800*v12)-4*(v12-v22)*(v12*810000-90000*v22);
            double x=(1800.0*v12-sqrt(dt))/2.0/(v12-v22);
        //若Asuka比Shion先到浮标#1，则Asuka获胜；否则失败
            if(sqrt((300.0-x)*(300.0-x)+90000.0)/v1+900.0/v1<=t+(300+ x)/v2)
                puts("Yes");
            else
                puts("No");
    }
    return 0;
}
上一章目录下一章