Re: String Pattern Matching algo

On 29 Apr 2006 13:52:28 -0700, "116Rohan@xxxxxxxxx"
<116Rohan@xxxxxxxxx> wrote:

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.
Then I thought that maybe I should start comparing characters from the
right rather than the left.
But these two examples even negate that theory;

1/7 gives me ---> 0.1428571428571428571428571429 on a 16bit machine

45/56 gives me ---> 0.8035714285714285714285714286

I was trying to eliminate the last number as it rounds off, and so I
can start creating combinations from right to left. But nothing seems
to be working.

Any hints/suggestions will be appreciated.

Somewhere in the depths of number theory remembrances, I recall a
method of determining when the repetition starts and the length of the
repetition. Unfortunately, the details have long been forgotten.
Attempting to compare digits is error prone because if you see a value
of .121212 you might conclude the answer is .(12) when the answer
really is .(1212121212123).

This is really more an algorithm question rather than C.


Remove del for email
.