Red de conocimiento informático - Material del sitio web - Solución algorítmica a fracciones egipcias

Solución algorítmica a fracciones egipcias

Tema

Fracciones egipcias

En el antiguo Egipto, se usaba la suma de fracciones unitarias (de la forma 1/a, donde a es un número natural) para representar todos los números racionales. Por ejemplo:

2/3=1/2 1/6, pero 2/3=1/3 1/3 no está permitido porque los sumandos son iguales. Hay muchas formas de expresar la fracción a/b

¿Pero cuál es mejor?

En primer lugar, un sumando más pequeño es mejor que un sumando más grande. En segundo lugar, cuando los sumandos son iguales, cuanto mayor sea la fracción mínima, mejor. Por ejemplo:

El mejor es el último porque 1/18 es mayor que 1/180, 1/45, 1/30 y 1/180.

Archivo de entrada

Dados dos enteros positivos a, b (0 lt; a lt; b lt; 1000), compila la mejor expresión para la fracción a/b.

Archivo de salida

Varios números ordenados en orden ascendente de denominadores de fracciones unitarias.

Ejemplo de entrada

19 45

Ejemplo de salida

5 6 18

código Pascal (repetidamente, allí son mejores algoritmos)

var

temp, ans: array[1.20]of longint;

flag: boolean;

aim: extendido;

a, b, te, maxd: longint;

función gcd(a, b: longint):

comenzar

p>

si b=0 entonces salga (a);

salir(gcd(b, a mod b));

end;

función lcm(a, b: longint): int64;

var

t: longint

begin

if a lt; b entonces

comenzar

t:=a; a:=b; b:=t

salir; a div gcd(a, b)*b);

end;

procedimiento suma(var s1, s2: int64; m.longint

); var

t:int64;

begin

t:=lcm(s2,m);

si tgt; /p>

comienzo

s1:=10000;

s2:= 1;

salir;

fin;

s1:=t div s2*s1 t div m;

s2:=t;

t:=gcd(s1,s2);

s1:=s1 div t;

s2:=s2 div t;

fin;

procedimiento fc(s1, s2: entero largo) ;

var

i: longint;

comenzar

si (s1=a)y(s2=b) entonces p>

comenzar

bandera:= verdadero;

si ans[maxd]gt;temp[maxd] entonces

ans:=temp ;

fin;

fin;

procedimiento dfs(s: extendido; s1, s2, m, i: int64); >var

j: longint;

arriba, abajo, t1, t2: int64

comenzar

if s1/s2gt; apuntar y luego salir;

si igt; maxd entonces comenzar fc(s1, s2; finalizar;

up:=trunc(1/(aim-s));

si uplt;m entonces arriba:=m;

abajo:=trunc((maxd-i 1)/(aim-s)) 100;

para j :=arriba a abajo

comenzar

temp[i]:=j;

t1:=s1;t2:=s2; <

p>suma(t1, t2, j);