1334
:简单的说就是分数逼近,分母从1
开始,这题涉及到两个知识点:
- 在
<math.h>
中,abs()
获得的是整数的绝对值,获得浮点数的绝对值应使用fabs()
; - 有浮点数比较的情况应该转换为整数比较,因为在计算机中,浮点数的比较是不准确的。
这道题的代码如下:
#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;
}
}