11******@gmail.com 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.

Here's a hint. For a fraction in the range 0 to 1, it will be in the form

.baaaa

where b has k digits and a has n

This number can be written as

pow(10,-k)( b + a/(pow(10,n)-1))

^^^^^^^^^^^^

(Q)This part is n nines

The expression labeled with Q is all nines, so it has no factors which

are 2 or 5. In your rational expression N/D collect the factors of 2

and 5, so

D = pow(2,r) * pow(5,s) * R

k must be the larger of r and s, and n (number of nines in Q) will be at

most R and could be less. b has at most than k digits. Notice that

16-bit signed numbers can reach pow(2,15)-1 == 32767. Luckily this is

not prime, but there are lots of prime numbers nearby. For example,

32749 is prime. Be prepared to handle repeating digits of at least this

size.

The above discussion should tell you thar 1/3 has no leading decimals

before the repeating segment, and 1/6 has 1

(since 6 = pow(2,1)*pow(5,0)*3) .

So 1/3 is pow(10,0) * (3/9) where 3 is 'a', the repeating. Because

k == 0, the nonrepeating intial sequence has no digits (so is not

even shown as a zero),

abd 1/6 is pow(10,-1) * (1 + 6/9). The nonrepeating section b is one

digit (since k = 1) and the repeating segment is a 6. Note that we did

not use denominators of 3 or 6 nines. We nneded the smallest number of

the form pow(10,n)-1 with 3 as a factor. That number is 9, with a

single digit. 1/7 has 7 digits in the repeating string, because 9999999

is the smallest such number with 7 for a factor.

So here's the strategy.

If the fraction is improper (N >= D) remove the integgal part and write it:

I. (so N/D = I + N'/D with a proper fraction)

otherwise write

0,

Factor out the 2's and 5's in D. The larger index tells us how many

digits are in the non-repeating segment.

Compute it and write it down.

I.b

The residual D', D with all the factors 2 and 5, either must be 1 (so

I.b us terminating, a = 0, and we'ew done) our must divide a number of

the form 9....9 of 1 to D' digits. Start with Q=9, Q = 10*Q+9, etc

until you have one or have reached the timits of your machine. This part

need not be reported and may be done with, say, unsigned long long ints

even if the problem space is for signed ints. This rells you n, the

length the repeating string. Wrete the '(', generate the n digits,

write down a ')':

I.a(b)