Когда вы преобразуете дробь в десятичное число и хотите сохранить это число, вам часто приходится округлять его, потому что вы хотите использовать только определенный объем памяти. Допустим, вы можете хранить только 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
repeat
создается бесконечный список аргументов. Кажется, что это цикл, но на самом деле он имеет временную сложность O (1). Но я думаю, лучше сортировать каждый случай отдельно, чем не использовать функциональные языки.for n in numbers: f(g(n))
эквивалентноmap(f, map(g, numbers))
. Функциональная версия используетmap
дважды, это действительно должно быть запрещено?Ответы:
CJam,
414036 байтПредполагается, что входная строка хранится в Q, что явно разрешено вопросом. Попробуйте онлайн.
Контрольные примеры
Как это работает
источник
T-SQL 254
Хотя T-SQL на самом деле не подходит для такого рода вещей, его стоит попробовать. Производительность становится очень плохой, чем выше знаменатель. Он ограничен знаменателем 1000.
Ввод является переменной с плавающей точкой @
Разбивка запроса
источник
3.14159
и это должным образом дало мне355/113
Хаскелл,
6259если бы имена не были такими длинными ...
это функция, возвращающая
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 означает, что на входе всегда есть «.»). отсюда код довольно прост.контрольные примеры:
к сожалению это не работает на "0" потому что функция синтаксического анализа Haskell не распознает
.
в конце числа с плавающей точкой. это можно исправить на 5 байтов, заменивread s
наread$s++"0"
.источник
Рубин,
127125 байтОпределяет функцию,
f
которая возвращает результат какRational
. Например, если вы добавите этот кодВы получаете
Цикл по знаменателям. Я начинаю с полной дроби, например,
31416/10000
для последнего примера. Затем я уменьшаю знаменатель, пропорционально уменьшаю числитель (и округляем его). Если полученные рациональные округления совпадают с входным числом, я запоминаю новую лучшую дробь.источник
Mathematica,
4953 персонажаИспользование:
Выход:
Тестовые случаи:
Случай 0,001 кажется мне странным; поскольку функция рационализации не работала в соответствии с ее описанием, когда она не нашла случай 1/667. Он должен вывести число с наименьшим знаменателем, который находится в указанных пределах.
источник
0.001
не соответствует OP, потому чтоRationalize
не ограничен в знаменателе. Как я уже говорил гордому haskeller, функция рационального приближения, при которой минимизируется знаменатель, очень эзотерична (короче, потому что это паршивый и неэффективный способ аппроксимации чисел). Я обычно не ожидал бы, что это будет стандартная библиотечная функция.1/999
. 999 становится (приемлемым) наименьшим знаменателем только для ошибки примерно от 1e-6 до 2e-6. Граница ошибки явно 5e-4. Таким образом, что бы Mathematica ни делала в этом случае, это определенно не работает по спецификации. : PPython 2.7+, 111 символов
Доказательство того, что вы можете написать ужасный код на любом языке:
Выход
источник
APL, 50
Пока ты не считаешь
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 элемента, которые являются первой найденной парой числитель-знаменатель.источник
GNU dc, 72 байта
Никаких петель - у DC их даже нет. Вместо этого управление происходит от одного хвостового рекурсивного макроса - идиоматического для DC.
Выход:
Уф. Частичное объяснение в этом ответе .
источник
Mathematica, 111 символов
На самом деле довольно просто, и я не думаю, что оно сходится где-то так же быстро, как другие решения, поскольку числитель и знаменатель увеличиваются только на единицу. Я в основном хотел найти простое решение для этого. Я должен увидеть другие ответы и посмотреть, что там происходит.
Выход
Кто-нибудь здесь празднует День Приближения Пи ?
источник
Applescript,> 300 байт
Я хотел сделать это на языке, который изначально выполняет требуемый тип округления. Оказывается, Applescript отвечает всем требованиям. Потом я увидел перечисление
rounding as taught in school
и не смог удержаться от его использования, несмотря на вопиющую неконкурентоспособность Applescript для целей игры в гольф:Это может быть немного больше, но, вероятно, не стоит.
Выход:
источник
До н.э.,
151148 байтРедактировать - более быстрая и короткая версия
тот же тест.
Многое похоже на предыдущую версию, но вместо того, чтобы пробовать все возможные комбинации n / d, мы поднимаемся на холм по остаткам v и обратным коэффициентам, кратным m == v * d и знаменателям d. Опять же, точность вычислений одинакова.
Вот это распутано:
Эта версия действительно имеет простой цикл и выполняет только арифметические операции $ \ Theta \ left (\ operatorname {дробное_значение} (v) \ справа) $.
Оригинал - медленная версия
Эта функция вычисляет наименьший знаменатель n и знаменатель d, так что дробь n / d, округленная до цифр дробных_десятичных (v), равна заданному десятичному значению v.
прецедент:
И вот это распутано:
Признаюсь, я немного обманул, эмулировав второй внутренний цикл внутри одного внешнего цикла, но без использования каких-либо дополнительных операторов цикла. И именно поэтому он фактически выполняет арифметические операции $ \ Theta \ left (v \ operatorname {фракция_десятичные} (v) ^ 2 \ right) $.
источник
С 233
Это работает путем вызова функции рационализации r () с начальным знаменателем, равным 1. Функция начинает увеличивать числитель и проверять при каждом приращении, имеет ли результирующее число, округленное до того же числа цифр, что и оригинал, ту же строку представление как оригинал. После того как числитель был настолько увеличен, что результат больше исходного, функция увеличивает знаменатель и вызывает себя.
Это, конечно, использует гораздо больше кода, но я думаю, что дух проблемы оправдывает этот простой подход; Насколько нам известно, внутренние функции рационализации () современных языков имеют множество внутренних циклов.
Обратите внимание, что это не работает для ввода «0». потому что это не стандартный способ записи числа с плавающей запятой, поэтому, когда он переписывает число с плавающей запятой в строку, результатом никогда не будет «0».
Спецификациям нужна функция, которая возвращает значения, а не просто печатает на экран, отсюда и передача аргументов.
Код (без золота):
Использование:
Гольф-код:
источник
approxRational
имеет только одну рекурсивную вспомогательную функцию и не более зацикливается, чем эта.Чистый Баш, 92 байта
В качестве частичного объяснения этого ответа здесь он портирован на bash:
В частности:
Выход:
источник
int
единственный порт для cJavaScript (E6) 85
Ungolfed
Тест в консоли FireFox / FireBug
Выход
источник