Haskell - Fraccions egípcies P75176
Els antics egipcis tenien una codificació curiosa per als nombres racionals: consideraven que les fraccions havíen de ser unitaries, és a dir, amb un 1 al numerador. Quan havíen de codificar una d’aquestes fraccions ho feien com a sumes de fraccions unitàries. Per exemple, la fracció 2/3 l’escrivien com a 1/2+1/6. Encara avui dia hi ha llibres de matemàtiques que anomenen fraccions vulgars les que no són unitàries.
El nostre amic Fibonacci va dissenyar un algorisme per convertir fraccions vulgars a notació egipcia (com a suma de fraccions unitàries):
| egypt | ⎛ ⎜ ⎜ ⎝ |
| ⎞ ⎟ ⎟ ⎠ | = |
| +egypt(r) |
on
| r= |
|
Fixeu-vos que a la fórmula apareix el residu de la divisió (mod) i la funció ceiling.
Per treballar amb nombres racionals en Haskell heu d’afegir aquest import al principi del programa:
El nombres racionals es codifiquen amb el símbol de tant per cent: Per exemple, 1/2 és @1
Es demana:
- Implementeu (usant funcionds d’ordre superior i sense usar recursivitat ni la funció estàndard until) una funció myUntil :: (a -> Bool) -> (a -> a) -> a -> a que, donat un predicat p, una funció f i un valor x, retorni la llista [x, f x, f (f x), ...] fins es que satisfà el predicat p. Per exemple, myUntil (>100) (*2) 1 val 128.
- Feu una funció egypt :: Rational -> [Rational] que, utilitzant myUntil, implementi l’algorisme de Fibonacci per codificar fraccions a la egípcia. Per exemple, egypt (2[1
- Feu un programa que llegeixi una fracció per línia i, per a cadscuna, escrigui el seu equivalent egicpi.
Input
2 % 3 (-2) % 3 (-2) % (-3) 4 % 6 21 % 50 1 % 1 0 % 10 5426 % 1484
Output
[1 % 2,1 % 6] [(-1) % 1,1 % 3] [1 % 2,1 % 6] [1 % 2,1 % 6] [1 % 3,1 % 12,1 % 300] [1 % 1] [] [1 % 1,1 % 1,1 % 1,1 % 2,1 % 7,1 % 75,1 % 6957,1 % 64526175]
- Author
- Gerard Escudero
- Language
- Catalan
- Official solutions
- Haskell
- User solutions
- Haskell