Τρίγωνο Pascal (-Khayyám-Yang Ηui)

Τελευταία ενημέρωση 23/9/2016

Το τρίγωνο Πασκάλ n γραμμών κατασκευάζεται (μεταξύ άλλων) σύμφωνα με τον ακόλουθο αλγόριθμο:

1) Θεώρησε έναν τετραγωνικό πίνακα φυσικών αριθμών n × n – η θέση (κ,λ) στον πίνακα είναι η θέση στην γραμμή κ και στην στήλη λ. Θεώρησε ότι η πρώτη γραμμή και η πρώτη στήλη είναι η 0 (όπως συνηθίζεται γενικότερα στα μαθηματικά).

2) Αρχικοποίησε τον πίνακα θέτοντας την τιμή 0 σε κάθε θέση.

3) Για την γραμμή 0 θέσε την τιμή της θέσης (0,0) ίση με 1.

4) Για κάθε επόμενη γραμμή:

Για κάθε θέση της γραμμής ξεκινώντας από την θέση 0 (και μεταβαίνοντας κάθε φορά στην αμέσως επόμενη):

α) Αν πρόκειται για την πρώτη θέση της γραμμής (στήλη 0) θέσε την τιμή της θέσης ίση με 1.

β) Αν πρόκειται για άλλη θέση και στην προηγούμενη γραμμή και στην τρέχουσα στήλη (δηλαδή στην θέση ακριβώς από πάνω από την τρέχουσα) είναι το 0, θέσε την τιμή της τρέχουσας θέσης σε 1, προχώρησε στην επόμενη γραμμή και πήγαινε στο α).

γ) Αν πρόκειται για άλλη θέση από αυτή που περιγράφεται στα α), β) θέσε την τιμή της θέσης ίση με το άθροισμα της τιμής της πάνω αριστερά θέσης και της τιμής της θέσης ακριβώς πάνω από την τρέχουσα.

Πρόβλημα

Γράψτε μια διαδικασία με παράμετρο έναν τετραγωνικό πίνακα και έναν ακέραιο που εκφράζει τις διαστάσεις του πίνακα, η οποία κατασκευάζει το τρίγωνο Πασκάλ στον πίνακα της παραμέτρου. Θεωρείστε ότι κατά την κλήση της διαδικασίας η παράμετρος που εκφράζει τις διαστάσεις του πίνακα δεν ξεπερνάει το 500. Κάντε τον απαραίτητο μετασχηματισμό στον παραπάνω αλγόριθμο, λαμβάνοντας υπόψη ότι η πρώτη γραμμή και η πρώτη στήλη ενός πίνακα στην Γλώσσα του μαθήματος ΑΕΠΠ δεν είναι η 0, αλλά η 1.

Λύση

pascalt

Η απόδειξη ορθότητας παραλείπεται ως άσκηση

Ασκήσεις για εμβάθυνση

1)

Σημείωση:

Στην παρακάτω διατύπωση του προβλήματος για όλες τις αναφερόμενες θέσεις πίνακα (κ,λ) θεωρείται ως πρώτη γραμμή και πρώτη στήλη η 0. Κάντε την απαραίτητη μετατροπή για τις θέσεις του πίνακα στην Γλώσσα (όπου πρώτη γραμμή και πρώτη στήλη είναι πάντα η 1).

Θεωρείστε ένα “στιγμιότυπο” του προβλήματος Ζευγάρια με πλήθος μαθητών τάξης 20. Γράψτε ένα πρόγραμμα που εμφανίζει στην οθόνη την λύση του προβλήματος καλώντας την συνάρτηση pairs και αμέσως μετά κατασκευάζει ένα τρίγωνο Πασκάλ 21 γραμμών και εμφανίζει στην οθόνη την τιμή στην θέση (20, 2) του πίνακα του τριγώνου Πασκάλ. Εκτελέστε το πρόγραμμα στον διερμηνευτή. Τι παρατηρείτε; Σκεπτόμενοι επαγωγικά, ποια σημασία εικάζετε ότι έχει η τιμή του πίνακα, για παράδειγμα στις θέσεις (20,3), (19,4), (15,0);

2)

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

η πρώτη θέση της διάταξης είναι στην πρώτη στήλη και στην γραμμή που υποδεικνύει η δεύτερη παράμετρος (θεωρείστε σ’ αυτήν την περίπτωση ότι η πρώτη γραμμή του τριγώνου είναι η 1 και κατά την κλήση της συνάρτησης το όρισμα που αντιστοιχεί στην δεύτερη παράμετρο είναι πάντα μεγαλύτερο ή ίσο του 1). Η δεύτερη θέση είναι η πάνω δεξιά της πρώτης, η τρίτη είναι η πάνω δεξιά της δεύτερης κοκ μέχρι την θέση όπου η τιμή της είναι 0 ή η επόμενή της υπερβαίνει τα όρια του πίνακα.

Γράψτε ένα πρόγραμμα το οποίο εμφανίζει τις τιμές που επιστρέφει η προηγούμενη συνάρτηση με όρισμα που αντιστοιχεί στην δεύτερη παράμετρο διαδοχικά 1, 2, 3, … ,20. Στην συνέχεια εμφανίζει τις τιμές που επιστρέφει η συνάρτηση F(ν) (ακολουθία Fibonacci) με όρισμα διαδοχικά 1, 2, 3, … ,20. Τι παρατηρείτε;

3)

Στην γραμμή 2 (θεωρώντας εδώ ως πρώτη γραμμή την 0) του τριγώνου Πασκάλ υπάρχουν τρεις τιμές, οι 1, 2 και 1. Θεωρώντας την γνωστή ταυτότητα (α+β)2 = α2+2αβ+β2 = 1α2+2αβ+1β2, σκεπτόμενοι επαγωγικά ποια σημασία εικάζετε ότι έχει η ακολουθία τιμών κάθε γραμμής στο τρίγωνο Πασκάλ;

Σχετικοί σύνδεσμοι

https://en.wikipedia.org/wiki/Inductive_reasoning

https://en.wikipedia.org/wiki/Deductive_reasoning

https://en.wikipedia.org/wiki/Pascal%27s_triangle

http://mathworld.wolfram.com/PascalsTriangle.html

https://en.wikipedia.org/wiki/Omar_Khayyam

https://en.wikipedia.org/wiki/Yang_Hui

https://en.wikipedia.org/wiki/Blaise_Pascal

Βίντεο

ν παραγοντικό (ν!)

Πρόβλημα

Το ν! παραγοντικό ορίζεται για κάθε φυσικό αριθμό ν ως εξής:

για ν=0: 0! = 1

για ν>0: ν! = 1⋅2⋅3⋅ …⋅ν

Γράψτε μια συνάρτηση με μία ακέραια παράμετρο η οποία επιστρέφει το παραγοντικό που υποδεικνύει η παράμετρος. Για παράδειγμα με όρισμα 0 η συνάρτηση πρέπει να επιστρέφει 0!= 1 ενώ με όρισμα 3 πρέπει να επιστρέφει 3! = 1⋅2⋅3 = 6.

Λύση

parag1

Απόδειξη ορθότητας

Για n=0 η συνάρτηση εκχωρεί στην μεταβλητή π την τιμή 1, ενώ η δομή επανάληψης δεν εκτελεί καμία επανάληψη, αφού η συνθήκη 1<=0 είναι ψευδής (βλ. Ακριβής). Επομένως, τελικά επιστρέφει 1, το οποίο είναι σωστό με βάση τον ορισμό του παραγοντικού.

Για ν>1 είναι εύκολο να δούμε ότι ν! = 1⋅2⋅3⋅ …⋅(ν-1) ⋅ν = (1⋅2⋅3⋅ …⋅(ν-1) )⋅ν = (ν-1)! ⋅ ν, το τελευταίο ισχύει και για ν=1 αφού 0!=1, δηλαδή το παραγοντικό ενός θετικού αριθμού είναι το παραγοντικό του προηγούμενου αριθμού επί τον αριθμό. Αυτή είναι και η λειτουργία της δομής επανάληψης στην παραπάνω συνάρτηση.

Άσκηση για εμβάθυνση

Το πρωτοντικό (primorial), το οποίο συμβολίζουμε με pn#, όπου n θετικός ακέραιος, ορίζεται ως εξής:

pn# = p1⋅ p2⋅ … ⋅pn, όπου, p1 , ο πρώτος “πρώτος” αριθμός (βλ. Πρώτοι αριθμοί), δηλαδή ο 2, p2 ο δεύτερος πρώτος αριθμός, δηλαδή ο 3, p3 ο τρίτος πρώτος αριθμός, δηλαδή ο 5 κοκ. Γράψτε μια συνάρτηση με μία ακέραια παράμετρο που επιστρέφει το πρωτοντικό που υποδεικνύει η παράμετρος.

Ακριβής λειτουργία της δομής επανάληψης ΓΙΑ…ΑΠΟ…ΜΕΧΡΙ…ΜΕ_ΒΗΜΑ

Τελευταία ενημέρωση 22/9/2016

Θεωρούμε τις ακέραιες* μεταβλητές ι, α, β, γ με τον περιορισμό γ≠0 και την γενική μορφή αυτής της δομής επανάληψης:

(*Σημείωση: Οι μεταβλητές ι, α, β και γ μπορεί να είναι και πραγματικές. Η γενική λογική παραμένει η ίδια με την διαφορά ότι ο τύπος α + (Α_Τ(α – β)  DIV  Α_Τ(γ) + 1) * γ ο οποίος παρουσιάζεται παρακάτω δεν ισχύει σ’ αυτήν την περίπτωση)

ΓΙΑ  ι  ΑΠΟ  α  ΜΕΧΡΙ  β  ΜΕ_ΒΗΜΑ  γ

ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Η ακριβής λειτουργία αυτής της δομής επανάληψης είναι η εξής (με την αυστηρή σειρά βημάτων που υποδεικνύει ο παρακάτω αλγόριθμος):

1) Εκχώρησε στην μεταβλητή ι την τιμή της α.

2)

α) Εάν η μεταβλητή γ (βήμα) είναι θετική

Εάν η λογική συνθήκη ι <= β (η ι είναι μικρότερη ή ίση της β) είναι αληθής, τότε εκτέλεσε το σώμα του βρόγχου, αλλιώς τερμάτισε την δομή επανάληψης (οπότε το πρόγραμμα συνεχίζεται με τις εντολές που βρίσκονται ακριβώς μετά την εντολή “ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ”)

β) Εάν η μεταβλητή γ (βήμα) είναι αρνητική

Εάν η λογική συνθήκη ι >= β (η ι είναι μεγαλύτερη ή ίση της β) είναι αληθής, εκτέλεσε το σώμα του βρόγχου, αλλιώς τερμάτισε την δομή επανάληψης (οπότε το πρόγραμμα συνεχίζεται με τις εντολές που βρίσκονται ακριβώς μετά την εντολή “ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ”).

3) Εκχώρησε στην τιμή του ι την τρέχουσα τιμή του ι συν την τιμή του βήματος:

ι  <-  ι + γ

(Αν το γ (βήμα) είναι αρνητικό, πχ -4, έχουμε ι  <-  ι + (-4), ή ισοδύναμα    ι  <-  ι – 4 )

4) Πήγαινε στο βήμα 2).

Σημείωση 1:

Για την δομή επανάληψης ΓΙΑ…ΑΠΟ…ΜΕΧΡΙ…ΜΕ_ΒΗΜΑ είναι δυνατό να μην εκτελεστεί καμία (!) επανάληψη, εάν η λογική συνθήκη που ελέγχεται είναι ψευδής χωρίς να έχει εκτελεστεί προηγούμενα καμία επανάληψη. Αυτό γενικά είναι “νόμιμο” και μάλιστα χρήσιμο σε πολλές περιπτώσεις τόσο στην Γλώσσα όσο και σε πραγματικές γλώσσες προγραμματισμού.

Σημείωση 2:

Ακριβώς μετά τον τερματισμό της δομής επανάληψης η μεταβλητή ι έχει τιμή:

α) Εάν δεν έχει εκτελεστεί καμία επανάληψη (δηλαδή αν ι =α )

Ίση με το α

Σημείωση:

Μετά το τέλος της  δομής επανάληψης ΓΙΑ…ΑΠΟ…ΜΕΧΡΙ…ΜΕ_ΒΗΜΑ δεν έχει εκτελεστεί καμία επανάληψη αν και μόνο αν η λογική συνθήκη ι=α είναι αληθής.

β) Εάν έχει εκτελεστεί τουλάχιστον μία επανάληψη (δηλαδή αν ι <> α)

Ίση με  α + (Α_Τ(α – β)  DIV  Α_Τ(γ) + 1) * γ

(όπου Α_Τ η ενσωματωμένη συνάρτηση που επιστρέφει την απόλυτη τιμή της παραμέτρου)

Σημείωση:

Μετά το τέλος της  δομής επανάληψης ΓΙΑ…ΑΠΟ…ΜΕΧΡΙ…ΜΕ_ΒΗΜΑ έχει εκτελεστεί τουλάχιστον μία επανάληψη αν και μόνο αν η λογική συνθήκη ι<>α είναι αληθής.

Παραδείγματα

A)

ΓΙΑ ι ΑΠΟ 5 ΜΕΧΡΙ 3
ΓΡΑΨΕ ι
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Έχουμε δηλαδή:

α = 5
β = 3
γ = 1

Με την εφαρμογή του παραπάνω αλγορίθμου έχουμε:

1) Η μεταβλητή ι παίρνει την τιμή 5

2) Ελέγχεται η συνθήκη 5 <= 3 η οποία είναι ψευδής και η δομή επανάληψης τερματίζει.

Βλέπουμε δηλαδή ότι δεν εκτελείται καμία επανάληψη.

Κατά την συνέχεια του προγράμματος η μεταβλητή ι θα έχει τιμή σύμφωνα με τα παραπάνω:
ίση με α, δηλαδή 5

Β)

ΓΙΑ ι ΑΠΟ 5 ΜΕΧΡΙ 15 ΜΕ_ΒΗΜΑ 5
ΓΡΑΨΕ ι
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Έχουμε δηλαδή:

α = 5
β = 15
γ = 5

Με την εφαρμογή του παραπάνω αλγορίθμου έχουμε:

1) Η μεταβλητή ι παίρνει την τιμή 5

2) Ελέγχεται η συνθήκη 5 <= 15 η οποία είναι Αληθής, άρα εκτελείται το σώμα του βρόγχου:

Εμφανίζεται στην οθόνη η τιμή του ι, δηλαδή 5.

3) Η τιμή του ι αυξάνεται κατά 5, δηλαδή γίνεται 10.

4) Ελέγχεται η συνθήκη 10 <= 15 η οποία είναι Αληθής, άρα εκτελείται το σώμα του βρόγχου:

Εμφανίζεται στην οθόνη η τιμή του ι, δηλαδή 10.

5) Η τιμή του ι αυξάνεται κατά 5, δηλαδή γίνεται 15.

6) Ελέγχεται η συνθήκη 15 <= 15 η οποία είναι Αληθής, άρα εκτελείται το σώμα του βρόγχου:

Εμφανίζεται στην οθόνη η τιμή του ι, δηλαδή 15.
.
7) Η τιμή του ι αυξάνεται κατά 5, δηλαδή γίνεται 20.

8) Ελέγχεται η συνθήκη 20 <= 15 η οποία είναι Ψευδής, άρα η δομή επανάληψης τερματίζει.

Άρα, κατά την συνέχεια του προγράμματος η μεταβλητή ι θα έχει τιμή 20, αυτό όμως μπορεί να υπολογιστεί σύμφωνα με τον παραπάνω τύπο και χωρίς την προηγούμενη προσομοίωση εκτέλεσης του αλγορίθμου:

5 + (Α_Τ(5 – 15)  DIV  Α_Τ(5) + 1) * 5 = 5 + (Α_Τ(-10)  DIV  Α_Τ(5) + 1) * 5 =
5 + (10 DIV  5 + 1) * 5 = 5 + (2 + 1) * 5 = 5 + (2 + 1) * 5 = 5+3*15  = 5+15 = 20

Γ)

ΓΙΑ ι ΑΠΟ -5 ΜΕΧΡΙ -2 ΜΕ_ΒΗΜΑ -1
ΓΡΑΨΕ ι
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Έχουμε δηλαδή:

α = -5
β = -2
γ = -1

Με την εφαρμογή του παραπάνω αλγορίθμου έχουμε:

1) Η μεταβλητή ι παίρνει την τιμή -5

2) Ελέγχεται η συνθήκη -5 >= -2 η οποία είναι ψευδής και η δομή επανάληψης τερματίζει.

Βλέπουμε δηλαδή ότι δεν εκτελείται καμία επανάληψη.

Κατά την συνέχεια του προγράμματος η μεταβλητή ι θα έχει τιμή σύμφωνα με τα παραπάνω:
ίση με α, δηλαδή -5

Δ)

ΓΙΑ ι ΑΠΟ -5 ΜΕΧΡΙ -8 ΜΕ_ΒΗΜΑ -2
ΓΡΑΨΕ ι
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Έχουμε δηλαδή:

α = -5
β =  -8
γ = -2

Με την εφαρμογή του παραπάνω αλγορίθμου έχουμε:

1) Η μεταβλητή ι παίρνει την τιμή -5

2) Ελέγχεται η συνθήκη -5 >= -8 η οποία είναι Αληθής, άρα εκτελείται το σώμα του βρόγχου:

Εμφανίζεται στην οθόνη η τιμή του ι, δηλαδή -5.

3) Η τιμή του ι μειώνεται κατά 2, δηλαδή γίνεται -7.

4) Ελέγχεται η συνθήκη -7 >= -8 η οποία είναι Αληθής, άρα εκτελείται το σώμα του βρόγχου:

Εμφανίζεται στην οθόνη η τιμή του ι, δηλαδή -7.

5) Η τιμή του ι μειώνεται κατά -2, δηλαδή γίνεται -9.

6) Ελέγχεται η συνθήκη -9 >= -8 η οποία είναι Ψευδής, άρα η δομή επανάληψης τερματίζει.

Άρα, κατά την συνέχεια του προγράμματος η μεταβλητή ι θα έχει τιμή -9, αυτό όμως μπορεί να υπολογιστεί σύμφωνα με τον παραπάνω τύπο και χωρίς την προηγούμενη προσομοίωση εκτέλεσης του αλγορίθμου:

-5 + (Α_Τ(-5 – (-8))  DIV  Α_Τ(-2) + 1) * (-2) = -5 + (Α_Τ(-5 + 8)  DIV  Α_Τ(-2) + 1)* (-2)=
-5 + (Α_Τ(3)  DIV  Α_Τ(-2) + 1) * (-2) = -5 + (3  DIV 2 + 1) * (-2) = -5 + (1 + 1) * (-2) =
-5 + 2 * (-2) = -5-4 = -9

Ιστορικό σημείωμα

Μια πρώιμη μορφή της δομής επανάληψης ΓΙΑ…ΑΠΟ…ΜΕΧΡΙ…ΜΕ_ΒΗΜΑ εμφανίστηκε στον χώρο των μαθηματικών το 1931 με την ονομασία «πρωτόγονη αναδρομική συνάρτηση» κατά την δημοσίευση των αποδείξεων των θεωρημάτων μη-πληρότητας του Κουρτ Γκέντελ. Οι πρωτόγονες αναδρομικές συναρτήσεις είχαν προταθεί 8 χρόνια νωρίτερα από τον Σκόλεμ.

Ζευγάρια

Πρόβλημα

Ένας καθηγητής γυμναστικής ζητάει δύο εθελ-οντές/όντριες από την σχολική τάξη προκειμένου να παρουσιάσει μία άσκηση γυμναστικής για δύο άτομα. Γράψτε μία συνάρτηση με μια ακέραια παράμετρο η οποία αντιστοιχεί στο πλήθος των μαθητών της τάξης, η οποία επιστρέφει το πλήθος όλων των δυνατών επιλογών δύο ατόμων. Για παράδειγμα αν η τάξη έχει 3 άτομα με σύνολο ονομάτων {Μαρία, Νίκος, Ελένη} οι δυνατές επιλογές είναι 3: {Μαρία, Νίκος}, {Μαρία, Ελένη} και {Νίκος, Ελένη}.

Λύση

l1

Απόδειξη ορθότητας

Προκειμένου να βρούμε όλα τα δυνατά ζευγάρια ν διακεκριμένων στοιχείων χωρίς να μας ενδιαφέρει η διάταξη των ζευγαριών, δηλαδή τα υποσύνολα με πλήθος στοιχείων 2 των ν διακεκριμένων στοιχείων, μπορούμε να διατρέξουμε το σύνολο των στοιχείων συνδυάζοντας κάθε στοιχείο με όλα τα υπόλοιπα. Μ’ αυτό τον τρόπο σίγουρα δεν παραλείπουμε κάποιο υποσύνολο, όμως κάποια υποσύνολα θα συμπεριληφθούν περισσότερες από μία φορές. Ας εφαρμόσουμε αυτή τη μέθοδο στο παράδειγμα της διατύπωσης του προβλήματος:

1) Συνδυάζουμε την Μαρία με τα υπόλοιπα άτομα:

{Μαρία, Νίκος}, {Μαρία, Ελένη}

2) Συνδυάζουμε τον Νίκο με τα υπόλοιπα άτομα:

{Νίκος, Μαρία}, {Νίκος, Ελένη}

3) Συνδυάζουμε την Ελένη με τα υπόλοιπα άτομα:

{Ελένη, Μαρία}, {Ελένη, Νίκος}

Παρατηρούμε ότι μ’ αυτόν τον τρόπο κάθε ζευγάρι αναφέρεται δύο φορές. Ας δούμε πως μπορούμε να αποφύγουμε τα “διπλότυπα” στην γενική περίπτωση ν στοιχείων:

Τοποθετούμε τα ν στοιχεία σε μια σειρά και διατρέχουμε τα στοιχεία δημιουργώντας ζεύγη με το πρώτο στοιχείο από αριστερά και καθένα από τα στοιχεία που βρίσκονται δεξιότερα από αυτό, το δεύτερο στοιχείο από αριστερά και καθένα από τα στοιχεία που βρίσκονται δεξιότερα από αυτό, το τρίτο στοιχείο και καθένα από τα στοιχεία που βρίσκονται δεξιότερα από αυτό…μέχρι να φτάσουμε στο τελευταίο στοιχείο, όπου δεν υπάρχει κανένα στοιχείο δεξιότερα από αυτό. Με τον τρόπο αυτό (συνδυάζοντας το τρέχον στοιχείο μόνο με τα στοιχεία που βρίσκονται δεξιότερα από αυτό, αφού ο συνδυασμός με τα στοιχεία που βρίσκονται προς τα αριστερά έχει γίνει προηγούμενα κατά τον συνδυασμό αυτών των στοιχείων με τα στοιχεία που βρίσκονται δεξιότερά τους, ενώ ο συνδυασμός με τα δεξιότερα στοιχεία δεν έχει συμπεριληφθεί, αφού μόνο τα στοιχεία στα αριστερά του τρέχοντος έχουν συνδυαστεί με τα τελευταία!) αποφεύγουμε να μετρήσουμε το ίδιο ζευγάρι περισσότερες από μία φορές, αλλά και να παραλείψουμε κάποιο ζευγάρι (αφού η διαφορά της δεύτερης μεθόδου από την πρώτη είναι ότι παραλείπονται μόνο τα στοιχεία που έχουν ήδη συμπεριληφθεί). Αυτήν ακριβώς την λειτουργία προσομοιώνει και το παραπάνω πρόγραμμα.

Εναλλακτική λύση 1

en1

Απόδειξη ορθότητας

Στο πρόγραμμα της αρχικής λύσης παρατηρούμε ότι για κάθε επανάληψη του εξωτερικού βρόγχου ο εμφωλευμένος βρόγχος προσθέτει στην μεταβλητή “πλήθος” την ποσότητα ν – (ι+1) + 1 = ν – ι (αφού ο τελευταίος βρόγχος εκτελείται για κ από ι+1 ως ν). Το ι όμως παίρνει τιμές από 1 ως ν, οπότε στην πρώτη επανάληψη του εξωτερικού βρόγχου αυξάνεται η τιμής της “πλήθος” κατά ν-1, στην δεύτερη κατά ν-2, στην τρίτη κατά ν-3 κοκ. Αυτή όμως είναι και η λειτουργία του παραπάνω προγράμματος.

Εναλλακτική λύση 2

ΣΥΝΑΡΤΗΣΗ count_2combination3(ν): ΑΚΕΡΑΙΑ
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: ν
ΑΡΧΗ
count_2combination3 <- (ν*ν – ν) DIV 2
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

Η απόδειξη ορθότητας αφήνεται ως άσκηση.

Άσκηση για εμβάθυνση

Υποθέστε ότι ο καθηγητής γυμναστικής ζητάει τρεις εθελ-οντές/όντριες. Πόσες είναι οι δυνατές επιλογές;

Υπόδειξη:

Στον εμφωλευμένο βρόγχο της βασικής λύσης εμφωλεύστε έναν ακόμα βρόγχο…

Πρώτοι αριθμοί

Τελευταία ενημέρωση: 4/10/2016, 21:44

Πρόβλημα 1

Ένας φυσικός αριθμός είναι πρώτος αν και μόνο αν το σύνολο των διαιρετών του έχει πλήθος στοιχείων ίσο με 2.

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

Λύση

pr

Απόδειξη ορθότητας

Με βάση τον ορισμό του πρώτου αριθμού που δίνεται στην διατύπωση του προβλήματος το 0 και το 1 δεν είναι πρώτοι αριθμοί, γιατί το πλήθος των διαιρετών του 0 ({1,2,3,4,…}) είναι άπειρο, ενώ το πλήθος των διαιρετών του 1 ({1}) είναι 1. Κάθε φυσικός αριθμός μεγαλύτερος του 1 έχει σύνολο διαιρετών με πλήθος τουλάχιστον 2. Πράγματι, κάθε φυσικός αριθμός μεγαλύτερος του 1 διαιρείται με τον εαυτό του και το 1. Επομένως, για να είναι πρώτος ένας φυσικός αριθμός μεγαλύτερος του 1 θα πρέπει να μην έχει κανένα άλλο διαιρέτη εκτός από αυτούς που προαναφέραμε. Με βάση τα προηγούμενα η απόδειξη ορθότητας του αλγορίθμου είναι άμεση.

Σχόλια

-Ελέγχουμε αν ο φυσικός αριθμός k διαιρείται με τον φυσικό αριθμό m χρησιμοποιώντας τον τελεστή MOD: αν k MOD m = 0, ο m είναι διαιρέτης του k και αντίστροφα (αυτός είναι και ο τυπικός μαθηματικός ορισμός).

-Στο παραπάνω πρόγραμμα η επαναληπτική δομή ΓΙΑ δεν εκτελείται για κ = 2, αφού η αρχική τιμή που θα πάρει η μεταβλητή-μετρητής ι είναι 2-1 = 1: ο έλεγχος της συνθήκης 1 >= 2 (η οποία είναι ψευδής) που ακολουθεί (ο τελεστής >= είναι λόγω του αρνητικού βήματος) δεν επιτρέπει την εκτέλεση καμιάς επανάληψης.

Πρόβλημα 2
Ένας φυσικός αριθμός μεγαλύτερος του 1 ο οποίος δεν είναι πρώτος λέγεται “σύνθετος”.

Λύστε το πρόβλημα 1 χρησιμοποιώντας τα παρακάτω δύο θεωρήματα:

1) Ένας φυσικός αριθμός μεγαλύτερος του 1 ο οποίος είναι σύνθετος γράφεται ως γινόμενο πρώτων παραγόντων, με πλήθος παραγόντων τουλάχιστον 2 – και μάλιστα κατά μοναδικό τρόπο, αν θεωρήσουμε ότι τα γινόμενα που προκύπτουν με την εφαρμογή της αντιμεταθετικής ιδιότητας του πολλαπλασιασμού δεν συνιστούν διαφορετικό γινόμενο. Για παράδειγμα ο αριθμός 4 γράφεται μοναδικά ως γινόμενο πρώτων παραγόντων ως 2⋅2. Το θεώρημα είναι γνωστό και ως “θεμελιώδες θεώρημα της αριθμητικής” *.

2) Εάν ένας αριθμός είναι πρώτος μεγαλύτερος του 3, τότε ο επόμενος ή ο προηγούμενος είναι πολλαπλάσιο του 6” (το αντίστροφο δεν ισχύει).

Λύση

pr2

Απόδειξη ορθότητας

Ένας πρώτος αριθμός σίγουρα δεν γράφεται ως γινόμενο με τουλάχιστον δύο πρώτους παράγοντες, αφού οι μόνοι του διαιρέτες είναι το 1 και ο εαυτός του: γράφεται μόνο ως γινόμενο του εαυτού του με το 1, και το 1 δεν είναι πρώτος αριθμός. Από το δεύτερο θεώρημα συνεπάγεται ότι μπορούμε να αναζητήσουμε τους πρώτους αριθμούς που είναι μεγαλύτεροι του 3 δίπλα (πριν ή μετά) από τα πολλαπλάσια του 6. Από το ίδιο θεώρημα συνεπάγεται επίσης (μέσω αντιθετοαντιστροφής) ότι “αν για έναν αριθμό μεγαλύτερο του 3 ισχύει ότι ούτε ο προηγούμενος ούτε ο επόμενος είναι πολλαπλάσιο του 6, τότε ο αριθμός είναι σύνθετος”. Από το πρώτο θεώρημα και τον ορισμό του πρώτου και του σύνθετου αριθμού συνεπάγεται ότι προκειμένου να αποδείξουμε ότι ένας αριθμός μεγαλύτερος του 1 είναι πρώτος αρκεί να εξετάσουμε αν υπάρχει πρώτος διαιρέτης του, ο οποίος βέβαια πρέπει να είναι διαφορετικός από τον ίδιο τον αριθμό (αν υπάρχει ο αριθμός δεν είναι πρώτος, αλλιώς είναι). Από τα παραπάνω συνεπάγεται άμεσα η ορθότητα του προγράμματος.

Σχόλια

Ο τελεστής MOD έχει την ίδια προτεραιότητα με τον τελεστή του πολλαπλασιασμού (*) και της διαίρεσης (/), η οποία είναι μεγαλύτερη από αυτή του τελεστή πρόσθεσης (+) και αφαίρεσης (-). Οπότε, για παράδειγμα, αν θέλουμε να ελέγξουμε αν ένας αριθμός κ δεν διαιρείται με τον προηγούμενο ενός αριθμού ι, χρησιμοποιούμε την συνθήκη κ MOD (ι-1) <> 0, περικλείοντας με παρενθέσεις το “ι-1”. Σε διαφορετική περίπτωση θα εκτελεστεί (κ MOD ι) – 1 , το οποίο είναι διαφορετικό.

Άσκηση για εμβάθυνση

Λύστε το πρόβλημα 1 χρησιμοποιώντας επιπλέον το παρακάτω θεώρημα:

Εάν ένας αριθμός είναι σύνθετος, τότε υπάρχει ένας πρώτος διαιρέτης του ο οποίος είναι μικρότερος ή ίσος από την τετραγωνική ρίζα του αριθμού (η τετραγωνική ρίζα ενός φυσικού αριθμού είναι γενικά πραγματικός αριθμός).

*Πάραυτα δεν διδάσκεται στην πρωτοβάθμια, ούτε στην δευτεροβάθμια εκπαίδευση