2013
11-10

Integer Approximation

The FORTH programming language does not support floating-point arithmetic at all. Its author, Chuck Moore, maintains that floating-point calculations are too slow and most of the time can be emulated by integers with proper scaling. For example, to calculate the area of the circle with the radius R he suggests to use formula like R * R * 355 / 113, which is in fact surprisingly accurate. The value of 355 / 113 ≈ 3.141593 is approximating the value of PI with the absolute error of only about 2*10-7. You are to find the best integer approximation of a given floating-point number A within a given integer limit L. That is, to find such two integers N and D (1 <= N, D <= L) that the value of absolute error |A - N / D| is minimal.

The first line of input contains a floating-point number A (0.1 <= A < 10) with the precision of up to 15 decimal digits. The second line contains the integer limit L. (1 <= L <= 100000).

Output file must contain two integers, N and D, separated by space.

3.14159265358979
10000


355 113

/* @author: */
import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
double a;
int d;
a=sc.nextDouble();
d=sc.nextInt();

double ans;
double min=a;
int v1=0,v2=0,m=1,n=1;
while(m<=d&&n<=d)
{
ans=m*1.0/n*1.0;
if(ans>=a)
{
if(min>ans-a)
{
min=ans-a;
v1=m;
v2=n;
}
n++;
}
else if(ans< a)
{
if(min>a-ans)
{
min=a-ans;
v1=m;
v2=n;
}
m++;
}
}
System.out.printf("%d %d",v1,v2);
}
}

1. #include <stdio.h>
int main(void)
{
int arr[] = {10,20,30,40,50,60};
int *p=arr;
printf("%d,%d,",*p++,*++p);
printf("%d,%d,%d",*p,*p++,*++p);
return 0;
}

为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下？

2. 第23行：
hash = -1是否应该改成hash[s ] = -1

因为是要把从字符串s的start位到当前位在hash中重置

修改提交后能accept，但是不修改居然也能accept

3. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

4. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish