аватар question@mail.ru · 01.01.1970 03:00

The period of decimal fraction

Task: Two integers are presented to the function of the function (int (a), int (b)) . You need to retu the private a/b , and the repeated numbers (period) need to be taken into brackets.

Examples:

   1 / 3  = & gt;    0.  ( 3 )   29 / 12  = & gt;   2.41  ( 6 )   5 / 3  = & gt;   1.  ( 6 )     

approached the problem of the problem of brushword. He sorted out the fractional part, searched for coincidences. But in the case of 1/117, the period includes more than 90 numbers and the overkill of numbers takes more time than is allowed in the problem.

How in a different way to solve this problem? Maybe there is a more elegant solution?

аватар answer@mail.ru · 01.01.1970 03:00

To search for a period of a rational number, there is a separate algorithm. We sort one after a different degree of the number 10: 10, 100, 1000, 10000, etc. We look at the remainder from dividing this number into denominator. If the rest of the division is 1, then the degree of number 10, this is the length of the period. For example, if the denominator costs 13, then:

   10  %  13  =  10    100  %  13  =  9    1000  13  13  =  12    10000  %  13  =  3    100000  %  13  =  4    1000000  %  13  =  1      

it tus out, the period is 6. This period does not depend on what is in the numerator (if the fraction is reduced).

the method does not work if the denominator is divided by 5 or 2. In this case, it needs to be divided by 2, or 5, until the number that is not divided by 2, 2, 2, 5.

In the general case (as for your example 1/117), you will have to use long arithmetic.

the algorithm is looking for only the length of the period to get the period itself, you need to divide it yourself.

Latest

Similar