projecteuler.net/index.php?section=problems&id=1If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Να βρεθεί το άθροισμα όλων των αριθμών μικρότερων του 1000 που είναι πολλαπλάσια του 3 ή του 5.
Κάνετε κλικ πάνω στα spoilers για να δείτε τον κώδικα.
Το πρόβλημα μπορεί πολύ εύκολα να λυθεί με 2 nested loops.
def simple(numbers, limit):
tot = 0
for i in range(min(numbers), limit):
for elem in numbers:
if i % elem == 0:
tot += i
break
return totH παραπάνω λύση είναι εύκολη στη σύλληψη και στην υλοποίηση αλλά καθώς χρησιμοποιεί loops δεν είναι και ότι καλύτερο από πλευράς απόδοσης κώδικα. Μια πιο γρήγορη λύση είναι να χρησιμοποιηθούν τα sets (σύνολα) της Python τα οποία δημιουργούνται και γίνονται iterate σημαντικά πιο γρήγορα από τις λίστες.
def sets(numbers, limit):
a = []
for number in numbers:
a.extend(range(number, limit, number))
return sum(list(set(a)))Μια διαφορετική προσέγγιση είναι να χρησιμοποιηθεί functional προγραμματισμός.
def functional(a, b, limit):
return sum(x for x in range(min(a,b), limit) if x % a == 0 or x % b == 0)Μια πιο "μαθηματική" προσέγγιση και ιδιαίτερα γρήγορη είναι η ακόλουθη.
def sum_of_multiples(a, b, limit):
return sum(range(a, limit, a)) + sum(range(b, limit, b)) - sum(range(a * b, limit, a * b))Τέλος μια λύση που χρησιμοποιεί recursion είναι η εξής
def recursion(a, b, limit, r):
if limit == 0:
r = 0
return r
elif (limit % a == 0) or (limit % b == 0):
r = recursion(a, b, limit - 1, r)
r += limit
else:
r = recursion(a, b, limit - 1, r)
return r--------------------------------------------------
simple => 0.450550079346
sets => 0.0812981128693
functional => 0.295082092285
sum_of_multiples => 0.0238010883331
recursion => 0.808387041092
--------------------------------------------------
Όπως φαίνεται από τη σύγκριση των παραπάνω αλγορίθμων, η αποδοτικότερη υλοποίηση είναι η sum_of_multiples καθώς περιλαμβάνει τις λιγότερες πράξεις από όλες. Η λύση με τα sets είναι η δεύτερη καλύτερη και δεδομένου ότι είναι πιο γενική (βγάζει σωστά αποτελέσματα για οποιοδήποτε αριθμό μεταβλητών) είναι μάλλον η προτιμότερη. Η αναδρομική λύση είναι η χειρότερη από πλευράς απόδοσης. Αυτό οφείλεται στο ότι οι κλήσεις συναρτήσεων (function calls) στην Python είναι αρκετά χρονοβόρα.
Ξέρει κανείς κάποιον άλλο τρόπο να λύσει το πρόβλημα? Ή να προτείνει κάποια βελτίωση στις ήδη υπάρχουσες?
Οποιοδήποτε άλλο σχόλιο ή απορία φυσικά ευπρόσδεκτο.
Ολοκληρωμένη η λύση, μαζί με τον κώδικα τεκμηρίωσης και σύγκρισης μπορεί να βρεθεί
ΕΔΩ
