Обзор:
Из Википедии : Египетская дробь - это сумма различных дробных единиц. То есть каждая дробь в выражении имеет числитель, равный 1, и знаменатель, который является положительным целым числом, и все знаменатели отличаются друг от друга. Значением выражения этого типа является положительное рациональное число a / b. Каждое положительное рациональное число может быть представлено египетской дробью.
Вызов:
Напишите самую короткую функцию, которая будет возвращать значения всех знаменателей для наименьшего набора дробных единиц, которые складываются в заданную дробь.
Правила / Ограничения:
- На входе будут два положительных целых числа.
- Это может быть
STDIN
,argv
через запятую, через пробел, или любой другой метод , который вы предпочитаете.
- Это может быть
- Первое входное значение должно быть числителем, а второе входное значение - знаменателем.
- Первое входное значение должно быть меньше второго.
- Вывод может включать значение (я), которое превышает ограничения памяти вашей системы / языка (RAM, MAX_INT или любые другие ограничения кода / системы). Если это произойдет, просто обрежьте результат до максимально возможного значения и обратите внимание, что каким-то образом (то есть
...
). - Вывод должен быть в состоянии обрабатывать знаменатель по крайней мере до 2 147 483 647 (2 31 -1, 32-разрядный со знаком
int
).- Более высокое значение (
long
и т. Д.) Вполне приемлемо.
- Более высокое значение (
- Выходными данными должен быть список всех значений знаменателей наименьшего набора найденных дробных единиц (или самих дробных дробей, т.е.
1/2
). - Выходные данные упорядочиваются по возрастанию в соответствии со значением знаменателя (по убыванию по значению дроби).
- Выходные данные могут быть разделены любым удобным для вас способом, но между ними должен быть какой-то символ, чтобы отличать одно значение от другого.
- Это код гольф, поэтому выигрывает самое короткое решение.
Exmaples:
Вход 1:
43, 48
Выход 1:
2, 3, 16
Вход 2:
8/11
Выход 2:
1/2 1/6 1/22 1/66
Вход 3:
5 121
Выход 3:
33 121 363
8, 11
и2, 6, 22, 66
прав?1/2 1/6 1/22 1/66
было бы предпочтительным1/2 1/5 1/37 1/4070
для ввода8/11
.5/121 = 1/33+1/121+1/363
к тестам. Все жадные программы (включая мою) дают за это 5 фракций. Пример взят из Википедии .Ответы:
Common Lisp, 137 символов
(z 43/48) -> (2 3 16)
(z 8/11) -> (2 5 37 4070)
(z 5/121) -> (25 757 763309 873960180913 1527612795642093418846225)
Не нужно беспокоиться об огромных числах или обработке дробных обозначений!
источник
Python 2,
169167 символовПринимает разделенные запятыми аргументы в stdin и печатает список python в stdout.
источник
PHP 82 байта
Это можно сделать короче, но текущий числитель и знаменатель должны быть сохранены как целые числа, чтобы избежать ошибки округления с плавающей запятой (вместо сохранения текущей дроби).
Пример использования:
источник
5 121
или31 311
, он даст неправильный ответ (через очень долгое время).C
163177 символов6/6 : Наконец, программа теперь корректно обрабатывает усечение во всех случаях. Потребовалось намного больше символов, чем я надеялся, но оно того стоило. Программа должна на 100% соответствовать требованиям проблемы сейчас.
Программа берет числитель и знаменатель на стандартный ввод. Знаменатели выводятся на стандартный вывод, по одному на строку. Усеченный вывод указывается путем печати нулевого знаменателя в конце списка:
Знаменатели во втором примере составляют 95485142815/107645519046, что отличается от 6745/7604 примерно на 1e-14.
источник
31 311
например).31 311
переполняется, но программа не может пометить его.Питон, 61 символ
Ввод из STDIN, через запятую.
Вывод в STDOUT, новая строка разделена.
Не всегда возвращает самое короткое представление (например, для 5/121).
Символы подсчитываются без лишних новых строк (то есть, соединяя все строки в пределах
while
использования;
).Фракция есть
a/b
.i
этоb/a
округлый, так что я знаю1/i <= a/b
.После печати
1/i
заменяюa/b
наa/b - 1/i
, что есть(a*i-b)/(i*b)
.источник
C 94 байта
Попробуйте онлайн
редактировать: более короткая версия кода была размещена в комментариях, поэтому я заменил ее. Благодарность!
источник
for(i=2;n>0&&i>0;i++)
играть в гольф: могут бытьfor(i=1;n>0&++i>0;)
; скобки петли for могут быть удалены (потому что она имеет толькоif
внутреннюю часть);d=d*i;
может бытьd*=i;
; и я не совсем уверен, но думаю#include <stdio.h>
можно без пробелов#include<stdio.h>
. О, и это может быть интересно прочитать Советы по игре в гольф на Си и Советы по игре в гольф на <все языки>Stax , 18 байт
Запустите и отладьте его
На каждом шаге он пытается свести к минимуму последующий числитель . Кажется, это работает, но я не могу доказать это.
источник
АКСИОМА, 753 байта
Идея состоит в том, чтобы применить «алгоритм жадности» с разными начальными точками и сохранить список с минимальной длиной. Но не всегда он нашел бы минимальное решение с менее дифференцированным: «массив A будет меньше, чем массив B, если и только если A имеет несколько элементов из B, или если число элементов в A равно количеству элементов в B , чем A меньше B, если более маленький элемент A больше числа, чем более маленький элемент B ". Разобраться и проверить
ссылка и номера с: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/egyptian.html
для добавления чего-либо, эта ниже будет оптимизирована для поиска доли минимальной длины, у которой максимальный знаменатель меньше (и не оптимизирована для длины)
результаты:
Кажется, многие хорошие знаменатели имеют в качестве делителей факторов знаменателя входной дроби.
источник
C
8578 байтУлучшено @ceilingcat , 78 байт:
Попробуйте онлайн!
Мой оригинальный ответ, 85 байт:
Попробуйте онлайн!
Часть заслуг должна принадлежать Джонатану Фреху , который написал это 94-байтовое решение, которое я улучшил.
источник
APL (NARS), 2502 байта
Перевод из кода AXIOM для этой задачи в APL, впервые использующий (для меня) тип дроби (то есть bignum ...).
103r233 означает фракцию 103/233. Тестовое задание:
источник