Χωρίς “Aν”

Μ’ αυτήν την δημοσίευση θα εγκαινιάσω την κατηγορία “Ασκήσεις ΑΕΠΠ”.

Πρόβλημα:

Χωρίς να χρησιμοποιήσετε τις δομές επιλογής “Αν…Τότε…” και “Επίλεξε…Περίπτωση…”, γράψτε ένα πρόγραμμα το οποίο δέχεται ως είσοδο από το πληκτρολόγιο έναν φυσικό αριθμό (χωρίς έλεγχο εγκυρότητας) και εάν ο αριθμός αυτός είναι άρτιος εμφανίζει στην οθόνη “Άρτιος”, ενώ αν είναι περιττός εμφανίζει “Περιττός”.

Λύση:

ΠΡΟΓΡΑΜΜΑ ΧΩΡΙΣ_ΑΝ_1
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: κ
ΧΑΡΑΚΤΗΡΕΣ: Α[2]
ΑΡΧΗ
Α[1] <- «Άρτιος»
Α[2] <- «Περιττός»
ΓΡΑΨΕ «Δώσε έναν φυσικό αριθμό.»
ΔΙΑΒΑΣΕ κ
ΓΡΑΨΕ Α[κ MOD 2 + 1]
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Σχολιασμός, απόδειξη ορθότητας και ιστορική παρακίνηση

Δηλώνουμε έναν πίνακα χαρακτήρων 2 θέσεων και τον ακέραιο κ. Στην θέση 1 του πίνακα εκχωρούμε την τιμή «Άρτιος» ενώ στην θέση 2 την τιμή «Περιττός». Τότε, η απάντηση του προβλήματος δίνεται από την τιμή Α[κ MOD 2 + 1] , δηλαδή από το “αλφαριθμητικό”* που βρίσκεται στην θέση κ MOD 2 + 1 του πίνακα Α.

Για να αποδείξουμε την ορθότητα του προγράμματος θα πρέπει να αποδείξουμε δύο πράγματα:

1) Αν ο κ είναι άρτιος, τότε το πρόγραμμα εμφανίζει “Άρτιος”.

2) Αν ο κ είναι περιττός, τότε το πρόγραμμα εμφανίζει “Περιττός”.

Απόδειξη:

Αν ο κ είναι άρτιος, τότε κ MOD 2 = 0, άρα κ MOD 2 + 1 = 1. Άρα, το πρόγραμμα θα εμφανίσει το Α[1], το οποίο είναι “Άρτιος”

Αν ο κ είναι περιττός, τότε κ Mod 2 = 1, άρα κ MOD 2 + 1 = 2. Άρα, το πρόγραμμα θα εμφανίσει το Α[2], το οποίο είναι “Περιττός”.

Το 1931 ο μαθηματικός Κουρτ Γκέντελ δημοσίευσε την απόδειξη των περίφημων θεωρημάτων “μη-πληρότητας”. Στην απόδειξη χρησιμοποίησε μία κλάση συναρτήσεων γνωστών ως “μ-Αναδρομικές” (“μ-Recursive”). Αργότερα, αποδείχτηκε ότι οι “μ-Αναδρομικές” συναρτήσεις μπορούν να υπολογίσουν ό,τι υπολογίζει και ένα πρόγραμμα μιας μοντέρνας γλώσσας προγραμματισμού. Ένα υποσύνολο των μ-Αναδρομικών συναρτήσεων είναι οι “πρωτόγονες αναδρομικές” (“primitive recursive”), οι οποίες κατασκευάζονται με ειδική χρήση κάποιων άλλων συναρτήσεων, οι οποίες είναι γνωστές ως “βασικές”. Μια από τις τελευταίες είναι και η “προβολική” συνάρτηση. Η συνάρτηση αυτή, έστω P, ορίζεται ως εξής:

P(n1, n2, … , nk, i) = ni

Η σημασία της είναι η εξής: δοσμένων k (>0) φυσικών αριθμών n1, n2, … , nk και ενός φυσικού αριθμού i τέτοιου ώστε 0 < i ≤ k, η συνάρτηση ουσιαστικά επιλέγει τον αριθμό ni. Η επιλογή στον σύγχρονο προγραμματισμό γίνεται με τις δομές επιλογής “Αν…Τότε…” και “Επίλεξε…Περίπτωση…” ή (λιγότερο συχνά) με την χρήση ενός πίνακα: Η εντολή A[i] ενός πίνακα k θέσεων, όπου 0 < i ≤ k, επιλέγει το στοιχείο του πίνακα που βρίσκεται στην θέση i – και αποτελεί ουσιαστικά μια μορφή “προβολικής” συνάρτησης ή μια μορφή δομής επιλογής (η οποία δεν αναφέρεται συνήθως ως τέτοια).

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

Χωρίς να χρησιμοποιήσετε τις δομές επιλογής “Αν…Τότε…” και “Επίλεξε…Περίπτωση…”, γράψτε ένα πρόγραμμα το οποίο δέχεται ως είσοδο από το πληκτρολόγιο έναν φυσικό αριθμό (χωρίς έλεγχο εγκυρότητας) και εάν ο αριθμός αυτός είναι μεγαλύτερος από το 5 εμφανίζει στην οθόνη “Μεγαλύτερος του 5”, αν είναι μικρότερος του 5 εμφανίζει “Μικρότερος του 5” και εάν είναι ίσος με 5 εμφανίζει “Ίσος με 5”.

*Θεωρώ ότι αυτό που εννοείται με τον όρο “αλφαριθμητικό” του σχολικού βιβλίου είναι αυτό που συνήθως (και πιο σωστά) λέμε “συμβολοσειρά” (“string” είναι ο διεθνής όρος). Συνήθως, ως “αλφαριθμητικό” (“alphanumeric”) αναφέρεται διεθνώς μια ακολουθία από αλφαβητικά σύμβολα και αριθμητικά ψηφία. Η “συμβολοσειρά” είναι κάτι ευρύτερο, μπορεί να περιλαμβάνει όλα τα σύμβολα του πληκτρολογίου (και όλα τα σύμβολα γενικότερα).