Ваша задача, учитывая x, вывод 2*x. Легко, правда !? Но есть одна загвоздка: xбудет задана как (возможно, бесконечная) непрерывная дробь , а результат должен быть продолженной дробью. Входные данные гарантированно являются действительным алгебраическим числом, степень которого не больше 2.

Входные данные : продолжение доли x. Это разделено на 3 части: целочисленная часть, префикс и повторяющаяся часть. Целая часть состоит из одного целого числа. Префикс и повторяющаяся часть являются (возможно, пустыми) массивами натуральных чисел, которые описывают префикс и повторяющуюся часть непрерывной дроби. Например, ввод (3, [1], [2, 4])представляет собой непрерывную дробь [3; 1, 2, 4, 2, 4, ...].

Если повторяющаяся часть пуста, это означает рациональное число. Например, (3, [1, 2], [])представляет [3; 1, 2] = 11/3. Вы должны принять обе формы рационального числа (то есть (3, [1, 1, 1], []), которое [3; 1, 1, 1] = 11/3также должно быть допустимым вводом).

Вывод : Выведите продолженную дробь, вдвое превышающую ввод, в том же формате, что и ввод. Если вывод является рациональным, вы можете вывести любую форму продолжения дроби. Пока ответ эквивалентен правильному ответу, это нормально; нет необходимости в «сжатии», поэтому бесконечная часть может быть немного «развернута» (например, [1; 4, 2, 3, 2, 3...]может быть написана (1, [4], [2, 3])или (1, [4, 2, 3], [2, 3])). Все ответы должны быть точными.

Контрольные примеры : точный столбец формы приведен для удобства.

Input               Exact Form       Output
(0, [] [])          0                (0, [] []) or (-1, [1], [])
(-5, [1, 1], [])    -4.5             (-9, [], []) or (-10, [1], [])
(3, [1, 2], [])     11/3             (7, [3], []) or (7, [2, 1], [])
(1, [], [2])        sqrt(2)          (2, [], [1, 4])
(-1, [2], [2, 1])   -1/sqrt(3)       (-2, [1, 5], [2, 6])

И , наконец, немного больше , тест , чтобы обеспечить точность: (0, [1], [6, 1, 3, 1, 42, 1, 3, 1, 6, 2]) --> (1, [], [1, 2, 1, 8, 1, 20, 1, 8, 1, 2, 1, 2]).

Самый короткий код выигрывает!

Подсказка : Вы можете выполнять арифметику довольно простым способом для непрерывных дробей, как описано здесь . Удвоение непрерывной дроби является лишь частным случаем этого алгоритма (хотя сложная часть заключается в том, чтобы найти повторение продолжения дробной части).

Wolfram Language (Mathematica) , 44 байта

ContinuedFraction[2FromContinuedFraction@#]&

Попробуйте онлайн!

Mathematica имеет встроенный! Ура! Встроенная Mathematica очень длинная. Оо.

Непрерывные дроби Mathematica выглядят как {integer, ...prefix, {...repeating}}

-1 благодаря JungHwan Мин

JavaScript (ES6), 267 байт

(n,f,r)=>eval(`f=[0,...f];e=i=[0,2,1,0];o=j=[];k=[];m={};while([a,b,c,d]=e,c|d&&o)i*m[s=i+m+(e=c*d&&(q=a/c|0)==(b/d|0)?(o.push(q),[c,d,a-c*q,b-d*q]):1/(++i,[p,...f]=f+f?f:(i=r[0],r),p)?[b,a+b*p,d,c+d*p]:[b,b,d,d])]?k+(o=k)?o=0:(m={})[s]=1:m[s]=1;[2*n+j.shift(),j,k]`)

Принимает 3 аргумента (n = целая часть, f = префикс, r = повторяющаяся часть). Выводит три части в массив. Попробуйте онлайн!

объяснение

Это довольно прямая реализация алгоритма для вычисления арифметики непрерывной дроби, связанной с задачей здесь . Повторяющиеся термины обрабатываются путем хранения промежуточных матриц в таблице поиска, ожидания дубликата и вывода терминов до следующего появления этого дубликата. Это не элегантно и почти удваивает количество байтов, необходимых для обработки непрерывных дробей, но я не мог придумать лучшей альтернативы.

Первый член вычисляется отдельно, чтобы гарантировать, что отрицательные непрерывные дроби сохраняют положительные значения для всех терминов, кроме первого.

Во избежание ложных срабатываний при ожидании повторного цикла, таблицы поиска сохраняет данные следующим образом : <index of input repeating part><delimiter><matrix values>.

Обратите внимание, что версия evalдля гольфа использует для сохранения 1 байта.

(n, f, r) => {
    f = [0, ...f];                       // use a 0 to chop off the integer part
    e = i = [0,2,1,0];                   // e: matrix with starting values to handle doubling
                                         // 0 + 2x
                                         // ------
                                         // 1 + 0x
                                         // i: tracks index of repeating part; until the function loops through the
                                         // repeating part, i is equivalent to NaN
    o = j = [];                          // o: alias for group of terms currently being computed
                                         // j: output array of non-repeating terms
    k = [];                              // k: output array of repeating terms
    m = {};                              // lookup table
    while ([a,b,c,d] = e, c | d && o)    // destructure matrix
                                         // c | d stops loop if both a/c and b/d equal infinity
        i * m[s = i + m + (              // m also serves as the delimiter; JS will stringify it as "[object Object]"
                                         // if i equals a value that is coerced to NaN, this multiplication
                                         // will be falsy
            e = c * d && (q=a/c|0) == (b/d|0) // checks if either c or d is 0 to avoid converting an Infinity value to 0 using the bitwise or
                ? (o.push(q), [c, d, a - c*q, b - d*q]) // append the output term and compute the new matrix
                : 1/(++i, [p, ...f] = f+f ? f : (i=r[0], r), p) // 1/(... p) checks if p is a valid number
                                         // f+f is a short way to check length of f; if f is an empty
                                         // array, f+f = '' (which is falsy)
                                         // if f is empty, try to replace with r
                                         // if r is empty, the value of i will be set to undefined (e.g. NaN)
                    ? [b, a + b*p, d, c + d*p]
                    : [b,b,d,d]
            )
        ]                                // checks if matrix has been cached in lookup table
            ? k+(o=k)                    // if the repeating part of the output has a value...
                ? o=0                    // o serves as a flag to halt the loop
                : (m={})[s] = 1          // reset lookup table to only hold the first duplicate matrix
            : m[s] = 1;                  // otherwise flag a matrix as seen
    return [2*n + j.shift(), j, k]       // add the doubled integer part to the first term
}