Life of xhu

About

HOJ_1334 & HOJ_1357

Feb 11, 2014

  |   #HOJ   |   #Algorithm

1334:简单的说就是分数逼近,分母从1开始,这题涉及到两个知识点:

  1. <math.h>中,abs()获得的是整数的绝对值,获得浮点数的绝对值应使用fabs()
  2. 有浮点数比较的情况应该转换为整数比较,因为在计算机中,浮点数的比较是不准确的。

这道题的代码如下:

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    int gain, lose, count, tmp3, tmp2, tmp1, test = 0;
    while(cin >> gain >> lose){
        if(test != 0)
            cout << endl;
        test++;
        count = 1;
        tmp1 = 1;
        tmp2 = (int)((double)gain / (double)lose + 0.5);
        cout << tmp2 << '/' << 1 << endl;
        while(count++){
            tmp3 = (int)((double)gain / (double)lose * (double)count + 0.5);
            if(count * abs(tmp2 * lose - gain * tmp1) > tmp1 * abs(tmp3 * lose - gain * count)){
                cout << tmp3 << '/' << count << endl;
                tmp2 = tmp3;
                tmp1 = count;
            }
            if(tmp3 * lose == gain * count)
                break;
        }
    }
}

1357:题意是,针对输入的m, a, b三个数,找出两个质数p, q, 使p * q <= m,且a / b <= p / q <= 1,想到了刚刚学会的筛法,然后把后面的浮点比较转换为整数比较,感觉应该很容易。

可是事实不是那么简单,使用筛法后,在HOJ上出现了超时错误,然后看了网上一个大神的代码,想到应该把质数放到一个数组里然后打表,这样可以减少循环次数,然后把代码放到HOJ上,仍然超时。。。

然后我把大神的代码放到HOJ上试了试,还是超时。。。

这道题就到此为止了,我觉得我是找不出时间更短的方法了,代码如下,不过过不了HOJ

#include <iostream>
using namespace std;
int m, a, b, num = 0, result1, result2, notPrime[100010], prime[10000];

void init(int data[]){
    for(int i = 0; i < 100010; i++)
        notPrime[i] = 0;

    for(int i = 2; i < 100010; i++){
        for(int j = i * 2; j < 100010; j += i)
            notPrime[j]++;
    }

    for(int i = 2; i < 100010; i++){
        if(!notPrime[i]){
            prime[num] = i;
            num++;
        }
    }
}

int main(){
    init(notPrime);
    while((cin >> m >> a >> b) && !(m == 0 && a == 0 && b == 0)){
        result1 = 2;
        result2 = 2;
        for(int i = num - 1; i >= 0; i--){
            for(int j = num - 1; j >= i; j--){
                if(prime[i] * prime[j] <= m && a * prime[j] <= b * prime[i] && prime[i] * prime[j] >= result1 * result2){
                    result1 = prime[i];
                    result2 = prime[j];
                }
            }
        }
        cout << result1 << ' ' << result2 << endl;
    }
}