放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理,大约每周末一次。另外,不要叫我楼主,谢谢。

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 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机