Fractional representation of 11076 floating-point numbers (priority)
Time limit :1000MS Memory limit :1000K GCC; VC
Description
To accurately represent a floating-point number, it is best to use fractions. Either finite or infinite repeating decimals can be converted to fractions. The repeating section of infinite repeating decimals is marked with parentheses. 0.9 = 9/10
0.(3) = 0.3(3) = 0.3(33) = 1/3
Of course, a decimal can be expressed in several fractions, but we are only interested in the simplest fraction (that is, the lowest denominator), as in:
0.3(33) = 1/3 = 3/9
Because any number can be converted to a sum of an integer and a pure decimal, the whole number part is relatively simple and you don’t need to do anything extra, just convert the pure decimal part into a fraction, and the fraction part of the whole number part is very easy.
Now, given a positive pure decimal (either a finite or an infinite repeating decimal), return the pure decimal in its simplest fraction form.
Input format
Given a pure decimal, if you are repeating a decimal indefinitely, mark the repeating section with parentheses and enter a decimal that does not exceed 100 characters.
Note: If you find high precision difficult, consider using 64 – bit integers first. The test data is not too long, and the number of bits does not exceed the range of 64 – bit integers. That is, if you do it with 64 integers, you can pass this problem.
The output format
Output: to the simplest fraction form, numerator first, denominator after, space in the middle.
Enter the sample
0.3 (33)
The output sample
1 3
prompt
This question involves the following questions:
First, the string input problem
C =getchar())! = ‘\n’ and so on, one character at a time, and then determine whether it is a carriage return symbol to end the input, such a way to run on your machine will not have a problem, but OJ system will have an error, cannot output results, because OJ test platform line end is not ‘\n’ character. Accept data using scanf %s, cin, etc., will automatically recognize the end character, you do not have to recognize or absorb carriage return characters in your program.
char a[105];
scanf(“%s”,a); Or cin > > a.
Two, high precision or 64-bit integer representation of the problem
The input decimal should contain no more than 100 characters. Such a long number is meant to be solved with a high degree of precision. But the background test data isn’t that long (or I’m masking the longest set of test data), so relax, 64-bit integers are still allowed to pass this problem!
All numerator and denominator variables, as well as the greatest common divisor, must be implemented as 64 – bit integers. 1) the long long type in gnu GCC /g++, or the unsigned long long type in gnu GCC /g++. The input and output are cin and cout. long long a; cin >> a; cout << a;
You can also use :(note that this OJ system GCC /g++ does not support 64-bit integers as “%I64d”, but the standard gnu GCC does support the following, which runs correctly on codeblocks) long long a; scanf(“%I64d”,&a); printf(“%I64d”,a);
2) VC uses __int64, or unsigned __int64
__int64 a;
scanf(“%I64d”,&a);
printf(“%I64d”,a);
Vc, 64 integer do not use CIN and Cout to input and output, it is said that vc 64-bit integer compatibility is not good, will error! You can test the following procedures
Is there an error under VC?
__int64 a;
cin >> a;
cout << a;
3. How to solve this problem
Let’s say we’re putting in pure decimals, but let’s just ignore the fact that we have common factors in the numerator and denominator.
(1) Suppose finite decimal: X = 0. A1a2… An, where a1,a2… And an are all numbers from 0 to 9. X = 0. A1a2… The an = a1a2… an/10^n
(2) Assume an infinite repeating decimal: X = 0. A1a2… The an (b1b2… Bm), where a1,a2… , an, b1, b2,… ,bm are all numbers from 0 to 9, and the parentheses are cyclic sections. The first step is to reduce X to a pure decimal with only the repeating part. X = 0. A1a2… The an (b1b2… Bm) (10 ^ n) * X = a1a2… The an + 0. (b1b2… X = (bm) a1a2… The an + 0. (b1b2… Bm)/(10^n) where, a1a2… An is an integer part, easy to solve. Focus on the decimal part 0.(b1B2… Bm) in fractional form, plus the integer part. Step 2, consider Y = 0.(b1b2… Bm), convert Y into a fraction, (10^m)Y = b1b2… Bm + 0. (b1b2… Bm) (10 ^ (m) – 1) Y = b1b2… Bm Y = b1b2… Bm/(10^m)-1) substitute the Y of the second step into the X of the first step: X = (a1a2… The an + Y)/(10 ^ n) = ((a1a2… An) (10 ^ (m) – 1) + (b1b2… bm)) / (((10m)-1)(10n))
At this point, any finite decimal, or infinite repeating decimal, can be expressed as a fraction, the numerator and denominator of the fraction as analyzed above. However, the numerator and denominator are not necessarily the most simplified, so divide the numerator and denominator again, delete the common factors, and A/B = (A/GCD(A,B))/(B/GCD(A,B)), and convert it into A simple form. Here, GCD(A,B) represents the greatest common divisor of A and B.
The example they give is 0.3(33) and if it is 1/3, analyze it according to the formula above.
So let’s say the input is X. X = 0.3(33) 10X = 3.(33) X = 3/10 + 0.(33)/10 // 0.(33), and change the original number before the cyclic segment // to the part of the finite decimal (because the finite decimal is easier to deal with), now we need to focus on how to convert only the pure decimal of the cyclic segment // minute into a fraction.
Y = 0.(33) (10^2) Y = 33 + Y (10^ 2-1) Y = 33 Y = 33/99
Then initial data: X = 3/10 + (1/10)Y X = 3/10 + (1/10)(33/99) X = 330/990
Subtract the greatest common divisor from the numerator and denominator and you get X = 1/3
#include "stdio.h" #include "stdlib.h" #include "string.h" #include "math.h" using namespace std; long long GCD(long long large,long long small) { if (large < small) { long long tmp = large; large= small; small = tmp; } if (small == 0) return large; else return GCD(small,large % small); } int findCh(char str[],char ch) { for(int i=2; i<strlen(str); i++) { if(str[i]==ch) { return i; } } return 0; } int main() { char num[101]; // scanf("%s",&num); cin >> num; int len = strlen(num); long long Top=0; // long long Bottom; / / the denominator the if (findCh (num, '(') = = 0) / * decimal fraction * / {for (int I = 2; i<len; i++) { Top=Top*10+num[i]-'0'; /* convert the numerator to a positive decimal number */} Bottom=1; for(int i=2; i<len; i++) { Bottom *= 10; } //printf("%ld\n",Bottom); long long gcd = GCD(Top,Bottom); Top /=gcd; Bottom /=gcd; printf("%lld %lld\n",Top,Bottom); // cout << Top << endl; Int start =findCh(num,'('); int end =findCh(num,')'); int n = start-2; int m = end - start - 1; for(int i=2; i<start; i++) { Top=Top*10+num[i]-'0'; } Bottom=0; for(int i=start+1; i<len-1; i++) { Bottom=Bottom*10+num[i]-'0'; } long long mp = 1; mp=pow(10,m); long long np = 1; np=pow(10,n); Top = Top*(mp-1)+Bottom; Bottom = (mp-1)*np; long long gcd = GCD(Top,Bottom); cout<< Top/gcd << " " <<Bottom/gcd; } return 0; }Copy the code