Египетские фракции

20

Обзор:

Из Википедии : Египетская дробь - это сумма различных дробных единиц. То есть каждая дробь в выражении имеет числитель, равный 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

Gaffi
источник
Вход / Выход 2 должен быть 8, 11и 2, 6, 22, 66прав?
mellamokb
2
Одним из возможных предложений по устранению неопределенности может быть требование наименьшего набора дробных единиц с наименьшим конечным знаменателем. Например, 1/2 1/6 1/22 1/66было бы предпочтительным 1/2 1/5 1/37 1/4070для ввода 8/11.
Примо
2
Я предлагаю добавить 5/121 = 1/33+1/121+1/363к тестам. Все жадные программы (включая мою) дают за это 5 фракций. Пример взят из Википедии .
Угорен
1
@primo Я думаю, что если есть несколько минимумов, то любой найденный будет приемлемым. Если один алгоритм может быть написан с меньшим количеством символов в результате, я бы не хотел мешать этому решению.
Гаффи
1
Дали +1, так как я фактически узнал о египетских дробях в курсе «История математики» (и с ними пришлось заниматься математикой, а также находить дробные суммы, подобные этой задаче.) Хорошая и творческая задача.
mbomb007

Ответы:

6

Common Lisp, 137 символов

(defun z(n)(labels((i(n s r)(cond((= n 0)r)((< n(/ 1 s))(i n(ceiling(/ 1 n))r))(t(i(- n(/ 1 s))(1+ s)(cons s r))))))(reverse(i n 2'()))))

(z 43/48) -> (2 3 16)

(z 8/11) -> (2 5 37 4070)

(z 5/121) -> (25 757 763309 873960180913 1527612795642093418846225)

Не нужно беспокоиться об огромных числах или обработке дробных обозначений!

Пол Рихтер
источник
(defun z (n) (метки ((i (nsr) (cond ((= n 0) r) ((<n (/ 1 s)) (in (потолок (/ 1 n)) r)) (t ( i (- n (/ 1 s)) (1+ s) (cons sr)))))) (обратный (в 2 '())))) (z 43/48) Показать не результат в т ... Что я должен использовать для печати результата?
РосЛюП
1
(print (z 103/333)) возвращает один список из 5 чисел, но будет существовать один список из 4 чисел в виде: 1 / 4,1 / 18,1 / 333,1 / 1332. Таким образом, вышеприведенная функция не будет возвращать минимум.
Рослуп
8

Python 2, 169 167 символов

x,y=input()
def R(n,a,b):
 if n<2:return[b/a][b%a:]
 for m in range((b+a-1)/a,b*n/a):
  L=R(n-1,a*m-b,m*b)
  if L:return[m]+L
n=L=0
while not L:n+=1;L=R(n,x,y)
print L

Принимает разделенные запятыми аргументы в stdin и печатает список python в stdout.

$ echo 8,11 | ./egypt.py 
[2, 5, 37, 4070]
Кит Рэндалл
источник
2
1. Я думаю, что вы можете сохранить два символа, используя вкладку на втором уровне отступа. 2. Скрипт не указывает на усечение из-за превышения ограничений системной памяти.
хлебница
In Tio Вашему коду не хватает памяти всего на 103/45533
RosLuP
Вместо этого в Ideone ваш код идет во время выполнения ошибки для того же ввода 103,45533: Ошибка времени выполнения #stdin #stdout #stderr 0.89s 99264KB
RosLuP
4

PHP 82 байта

<?for(fscanf(STDIN,"%d%d",$a,$b);$a;)++$i<$b/$a||printf("$i ",$a=$a*$i-$b,$b*=$i);

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

Пример использования:

$ echo 43 48 | php egyptian-fraction.php
2 3 16
$ echo 8 11 | php egyptian-fraction.php
2 5 37 4070
Примо
источник
Оператор запятой эмулируется как бесполезные аргументы для printf? Я должен сохранить этот трюк где-нибудь.
Конрад Боровски
1
Я почти уверен, что это жадный алгоритм , поэтому он не всегда дает наименьший набор дробей. Если вы запустите его с помощью ввода 5 121или 31 311, он даст неправильный ответ (через очень долгое время).
grc
@grc 31/311 -> {a [1] -> 11, a [2] -> 115, a [3] -> 13570, a [4] -> 46422970}
доктор Белизарий
4

C 163 177 символов

6/6 : Наконец, программа теперь корректно обрабатывает усечение во всех случаях. Потребовалось намного больше символов, чем я надеялся, но оно того стоило. Программа должна на 100% соответствовать требованиям проблемы сейчас.

d[99],c,z;
r(p,q,n,i){for(c=n+q%p<2,i=q/p;c?d[c++]=i,0:++i<n*q/p;)q>~0U/2/i?c=2:r(i*p-q,i*q,n-1);}
main(a,b){for(scanf("%d%d",&a,&b);!c;r(a,b,++z));while(--c)printf("%d\n",d[c]);}

Программа берет числитель и знаменатель на стандартный ввод. Знаменатели выводятся на стандартный вывод, по одному на строку. Усеченный вывод указывается путем печати нулевого знаменателя в конце списка:

$ ./a.out
2020 2064
2
3
7
402
242004

$ ./a.out
6745 7604
2
3
19
937
1007747
0

Знаменатели во втором примере составляют 95485142815/107645519046, что отличается от 6745/7604 примерно на 1e-14.

Хлебница
источник
Опять же, я думаю, что это жадный алгоритм.
grc
Внешний цикл исследует все возможные ответы N знаменателей, прежде чем он начнет тестировать ответы N + 1 знаменателей. Вы можете назвать это жадным, я полагаю, но я считаю, что это решает поставленную проблему.
хлебница
Извините, я забираю это обратно. Он не следует жадному решению, но я обнаружил, что он не совсем точен для некоторых входных данных ( 31 311например).
grc
31 311переполняется, но программа не может пометить его.
хлебница
3

Питон, 61 символ

Ввод из STDIN, через запятую.
Вывод в STDOUT, новая строка разделена.
Не всегда возвращает самое короткое представление (например, для 5/121).

a,b=input()
while a:
    i=(b+a-1)/a
    print"1/%d"%i
    a,b=a*i-b,i*b

Символы подсчитываются без лишних новых строк (то есть, соединяя все строки в пределах whileиспользования ;).
Фракция есть a/b.
iэто b/aокруглый, так что я знаю 1/i <= a/b.
После печати 1/iзаменяю a/bна a/b - 1/i, что есть (a*i-b)/(i*b).

ugoren
источник
Я хочу , чтобы голосовать этот план, так как он является настолько мал, но это просто не хватает , что один кусок!
Гаффи
2
Я хочу исправить этот кусок, но тогда он не будет таким маленьким ... У меня такое чувство, что я просто заново изобрету решение Кейта Рэндалла.
Угорен
2

C 94 байта

n,d,i;main(){scanf("%i%i",&n,&d);for(i=1;n>0&++i>0;){if(n*i>=d)printf("%i ",i),n=n*i-d,d*=i;}}

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

редактировать: более короткая версия кода была размещена в комментариях, поэтому я заменил ее. Благодарность!

う ち わ 密 か
источник
2
Здравствуйте и добро пожаловать на сайт! Это соревнование по коду для игры в гольф , поэтому цель - сделать ваш код максимально коротким . Похоже, есть много вещей, которые вы могли бы сделать, чтобы сделать ваш код короче. Например, вы можете удалить все ненужные пробелы в своем ответе.
DJMcMayhem
@DJMcMayhem Спасибо, сэр, все поняли и сделали.
う ち わ 密 か
Привет, добро пожаловать в PPCG! Не могли бы вы добавить ссылку TryItOnline с тестовым кодом для тестовых случаев в задании ? Кроме того, некоторые вещи, которые вы могли бы 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>. О, и это может быть интересно прочитать Советы по игре в гольф на Си и Советы по игре в гольф на <все языки>
Кевин Круйссен,
@KevinCruijssen Спасибо за советы.
う ち わ 密 か
94 байта .
Джонатан Фрех
0

АКСИОМА, 753 байта

L==>List FRAC INT
macro  M(q)==if c<m or(c=m and m<999 and reduce(max,map(denom,q))<xv)then(m:=c;a:=q;xv:=reduce(max,map(denom,a)))
f(x,n)==(y:=x;a:L:=[];c:=0;q:=denom x;q:=q^4;for i in n.. repeat((c:=c+1)>50=>(a:=[];break);1/i>y=>1;member?(1/i,a)=>1;a:=concat(a,1/i);(y:=y-1/i)=0=>break;numer(y)=1 and ~member?(y,a)=>(a:=concat(a,y);break);(i:=floor(1/y))>q=>(a:=[];break));a)
h(x:FRAC INT):L==(a:L:=[];x>1=>a;numer(x)=1=>[x];n:=max(2,floor(1/x));xv:=m:=999;d:=denom x;zd:=divisors d;z:=copy zd;for i in 2..30 repeat z:=concat(z,i*zd);d:=min(10*d,n+9*m);for i in n..d repeat((c:=maxIndex(b:=f(x,i)))=0=>1;c>m+1=>1;M(b);v:=reduce(+,delete(b,1));for j in z repeat((c:=1+maxIndex(q:=f(v,j)))=1=>1;member?(b.1,q)=>1;q:=concat(b.1,q);M(q)));reverse(sort a))

Идея состоит в том, чтобы применить «алгоритм жадности» с разными начальными точками и сохранить список с минимальной длиной. Но не всегда он нашел бы минимальное решение с менее дифференцированным: «массив A будет меньше, чем массив B, если и только если A имеет несколько элементов из B, или если число элементов в A равно количеству элементов в B , чем A меньше B, если более маленький элемент A больше числа, чем более маленький элемент B ". Разобраться и проверить

-- this would be the "Greedy Algorithm"
fracR(x,n)==
   y:=x;a:L:=[];c:=0;q:=denom x;q:=q^4
   for i in n.. repeat
      (c:=c+1)>50   =>(a:=[];break)
      1/i>y         =>1
      member?(1/i,a)=>1
      a:=concat(a,1/i)
      (y:=y-1/i)=0  =>break
      numer(y)=1 and ~member?(y,a)=>(a:=concat(a,y);break)
      (i:=floor(1/y))>q           =>(a:=[];break)
   a

-- Return one List a=[1/x1,...,1/xn] with xn PI and x=r/s=reduce(+,a) or return [] for fail
Frazione2SommaReciproci(x:FRAC INT):L==
    a:L:=[]
    x>1       =>a
    numer(x)=1=>[x]
    n:=max(2,floor(1/x));xv:=m:=999;d:=denom x;zd:=divisors d;z:=copy zd
    for i in 2..30 repeat z:=concat(z,i*zd)
    d:=min(10*d,n+9*m) 
    for i in n..d repeat
        (c:=maxIndex(b:=fracR(x,i)))=0=>1 
        c>m+1                         =>1
        M(b)
        v:=reduce(+,delete(b,1))
        for j in z repeat
              (c:=1+maxIndex(q:=fracR(v,j)))=1=>1
              member?(b.1,q)                  =>1
              q:=concat(b.1,q)
              M(q) 
    reverse(sort a)

(7) -> [[i,h(i)] for i in [1/23,2/23,43/48,8/11,5/121,2020/2064,6745/7604,77/79,732/733]]
   (7)
      1   1      2   1  1      43  1 1  1      8  1 1  1  1
   [[--,[--]], [--,[--,---]], [--,[-,-,--]], [--,[-,-,--,--]],
     23  23     23  12 276     48  2 3 16     11  2 6 22 66
      5    1  1   1      505  1 1 1  1    1
    [---,[--,---,---]], [---,[-,-,-,---,----]],
     121  33 121 363     516  2 3 7 602 1204
     6745  1 1  1  1    1      1       77  1 1 1  1  1   1
    [----,[-,-,--,---,-----,------]], [--,[-,-,-,--,---,---]],
     7604  2 3 19 950 72238 570300     79  2 3 8 79 474 632
     732  1 1 1  1   1    1     1
    [---,[-,-,-,--,----,-----,-----]]]
     733  2 3 7 45 7330 20524 26388
                                                      Type: List List Any
       Time: 0.07 (IN) + 200.50 (EV) + 0.03 (OT) + 9.28 (GC) = 209.88 sec
(8) -> h(124547787/123456789456123456)
   (8)
        1             1                         1
   [---------, ---------------, ---------------------------------,
    991247326  140441667310032  613970685539400439432280360548704
                                     1
    -------------------------------------------------------------------]
    3855153765004125533560441957890277453240310786542602992016409976384
                                              Type: List Fraction Integer
                     Time: 17.73 (EV) + 0.02 (OT) + 1.08 (GC) = 18.83 sec
(9) -> h(27538/27539)
         1 1 1  1  1    1      1        1
   (9)  [-,-,-,--,---,-----,------,----------]
         2 3 7 52 225 10332 826170 1100871525
                                              Type: List Fraction Integer
                     Time: 0.02 (IN) + 28.08 (EV) + 1.28 (GC) = 29.38 sec

ссылка и номера с: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/egyptian.html

для добавления чего-либо, эта ниже будет оптимизирована для поиска доли минимальной длины, у которой максимальный знаменатель меньше (и не оптимизирована для длины)

L==>List FRAC INT

-- this would be the "Greedy Algorithm"
fracR(x,n)==
   y:=x;a:L:=[];c:=0;q:=denom x;q:=q^20
   for i in n.. repeat
      (c:=c+1)>1000  =>(a:=[];break)
      1/i>y          =>1
      member?(1/i,a) =>1
      a:=concat(a,1/i)
      (y:=y-1/i)=0  =>break
      numer(y)=1 and ~member?(y,a)=>(a:=concat(a,y);break)
      (i:=floor(1/y))>q           =>(a:=[];break)
   a

-- Return one List a=[1/x1,...,1/xn] with xn PI and x=r/s=reduce(+,a) or return [] for fail
Frazione2SommaReciproci(x:FRAC INT):L==
    a:L:=[]
    x>1       =>a
    numer(x)=1=>[x]
    n:=max(2,floor(1/x));xv:=m:=999;d:=denom x;zd:=divisors d;z:=copy zd; 
    w1:= if d>1.e10 then 1000 else 300; w2:= if d>1.e10 then 1000 else if d>1.e7 then 600 else if d>1.e5 then 500 else if d>1.e3 then 400 else 100;
    for i in 2..w1 repeat(mt:=(i*zd)::List PI;mv:=[yy for yy in mt|yy>=n];z:=sort(removeDuplicates(concat(z,mv)));#z>w2=>break)
    for i in z repeat
        (c:=maxIndex(b:=fracR(x,i)))=0=>1 
        c>m+1                         =>1
        if c<m or(c=m and m<999 and reduce(max,map(denom,b))<xv)then(m:=c;a:=b;xv:=reduce(max,map(denom,a)))
        v:=reduce(+,delete(b,1))
        for j in z repeat
              (c:=1+maxIndex(q:=fracR(v,j)))=1=>1
              member?(b.1,q)                  =>1
              q:=concat(b.1,q)
              if c<m or(c=m and m<999 and reduce(max,map(denom,q))<xv)then(m:=c;a:=q;xv:=reduce(max,map(denom,a)))
    reverse(sort a)

результаты:

(5) -> [[i,Frazione2SommaReciproci(i)] for i in [1/23,2/23,43/48,8/11,5/121,2020/2064,6745/7604,77/79,732/733]]
   (5)
      1   1      2   1  1      43  1 1  1      8  1 1  1  1
   [[--,[--]], [--,[--,---]], [--,[-,-,--]], [--,[-,-,--,--]],
     23  23     23  12 276     48  2 3 16     11  2 6 22 66
      5    1  1   1      505  1 1 1  1    1
    [---,[--,---,---]], [---,[-,-,-,---,----]],
     121  33 121 363     516  2 3 7 602 1204
     6745  1 1  1  1    1      1       77  1 1 1  1  1   1
    [----,[-,-,--,---,-----,------]], [--,[-,-,-,--,---,---]],
     7604  2 3 19 950 72238 570300     79  2 3 8 79 474 632
     732  1 1 1  1   1    1     1
    [---,[-,-,-,--,----,-----,-----]]]
     733  2 3 7 45 7330 20524 26388
                                                      Type: List List Any
                     Time: 0.08 (IN) + 53.45 (EV) + 3.03 (GC) = 56.57 sec
(6) -> Frazione2SommaReciproci(124547787/123456789456123456)
   (6)
        1            1               1                  1
   [---------, ------------, ----------------, -------------------,
    994074172  347757767307  2764751529594496  1142210063701888512
                      1
    -------------------------------------]
    2531144929865351036156388364636113408
                                              Type: List Fraction Integer
         Time: 0.15 (IN) + 78.30 (EV) + 0.02 (OT) + 5.28 (GC) = 83.75 sec
(7) -> Frazione2SommaReciproci(27538/27539)
         1 1 1  1   1     1       1       1
   (7)  [-,-,-,--,----,-------,-------,-------]
         2 3 7 43 1935 3717765 5204871 7105062
                                              Type: List Fraction Integer
                     Time: 0.05 (IN) + 45.43 (EV) + 2.42 (GC) = 47.90 sec

Кажется, многие хорошие знаменатели имеют в качестве делителей факторов знаменателя входной дроби.

RosLuP
источник
0

C 85 78 байт

Улучшено @ceilingcat , 78 байт:

n,d;main(i){for(scanf("%i%i",&n,&d);n;n*++i/d&&printf("%i ",i,d*=i,n=n*i-d));}

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


Мой оригинальный ответ, 85 байт:

n,d,i=1;main(){for(scanf("%i%i",&n,&d);n&&++i;n*i/d?printf("%i ",i),n=n*i-d,d*=i:0);}

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

Часть заслуг должна принадлежать Джонатану Фреху , который написал это 94-байтовое решение, которое я улучшил.

OverclockedSanic
источник
0

APL (NARS), 2502 байта

fdn←{1∧÷⍵}⋄fnm←{1∧⍵}⋄ffl←{m←⎕ct⋄⎕ct←0⋄r←⌊⍵⋄⎕ct←m⋄r}⋄divisori←{a[⍋a←{∪×/¨{0=≢⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}π⍵}⍵]}

r←frRF w;x;y;c;q;i;j
(x i)←w⋄i-←1⋄y←x⋄r←⍬⋄c←0⋄q←fdn x⋄q←q*20
i+←1
→4×⍳∼1000<c+←1⋄→6
j←÷i⋄→2×⍳j>y⋄→2×⍳(⊂j)∊r⋄r←r,(⊂j)⋄y←y-j⋄→0×⍳y=0⋄→5×⍳1≠fnm y⋄→5×⍳(⊂y)∊r⋄r←r,⊂y⋄→0
→2×⍳∼q<i←ffl ÷y
r←⍬

r←fr2SumF x;n;xv;m;d;zd;z;i;b;c;t;v;j;k;q;w1;w2;t;b1
z←r←⍬⋄→0×⍳1≤ffl x
:if 1=fnm x⋄r←,⊂x⋄→0⋄:endif
n←2⌈ffl÷x⋄xv←m←999⋄d←fdn x⋄zd←divisori d
w1←1000⋄w2←50⋄:if d>1.e10⋄w2←700⋄:elseif d>1.e7⋄w2←600⋄:elseif d>1.e5⋄w2←500⋄:elseif d>1.e3⋄w2←400⋄:elseif d>1.e2⋄w2←100⋄:endif
:for i :in ⍳w1⋄z←∪z∪k/⍨{⍵≥n}¨k←i×zd⋄:if w2<≢z⋄:leave⋄:endif⋄:endfor
z←∪z∪zd⋄z←z[⍋z]
:for i :in z
    :if 0=c←≢b←frRF x i ⋄:continue⋄:endif
    :if      c>m+1      ⋄:continue⋄:endif
    :if      c<m        ⋄m←c⋄r←b⋄xv←⌈/fdn¨b
    :elseif (c=m)∧(m<999)
         :if xv>t←⌈/fdn¨b⋄m←c⋄r←b⋄xv←t⋄:endif
    :endif
    :if c≤2⋄:continue⋄:endif
    v←↑+/1↓b⋄b1←(⊂↑b)
    :for j :in z
       :if 1=c←1+≢q←frRF v j⋄:continue⋄:endif
       :if        b1∊q      ⋄:continue⋄:endif
       q←b1,q
       :if  c<m⋄m←c⋄r←q     ⋄xv←⌈/fdn¨q
       :elseif (c=m)∧(m<999)
           :if xv>t←⌈/fdn¨q⋄m←c⋄r←q⋄xv←t⋄:endif
       :endif
    :endfor
:endfor
→0×⍳1≥≢r⋄r←r[⍋fdn¨r]

Перевод из кода AXIOM для этой задачи в APL, впервые использующий (для меня) тип дроби (то есть bignum ...).

103r233 означает фракцию 103/233. Тестовое задание:

  ⎕fmt fr2SumF 1r23
┌1────┐
│ 1r23│
└~────┘
  ⎕fmt fr2SumF 2r23
┌2──────────┐
│ 1r12 1r276│
└~──────────┘
  ⎕fmt fr2SumF 43r48
┌3────────────┐
│ 1r2 1r3 1r16│
└~────────────┘
  fr2SumF 8r11
1r2 1r6 1r22 1r66 
  fr2SumF 5r121
1r33 1r121 1r363 
  fr2SumF 2020r2064
1r2 1r3 1r7 1r602 1r1204 
  fr2SumF 6745r7604
1r2 1r3 1r19 1r950 1r72238 1r570300 
  fr2SumF 77r79
1r2 1r3 1r8 1r79 1r474 1r632 
  fr2SumF 732r733
1r2 1r3 1r7 1r45 1r7330 1r20524 1r26388 
  fr2SumF 27538r27539
1r2 1r3 1r7 1r43 1r1935 1r3717765 1r5204871 1r7105062 
  fr2SumF 124547787r123456789456123456
1r994074172 1r347757767307 1r2764751529594496 1r1142210063701888512 
  1r2531144929865351036156388364636113408 
RosLuP
источник