`

HDU 1717 小数化分数2

阅读更多
http://acm.hdu.edu.cn/showproblem.php?pid=1717

题意:小数化分数

Sample Input
3
0.(4)
0.5
0.32(692307)   //括号里是循环节

Sample Output
4/9
1/2
17/52


众所周知,有限小数是十进分数的另一种表现形式,因此,任何一个有限小数都可以直接写成十分之几、百分之几、千分之几……的数。那么无限小数能否化成分数?

    首先我们要明确,无限小数可按照小数部分是否循环分成两类:无限循环小数和无限不循环小数。无限不循环小数不能化分数,这在中学已经得到详尽的解释
    无限循环小数是可以化成分数的。那么,无限循环小数又是如何化分数的呢?
    由于它的小数部分位数是无限的,显然不可能写成十分之几、百分之几、千分之几……的数。
    其实,循环小数化分数难就难在无限的小数位数。
    所以我就从这里入手,想办法“剪掉”无限循环小数的“大尾巴”。
    策略就是用扩倍的方法

例子:

把0.4777……和0.325656……化成分数。

1:0.4777……×10=4.777……①

0.4777……×100=47.77……②

用②-①即得:

0.4777……×90=47-4

所以, 0.4777……=43/90



2:0.325656……×100=32.5656……①

0.325656……×10000=3256.56……②

用②-①即得:

0.325656……×9900=3256.5656……-32.5656……

0.325656……×9900=3256-32

所以, 0.325656……=3224/9900

以上是网上复制的分析

下面我描述一下算法:

第一步:找出最少扩展k1位使其小数部分刚好成周期串,此时整数部分为xx

第二步:找出再次扩展k2位(k2>0)使其小数部分刚好成周期串,此时总共扩展了(k1+k2)位,整数部分为yy

第三步:分子==yy-xx, 分母==pow(10.0, k1+k2) - pow(10.0, k1)

第四步:利用最大公约数化简

其实说到这里,大家都可以YY了,只是字符串怎么提取出来并且转成整数求分子呢?貌似有点麻烦,我的代码用了函数itoa,挺好用的


仅供参考:
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;

int gcd (int a, int b)
{
	int t;
	while (a)
	{
		t = a;
		a = b % a;
		b = t;
	}
	return b;
}

int main()
{
	int a, b, i, len, t, xx, yy, p, q;
	char s[20], x[20], y[20];
	scanf ("%d", &t);
	while (t--)
	{
		scanf ("%s", s);
		len = strlen (s);
		for (i = 0; i < len; i++)
			if (s[i] == '.')
				break;
		a = 0;
		for (i = i + 1; i < len; i++)
		{
			if (s[i] == '(')
				break;
			x[a] = y[a] = s[i];
			a++;
		}
		x[a] = 0;
		xx = atoi (x);    //把x转成整数
		b = 0;
		for (i = i + 1; i < len; i++)
		{
			if (s[i] == ')')
				break;
			y[a+b] = s[i];
			b++;
		}
		y[a+b] = 0;
		yy = atoi (y);
		if (b == 0)    //说明这是有限非循环小数
		{
			p = yy;
			q = pow (10.0, a);
		}
		else
		{
			p = yy - xx;
			q = pow (10.0, a+b) - pow (10.0, a);
		}
		int temp = gcd (p, q);
		p /= temp, q /= temp;
		printf ("%d/%d\n", p, q);
	}
	return 0;
}
分享到:
评论

相关推荐

    小数化分数2(hdu1717)

    题目"小数化分数2(hdu1717)"正是这样一种挑战,它要求我们开发一个算法来精确地表示给定的小数为一个分数形式。 首先,我们要理解小数到分数转换的基本原理。对于有限小数,这个过程相对直接,因为我们可以直接...

    hdu.rar_hdu

    2. **高级算法**:包括动态规划(状态转移、记忆化搜索)、贪心策略、回溯法、分支限界法等。 3. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图(邻接矩阵、邻接表、最小生成树、...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    HDU-EID-V2-核心板1

    CAN(Controller Area Network)总线,如PB9/CAN1_TX和PB8/CAN1_RX,用于汽车和工业自动化中的通信。还有LCD(Liquid Crystal Display)接口,用于连接显示器,如PD7/LCD_CS(片选)、PD6/GPD5/LCD_WR(写信号)和...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    hdu2101解决方案

    hdu2101AC代码

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    杭电ACMhdu1163

    2. **数据结构**:常用的数据结构包括数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图等,对于不同的问题,选择合适的数据结构能有效提高解题效率。 3. **字符串处理**:杭电ACM中的题目可能涉及到...

    hdu动态规划算法集锦

    根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...

    2-sat---hdu3062

    2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

    Hdu1000—2169部分代码

    HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...

    hdu acm1166线段树

    hdu 1166线段树代码

Global site tag (gtag.js) - Google Analytics