Re: String Pattern Matching algo


<116Rohan@xxxxxxxxx> wrote in message
news:1146343948.469971.217040@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I came across a question in one of the Computing olympiad regarding
string pattern matching.

Write a program that will accept a fraction of the form N/D, where N is
the numerator and D is the denominator, that prints out the decimal
representation. If the decimal representation has a repeating sequence
of digits, it should be indicated by enclosing it in brackets. For
example, 1/3 = .33333333...is denoted as .(3), and 41/333 =
.123123123...is denoted as .(123).

Typical conversions are:

1/3 = .(3)
22/5 = 4.4
1/7 = .(142857)
3/8 = .375
45/56 = .803(571428)

Now I could not think how do I even start writing a logic for creating
a pattern.

IIRC, there is a recursive algorithm (using 1/X ?) to convert terminated
(non-repeating and not random values PI, etc.) decimals to the form N/D. If
so (and since they gave you a valid fraction), you could compute N/D as
decimal and then attempt to convert back to N/D. If the number is
non-repeating, the first N and D should be the same as the second conversion
N and D. If the number is repeating, it will be terminated by the precision
of the machine. This means that the first N and D will be different from
the conversion N and D, because it lost some precision. For the repeating
numbers, you then need to determine the length of the repeat. I don't know
if there is a simple method for that.


Rod Pemberton


.

Relevant Pages

  • Re: Making a decimal to fraction converter
    ... This is the full text of a program that converts a decimal number to a fraction, and handles repeating decimals correctly, including the case where there is a portion of the fractional part that is non-recurring. ... Dim value As Double, numer As Double, denom As Double ...
    (microsoft.public.dotnet.languages.vb)
  • Re: Making a decimal to fraction converter
    ... fraction, and handles repeating decimals correctly, including the case where there is a portion of the fractional part that is non-recurring. ... Note that the repeating test is not foolproof - for instance it will detect the repeating part of 1.25252 as 52, which might not be what was intended. ... This also means it will NOT work properly with decimal numbers created from a fraction, because the computer will usually round the last digit. ... Dim value As Double, numer As Double, denom As Double ...
    (microsoft.public.dotnet.languages.vb)
  • Re: Fraction to decimal
    ... to output the decimal representation of the fraction as a list in a particular form. ... The first member of the list is the whole number of the decimal representation. ... matlab separate the period of the number from the decimals that come before it. ... of the number and intend to try to pick out the repeating decimal from there. ...
    (comp.soft-sys.matlab)
  • Re: String Pattern Matching algo
    ... string pattern matching. ... Write a program that will accept a fraction of the form N/D, ... decimals to the form N/D. ... the conversion N and D, ...
    (comp.lang.c)