How can a C ++ translate a number represented as a decimal fraction into a continuous (continued) fraction?

Closed due to the fact that the essence of the question is not clear by the participants Vladimir Martyanov , D-side , fori1ton , Pavel Parshin , VenZell 24 Mar '16 at 8:21

Try to write more detailed questions. To get an answer, explain what exactly you see the problem, how to reproduce it, what you want to get as a result, etc. Give an example that clearly demonstrates the problem. If the question can be reformulated according to the rules set out in the certificate , edit it .

  • An example of both is possible? - sanmai
  • @sanmai 1.25 = 1+ 1/4 - pishak
  • That is, it is known in advance that the number can be exactly converted - sanmai
  • four
    Describe the problem more specifically, what did not work out? Give an example code. While your question looks like a task. - Axifive
  • What is continuous fraction? - andreymal

3 answers 3

Recursively iteratively, as you like more :) - selection of the whole part + 1/x . Another thing is that after a certain number of steps about accuracy can be forgotten.

I would not like to write code for you, this is non-pedagogical :) Therefore, just a few steps manually for pi:

 3 + 0.1415925... = 3 + 1/(7+0.0625133...) = 3 + 1/(7 + 1/(15+0.996...)

and so on.

  • Quite often the task is to restore the original fraction - say, 17/7. And preferably without additional manual work. - Yuri Negometyanov

To solve such problems, it would be useful to get acquainted with the representation of floating point numbers.

You can offer such an algorithm.

  1. We divide the number into integer and fractional parts (for example, by the function modf ).
  2. We FLT_RADIX numerator and denominator multiplying the remaining fractional part by FLT_RADIX until it becomes zero.
  • You confuse "ordinary fraction" and "continuous fraction" - these are two different things (and, by the way, the question has been fixed in vain - the question has become completely different). See ru.wikipedia.org/wiki/… - Harry

Continuous fraction is built using the Euclidean algorithm:
x = [q 0 , q 1 , q 2 ...] , where

q 0 = [x], r 0 = x - q 0 ,
q s + 1 = [1 / r s ], r s + 1 = 1 / r s - q s + 1 , s = 0, 1, ...

Suitable fractions (approximations of the number x of the form P s / Q s ) are calculated by the formulas:
P 0 = 1, Q 0 = 0
P 1 = q 0 , Q 1 = 1
P s + 1 = q s + 1 P s + P s-1 ,
Q s + 1 = q s + 1 Q s + Q s-1 ,
s = 1, 2, ...

According to the logic of continued fractions (compact approximations of the number x ) this process should not be infinite. Therefore, calculations should be terminated not only at the zero fractional part, but also when the specified accuracy is reached.

A PHP program looks like this:

 function print_e($text, $entier){ print $text."["; foreach($entier as $key => $ent){ if($key) print ", "; print $ent; } print "]"; } function print_c($text, $num, $denom){ print $text; $first = true; array_map(function($n, $d) use(&$first){ if(!$first) print "&emsp;"; print "$n/$d"; $first = false; }, $num, $denom); }; function float_to_ratio($x, $epsilon = 1e-7, $ent = []){ $numerator[] = 1; $denominator[] = 0; $ent[0] = floor($x); $frac = $x - $ent[0]; $numerator[] = $ent[0]; $denominator[] = 1; while((abs($x - end($numerator)/end($denominator)) > $epsilon) && ($frac > 0)){ $verse = 1/$frac; $ent[] = floor($verse); $frac = $verse - end($ent); $numerator[] = end($ent)*current($numerator) + prev($numerator); $denominator[] = end($ent)*current($denominator) + prev($denominator); }; print_e("* x = $x&emsp;epsilon = $epsilon<br>* continued fraction: ", $ent); print_c("<br>* convergents: ", $numerator, $denominator); return [end($numerator), end($denominator)]; } $ratio = float_to_ratio($x = 17/7); print "<br>&emsp;$x = {$ratio[0]}/{$ratio[1]}<br><br>"; $ratio = float_to_ratio($x = 5.333); print "<br>&emsp;$x = {$ratio[0]}/{$ratio[1]}<br><br>"; $ratio = float_to_ratio($x = 5.333, 1e-3); print "<br>&emsp;$x = {$ratio[0]}/{$ratio[1]}";

Results:

 * x = 2.42857142857 epsilon = 1.0E-7
 * continued fraction: [2, 2, 2, 1]
 * convergents: 1/0 2/1 5/2 12/5 17/7
 2.42857142857 = 17/7

 * x = 5.333 epsilon = 1.0E-7
 * continued fraction: [5, 3, 333]
 * convergents: 1/0 5/1 16/3 5333/1000
 5.333 = 5333/1000

 * x = 5.333 epsilon = 0.001
 * continued fraction: [5, 3]
 * convergents: 1/0 5/1 16/3
 5.333 = 16/3