POJ 1930 Dead Fraction 题解 《挑战程序设计竞赛》

POJ 1930 Dead Fraction

赶论文：论文里无限循环小数到底是由哪两个数除出来的呢？求分母最小的那一对。

2.6 数学问题的解题窍门

小学奥数水平的无聊题目，没做过无限循环小数的奥数题也无妨，看看百度百科里的公式就可以套出来：

纯循环

用9做分母，有多少个循环数就几个9，比如0.3，3的循环就是9分之3，0.654，654的循环就是999分之654， 0.9，9的循环就是9分之9（1），以此类推。

混循环

先来看几个例子

例：把混循环小数0.228˙化为分数：

解：0.228˙

=[（228/1000）+8/9000）]

=228/（900+100）+8/9000

=[（228/900）-（228/9000）]+（8/9000）

=（228/900）+[（8/9000）-（228/9000）]

=（228/900）-（22/900）

=（228-22）/900

=206/900

=103/450；

例：把混循环小数0.123˙68˙化成分数：

解：0.123˙68˙=(0.12368+0.00000˙68˙)

=(12368/100000)+（68/9900000）

=[（12368/99000）-（12368/990000）]+（68/9900000）

=（12368/99000）+[（68/9900000）-（12368/9900000）]

=（12368/99000）-（12300/9900000）

=(12368-123)/99000

公式

用9和0做分母，首先有几个循环节就几个9，接着有几个没加入循环的数就加几个0，再用小数点后面的数减 没加入循环的数，比如0.43，3的循环，有一位数没加入循环，就在9后面加一个0做分母，再用43减4做分子，得 90分之39，0.145，5的循环就用9后面加2个0做分母，再用145减14做分子，得900分之131，0.549，49的循环，就 用99后面加1个0做分母，用549减5做分子，最后得990分之545，以此类推，能约分的要化简。

关键点在于题目在玩文字游戏，循环小数到底从哪一位开始没有明说，所以无脑暴力穷举一遍就行了。

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <string>
#include <limits>
using namespace std;

typedef unsigned long long ULL;

ULL gcd(ULL a, ULL b)
{
	if (b == 0)return a;
	return gcd(b, a%b);
}

ULL ten_pow(unsigned int x)
{
	ULL result = 1;
	for (unsigned int i = 0; i < x; ++i)
	{
		result *= 10;
	}
	return result;
}


///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	string line;
	while (cin >> line)
	{
		if (line == "0")
		{
			break;
		}
		string digit = line.substr(2, line.length() - 5);
		unsigned int length = digit.length();
		const ULL n = atoi(digit.c_str());
		if (n == 0)
		{
			cout << "0/1" << endl;
			continue;
		}
		ULL min_x = numeric_limits<ULL>::max();
		ULL min_y = 0;
		for (int i = 1; i <= length; ++i)
		{
			string first = digit.substr(0, length - i);
			ULL x = ten_pow(length) - ten_pow(length - i);
			ULL y = n - atoi(first.c_str());
			ULL d = gcd(x, y);
			x /= d;
			y /= d;
			if (min_x > x)
			{
				min_x = x;
				min_y = y;
			}
		}
		cout << min_y << '/' << min_x << endl;
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1930 Dead Fraction 题解 《挑战程序设计竞赛》