1.3　在实数和整数之间转换

程序设计语言的基本数据类型有整数型、实数型、字符型等。有些试题的数据对象是实数和整数，并且要进行实数和整数之间的转换运算。

【1.3.1 I Think I Need a Houseboat】是实数向整数转换的实验范例，【1.3.2 Integer Approximation】则是在整数运算过程中产生实数的实验范例。

【1.3.1　I Think I Need a Houseboat】

Fred Mapper计划在Louisiana购买一块土地，并在这块土地上建造他的家。在对土地调查后，他发现，由于Mississippi河的侵蚀，Louisiana州的土地每年减少50平方英里。因为Fred准备在他所建的家中度过后半生，所以他要知道他的土地是否会因为河流的侵蚀而消失。

在做了大量研究后，Fred发现正在失去的土地构成一个半圆形（半圆如图1.3-1所示）。这一半圆形是一个圆的一部分，圆心在(0,0)，二等分这个圆的线是x轴，x轴的下方是河水。在第1年开始的时候，这个半圆的面积为0。

图　1.3-1

输入

输入的第一行是一个正整数，表示有多少个测试用例（N）。后面有N行，每行给出笛卡儿坐标x和y，表示Fred考虑购买的土地的位置。这些数是浮点数，以英里为单位。y坐标非负。不会给出坐标（0,0）。

输出

对每个输入的测试用例，输出一行。这一行的形式为“Property N:This property will begin eroding in year Z.”，其中N是测试用例编号（从1开始记数），Z表示Fred的土地在第Z年结束的时候要落到半圆形中（从1开始记数），Z必须是一个整数。在最后一个测试用例后，输出“END OF OUTPUT.”。

说明

1）购买的土地不会在半圆形的边界上，它或者落在半圆形内，或者位于在半圆形外。

2）这一问题被自动裁判，所以输出要精确匹配，包括大小写、标点符号和空格，以及到行末的完整的句子。

3）所有的地点都以英里为单位。

试题来源：ACM Mid-Atlantic 2001

在线测试：POJ 1005，ZOJ 1049，UVA 2363

试题解析

由于测试用例的个数N预先确定，且每个测试用例是笛卡儿坐标，因此可直接采用for循环处理所有测试用例。第i个测试用例（xi,yi）与圆心（0,0）构成的半圆面积即土地被河流侵蚀的范围。由于每年减少50平方英里土地，而年份是整数，因此淹没（xi,yi）的年份应为大于的最小整数，这个取整过程应使用向上取整函数ceil(x)。若使用向下取整函数floor(x)，则会提前1年失去土地。

参考程序

#include <stdio.h>               //预编译命令
#include <math.h>
#define M_PI 3.14159265
int num_props;                   //定义测试用例数为整数
float x, y;                      //定义笛卡儿坐标为单精度实数
int i;
double calc;                     //定义半圆面积/50为双精度实数
int years;                       //定义失去土地的年份为整数
int main(void)                   //主函数            
{                                //主函数开始
    scanf("%d", &num_props);     //输入测试用例数
    for (i = 1; i <= num_props; i++)
    {
        scanf("%f %f", &x, &y);  //输入第i个考虑购买的土地位置，计算和输出半圆面积/50
//（向上取整后即土地失去的年份）
        calc = (x*x + y*y)* M_PI / 2 / 50;
        years = ceil(calc);                
        printf("Property %d: This property will begin eroding in year %d.\n", i, years);
    }
    printf("END OF OUTPUT.\n");
}

【1.3.2　Integer Approximation】

FORTH程序设计语言不支持浮点数的算术运算。它的发明者Chuck Moore坚持认为浮点数的运算太慢，而且在大多数时候都可以用适当的整数比来仿真浮点数。例如，要计算半径为R的圆的面积，他建议使用R×R×355/113这一公式，这实际上是非常精确的。整数比355/113≈3.141593是π的近似值，绝对值误差约为2×10-7。给出一个浮点数A和一个整数限制L，请找出在范围[1,L]内的两个整数N和D（1≤N,D≤L），使得N和D的比是A的最佳整数近似，即找到绝对值误差|A-N/D|最小的两个整数N和D。

输入

输入的第一行给出浮点数A（0.1≤A<10），精度达15位小数。第二行给出整数限制L（1≤L≤100000）。

输出

输出给出两个用空格分隔的整数：N和D。

试题来源：ACM Northeastern Europe 2001,Far-Eastern Subregion

在线测试：POJ 1650

试题解析

本题采用“追赶法”，在分子和分母不超过整数限制的前提下不断枚举a和b。设最小绝对值误差为Min，整数限制为n。初始时取a、b为1，Min为n+1；然后每次对a、b求商，调整Min：

·在a/b>x的情况下，若a/b-x小于Min，则Min调整为a/b–x，记录下此时的a和b值；为了使下一次枚举时的a/b更趋近x，b增加1。

·在a/b≤x的情况下，若x-a/b小于Min，则Min调整为x-a/b，记录下此时的a和b值；为了使下一次枚举时的a/b更趋近x，a增加1。

本题处理的数据是精度达15位小数的浮点数，因此变量x、a、b、n和Min采用双精度类型。

参考程序

#include <stdio.h>
int main()
{
    double x, a, b, n, Min, n1, n2; //浮点数x，整数限制n，当前分母和分子为a和b，绝对值的最
                                    //小误差为Min，绝对值误差为Min时的分母和分子为n1和n2
    scanf("%lf%lf", &x, &n);        //输入浮点数x和整数限制n
    a = 1;                          //绝对值误差最小的两个整数初始化
    b = 1;
    Min = n + 1;                    //最小误差值初始化
    while(a <= n && b <= n)         //若两个整数未超过限制
    {
        if (a / b > x)              //若a/b在数轴上位于x右方且与x的距离值目前最小，
                                    //则记下a和b并将a/b – x调整为最小绝对值误差
        {
            if (a / b - x < Min)
            {
                Min = a / b - x;
                n1 = a;
                n2 = b;
            }
            b++;                    //增大分母b，使a/b更趋近x
        }
//若在数轴上，a/b位于x左方且与x的距离值目前最小，则记下a和b并将x-a/b调整为最小绝对值误差
        else
        {
            if (x - a / b < Min)
            {
                Min = x - a / b;
                n1 = a;
                n2 = b;
            }
            a++;                    //增大分子a，使a/b更趋近x
        }
    }
    printf("%.0f %.0f\n", n1, n2);  //输出绝对值误差|x-n1/n2|最小的n1和n2
    return 0;
}
上一章目录下一章