Раскругленные дроби

22

Когда вы преобразуете дробь в десятичное число и хотите сохранить это число, вам часто приходится округлять его, потому что вы хотите использовать только определенный объем памяти. Допустим, вы можете хранить только 5 десятичных цифр, тогда 5/3 становится 1,6667. Если вы можете сохранить только 2 десятичных знака, это будет 1.7 (теперь предполагается, что оно всегда между 0 и 9.99 ...).

Если вы сейчас попытаетесь повернуть этот процесс в обратном порядке с 1,7 и хотите вернуть свою дробь, это может быть затруднительно, поскольку вы знаете, что 1,7 - это только округленное число. Конечно, вы можете попробовать 17/10, но это довольно «уродливая» фракция по сравнению с «элегантной» 5/3.

Таким образом, цель теперь состоит в том, чтобы найти дробь a / b с наименьшим знаменателем b, которая приводит к округленному десятичному числу при правильном округлении.

Детали

Входные данные содержат строку с числом от 1 до 5 цифр от 0 (включая) до 10 (не включая) с символом «.» после первой цифры. Допустим, nобозначает количество цифр. Выходными данными должен быть список / массив из двух целых чисел [numerator, denominator]или рациональный тип данных (вы можете создать свой собственный или использовать встроенный), где числитель неотрицательный, а знаменатель положительный. Числитель / знаменатель дроби должен быть равен вводу при правильном округлении до nцифр (что означает n-1цифры после десятичной точки).

Ограничение: допустимо только одно утверждение цикла. Это означает, что вы можете использовать только один единственный оператор зацикливания (например, forили whileили gotoи т. Д., А также функциональные циклы, например mapили foldприменяющие код к каждому элементу списка / массива) во всем коде, но вы можете свободно его использовать или используйте рекурсию и т. д.

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

округление

Округление должно соответствовать «обычным» правилам округления, т. Е. Если последняя цифра, которая будет обрезана, равна 5 или больше, вы округлите число вверх и округлите значение для других случаев, например:

4.5494 будет результатом округления до

  • 1 цифра: 5
  • 2 цифры: 4,5
  • 3 цифры: 4,55
  • 4 цифры: 4,549

Примеры

Пожалуйста, включите следующие тестовые примеры и другие «интересные»:

Input 1.7     Output 5/3
Input 0.      Output 0/1
Input 0.001   Output 1/667
Input 3.1416  Output 355/113
flawr
источник
1
Но в функциональных языках нет такого понятия, как цикл. Например, в haskell repeatсоздается бесконечный список аргументов. Кажется, что это цикл, но на самом деле он имеет временную сложность O (1). Но я думаю, лучше сортировать каждый случай отдельно, чем не использовать функциональные языки.
гордый haskeller
3
Мне не нравится текущее определение "петли". В Python, например, for n in numbers: f(g(n))эквивалентно map(f, map(g, numbers)). Функциональная версия использует mapдважды, это действительно должно быть запрещено?
ураган
1
@ MartinBüttner Я говорил о том, что функциональные языки будут запрещены из-за неоднозначности
гордый haskeller,
1
Я сожалею, что не могу внести свой вклад в эту дискуссию, поскольку мои знания о функциональном программировании в основном равны нулю. Если у вас есть решение, в отношении которого вы не уверены, соответствует ли оно «правилам», отправьте его в любом случае! В конце концов, это должно быть весело и познавательно!
Flawr
2
@Dennis Нет, это была неудачная формулировка, вы можете представить ее в любой форме, которая вам нравится, основная идея этого абзаца заключалась в том, что у вас не должно быть недостатка, если ваш язык требует больше байтов для «чтения» введенного числа.
flawr

Ответы:

4

CJam, 41 40 36 байт

Q'./1=,:L0\{;)_Qd*mo_d2$/LmOQd-}g'/@

Предполагается, что входная строка хранится в Q, что явно разрешено вопросом. Попробуйте онлайн.

Контрольные примеры

$ for d in 1.7 0. 0.001 3.1416; do cjam <(echo "\"$d\":Q;
> Q'./1=,:L0\{;)_Qd*mo_d2$/LmOQd-}g'/@
> "); echo; done
5/3
0/1
1/667
355/113

Как это работает

Q'./1=,:L  " Count the number of characters after the dot and store it in L.     ";
0\         " Push 0 (denominator) and swap it with L (dummy value).              ";
{          "                                                                     ";
  ;        " Discard the topmost item from the stack (numerator or dummy value). ";
  )        " Increment the denominator.                                          ";
  _Qd*mo   " Multiply a copy by Double(Q) and round.                             ";
  _d2$/    " Cast a copy to Double and it divide it by the denominator.          ";
  LmO      " Round to L digits.                                                  ";
  Qd       " If the result is not Double(Q),                                     ";
}g         " repeat the loop.                                                    ";
./@        " Push a slash and rotate the denominator on top of it.               ";
Деннис
источник
15

T-SQL 254

Хотя T-SQL на самом деле не подходит для такого рода вещей, его стоит попробовать. Производительность становится очень плохой, чем выше знаменатель. Он ограничен знаменателем 1000.

Ввод является переменной с плавающей точкой @

WITH e AS(SELECT *FROM(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(0))n(n)),t AS(SELECT ROW_NUMBER()OVER(ORDER BY(SELECT \))N FROM e a,e b,e c,e d)SELECT TOP 1concat(n.n,'/',d.n)FROM t d,t n WHERE round(n.n/(d.n+.0),len(parsename(@,1)))=@ ORDER BY d.n,n.n

Разбивка запроса

WITH                                      -- Start CTE(Common Table Expression)
 e AS(                                    --Create a set of 10 rows
   SELECT *
   FROM(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(0))n(n)
 ),
 t AS(                                    
   SELECT ROW_NUMBER()OVER(ORDER BY(SELECT \))N 
   FROM e a,e b,e c,e d                   --Cross join e to produce 1000 numbered rows
 )
SELECT 
  TOP 1                                   --Grab first result
  concat(n.n,'/',d.n)                     --Build output
FROM t d,t n                              --Cross join t against itself for denominator and numerator
WHERE round(
  n.n/(d.n+.0),                           --Force float division with +.0
  len(parsename(@,1))                     --Get rounding length
  )=@                                     --Filter where the rounded result = input
ORDER BY d.n,n.n                          --Order by denominator then numerator
MickyT
источник
+1. Я люблю это. Я вставил, 3.14159и это должным образом дало мне355/113
Том Чантлер
1
+1 Я никогда не ожидал увидеть здесь язык SQL !!!
flawr
@ TomChantler Я подозреваю, что вы имеете в виду в конце концов :)
MickyT
@flawr Честно говоря, я не думал, что это сработает .. хотя метод очень грубой силы.
MickyT
12

Хаскелл, 62 59

если бы имена не были такими длинными ...

import Data.Ratio
f s=approxRational(read s)$50/10^length s

это функция, возвращающая Rationalзначение.

Объяснение: функция approxRational- это функция, которая принимает число с плавающей запятой и эпсилон с плавающей запятой и возвращает самое простое рациональное значение, которое находится в эпсилоне расстояния от входных данных. в основном, возвращает простейшее приближение типа float к рациональному на расстоянии «прощаемой ошибки».

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

давайте попробуем 1,7, например. наименьшее число с плавающей точкой, равное 1.7, составляет 1.65. любое понижение не будет округляться до 1,7. аналогично, верхняя граница числа с плавающей точкой, равного 1,7, равна 1,75.
оба предела являются пределами ввода номера +/- 0,05. Легко показать, что это расстояние всегда 5 * 10 ^ -(the length of the input - 1)(-1 означает, что на входе всегда есть «.»). отсюда код довольно прост.

контрольные примеры:

*Main> map f ["1.7", "0.001", "3.1416"]
[5 % 3,1 % 667,355 % 113]

к сожалению это не работает на "0" потому что функция синтаксического анализа Haskell не распознает .в конце числа с плавающей точкой. это можно исправить на 5 байтов, заменив read sна read$s++"0".

гордый хаскеллер
источник
Это интересная функция. Обычно такие функции существуют с целью нахождения наилучшего рационального приближения к числу за наименьшее количество шагов, что доказуемо достигается с помощью усеченных непрерывных представлений дробей. Кроме того, поиск дроби с наименьшим знаменателем - это скорее академическое любопытство. Обычно никто не ожидал бы найти его как стандартную библиотечную функцию.
COTO
4
@COTO Ну, это Haskell, он полон научных исследований.
гордый haskeller
7

Рубин, 127 125 байт

f=->n{b=q=r=(m=n.sub(?.,'').to_r)/d=10**p=n.count('0-9')-1
b=r if(r=(q*d-=1).round.to_r/d).round(p).to_f.to_s==n while d>1
b}

Определяет функцию, fкоторая возвращает результат как Rational. Например, если вы добавите этот код

p f["1.7"]
p f["0."]
p f["0.001"]
p f["3.1416"]

Вы получаете

(5/3)
(0/1)
(1/667)
(355/113)

Цикл по знаменателям. Я начинаю с полной дроби, например, 31416/10000для последнего примера. Затем я уменьшаю знаменатель, пропорционально уменьшаю числитель (и округляем его). Если полученные рациональные округления совпадают с входным числом, я запоминаю новую лучшую дробь.

Мартин Эндер
источник
4

Mathematica, 49 53 персонажа

Rationalize[ToExpression@#,5 10^(1-StringLength@#)]&@

Использование:

Rationalize[ToExpression@#,5 10^(1-StringLength@#)]&@"1.7"

Выход:

5/3

Тестовые случаи:

input: 1.7     output: 5/3
input: 0.      output: 0
input: 0.001   output: 1/999
input: 3.1416  output: 355/113

Случай 0,001 кажется мне странным; поскольку функция рационализации не работала в соответствии с ее описанием, когда она не нашла случай 1/667. Он должен вывести число с наименьшим знаменателем, который находится в указанных пределах.

число
источник
2
хаха, я использовал точно такое же решение. Жаль, что в Хаскеле это дольше. Кстати, не похоже, что ваше решение принимает строку в качестве входных данных, как того требует спецификация.
гордый haskeller
Подождите, на входе была строка? Черт, это означает, что я могу извлечь некоторые вещи из кода.
Tally
Ваш вывод для 0.001не соответствует OP, потому что Rationalizeне ограничен в знаменателе. Как я уже говорил гордому haskeller, функция рационального приближения, при которой минимизируется знаменатель, очень эзотерична (короче, потому что это паршивый и неэффективный способ аппроксимации чисел). Я обычно не ожидал бы, что это будет стандартная библиотечная функция.
COTO
@COTO Согласно документам, он все же минимизирует знаменатель.
Мартин Эндер
@ MartinBüttner: довольно интересно, что он выводит 1/999. 999 становится (приемлемым) наименьшим знаменателем только для ошибки примерно от 1e-6 до 2e-6. Граница ошибки явно 5e-4. Таким образом, что бы Mathematica ни делала в этом случае, это определенно не работает по спецификации. : P
COTO
4

Python 2.7+, 111 символов

Доказательство того, что вы можете написать ужасный код на любом языке:

def f(s):
 t,e,y=float(s),50*10**-len(s),1;n=d=x=0
 while x|y:n,d=n+x,d+y;a=1.*n/d;x,y=a<t-e,a>t+e
 return n,d

Выход

>>> [f(s) for s in ("1.7", "0.", "0.001", "3.1416")]
[(5, 3), (0, 1), (1, 667), (355, 113)]
Стив
источник
3

APL, 50

2↑⍎⍕(⍎x←⍞){50>|(10*⍴x)×⍺-⍵÷⍨n←⌊.5+⍺×⍵:n ⍵⋄''}¨⍳1e5

Пока ты не считаешь evalи toStringкак петли

объяснение

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

(⍎x←⍞)Возьмите строковый ввод с экрана, назначьте xи оцените.
⍳1e5Создайте массив от 1 до 10000.
{...}¨Для каждого элемента массива вызовите функцию с ним (⍎x←⍞)и аргументы (loop).

⍺×⍵Умножение аргументы
⌊.5+закруглить (путем добавления 0,5 округление вниз)
n←Присвоить n
⍺-⍵÷⍨Разделить по правому аргументу, а затем вычесть из левого аргумента
(10*⍴x)×Умножить на 10 к силе «длины x»
|Возьмите абсолютное значение
50>Проверьте , если меньше , чем 50 (длина xсоставляет еще 2 чем номер dp, так что используйте здесь 50 вместо 0,5)
:n ⍵⋄''Если предыдущая проверка вернула true, верните массив nи правильный аргумент, иначе верните пустую строку.

⍎⍕ toStringи затем evalполучить массив всех чисел в массиве.
2↑Выберите только первые 2 элемента, которые являются первой найденной парой числитель-знаменатель.

TwiNight
источник
2

GNU dc, 72 байта

Никаких петель - у DC их даже нет. Вместо этого управление происходит от одного хвостового рекурсивного макроса - идиоматического для DC.

?dXAr^d2*sf*sq1sd0[ld1+sd]sD[r1+r]sN[dlf*ld/1+2/dlq>Ndlq<Dlq!=m]dsmxpldp

Выход:

$ for n in 1.7 0. 0.001 3.1416; do echo "    n = $n:"; dc unround.dc <<< $n; done
    n = 1.7:
5
3
    n = 0.:
0
1
    n = 0.001:
1
667
    n = 3.1416:
355
113
$ 

Уф. Частичное объяснение в этом ответе .

Цифровая травма
источник
2

Mathematica, 111 символов

f=Module[{a=0,b=1,k},While[Round[a/b,10^-(StringLength[#]-2)]!=(k=ToExpression)@#,If[N[a/b]>k@#,b++,a++]];a/b]&

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

Выход

f/@{"1.7","0.0","0.001","3.1416","3.14"}
{5/3, 0, 1/667, 355/113, 22/7}

Кто-нибудь здесь празднует День Приближения Пи ?

krs013
источник
Нет, я только отмечаю день приближения тау. = P Но я только что заметил, что | 355/113 - pi | <10 ^ -6 =)
flawr
2

Applescript,> 300 байт

Я хотел сделать это на языке, который изначально выполняет требуемый тип округления. Оказывается, Applescript отвечает всем требованиям. Потом я увидел перечисление rounding as taught in schoolи не смог удержаться от его использования, несмотря на вопиющую неконкурентоспособность Applescript для целей игры в гольф:

on u(q)
    set n to 0
    set d to 1
    set x to 0
    set AppleScript's text item delimiters to "."
    set f to 10 ^ (q's text item 2's length)
    repeat until x = q as real
        set x to (round n * f / d rounding as taught in school) / f
        if x < q then set n to n + 1
        if x > q then set d to d + 1
    end repeat
    return {n, d}
end u

log my u("1.7")
log my u("0.")
log my u("0.001")
log my u("3.1416")

Это может быть немного больше, но, вероятно, не стоит.

Выход:

(*5, 3*)
(*0, 1*)
(*1, 667*)
(*355, 113*)
Цифровая травма
источник
2

До н.э., 151 148 байт

Редактировать - более быстрая и короткая версия

define f(v){s=scale(x=v);for(i=r=1;i<=10^s;i+=1){t=v*i+1/2;scale=0;p=t/=1;scale=s+1;t=t/i+10^-s/2;scale=s;t=t/1-v;if((t*=-1^(t<0))<r){r=t;n=p;d=i}}}

тот же тест.

Многое похоже на предыдущую версию, но вместо того, чтобы пробовать все возможные комбинации n / d, мы поднимаемся на холм по остаткам v и обратным коэффициентам, кратным m == v * d и знаменателям d. Опять же, точность вычислений одинакова.

Вот это распутано:

define f(v)
{
    s= scale(x=v)
    for( i=r=1; i <= 10^s; i+=1 ){
        t= v * i +1/2
        scale=0
        m=t/=1 # this rounded multiple becomes nominator if
               # backward quotient is first closest to an integer
        scale=s+1
        t= t / i +10^-s/2 # divide multiple back by denominator, start rounding again...
        scale=s
        t= t/1 - v # ...rounding done. Signed residue of backward quotient
        if( (t*= -1^(t < 0)) < r ){
            r=t
            n=m
            d=i
        }
    }
}

Эта версия действительно имеет простой цикл и выполняет только арифметические операции $ \ Theta \ left (\ operatorname {дробное_значение} (v) \ справа) $.

Оригинал - медленная версия

Эта функция вычисляет наименьший знаменатель n и знаменатель d, так что дробь n / d, округленная до цифр дробных_десятичных (v), равна заданному десятичному значению v.

define f(v){s=scale(v);j=0;for(i=r=1;j<=v*10^s;){scale=s+1;t=j/i+10^-s/2;scale=s;t=t/1-v;if((t*=-1^(t<0))<r){r=t;n=j;d=i};if((i+=1)>10^s){i=1;j+=1}};v}

прецедент:

define o(){ print "Input ",x,"\tOutput ",n,"/",d,"\n" }
f(1.7); o()
> 0
> Input 1.7       Output 5/3
> 0
f(0.); o()
> 0
> Input 0 Output 0/1
> 0
f(0.001); o()
> 0
> Input .001      Output 1/667
> 0
f(3.1416); o()
> 0
> Input 3.1416    Output 355/113
> 0

И вот это распутано:

define f(v)
{
    s=scale(x=v) # save in global for later print
    j=0
    # do a full sequential hill-climb over the residues r of v and all possible
    # fractions n / d with fractional_decimals(v) == s precision.
    for( i=r=1; j <= v * 10^s; ){
        scale=s+1
        t= j / i +10^-s/2 # start rounding...
        scale=s
        t= t/1 - v # ...rounding done. New residue, but still signed
        if( (t*= -1^(t < 0)) < r ){ # absolute residue better?
            # climb hill
            r=t
            n=j
            d=i
        }
        if( (i+=1) > 10^s ){ # next inner step. End?
            # next outer step
            i=1
            j+=1
        }
    }
    v
}

Признаюсь, я немного обманул, эмулировав второй внутренний цикл внутри одного внешнего цикла, но без использования каких-либо дополнительных операторов цикла. И именно поэтому он фактически выполняет арифметические операции $ \ Theta \ left (v \ operatorname {фракция_десятичные} (v) ^ 2 \ right) $.

Франки
источник
1
Вы, вероятно, должны переместить новую версию в начало поста
гордый haskeller
@proudhaskeller готово
Франки
1

С 233

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

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

Обратите внимание, что это не работает для ввода «0». потому что это не стандартный способ записи числа с плавающей запятой, поэтому, когда он переписывает число с плавающей запятой в строку, результатом никогда не будет «0».

Спецификациям нужна функция, которая возвращает значения, а не просто печатает на экран, отсюда и передача аргументов.

Код (без золота):

void r(char* x, int* a, int* b) {
    int i = -1;
    char z[32];
    double v =atof(x);
    while(1) {
        i++;
        double y = ((double)i)/((double)(*b));
        double w;
        sprintf(z, "%.*f", strlen(strchr(x,'.'))-1, y);
        if(strcmp(x, z)==0) {
            *a = i;
            return;
        }
        w = atof(z);
        if(w > v) {
            (*b)++;
            r(x, a, b);
            return;
        }
    }
}

Использование:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char* argv[]) {
    int num;
    int denom = 1; // start with a denominator of 1
    r(argv[1], &num, &denom);
    printf("%d/%d\n", num, denom);
    return 0;
}

Гольф-код:

typedef double D;
void r(char*x,int*a,int*b){int i=-1;char z[32];D v=atof(x);while(1){i++;D y=((D)i)/((D)(*b));D w;sprintf(z,"%.*f",strlen(strchr(x,'.'))-1,y);if(!strcmp(x,z)){*a=i;return;}w=atof(z);if(w>v){(*b)++;r(x,a,b);return;}}}
RT
источник
на самом деле, в реализации библиотеки Haskell ( hackage.haskell.org/package/base-4.7.0.1/docs/src/… ) определение approxRationalимеет только одну рекурсивную вспомогательную функцию и не более зацикливается, чем эта.
гордый haskeller
Что ж
Я не пытался сказать, что чьи-либо решения были недействительными, просто хотел опубликовать одно без встроенной рационализации :)
RT
конечно, но тот факт, что само определение не имеет циклов, приятно, и на самом деле, вы написали в своем посте: «насколько мы знаем, внутренние функции рационализации () современных языков имеют много внутренних циклов». так что я проверил это.
гордый haskeller
в любом случае, как работает решение?
гордый haskeller
1

Чистый Баш, 92 байта

В качестве частичного объяснения этого ответа здесь он портирован на bash:

f=${1#*.}
q=${1//.}
for((n=0,d=1;x-q;x=2*10**${#f}*n/d+1>>1,n+=x<q,d+=x>q));{ :;}
echo $n/$d

В частности:

  • Bash имеет только целочисленную арифметику. Таким образом, мы соответствующим образом увеличиваем все на 2 * 10 ^ (количество дробных цифр).
  • Баш раундов вниз до ближайшего целого числа; 2 в приведенном выше выражении означает, что вместо этого мы можем округлить до ближайшего целого числа ( вверх или вниз ).
  • Всего одна петля
  • мы проверяем, превышает ли рациональное число или меньше десятичного, и соответственно увеличиваем знаменатель или числитель.

Выход:

$ for n in 1.7 0. 0.001 3.1416; do echo "    n = $n:"; ./unround.sh $n; done
    n = 1.7:
5/3
    n = 0.:
0/1
    n = 0.001:
1/667
    n = 3.1416:
355/113
$ 
Цифровая травма
источник
Должен быть довольно простой - intединственный порт для c
Digital Trauma
1

JavaScript (E6) 85

F=r=>(l=>{for(n=r,d=1;l&&r!=((n=r*d+1/2|0)/d).toFixed(l);d++);})(r.length-2)||[n|0,d]

Ungolfed

F=r=>{
  l = r.length-2; // decimal digits
  if (l==0) return [r|0, 1] // if no decimal return the same (conv to number) with denominator 1

  // loop for increasing denominator 
  for(d = 2; 
      r != ( // loop until find an equal result
      // given R=N/D ==> N=R*D
      (n=r*d+1/2|0) // find possible numerator, rounding (+0.5 and trunc)
      /d).toFixed(l); // calc result to given decimals
      d++);
  return [n,d]
}

Тест в консоли FireFox / FireBug

;["1.7","0.","0.001","3.1416","9.9999"].forEach(v => console.log(v,F(v)))

Выход

1.7 [5, 3]
0. [0, 1]
0.001 [1, 667]
3.1416 [355, 113]
9.9999 [66669, 6667]
edc65
источник