Dead Fraction
Time Limit: 1000MS | Memory Limit: 30000K |
Total Submissions: 1198 | Accepted: 354 |
Description
Mike is frantically scrambling to finish his thesis at the last minute. He needs to assemble all his research notes into vaguely coherent form in the next 3 days. Unfortunately, he notices that he had been extremely sloppy in his calculations. Whenever he needed to perform arithmetic, he just plugged it into a calculator and scribbled down as much of the answer as he felt was relevant. Whenever a repeating fraction was displayed, Mike simply reccorded the first few digits followed by "...". For instance, instead of "1/3" he might have written down "0.3333...". Unfortunately, his results require exact fractions! He doesn't have time to redo every calculation, so he needs you to write a program (and FAST!) to automatically deduce the original fractions.
To make this tenable, he assumes that the original fraction is always the simplest one that produces the given sequence of digits; by simplest, he means the the one with smallest denominator. Also, he assumes that he did not neglect to write down important digits; no digit from the repeating portion of the decimal expansion was left unrecorded (even if this repeating portion was all zeroes).
Input
There are several test cases. For each test case there is one line of input of the form "0.dddd..." where dddd is a string of 1 to 9 digits, not all zero. A line containing 0 follows the last case.
Output
For each case, output the original fraction.
Sample Input
0.2...
0.20...
0.474612399...
0
Sample Output
2/9
1/5
1186531/2500000
Hint
Note that an exact decimal fraction has two repeating expansions (e.g. 1/5 = 0.2000... = 0.19999...).
Source
Waterloo local 2003.09.27
/*
這題主要是給出一個無限循環小數,要求去求他所對應的具有最小分母的分數。無限循環小數轉換為分數有
一定的規律和方法可循:
(1)假設輸入小數為0.i1 i2 ... it j1 j2 ... jk,即j1 j2 ... jk是循環的部分
那麼這個分數可以分兩部分來計算即不循環的部分和循環的部分.
(2)先來看不循環的部分,這個非常簡單.即為 i1i2 ... it / 10 ^ t,即不循環部分的分子分母分别為:
upd = i1 i2 ... it; downd = 10 ^ t;
(3)再來看循環部分,這部分有點難.在數論中的典型做法是:
取分子up為:j1 j2 ... jk
分母down為: 10 ^ (t + k) - 10 ^ t
(4)那麼最後所得的分數即為: upd / downd + up / down = (upd * down + downd * up) / (down * up)
(5)注意計算的時候要約分.另外由于題目沒有明确給出循環部分的長度,是以需要自己枚舉,然後計算出
所有的分數取分母最小的.另外要注意的是輸入中含有全0的情況(輸出0/1),這個太惡心了,因為題目明确說
了輸入不全為0的,害我WA了好幾次.
*/
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
char input[20];
int spos, epos;
__int64 minup, mindown;
__int64 gcd(__int64 a, __int64 b)
{
if(b == 0) return a;
else return gcd(b, a % b);
}
//利用最大公約數來約分
void trim(__int64 &up, __int64 &down)
{
__int64 gcdval;
while((gcdval = gcd(up, down)) != 1)
{
up /= gcdval;
down /= gcdval;
}
}
//判斷是否全0
bool allZero()
{
for(int i = strlen(input) - 4; i >= 2; i--)
if(input[i] != '0') return false;
return true;
}
int main()
{
while(scanf("%s", input) && strcmp(input, "0") != 0)
{
//當不全0時
if(!allZero())
{
mindown = -1;
epos = strlen(input) - 4; //輸入字元串數字位的結束位置
spos = 2; //小數點後面的起始位置
__int64 up = 0, down = 0, upd = 0, downd = 0, dupdown;
//枚舉循環部分的起始位置
for(int t = spos; t <= epos; t++)
{
upd = up = 0;
int k = spos;
while(k < t && input[k] == '0') k++; //找到非循環部分第一個不為0的位置
for(; k <= epos; k++)
{
if(k < t) upd = upd * 10 + int(input[k] - '0'); //統計非循環部分的分子值
if(k >= t) up = up * 10 + int(input[k] - '0'); //統計循環部分的分子值
}
downd = pow(10.0, t - spos); //非循環部分的分母值
down = pow(10.0, epos - spos + 1); //所有小數部分的分母值
dupdown = pow(10.0, epos - t + 1); //循環部分的分母值
down = down - down / dupdown; //制造循環部分小數的最終分母值
if(up != 0) trim(up, down); //約分
if(upd != 0) trim(upd, downd); //約分
__int64 newup, newdown;
newup = up * downd + down * upd;
newdown = down * downd;
if(newup != 0) trim(newup, newdown); //計算最終結果
if(mindown == -1 || newdown < mindown) //取分母最小的
{
mindown = newdown;
minup = newup;
}
}
printf("%I64d/%I64d/n", minup, mindown);
}
//全為0的情況
else printf("0/1/n");
}
return 0;
}