Σε αυτό το παράδειγμα, θα μάθετε να βρίσκετε το GCD δύο αριθμών χρησιμοποιώντας δύο διαφορετικές μεθόδους: λειτουργία και βρόχους και, αλγόριθμος Euclidean
Για να κατανοήσετε αυτό το παράδειγμα, θα πρέπει να γνωρίζετε τις ακόλουθες θεματολογίες προγραμματισμού Python:
- Λειτουργίες Python
- Επανάληψη Python
- Επιχειρήματα Python Function
Ο υψηλότερος κοινός παράγοντας (HCF) ή ο μεγαλύτερος κοινός διαιρέτης (GCD) δύο αριθμών είναι ο μεγαλύτερος θετικός ακέραιος που διαιρεί τέλεια τους δύο δεδομένους αριθμούς. Για παράδειγμα, το HCF των 12 και 14 είναι 2.
Πηγαίος κώδικας: Χρήση βρόχων
# Python program to find H.C.F of two numbers # define a function def compute_hcf(x, y): # choose the smaller number if x> y: smaller = y else: smaller = x for i in range(1, smaller+1): if((x % i == 0) and (y % i == 0)): hcf = i return hcf num1 = 54 num2 = 24 print("The H.C.F. is", compute_hcf(num1, num2))
Παραγωγή
Το HCF είναι 6
Εδώ, δύο ακέραιοι αποθηκευμένοι στις μεταβλητές num1 και num2 μεταφέρονται στη compute_hcf()συνάρτηση. Η συνάρτηση υπολογίζει το HCF αυτούς τους δύο αριθμούς και τον επιστρέφει.
Στη συνάρτηση, καθορίζουμε πρώτα τους μικρότερους από τους δύο αριθμούς αφού ο HCF μπορεί να είναι μόνο μικρότερος ή ίσος με τον μικρότερο αριθμό. Στη συνέχεια, χρησιμοποιούμε έναν forβρόχο για μετάβαση από 1 σε αυτόν τον αριθμό.
Σε κάθε επανάληψη, ελέγχουμε εάν ο αριθμός μας χωρίζει τέλεια και τους δύο αριθμούς εισόδου. Εάν ναι, αποθηκεύουμε τον αριθμό ως HCF Κατά την ολοκλήρωση του βρόχου, καταλήγουμε με τον μεγαλύτερο αριθμό που χωρίζει τέλεια και τους δύο αριθμούς.
Η παραπάνω μέθοδος είναι κατανοητή και εφαρμόσιμη, αλλά δεν είναι αποτελεσματική. Μια πολύ πιο αποτελεσματική μέθοδος για την εύρεση του HCF είναι ο αλγόριθμος Euclidean.
Ευκλείδειος αλγόριθμος
Αυτός ο αλγόριθμος βασίζεται στο γεγονός ότι το HCF δύο αριθμών διαιρεί επίσης τη διαφορά τους.
Σε αυτόν τον αλγόριθμο, διαιρούμε το μεγαλύτερο με μικρότερο και παίρνουμε το υπόλοιπο. Τώρα, διαιρέστε το μικρότερο με αυτό το υπόλοιπο. Επαναλάβετε μέχρι το υπόλοιπο να είναι 0.
Για παράδειγμα, εάν θέλουμε να βρούμε το HCF των 54 και 24, διαιρούμε το 54 με το 24. Το υπόλοιπο είναι 6. Τώρα, διαιρούμε το 24 με το 6 και το υπόλοιπο είναι 0. Ως εκ τούτου, το 6 είναι το απαιτούμενο HCF
Πηγαίος κώδικας: Χρησιμοποιώντας τον ευκλείδη αλγόριθμο
# Function to find HCF the Using Euclidian algorithm def compute_hcf(x, y): while(y): x, y = y, x % y return x hcf = compute_hcf(300, 400) print("The HCF is", hcf)
Εδώ βγαίνουμε μέχρι να γίνουν μηδέν. Η δήλωση x, y = y, x % yανταλλάσσει τιμές στο Python. Κάντε κλικ εδώ για να μάθετε περισσότερα σχετικά με την εναλλαγή μεταβλητών στο Python.
Σε κάθε επανάληψη, τοποθετούμε την τιμή του y σε x και το υπόλοιπο (x % y)σε y, ταυτόχρονα. Όταν το y γίνει μηδέν, έχουμε HCF στο x.
