C++

A continued fraction is an iterative, recursive expression of a number as the sum of an integer and the reciprocal of a second number, which is itself expressed as a continued fraction. In other words, a continued fraction looks like: 1 x = do + 1 ai + 1 a2 + where x is the number being represented, and the integers aj, aj, etc. are called the coefficients of the continued fraction. For example: 37 1 = 3+ 11 2 + 1 1+ 3 While there are many notations for continued fractions, one of the more compact notations simply lists the coefficients in square brackets; the first two coefficients (if more than one) are separated by a semicolon, while the remaining coefficients are separated by commas. For example, the continued fraction above for 37/11 would be written simply as [3:2,1,3]. Note that integers have no fractional part; thus the continued fraction representation of 42 is [42]. Continued fractions have some interesting and useful properties, such as the fact that a rational number will always have a finite continued fraction representation (contrast this with the decimal representation of rational numbers; for instance, 1/3 in decimal form has an infinite length). For an irrational real number, continued fractions have an infinite number of terms. You can read much more about continued fractions in the Wikipedia article. For this problem, you are given the numerator and denominator of a rational number and asked to return (as a string) the continued fraction representation of the number. The algorithm for converting a rational number to a continued fraction is based on Euclid's algorithm for greatest common denominator, and is really quite straightforward; you start by finding the integer quotient resulting from dividing the numerator by the denominator. This is your first coefficient. The remainder is necessarily a rational number less than 1 - so you simply need to take its reciprocal and repeat the steps above to extract the next coefficient. As soon as the remainder is zero, you're done! Taking 37/11 as an example, we can write 37/11 as 3 + 4/11. So 3 is our first coefficient, as expected. The remainder is 4/11, whose reciprocal is 11/4. We could therefore write that 37/11 = 3 +1/(11/4). If we then simply replace 11/4 with its continued fraction, you can see how the picture above starts to take shape. Writing the reciprocal (11/4) as a continued fraction to obtain the remaining coefficients: 11/4 = 2 + 3/4, so 2 is the next coefficient 4/3 = 1 + 1/3, so 1 is the next coefficient 3/1 = 3 + 0, so 3 is the last coefficient Constraints The inputs represent a non-negative rational number, given as the numerator and denominator. The input nun will be a non-negative integer. The input den will be a positive integer. Examples 1.1 1 Returns: "[1]" 2. 1 3 Returns: "[0;3]" 3. 117 10 Returns: "[11;1,2,3]" 4.17 42 Returns: "[0;2,2,8]