emu in blogjava
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
RecurringNumbers (code jam china 1000分真题)

Problem Statement

    

A rational number is defined as a/b, where a and b are integers, and b is greater than 0. Furthermore, a rational number can be written as a decimal that has a group of digits that repeat indefinitely. A common method of writing groups of repeating digits is to place them inside parentheses like 2.85(23) = 2.852323 ... 23...

Given a decimal representation of a rational number in decimalNumber, convert it to a fraction formatted as "numerator/denominator", where both numerator and denominator are integers. The fraction must be reduced. In other words, the denominator must be as small as possible, but greater than zero.

Definition

    
Class: RecurringNumbers
Method: convertToFraction
Parameters: String
Returns: String
Method signature: String convertToFraction(String decimalNumber)
(be sure your method is public)
    

Constraints

- decimalNumber will have between 3 and 10 characters inclusive.
- decimalNumber will contain only characters '0' - '9', '.', '(' and ')'.
- The second character in decimalNumber will always be '.'.
- There will be at most one '(' and ')' in decimalNumber.
- '(' in decimalNumber will be followed by one or more digits ('0' - '9'), followed by ')'.
- ')' in decimalNumber will not be followed by any other character.

Examples

0)
     
"0.(3)"
Returns: "1/3"
0.(3) = 0.333... = 1/3
1)
     
"1.3125"
Returns: "21/16"
Note there are no recurring digits here, although we could write it as 1.3125(0) or 1.3124(9).
2)
     
"2.85(23)"
Returns: "14119/4950"
2.85(23) = 2.852323... = 285/100 + 23/9900 = 28238/9900 = 14119/4950. Make sure to reduce the fraction, as shown in the final step.
3)
     
"9.123(456)"
Returns: "3038111/333000"
4)
     
"0.111(1)"
Returns: "1/9"
5)
     
"3.(000)"
Returns: "3/1"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

posted on 2005-12-23 09:30 emu 阅读(1334) 评论(2)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

评论

# re: RecurringNumbers (code jam china 1000分真题) 2006-07-07 15:24 黎吾平
import java.util.*;

public class RecurringNumbers
{
public static void main(String[] args)
{
System.out.println(convertToFraction("9.123(456)"));
}

public static String convertToFraction(String decimalNumber)
{
int intPart = Integer.parseInt(decimalNumber.substring(0, 1)); //整数部分

int dotIndex = decimalNumber.indexOf('.'); //小数点的位置
int braceIndex = decimalNumber.indexOf('('); //左括号的位置
int lastIndex = 0;

if (braceIndex == -1) //无循环部分
{
lastIndex = decimalNumber.length();
}
else //有循环部分
{
lastIndex = braceIndex;
}

//读取非循环部分
String part1 = decimalNumber.substring(dotIndex+1, lastIndex);

int numerator, denominator = 0;
if (braceIndex != -1) //有循环部分
{
//读循环部分
lastIndex = decimalNumber.indexOf(')');
String part2 = decimalNumber.substring(braceIndex+1, lastIndex);


//生成全是9的数，长度为循环部分的长度
for (int i = 0; i < part2.length(); i++)
{
denominator = denominator * 10 + 9;
}

if (part1.length() == 0) //如果非循环部分为空
{
numerator = Integer.parseInt(part2) - 0;
}
else
{
numerator = Integer.parseInt(part1 + part2) - Integer.parseInt(part1);
denominator *= ((int)Math.pow(10, part1.length()));
}
}
else //无循环部分
{
numerator = Integer.parseInt(part1);
denominator = (int)Math.pow(10, part1.length());
}

//加上整数部分并化简分数
numerator += denominator * intPart;
int min = denominator > numerator ? numerator : denominator;
for (int i = 2; i <= min;)
{
if ((numerator % i == 0) && (denominator % i == 0))
{
numerator /= i;
denominator /= i;
i = 2;
}
else
{
i++;
}
}

return Integer.toString(numerator) + "/" + Integer.toString(denominator);
}
}  回复  更多评论
  

# re: RecurringNumbers (code jam china 1000分真题) 2011-08-14 11:46 li.stayhere
题目很全。 这个题目的关键是转换为等比级数的形式(xyz)=xyz/(10的三次方 - 1)  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航:
博客园   IT新闻   Chat2DB   C++博客   博问