Frações egípcias

20

Visão global:

Da Wikipedia : Uma fração egípcia é a soma de frações unitárias distintas. Ou seja, cada fração da expressão tem um numerador igual a 1 e um denominador que é um número inteiro positivo, e todos os denominadores diferem entre si. O valor de uma expressão desse tipo é um número racional positivo a / b. Todo número racional positivo pode ser representado por uma fração egípcia.

Desafio:

Escreva a função mais curta que retornará os valores de todos os denominadores para o menor conjunto de frações de unidades que somam uma determinada fração.

Regras / restrições:

  • A entrada terá dois valores inteiros positivos.
    • Isto pode ser on STDIN, argv, separados por vírgula, espaço delimitado, ou qualquer outro método que você preferir.
  • O primeiro valor de entrada deve ser o numerador e o segundo valor de entrada o denominador.
  • O primeiro valor de entrada deve ser menor que o segundo.
  • A saída pode incluir um valor que exceda as limitações de memória do seu sistema / idioma (RAM, MAX_INT ou quaisquer outras restrições de código / sistema existentes). Se isso acontecer, basta truncar o resultado no valor mais alto possível e observe isso de alguma forma (ie ...).
  • A saída deve poder manipular um valor de denominador até pelo menos 2.147.483.647 (2 31 -1, assinado em 32 bits int).
    • Um valor mais alto ( long, etc.) é perfeitamente aceitável.
  • A saída deve ser uma lista de todos os valores dos denominadores do menor conjunto de frações unitárias encontradas (ou das próprias frações, ie 1/2).
  • A saída deve ser ordenada ascendente de acordo com o valor do denominador (decrescente pelo valor da fração).
  • A saída pode ser delimitada da maneira que você desejar, mas deve haver algum caractere entre eles para diferenciar um valor do outro.
  • Isso é código de golfe, então a solução mais curta vence.

Exemplos:

  • Entrada 1:

    43, 48

  • Saída 1:

    2, 3, 16

  • Entrada 2:

    8/11

  • Saída 2:

    1/2 1/6 1/22 1/66

  • Entrada 3:

    5 121

  • Saída 3:

    33 121 363

Gaffi
fonte
Input / Output 2 deve ser 8, 11e 2, 6, 22, 66certo?
precisa saber é o seguinte
2
Uma sugestão possível, para remover a abiguidade, seria exigir o menor conjunto de frações de unidade com o menor denominador final. Por exemplo, 1/2 1/6 1/22 1/66seria preferível 1/2 1/5 1/37 1/4070para a entrada 8/11.
Primo
2
Sugiro adicionar 5/121 = 1/33+1/121+1/363aos casos de teste. Todos os programas gananciosos (incluindo o meu) fornecem 5 frações por isso. Exemplo retirado da Wikipedia .
Ugoren
11
@primo Eu acho que, se houver vários mínimos, o que for encontrado será aceitável. Se um algoritmo puder ser escrito com menos caracteres como resultado, eu não gostaria de impedir essa solução.
Gaffi #
11
Dei +1 desde que eu realmente aprendi sobre frações egípcias em um curso de História da Matemática (e tive que fazer matemática com elas, além de encontrar somas fracionárias como esse problema.) Um desafio agradável e criativo.
mbomb007

Respostas:

6

Lisp comum, 137 caracteres

(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)

Não precisa se preocupar com grandes números ou lidar com notações fracionárias!

Paul Richter
fonte
(defun z (n) (rótulos ((i (nsr) (cond ((= n 0) r)) ((<n (/ 1 s)) (em (teto (/ 1 n)) r)) (t ( i (- n (/ 1 s)) (1+ s) (cons sr)))))) (inverter (em 2 '())))) (z 43/48) Mostrar não resultar em t ... O que tenho que usar para imprimir o resultado?
30817 RosLuP
11
(print (z 103/333)) retorna uma lista de 5 números, mas existiria uma lista de 4 números como: 1 / 4,1 / 18,1 / 333,1 / 1332. Portanto, a função acima não retornaria o mínimo.
RosLuP 30/10
8

Python 2, 169 167 caracteres

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

Pega argumentos separados por vírgula no stdin e imprime uma lista python no stdout.

$ echo 8,11 | ./egypt.py 
[2, 5, 37, 4070]
Keith Randall
fonte
2
1. Acho que você pode salvar dois caracteres usando tab no segundo nível de indentação. 2. O script não indica truncamento devido a limitações excessivas de memória do sistema.
breadbox
No Tio Seu código fica sem memória por apenas 103/45533 #
RosLuP 28/10
Em vez disso, em Ideone seu código vai em erro tempo de execução para a mesma entrada 103,45533: erro Runtime #stdin #stdout #stderr 0.89s 99264KB
RosLuP
4

PHP 82 bytes

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

Isso pode ser mais curto, mas o numerador e o denominador atuais precisam ser mantidos como números inteiros para evitar erros de arredondamento de ponto flutuante (em vez de manter a fração atual).

Uso da amostra:

$ echo 43 48 | php egyptian-fraction.php
2 3 16
$ echo 8 11 | php egyptian-fraction.php
2 5 37 4070
primo
fonte
Operador de vírgula emulado como argumentos inúteis para printf? Eu deveria guardar esse truque em algum lugar.
21430 Konrad Borowski
11
Tenho certeza de que este é um algoritmo ganancioso , portanto nem sempre fornece o menor conjunto de frações. Se você executá-lo com entrada como 5 121ou 31 311, ele dará a resposta errada (depois de muito tempo).
grc 6/06/12
@grc 31/311 -> {a [1] -> 11, a [2] -> 115, a [3] -> 13570, a [4] -> 46422970}
Dr. belisarius
4

C, 163 177 caracteres

6/6 : Finalmente, o programa agora lida corretamente com o truncamento em todos os casos. Demorou muito mais caracteres do que eu esperava, mas valeu a pena. O programa deve 100% aderir aos requisitos do problema agora.

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]);}

O programa leva o numerador e o denominador na entrada padrão. Os denominadores são impressos na saída padrão, um por linha. A saída truncada é indicada imprimindo um denominador zero no final da lista:

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

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

Os denominadores no segundo exemplo somam 95485142815/107645519046, que difere de 6745/7604 em aproximadamente 1e-14.

caixa de pão
fonte
Mais uma vez, acho que este é um algoritmo ganancioso.
grc
O loop mais externo explora todas as respostas possíveis dos denominadores N antes de começar a testar as respostas dos denominadores N + 1. Você pode chamá-lo de ganancioso, suponho, mas acredito que cumpre o problema declarado.
breadbox
Desculpe, eu retiro isso. Ele não segue a solução gananciosa, mas eu descobri que não é completamente preciso para algumas informações ( 31 311por exemplo).
grc 6/06/12
31 311estouros, mas o programa falha em sinalizá-lo.
breadbox
3

Python, 61 caracteres

Entrada de STDIN, separada por vírgula.
Saída para STDOUT, nova linha separada.
Nem sempre retorna a representação mais curta (por exemplo, para 5/121).

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

Caracteres contados sem novas linhas desnecessárias (ou seja, unindo todas as linhas no whileuso ;).
A fração é a/b.
ié b/aarredondado, então eu sei 1/i <= a/b.
Após a impressão 1/i, substituo a/bpor a/b - 1/i, que é (a*i-b)/(i*b).

Ugoren
fonte
Quero votar, já que é tão pequeno, mas falta apenas uma peça!
Gaffi #
2
Quero consertar essa peça, mas não será tão pequena ... Tenho a sensação de que vou apenas reinventar a solução de Keith Randall.
ugoren
2

C, 94 bytes

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;}}

Experimente Online

edit: Uma versão mais curta do código foi postada nos comentários, então eu a substituí. Obrigado!

う ち わ 密
fonte
2
Olá e bem-vindo ao site! Como é uma competição de código-golfe , o objetivo é tornar seu código o mais curto possível . Parece que há muitas coisas que você poderia fazer para diminuir seu código. Por exemplo, você pode remover todo o espaço em branco desnecessário da sua resposta.
DJMcMayhem
@DJMcMayhem Obrigado senhor, entendido e pronto.
precisa
Olá, seja bem-vindo ao PPCG! Você poderia adicionar um link TryItOnline com código de teste para os casos de teste do desafio? Além disso, algumas coisas que você pode jogar golfe: for(i=2;n>0&&i>0;i++)podem ser for(i=1;n>0&++i>0;); os suportes do loop for podem ser removidos (porque ele possui apenas o ifinterior); d=d*i;pode ser d*=i;; e eu não estou totalmente certo, mas acho que #include <stdio.h>pode ser sem espaços: #include<stdio.h>. Ah, e pode ser interessante ler Dicas para jogar golfe em C e Dicas para jogar golfe em todos os idiomas <
Kevin Cruijssen 26/17
@KevinCruijssen Obrigado pelas dicas.
precisa
94 bytes .
Jonathan Frech
1

Stax , 18 bytes

é├WüsOΩ↨÷╬6H╒σw[▐â

Execute e depure

Em cada etapa, ele tenta minimizar o numerador subseqüente . Parece funcionar, mas não posso provar.

recursivo
fonte
0

AXIOM, 753 bytes

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 idéia seria aplicar o "algoritmo ganancioso" com diferentes pontos iniciais e salvar a lista que tem tamanho mínimo. Mas nem sempre ela encontraria a solução mínima com menos difinida: "a matriz A será menor que a matriz B se e somente se A tiver poucos elementos de B, ou se o número de elementos de A for o mesmo número de elementos de B , que A é menor que B se o menor elemento de A for maior como número, que o menor elemento de B ". Ungolfed e teste

-- 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

referência e números de: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/egyptian.html

para adicionar algo, este abaixo seria o otimizado para encontrar a fração de comprimento mínimo que possui o denominador máximo menor (e não otimizado para o comprimento)

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)

os resultados:

(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

Parece que muitos bons denominadores têm como divisores de fator o denominador da fração de entrada.

RosLuP
fonte
0

C, 85 78 bytes

Melhorado por @ceilingcat , 78 bytes:

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

Experimente online!


Minha resposta original, 85 bytes:

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);}

Experimente online!

Parte do crédito deve ser para Jonathan Frech , que escreveu essa solução de 94 bytes que aprimorei.

OverclockedSanic
fonte
0

APL (NARS), 2502 bytes

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]

Tradução do código AXIOM para esse problema, para APL, usando pela primeira vez (para mim) o tipo de fração (que é bignum ...).

103r233 significa a fração 103/233. Teste:

  ⎕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
fonte