Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
70 lines (55 sloc) 4.41 KB
''' άσκηση από το http://pythonies.mysch.gr/chapters/craps.pdf
Το 1937, ο γερμανός μαθηματικός Lothar Collatz διατύπωσε τον παρα-
κάτω ισχυρισμό, ο οποίος παραμένει αναπόδεικτος:
Επιλέξτε έναν θετικό ακέραιο n. Αν είναι άρτιος διαιρέστε
τον με το 2, ενώ αν είναι περιττός πολλαπλασιάστε τον με το
3 και προσθέστε μια μονάδα. Επαναλάβετε τη διαδικασία με
τον νέο αριθμό που θα προκύψει. Από οποιονδήποτε αριθμό
n κι αν ξεκινήσετε, θα καταλήξετε στον αριθμό 1.
Η εικασία έχει επαληθευτεί αριθμητικά μέχρι και για αριθμούς της τά-
ξης των 6 δισεκατομμυρίων δισεκατομμυρίων, ωστόσο δεν υπάρχει ανα-
λυτική μαθηματική απόδειξη. Θεωρητικά υπάρχει πάντα το ενδεχόμενο
ένας ακόμα μεγαλύτερος αριθμός να παραβιάζει την εικασία!
Γράψτε ένα πρόγραμμα το οποίο θα διαβάζει από το χρήστη τον αριθμό
εκκίνησης n, θα επαναλαμβάνει τη διαδικασία που περιγράφεται πα-
ραπάνω και θα εμφανίζει τους διαδοχικούς αριθμούς που προκύπτουν
από αυτή, έως ότου η διαδικασία καταλήξει στον αριθμό 1. Μπορείτε να
εμπλουτίσετε το πρόγραμμά σας, ώστε μετά το τέλος της διαδικασίας
να εμφανίζει το χρόνο τερματισμού, δηλαδή το συνολικό αριθμό των βη-
μάτων που απαιτήθηκαν, αλλά και το σημείο πλημμυρίδας, δηλαδή τον
μεγαλύτερο αριθμό που προέκυψε κατά την εκτέλεση της διαδικασίας.
Για παράδειγμα, ξεκινώντας από το n=6 δημιουργείται η παρακάτω ακο-
λουθία, με χρόνο τερματισμού τα 8 βήματα και σημείο πλημμυρίδας το 16:
6 3 10 5 16 8 4 2 1
'''
print("Η εικασία του Collatz.")
print("Δώσε μου έναν ακέραιο αριθμό εκκίνησης:", end=" ")
n = int(input())
# Αποθήκευση αρχικού αριθμού για να χρησιμοποιηθεί στο τέλος
# προκειμένου να εμφανίσουμε τα κατάλληλα μηνύματα.
startValue = n
# Θα χρειαστούμε έναν μετρητή για το συνολικό αριθμό βήματων - επαναλήψεων που θα εκτελεστούν.
# Αρχικά θα του δώσουμε την τιμή 0.
steps = 0
# Θα χρησιμοποιήσουμε μια μεταβλητή για να βρούμε το σημείο πλημμυρίδας, δηλαδή τον μέγιστο αριθμό της ακολουθίας.
# Σαν αρχική τιμή θα της δώσουμε τον αρχικό αριθμό n.
maxn = n
# Η διαδικασία θα επαναλαμβάνεται όσο δεν έχουμε φτάσει στο 1.
# (Bέβαια αν καταφέρουμε να ανακαλύψουμε αριθμό που δεν ικανοποιεί την εικασία τη βάψαμε!)
while n > 1:
print(n, end=" ")
# αύξηση του μετρητή σε κάθε επανάληψη
steps = steps + 1
# έλεγχος αν ο αριθμός είναι άρτιος
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
# εφόσον ο νέος αριθμός είναι μεγαλύτερος από το σημείο πλημμυρίδας,
# ενημέρωσε κατάλληλα την τιμή του μέγιστου
if n > maxn:
maxn = n
print()
print("Η εικασία του Collatz επιβεβαιώθηκε για τον αριθμό", startValue)
print("Συνολικά βήματα:", steps)
print("Σημείο πλημμυρίδας:", maxn)