{"id":1100,"date":"2009-11-24T11:30:51","date_gmt":"2009-11-24T03:30:51","guid":{"rendered":"http:\/\/www.slyar.com\/blog\/?p=1100"},"modified":"2022-07-03T15:47:02","modified_gmt":"2022-07-03T22:47:02","slug":"poj-1650-cpp","status":"publish","type":"post","link":"http:\/\/www.slyar.com\/blog\/poj-1650-cpp.html","title":{"rendered":"POJ 1650 Integer Approximation C++\u7248"},"content":{"rendered":"

\u6587\u7ae0\u4f5c\u8005\uff1a\u59dc\u5357(Slyar) <\/span>\u6587\u7ae0\u6765\u6e90\uff1aSlyar Home (www.slyar.com<\/a>) \u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff0c\u8c22\u8c22\u5408\u4f5c\u3002<\/p>\n

\u66b4\u529b\u679a\u4e3e<\/p>\n

<\/p>\n

Description<\/span><\/p>\n

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 \u2248 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.<\/p>\n

Input<\/span><\/p>\n

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).<\/p>\n

Output<\/span><\/p>\n

Output file must contain two integers, N and D, separated by space.<\/p>\n

Sample Input<\/span><\/p>\n

3.14159265358979
\n10000<\/p>\n

Sample Output<\/span><\/p>\n

355 113<\/p>\n

Slyar:\u6c42\u51fa\u5728L\u8303\u56f4\u5185\u7684\u4e24\u4e2a\u6570\uff0c\u4f7f\u5f97\u5b83\u4eec\u76f8\u9664\u540e\u51cf\u53bbA\u7684\u7ed3\u679c\u7684\u7edd\u5bf9\u503c\u6700\u5c0f\u3002\u66b4\u529b\u679a\u4e3e\u5c31\u597d\u4e86\uff0c\u8fd9\u9898\u5f88\u6076\u5fc3...<\/span><\/p>\n

\r\n#include \r\n#include \r\n\r\nusing namespace std;\r\n\r\nint main()\r\n{\r\n    double a, min, temp;\r\n    int i, j, l, n, d;\r\n    \r\n    cin >> a >> l;\r\n    n = d = 1;\r\n    min = 20;\r\n\r\n    for (i = 1; i <= l; i++)\r\n    {\r\n        j = (int)(i \/ a);\r\n        \r\n        if (j > l) continue;\r\n        temp = fabs(a - (double)i \/ (double)j);\r\n        if (temp < min)\r\n        {\r\n            min = temp;\r\n            n = i;\r\n            d = j;\r\n        }\r\n        \r\n        j++;\r\n        if (j > l) continue;\r\n        temp = fabs(a - (double)i \/ (double)j);\r\n        if (temp < min)\r\n        {\r\n            min = temp;\r\n            n = i;\r\n            d = j;\r\n        }\r\n    }\r\n    \r\n    cout << n << \" \" << d << endl;\r\n    \r\n    \/\/system(\"pause\");\r\n    return 0;\r\n}\r\n<\/pre>\n
\u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff1aSlyar Home<\/a> » POJ 1650 Integer Approximation C++\u7248<\/a><\/p>","protected":false},"excerpt":{"rendered":"
\u6587\u7ae0\u4f5c\u8005\uff1a\u59dc\u5357(Slyar) \u6587\u7ae0\u6765\u6e90\uff1aSlyar Home (www.slyar.com) \u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff0c\u8c22\u8c22\u5408\u4f5c\u3002 \u66b4\u529b\u679a\u4e3e \u8f6c\u8f7d\u8bf7\u6ce8\u660e\uff1aSlyar Home » POJ 1650 Integer Approximation C++\u7248<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1103],"tags":[1006],"class_list":["post-1100","post","type-post","status-publish","format-standard","hentry","category-acm-oj-solution","tag-poj"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t