Προγραμματιστική πρόκληση Νο 15 : Κλάσματα

Είναι γνωστό από την αυγή των μαθηματικών [1] πως κάθε θετικό κλάσμα μπορεί να γραφτεί σαν άθροισμα πεπερασμένων (δηλαδή όχι άπειρων) όρων της μορφής \frac{1}{n}. Για παράδειγμα

\frac{3}{7} = \frac{1}{3} + \frac{1}{11} + \frac{1}{231}

Γράψτε ένα πρόγραμμα σε οποιαδήποτε γλώσσα προγραμματισμού που να παίρνει ένα κλάσμα ή ένα θετικό φυσικό αριθμό και να υπολογίζει μια τέτοια κλασματική αναπαράσταση του. Το να είσαι άπληστος και να τα θέλεις όλα ίσως να είναι μια χρήσιμη ιδιότητα να έχει κανείς.

Level 2
Αλλά είναι η απληστία η καλύτερη λύση; Αν θέλεις μια μεγαλύτερη πρόκληση αντί για

\frac{5}{31} = \frac{1}{7} + \frac{1}{55} + \frac{1}{3979} + \frac{1}{23744683} + \frac{1}{1127619917796295}

ίσως να είναι καλύτερο το

\frac{5}{31} = \frac{1}{7} + \frac{1}{91} + \frac{1}{247} + \frac{1}{475} + \frac{1}{775}

κριτήριο επιλογής μπορεί να είναι το πλήθος των όρων ή το άθροισμα των παρανομαστών (είναι άραγε το ίδιο;) Δοκιμάστε με το \frac{11}{199}.

Αλλά δεν είναι ανάγκη να το κάψουμε. Η πρώτο level είναι βατό για οποιονδήποτε ξέρει μια γλώσσα προγραμματισμού. Μην ξεχνάμε πως σκοπός μας εδώ είναι να παίξουμε να βάλουμε προκλήσεις στον εαυτό μας (και μόνον) και να ξεσκουριάσουμε τις γνώσεις μας στον προγραμματισμό. Και το φόρουμ είναι ανοικτό στον καθένα που θέλει να βάλει τις δικές του προκλήσεις :innocent:

Περιμένω τις λύσεις σας. Υπάρχει ένας online calculator για να δείτε παραδείγματα

https://planetcalc.com/8465/?fraction=11%2F199&method=fibonacci&comparator=rhind

1 «Μου αρέσει»

Το βιβλίο που αναφέρεται στο τέλος της σελίδας του planetcalc, που εμπεριέχει αλγορίθμους, παραδείγματα εφαρμογής αυτών, υλοποιήσεις σε C, κι αποδείξεις διαφόρων σχετικών θεωρημάτων, υπάρχει στη σελίδα του Gong.

http://kevingong.com/Math/EgyptianFractions.pdf

Βασικά το ζητούμενο είναι να γράψουμε x/y = 1/z + a/b, το οποίο μεταφράζεται σε μια επαναληπτική μέθοδο. Το πιο απλό είναι να πάρεις κανείς το μικρότερο δυνατό z για το οποίο το 1/z είναι μικρότερο του x/y. Δηλαδή 1/z = x/y - \epsilon_{min} \Rightarrow z = \lceil y/x \rceil . Έστω τότε b=z, άρα a=\lceil y/x \rceil x/y - 1=((-y) \mathrm{mod}\ x)/y. To ανάπτυγμα με τις προηγούμενες τιμές είναι ο άπληστος αλγόριθμος, που σταματάει για a=0, για το συγκεκριμένο πρόβλημα.

Περισσότερο μαθηματικό θα έλεγα πρόβλημα.

2 «Μου αρέσει»