Είδη αλγορίθμων - Υπερμάρκετ Γνώσης. Β6

Λέξεις-κλειδιά:

αλγόριθμος
ιδιότητες του αλγορίθμου
- διακριτικότητα
- σαφήνεια
- βεβαιότητα
- αποτελεσματικότητα
- μαζικός χαρακτήρας
εκτελεστής διαθήκης

χαρακτηριστικά ερμηνευτή
- σειρά εργασιών προς επίλυση
- Τετάρτη
- τρόπο λειτουργίας
- σύστημα εντολών
επίσημη εκτέλεση του αλγορίθμου

3.1.1. Έννοια αλγορίθμου

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

Παράδειγμα 1. Το πρόβλημα «Βρείτε τον αριθμητικό μέσο όρο δύο αριθμών» λύνεται σε τρία βήματα:

σκεφτείτε δύο αριθμούς.
Προσθέστε δύο αριθμούς στο μυαλό.
διαιρέστε το ποσό που προκύπτει με το 2.

Παράδειγμα 2. Η εργασία "Κατάθεση χρημάτων στον λογαριασμό του τηλεφώνου σας" χωρίζεται στα ακόλουθα βήματα:

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

Παράδειγμα 3. Τα στάδια επίλυσης του προβλήματος "Σχεδιάστε έναν αστείο σκαντζόχοιρο" παρουσιάζονται γραφικά:

Η εύρεση του αριθμητικού μέσου όρου, η κατάθεση χρημάτων σε έναν τηλεφωνικό λογαριασμό και η σχεδίαση ενός σκαντζόχοιρου είναι, με την πρώτη ματιά, εντελώς διαφορετικές διαδικασίες. Αλλά έχουν ένα κοινό χαρακτηριστικό: καθεμία από αυτές τις διαδικασίες περιγράφεται από μια σειρά σύντομων οδηγιών, η αυστηρή τήρηση των οποίων σας επιτρέπει να επιτύχετε το απαιτούμενο αποτέλεσμα. Οι ακολουθίες εντολών που δίνονται στα παραδείγματα 1-3 είναι αλγόριθμοι για την επίλυση των αντίστοιχων προβλημάτων. Ο εκτελεστής αυτών των αλγορίθμων είναι ένα άτομο.

Ο αλγόριθμος μπορεί να είναι μια περιγραφή μιας συγκεκριμένης ακολουθίας υπολογισμών (παράδειγμα 1) ή βημάτων μη μαθηματικού χαρακτήρα (παραδείγματα 2-3). Σε κάθε περίπτωση όμως, πριν την ανάπτυξή του, πρέπει να καθοριστούν με σαφήνεια οι αρχικές συνθήκες (αρχικά δεδομένα) και το τι πρόκειται να ληφθεί (αποτέλεσμα). Μπορούμε να πούμε ότι ένας αλγόριθμος είναι μια περιγραφή της ακολουθίας των βημάτων στην επίλυση ενός προβλήματος, που οδηγεί από τα αρχικά δεδομένα στο απαιτούμενο αποτέλεσμα.

Γενικά, το διάγραμμα λειτουργίας του αλγορίθμου μπορεί να αναπαρασταθεί ως εξής (Εικ. 3.1):

Ρύζι. 3.1.
Γενικό σχήμα του αλγορίθμου

Οι αλγόριθμοι είναι οι κανόνες πρόσθεσης, αφαίρεσης, πολλαπλασιασμού και διαίρεσης αριθμών, γραμματικοί κανόνες, κανόνες γεωμετρικών κατασκευών κ.λπ., που μελετώνται στο σχολείο.

Τα κινούμενα σχέδια "Εργασία με αλγόριθμο", "Μεγαλύτερος κοινός διαιρέτης", "Λιγότερο κοινό πολλαπλάσιο" (http://school-collection.edu.ru/) θα σας βοηθήσουν να θυμάστε μερικούς αλγόριθμους που μελετήθηκαν στη ρωσική γλώσσα και μαθήματα μαθηματικών.

Παράδειγμα 4. Κάποιος αλγόριθμος οδηγεί στο γεγονός ότι από μια αλυσίδα χαρακτήρων λαμβάνεται μια νέα αλυσίδα ως εξής:

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

Η αλυσίδα που προκύπτει είναι το αποτέλεσμα του αλγορίθμου.

Έτσι, εάν η αρχική αλυσίδα ήταν A#B, τότε το αποτέλεσμα του αλγορίθμου θα είναι η αλυσίδα #A1B2, και εάν η αρχική αλυσίδα ήταν ABC@, τότε το αποτέλεσμα του αλγορίθμου θα είναι η αλυσίδα BA@B2.

3.1.2. Εκτελεστής αλγορίθμου

Κάθε αλγόριθμος έχει σχεδιαστεί για έναν συγκεκριμένο εκτελεστή.

Υπάρχουν επίσημοι και άτυποι ερμηνευτές. Ένας επίσημος εκτελεστής εκτελεί πάντα την ίδια εντολή με τον ίδιο τρόπο. Ένας άτυπος εκτελεστής μπορεί να εκτελέσει μια εντολή με διαφορετικούς τρόπους.

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

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

Καλλιτεχνικό Περιβάλλον. Η περιοχή, η ρύθμιση, οι συνθήκες στις οποίες λειτουργεί ο ερμηνευτής ονομάζονται συνήθως περιβάλλον του συγκεκριμένου ερμηνευτή. Τα δεδομένα πηγής και τα αποτελέσματα οποιουδήποτε αλγορίθμου ανήκουν πάντα στο περιβάλλον του εκτελεστή για τον οποίο προορίζεται ο αλγόριθμος.

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

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

Ας δούμε παραδείγματα ερμηνευτών.

Παράδειγμα 5. Εκτελεστής Η χελώνα κινείται στην οθόνη του υπολογιστή, αφήνοντας ένα ίχνος με τη μορφή μιας γραμμής. Το σύστημα εντολών της χελώνας αποτελείται από δύο εντολές:

Δεξιά m (όπου m είναι ένας ακέραιος αριθμός) - κάνει την κατεύθυνση κίνησης της χελώνας να αλλάξει κατά m μοίρες δεξιόστροφα.

Επανάληψη εγγραφής k [<Команда1> <Команда2> ... <Командаn>] σημαίνει ότι η ακολουθία των εντολών σε αγκύλες θα επαναληφθεί k φορές.

Σκεφτείτε τι σχήμα θα εμφανιστεί στην οθόνη αφού η Χελώνα ολοκληρώσει τον παρακάτω αλγόριθμο.

Επαναλάβετε 12 [Δεξιά 4 5 Εμπρός 20 Δεξιά 45]

Παράδειγμα 6. Το σύστημα εντολών εκτελεστή Ο υπολογιστής αποτελείται από δύο εντολές, στις οποίες εκχωρούνται αριθμοί:

Το πρώτο από αυτά μειώνει τον αριθμό κατά 1, το δεύτερο αυξάνει τον αριθμό κατά 3 φορές. Κατά τη σύνταξη αλγορίθμων, για συντομία, υποδεικνύονται μόνο αριθμοί εντολών. Για παράδειγμα, ο αλγόριθμος 21212 σημαίνει την ακόλουθη σειρά εντολών:

Χρησιμοποιώντας αυτόν τον αλγόριθμο, ο αριθμός 1 θα μετατραπεί σε 15: ((1-3-1)-3-1)-3 = 15.

Παράδειγμα 7. Το Performer Robot λειτουργεί σε ένα καρό πεδίο, ανάμεσα σε γειτονικά κελιά μπορεί να υπάρχουν τοίχοι. Το ρομπότ κινείται κατά μήκος των κελιών του πεδίου και μπορεί να εκτελέσει τις ακόλουθες εντολές, στις οποίες εκχωρούνται αριθμοί:

Κατά την εκτέλεση κάθε τέτοιας εντολής, το ρομπότ μετακινείται σε ένα γειτονικό κελί προς την υποδεικνυόμενη κατεύθυνση. Εάν υπάρχει τοίχος προς αυτή την κατεύθυνση μεταξύ των κελιών, τότε το Ρομπότ καταστρέφεται. Τι θα συμβεί με το ρομπότ εάν εκτελέσει την ακολουθία των εντολών 32323 (εδώ οι αριθμοί υποδεικνύουν αριθμούς εντολών), αρχίζοντας να μετακινείται από το κελί Α; Ποια ακολουθία εντολών πρέπει να εκτελέσει το ρομπότ για να μετακινηθεί από το κελί Α στο κελί Β χωρίς να καταρρεύσει όταν χτυπήσει στους τοίχους;

Κατά την ανάπτυξη ενός αλγορίθμου:

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

Μπορούμε να πούμε ότι ένας αλγόριθμος είναι ένα μοντέλο της δραστηριότητας του εκτελεστή του αλγορίθμου.

3.1.3. Ιδιότητες αλγορίθμου

Δεν μπορεί να θεωρηθεί αλγόριθμος κάθε οδηγία, ακολουθία εντολών ή σχέδιο δράσης. Κάθε αλγόριθμος έχει απαραίτητα τις ακόλουθες ιδιότητες: διακριτικότητα, κατανοητό, βεβαιότητα, αποτελεσματικότητα και μαζικό χαρακτήρα.

Η ιδιότητα της διακριτικότητας σημαίνει ότι η διαδρομή προς την επίλυση ενός προβλήματος χωρίζεται σε ξεχωριστά βήματα (ενέργειες). Κάθε ενέργεια έχει μια αντίστοιχη εντολή (εντολή). Μόνο μετά την εκτέλεση μιας εντολής μπορεί ο εκτελεστής να αρχίσει να εκτελεί την επόμενη εντολή.

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

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

Η ιδιότητα απόδοσης σημαίνει ότι ο αλγόριθμος πρέπει να μπορεί να λάβει ένα αποτέλεσμα μετά από έναν πεπερασμένο, πιθανώς πολύ μεγάλο, αριθμό βημάτων. Στην περίπτωση αυτή, το αποτέλεσμα θεωρείται όχι μόνο η απάντηση που καθορίζεται από τη δήλωση του προβλήματος, αλλά και το συμπέρασμα σχετικά με την αδυναμία συνέχισης της επίλυσης αυτού του προβλήματος για οποιονδήποτε λόγο.

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

Παράδειγμα 8. Ας εξετάσουμε μία από τις μεθόδους για την εύρεση όλων των πρώτων αριθμών που δεν υπερβαίνουν το n. Αυτή η μέθοδος ονομάζεται «κόσκινο του Ερατοσθένη», που πήρε το όνομά της από τον αρχαίο Έλληνα επιστήμονα Ερατοσθένη που την πρότεινε.

Για να βρείτε όλους τους πρώτους αριθμούς όχι μεγαλύτερους από έναν δεδομένο αριθμό n, ακολουθώντας τη μέθοδο του Ερατοσθένη, πρέπει να εκτελέσετε τα ακόλουθα βήματα:

γράψτε όλους τους ακέραιους αριθμούς από το 2 έως το n στη σειρά (2, 3, 4, ..., n);
πλαίσιο 2 - ο πρώτος πρώτος αριθμός.
διαγράψτε από τη λίστα όλους τους αριθμούς που διαιρούνται με τον τελευταίο πρώτο αριθμό που βρέθηκε.
βρείτε τον πρώτο μη επισημασμένο αριθμό (οι σημειωμένοι αριθμοί είναι διαγραμμένοι αριθμοί ή αριθμοί που περικλείονται σε ένα πλαίσιο) και περικλείστε τον σε ένα πλαίσιο - αυτός θα είναι ένας άλλος πρώτος αριθμός.
επαναλάβετε τα βήματα 3 και 4 μέχρι να μην έχουν μείνει αριθμοί χωρίς επισήμανση.

Μπορείτε να πάρετε μια πιο οπτική ιδέα για τη μέθοδο εύρεσης πρώτων αριθμών χρησιμοποιώντας το κινούμενο σχέδιο "Το κόσκινο του Ερατοσθένη" (http://school-collection.edu.ru/).

Η εξεταζόμενη ακολουθία ενεργειών είναι ένας αλγόριθμος, καθώς ικανοποιεί τις ακόλουθες ιδιότητες:

διακριτικότητα - η διαδικασία εύρεσης πρώτων αριθμών χωρίζεται σε βήματα.
Κατανοησιμότητα - κάθε εντολή είναι κατανοητή σε έναν μαθητή της 9ης τάξης που εκτελεί αυτόν τον αλγόριθμο.
βεβαιότητα - κάθε εντολή ερμηνεύεται και εκτελείται από τον εκτελεστή χωρίς αμφιβολία. υπάρχουν οδηγίες για τη σειρά εκτέλεσης των εντολών.
αποτελεσματικότητα - μετά από έναν ορισμένο αριθμό βημάτων επιτυγχάνεται το αποτέλεσμα.
μαζικός χαρακτήρας - η ακολουθία των ενεργειών ισχύει για οποιοδήποτε φυσικό n.

Οι εξεταζόμενες ιδιότητες του αλγορίθμου μας επιτρέπουν να δώσουμε έναν πιο ακριβή ορισμό του αλγορίθμου.

3.1.4. Δυνατότητα αυτοματοποίησης ανθρώπινων δραστηριοτήτων

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

Η επίλυση ενός προβλήματος χρησιμοποιώντας έναν έτοιμο αλγόριθμο απαιτεί μόνο από τον εκτελεστή να ακολουθεί αυστηρά τις οδηγίες που δίνονται.

Παράδειγμα 9. Από ένα σωρό που περιέχει οποιονδήποτε αριθμό αντικειμένων μεγαλύτερο από τρία, δύο παίκτες παίρνουν εναλλάξ ένα ή δύο αντικείμενα ο καθένας. Νικητής είναι αυτός που μπορεί να πάρει όλα τα υπόλοιπα αντικείμενα στην επόμενη κίνησή του.

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

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

Ο ερμηνευτής μπορεί να μην εμβαθύνει στο νόημα αυτού που κάνει και όχι στο λόγο για τον οποίο ενεργεί έτσι και όχι διαφορετικά, δηλαδή μπορεί να ενεργήσει τυπικά. Η ικανότητα του ερμηνευτή να ενεργεί επίσημα παρέχει τη δυνατότητα αυτοματοποίησης της ανθρώπινης δραστηριότητας. Για αυτό:

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

Το πιο σημαντικό

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

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

Η ικανότητα του ερμηνευτή να ενεργεί επίσημα παρέχει τη δυνατότητα αυτοματοποίησης της ανθρώπινης δραστηριότητας.

Ερωτήσεις και εργασίες

Τι ονομάζεται αλγόριθμος;
Βρείτε συνώνυμα για τη λέξη "συνταγή".
Δώστε παραδείγματα αλγορίθμων που μελετήσατε στο σχολείο.
Ποιος μπορεί να είναι ο εκτελεστής του αλγορίθμου;
Δώστε ένα παράδειγμα επίσημου ερμηνευτή. Δώστε ένα παράδειγμα όταν ένα άτομο ενεργεί ως επίσημος ερμηνευτής.
Ποιες εντολές πρέπει να εκτελεί ένα ρομπότ τις λειτουργίες: α) ταμία σε κατάστημα; β) θυρωρός? γ) φύλακας;
Τι καθορίζει το εύρος των εργασιών που εκτελεί ο εκτελεστής του «υπολογιστή»;
Θεωρήστε τον επεξεργαστή κειμένου στον υπολογιστή σας ως τον εκτελεστή. Περιγράψτε το εύρος των εργασιών που επιλύθηκαν από αυτόν τον εκτελεστή και το περιβάλλον του.
Τι είναι μια ομάδα, ένα σύστημα εντολών εκτελεστών;
Καταγράψτε τις κύριες ιδιότητες του αλγορίθμου.
Σε τι μπορεί να οδηγήσει η απουσία οποιασδήποτε ιδιότητας σε έναν αλγόριθμο; Δώσε παραδείγματα.
Γιατί είναι σημαντικό να μπορούμε να εκτελούμε επίσημα έναν αλγόριθμο;
Η ακολουθία των αριθμών κατασκευάζεται σύμφωνα με τον ακόλουθο αλγόριθμο: οι δύο πρώτοι αριθμοί της ακολουθίας λαμβάνονται ίσοι με 1. Κάθε επόμενος αριθμός στην ακολουθία θεωρείται ίσος με το άθροισμα των δύο προηγούμενων αριθμών. Γράψτε τους 10 πρώτους όρους αυτής της ακολουθίας.
Κάποιος αλγόριθμος αποκτά μια νέα αλυσίδα από μια συμβολοσειρά χαρακτήρων ως εξής. Πρώτα, γράφεται η αρχική αλυσίδα χαρακτήρων, μετά από αυτήν γράφεται η αρχική αλυσίδα χαρακτήρων με αντίστροφη σειρά, στη συνέχεια γράφεται το γράμμα που ακολουθεί στο ρωσικό αλφάβητο μετά το γράμμα που βρισκόταν στην τελευταία θέση στην αρχική αλυσίδα. Εάν η τελευταία θέση στην αρχική αλυσίδα είναι το γράμμα Z, τότε το γράμμα A γράφεται ως το επόμενο γράμμα. Η αλυσίδα που προκύπτει είναι το αποτέλεσμα του αλγορίθμου. Για παράδειγμα, εάν η αρχική αλυσίδα χαρακτήρων ήταν DOM, τότε το αποτέλεσμα του αλγορίθμου θα είναι η αλυσίδα DOMMODN. Δίνεται η συμβολοσειρά χαρακτήρων COM. Πόσα γράμματα O θα υπάρχουν στην αλυσίδα των συμβόλων που θα ληφθούν εάν εφαρμόσετε τον αλγόριθμο σε αυτήν την αλυσίδα και στη συνέχεια εφαρμόσετε ξανά τον αλγόριθμο στο αποτέλεσμα της εργασίας της;
Βρείτε μια κινούμενη εικόνα των βημάτων του αλγόριθμου του Ερατοσθένη στο Διαδίκτυο. Χρησιμοποιήστε τον αλγόριθμο του Ερατοσθένη για να βρείτε όλους τους πρώτους αριθμούς που δεν υπερβαίνουν το 50.
Ποιο θα είναι το αποτέλεσμα της εκτέλεσης του αλγορίθμου από τη Χελώνα (βλ. παράδειγμα 5);
Καταγράψτε έναν αλγόριθμο για τον εκτελεστή Αριθμομηχανή (παράδειγμα 6), που δεν περιέχει περισσότερες από 5 εντολές:
Το σύστημα των εντολών του εκτελεστή Ο κατασκευαστής αποτελείται από δύο εντολές, στις οποίες εκχωρούνται αριθμοί:
Σύμφωνα με το πρώτο από αυτά, το 2 προστίθεται στον αριθμό στα δεξιά, σύμφωνα με το δεύτερο, ο αριθμός διαιρείται με το 2. Πώς θα μετατραπεί ο αριθμός 8 εάν ο εκτελεστής εκτελέσει τον αλγόριθμο 22212; Δημιουργήστε έναν αλγόριθμο στο σύστημα εντολών αυτού του εκτελεστή, σύμφωνα με τον οποίο ο αριθμός 1 θα μετατραπεί στον αριθμό 16 (ο αλγόριθμος δεν πρέπει να περιέχει περισσότερες από 5 εντολές).
Σε ποιο κελί πρέπει να βρίσκεται το Robot performer (παράδειγμα 7) για να επιστρέψει σε αυτό μετά την εκτέλεση του αλγόριθμου 3241;

Ο αλγόριθμος και οι ιδιότητές του.

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

Εκτελεστής αλγορίθμου- αυτό είναι το αντικείμενο ή το θέμα για το οποίο έχει σχεδιαστεί να ελέγχει ο αλγόριθμος.

Το σύστημα εντολών του εκτελεστή (SCS) είναι ολόκληρο το σύνολο εντολών που μπορεί να εκτελέσει ο εκτελεστής.

Ιδιότητες του αλγορίθμου: κατανοητότητα, ακρίβεια, πεπερασμένο.

Σαφήνεια:ο αλγόριθμος αποτελείται μόνο από εντολές που περιλαμβάνονται στο SKI του εκτελεστή.

Ακρίβεια:Κάθε εντολή του αλγορίθμου ελέγχου καθορίζει τη σαφή ενέργεια του εκτελεστή.

Φινίρισμα (ή απόδοση):Η εκτέλεση του αλγορίθμου πρέπει να οδηγεί σε ένα αποτέλεσμα σε πεπερασμένο αριθμό βημάτων.

Περιβάλλον εκτελεστή: το περιβάλλον στο οποίο δραστηριοποιείται ο εκτελεστής.

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

Πλήρες σύνολο δεδομένων:ένα απαραίτητο και επαρκές σύνολο δεδομένων για την επίλυση της εργασίας (απόκτηση του επιθυμητού αποτελέσματος).

Μέθοδοι γραφής αλγορίθμων.

Οι πιο συνηθισμένες μέθοδοι είναι: γραφικός, προφορικόςκαι στη μορφή προγράμματα υπολογιστή.

Γραφική μέθοδοςπεριλαμβάνει τη χρήση ορισμένων γραφικών συμβόλων - μπλοκ.

Όνομα μπλοκ	Ονομασία μπλοκ	Περιεχόμενο
Επεξεργάζομαι, διαδικασία		Επεξεργασία δεδομένων
Λήψη αποφάσης		Ένα λογικό μπλοκ για τον έλεγχο της αλήθειας ή της ψευτικότητας μιας συγκεκριμένης συνθήκης
Μεταφορά δεδομένων		Εισαγωγή ή έξοδος πληροφοριών
Ξεκίνα σταμάτα		Έναρξη ή τέλος προγράμματος
Τροποποίηση		Οργάνωση κυκλικής διαδικασίας - κεφαλίδα κύκλου

Η συλλογή των μπλοκ σχηματίζει το λεγόμενο διάγραμμα ροής αλγορίθμου.

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

Όταν γράφετε αλγόριθμους στη φόρμα προγράμματαοι υπολογιστές χρησιμοποιούν γλώσσες προγραμματισμού - συστήματα για την κωδικοποίηση οδηγιών και κανόνων για τη χρήση τους. Η σύνταξη αλγορίθμων με τη μορφή προγραμμάτων χαρακτηρίζεται από υψηλό βαθμό επισημοποίησης.

Αλγόριθμοι για την εργασία με ποσότητες. Βασικές αλγοριθμικές δομές.

Μια ποσότητα είναι ένα μεμονωμένο αντικείμενο πληροφοριών που έχει ένα όνομα, μια τιμή και έναν τύπο.

Ο εκτελεστής αλγορίθμων για την εργασία με ποσότητες μπορεί να είναι ένα άτομο ή μια ειδική τεχνική συσκευή, όπως ένας υπολογιστής. Ένας τέτοιος ερμηνευτής πρέπει να έχει μνήμηγια την αποθήκευση ποσοτήτων.

Οι ποσότητες μπορεί να είναι σταθερές ή μεταβλητές.

Σταθερή τιμή (σταθερή)δεν αλλάζει την τιμή του κατά την εκτέλεση του αλγορίθμου. Μια σταθερά μπορεί να υποδηλωθεί με τη δική της τιμή (αριθμοί 10, 3.5) ή με ένα συμβολικό όνομα (αριθμός).

Μεταβλητή τιμήμπορεί να αλλάξει την τιμή κατά την εκτέλεση του αλγορίθμου. Μια μεταβλητή προσδιορίζεται πάντα με ένα συμβολικό όνομα (X, A, R5, κ.λπ.).

Τύπος ποσότηταςορίζει το σύνολο των τιμών που μπορεί να λάβει μια τιμή και το σύνολο των ενεργειών που μπορούν να εκτελεστούν με αυτήν την τιμή. Βασικοί τύποι μεγεθών: ακέραιος, πραγματικός, συμβολικός, λογικός.

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

Α + Β; 2*X-Y; K + L - sin(X)

Μια εντολή εκχώρησης είναι μια εντολή εκτελεστή που έχει ως αποτέλεσμα μια μεταβλητή να λαμβάνει μια νέα τιμή. Μορφή εντολών:

όνομα μεταβλητής>:=έκφραση>

Η εντολή ανάθεσης εκτελείται με την ακόλουθη σειρά: πρώτα υπολογίζεται και μετά η τιμή που προκύπτει εκχωρείται σε μια μεταβλητή.

Παράδειγμα.Έστω η μεταβλητή Α την τιμή 6. Ποια τιμή θα λάβει η μεταβλητή Α μετά την εκτέλεση της εντολής: A:= 2 * A - 1;
Λύση.Ο υπολογισμός της παράστασης 2*A - 1 με A=6 θα δώσει τον αριθμό 11. Αυτό σημαίνει ότι η νέα τιμή της μεταβλητής A θα είναι ίση με 11.

Στη συνέχεια θα υποτεθεί ότι ο εκτελεστής των αλγορίθμων για την εργασία με ποσότητες είναι ένας υπολογιστής. Οποιοσδήποτε αλγόριθμος μπορεί να κατασκευαστεί από εντολές αναθέσεις, εισαγωγή, παραγωγή, διακλάδωσηΚαι κύκλος.

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

Παράδειγμα: εισαγωγή A - εισαγωγή της τιμής της μεταβλητής A από το πληκτρολόγιο του υπολογιστή.

Εντολή εξόδου: Μια εντολή που εμφανίζει την τιμή μιας ποσότητας σε μια συσκευή εξόδου υπολογιστή (όπως μια οθόνη).

Παράδειγμα: συμπέρασμα X - η τιμή της μεταβλητής X εμφανίζεται στην οθόνη.

Εντολή υποκαταστήματος- χωρίζει τον αλγόριθμο σε δύο μονοπάτια ανάλογα με κάποια συνθήκη. τότε η εκτέλεση του αλγορίθμου πηγαίνει σε γενική συνέχεια. Η διακλάδωση μπορεί να είναι πλήρης ή ατελής. Περιγραφή της διακλάδωσης σε μπλοκ διαγράμματα και σε αλγοριθμική γλώσσα:

Εδώ, μια σειρά σημαίνει μία ή περισσότερες διαδοχικές εντολές. kv - τέλος διακλάδωσης.

Εντολή βρόχουεξασφαλίζει την επαναλαμβανόμενη εκτέλεση μιας ακολουθίας εντολών (σώμα βρόχου) με βάση κάποια συνθήκη.

Βρόχος με προϋπόθεση- έναν βρόχο του οποίου η εκτέλεση επαναλαμβάνεται μέχρι να είναι αληθής η συνθήκη του βρόχου:

Βρόχος με παράμετρο- επαναλαμβανόμενη εκτέλεση του σώματος του βρόχου ενώ η ακέραια παράμετρος διατρέχει το σύνολο όλων των τιμών από την αρχική (In) έως την τελική (Ik):

Παράδειγμα.Δίνονται δύο απλά κλάσματα. Δημιουργήστε έναν αλγόριθμο για τη λήψη ενός κλάσματος που είναι το αποτέλεσμα της διαίρεσης τους.
Λύση.Σε αλγεβρική μορφή, η λύση του προβλήματος μοιάζει με αυτό:
a/b: c/d = a*d/b*c = m/n
Τα αρχικά δεδομένα είναι τέσσερις ακέραιες ποσότητες: a, b, c, d. Το αποτέλεσμα είναι δύο ακέραιοι m και n.

αλγδιαίρεση κλασμάτων
άθικτοςα, β, γ, δ, μ, ν
έναρξη εισαγωγήςΑ Β Γ Δ
m:=a*d
n:=b*c
έξοδος "Αριθμητής=", m
output "Denominator=", n
koi

Λάβετε υπόψη ότι για να εξάγετε κείμενο (οποιαδήποτε ακολουθία χαρακτήρων), πρέπει να γραφτεί σε εισαγωγικά στην εντολή συμπέρασμα.

Efimova O., Morozov V., Ugrinovich N. Μάθημα στην τεχνολογία των υπολογιστών με τα βασικά της επιστήμης των υπολογιστών. Εγχειρίδιο για το γυμνάσιο. - M.: LLC "AST Publishing House"? ABF, 2000
Βιβλίο-εργαστήριο προβλημάτων στην πληροφορική. Σε 2 τόμους/Εκδ. I. Semakina, E. Henner. - Μ.: Εργαστήριο Βασικής Γνώσης, 2001.
Ugrinovich N. Πληροφορική και τεχνολογίες πληροφορικής. 10-11 τάξη - Μ.: Εργαστήριο Βασικής Γνώσης, JSC "Moscow Textbooks", 2001

Εργασίες και δοκιμές με θέμα "Αλγόριθμοι και εκτελεστές"

Καλλιτέχνης Μάνατζμεντ Σχεδιαστής - Αλγόριθμοι ΣΤ' τάξη
Μαθήματα: 4 Εργασίες: 9 Τεστ: 1
2 Εργασίες: 9 Τεστ: 1

Αγαπητέ σπουδαστή!

Η γνώση του Θέματος «Αλγόριθμοι και Εκτελεστές» είναι απαραίτητη πρωτίστως για περαιτέρω μελέτη προγραμματισμού. Ως βάση για τη μελέτη προγραμματισμού επιλέχθηκε η γλώσσα προγραμματισμού QBasic. Εγκαταλείψαμε την ιδέα να συμπεριλάβουμε τη Visual Basic ή οποιαδήποτε άλλη αντικειμενοστρεφή γλώσσα προγραμματισμού στο μάθημά μας, καθώς αυτή η προσέγγιση δεν έχει ακόμη χρησιμοποιηθεί ευρέως στα περισσότερα σχολεία δευτεροβάθμιας εκπαίδευσης στη Ρωσική Ομοσπονδία. Επιπλέον, ο αντικειμενοστραφής προγραμματισμός βασίζεται στις αρχές του κλασικού προγραμματισμού Dos.

Το μάθημά μας έχει σχεδιαστεί για το πρόγραμμα γενικής εκπαίδευσης. Κατά την προετοιμασία για εισαγωγικές εξετάσεις στην τεχνολογία της πληροφορίας στα πανεπιστήμια, πρέπει να εξοικειωθείτε με τις ιδιαιτερότητες της μελέτης προγραμματισμού σε ένα συγκεκριμένο πανεπιστήμιο. Σε ορισμένες περιπτώσεις, είναι απαραίτητη μια εις βάθος μελέτη ενός αριθμού θεμάτων, για παράδειγμα, "Πίνακες". Θα πρέπει να δώσετε προσοχή σε αυτό όταν μελετάτε τη βιβλιογραφία για τον προγραμματισμό· ίσως θα πρέπει να χρησιμοποιήσετε τις μεθοδολογικές συστάσεις για την προετοιμασία για εξετάσεις, οι οποίες δημοσιεύονται επί του παρόντος στα περισσότερα ανώτατα εκπαιδευτικά ιδρύματα.

Συμπερασματικά, σημειώνουμε ότι η επίτευξη «αεροβατικών» στον προγραμματισμό είναι δυνατή μόνο με συνεχή εξάσκηση και επίλυση συγκεκριμένων εφαρμοσμένων προβλημάτων.

Θεωρητικές πληροφορίες

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

Ιδιότητες αλγορίθμων:

1. Διακριτικότητα (ο αλγόριθμος πρέπει να αποτελείται από συγκεκριμένες ενέργειες που ακολουθούν με συγκεκριμένη σειρά).

2. Ντετερμινισμός (κάθε ενέργεια πρέπει να ορίζεται αυστηρά και ξεκάθαρα σε κάθε περίπτωση).

3. Πεπερασμένο (κάθε ενέργεια και ο αλγόριθμος στο σύνολό του πρέπει να μπορεί να ολοκληρωθεί).

4. μαζικότητα (ο ίδιος αλγόριθμος μπορεί να χρησιμοποιηθεί με διαφορετικά δεδομένα πηγής).

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

Τύποι αλγορίθμων:

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

2. Κυκλικός αλγόριθμος (περιγραφή των ενεργειών που πρέπει να επαναληφθούν συγκεκριμένες φορές ή μέχρι να ολοκληρωθεί η εργασία).

3. Αλγόριθμος διακλάδωσης (αλγόριθμος στον οποίο, ανάλογα με την κατάσταση, εκτελείται είτε η μία είτε η άλλη ακολουθία ενεργειών)

Παραδείγματα επίλυσης προβλημάτων

Εκτελεστής Ο συντάκτης κινείται στο επίπεδο συντεταγμένων, αφήνοντας ένα ίχνος με τη μορφή μιας γραμμής. Ο συντάκτης μπορεί να εκτελέσει την εντολή Μετακίνηση στο (α, β)(όπου τα a,b είναι ακέραιοι), μετακινώντας τον Συντάκτη από ένα σημείο με συντεταγμένες (x, y) σε ένα σημείο με συντεταγμένες (x + a, y + b). Εάν οι αριθμοί a, b είναι θετικοί, η τιμή της αντίστοιχης συντεταγμένης αυξάνεται. εάν είναι αρνητικό, μειώνεται.

Για παράδειγμα, αν ο Draftsman βρίσκεται σε σημείο με συντεταγμένες (9, 5), τότε η εντολή Μετατόπιση σε

(1, -2) θα μετακινήσει τον συντάκτη στο σημείο (10, 3).

Επαναλάβετε k φορές

Team1 Team2 Team3

Τέλος

σημαίνει ότι η σειρά των εντολών Team1 Team2 Team3θα επαναληφθεί k φορές. Στον συντάκτη δόθηκε ο ακόλουθος αλγόριθμος για εκτέλεση:

Επαναλάβετε 3 φορές

Αλλαγή κατά (-2, -3) Αλλαγή κατά (3, 2) Αλλαγή κατά (-4, 0)

Τέλος

Με ποια εντολή μπορεί να αντικατασταθεί αυτός ο αλγόριθμος, ώστε ο Draftsman να καταλήξει στο ίδιο σημείο με την εκτέλεση του αλγόριθμου;

1) Μετακίνηση στο (-9, -3)

2) Μετακίνηση στο (-3, 9)

3) Μετακίνηση στο (-3, -1)

4) Μετακίνηση στο (9, 3)

Λύση:

Αυτή η εργασία επιλύεται καλύτερα διαδοχικά.

Σε ένα βρόχο, το Drafter εκτελεί μια ακολουθία εντολών

– Μετακίνηση κατά (-2, -3)

– Μετακίνηση σε (3, 2)

– Μετακίνηση στο (-4, 0),

η οποία μπορεί να αντικατασταθεί με μία εντολή: Μετακίνηση κατά (-2+3-4, -3+2+0), δηλ. Μετακίνηση στο (-3, -1).

Εφόσον ο βρόχος επαναλαμβάνεται 3 φορές, η εντολή Shift by (-3, -1) που προκύπτει θα εκτελεστεί 3 φορές. Αυτό σημαίνει ότι ο κύκλος μπορεί να αντικατασταθεί με την εντολή Shift με (-3*3, -1*3), π.χ. Μετακίνηση στο (-9, -3). Έτσι, παίρνουμε την εντολή Μετακίνηση σε (-9, -3) με την οποία μπορεί να αντικατασταθεί ολόκληρος ο αλγόριθμος.

Εργασίες για εκπαίδευση

1. Εκτελεστής Ο συντάκτης κινείται στο επίπεδο συντεταγμένων, αφήνοντας ένα ίχνος με τη μορφή μιας γραμμής. Ο συντάκτης μπορεί να εκτελέσει την εντολή Μετακίνηση στο (α, β)(όπου τα a, b είναι ακέραιοι), μετακινώντας τον Συντάκτη από ένα σημείο με συντεταγμένες (x, y) σε ένα σημείο με συντεταγμένες (x + a, y + b). Εάν οι αριθμοί a, b είναι θετικοί, η τιμή της αντίστοιχης συντεταγμένης αυξάνεται. εάν είναι αρνητικό, μειώνεται.

Για παράδειγμα, εάν ο Σχέδιος βρίσκεται στις συντεταγμένες (4, 2), τότε η εντολή Μετακίνηση σε (2, −3) θα μετακινήσει τον Σχέδιο στο σημείο (6, −1).

Επαναλάβετε k φορές

Team1 Team2 Team3

Τέλος

σημαίνει ότι η σειρά των εντολών Team1 Team2 Team3θα ξαναγίνει κμια φορά.

Στον συντάκτη δόθηκε ο ακόλουθος αλγόριθμος για εκτέλεση:

Επαναλάβετε 2 φορές

Μετακίνηση κατά (−6, −4)

Μετά την ολοκλήρωση αυτού του αλγόριθμου, ο Draftsman επέστρεψε στο σημείο εκκίνησης. Ποια εντολή πρέπει να τεθεί αντί για την εντολή Ομάδα 1?

1) Μετατόπιση κατά (−2, −1)

2) Μετακίνηση στο (1, 1)

3) Μετατόπιση κατά (−4, −2)

4) Μετακίνηση στο (2, 1)

2. Μετακίνηση στο (α, β)

Επαναλάβετε k φορές

Team1 Team2 Team3

Τέλος

Team1 Team2 Team3θα ξαναγίνει κμια φορά.

Επαναλάβετε 4 φορές

Εντολή 1 Μετακίνηση στο (3, 3) Μετακίνηση στο (1,−2) Τέλος

Μετατόπιση κατά (−8, 12)

Ομάδα 1?

1) Μετατόπιση κατά (−2, −4)

2) Μετατόπιση κατά (4,−13)

3) Μετακίνηση στο (2, 4)

4) Μετατόπιση κατά (−8, −16)

3. Εκτελεστής Ο συντάκτης κινείται στο επίπεδο συντεταγμένων, αφήνοντας ένα ίχνος με τη μορφή μιας γραμμής. Ο συντάκτης μπορεί να εκτελέσει την εντολή Μετακίνηση στο (α, β)(όπου τα a, b είναι ακέραιοι), μετακινώντας τον Συντάκτη από ένα σημείο με συντεταγμένες (x, y) σε ένα σημείο με συντεταγμένες (x + a, y + b). Εάν οι αριθμοί a, b είναι θετικοί, η τιμή της αντίστοιχης συντεταγμένης αυξάνεται. εάν είναι αρνητικό, μειώνεται.

Επαναλάβετε k φορές

Team1 Team2 Team3

Τέλος

σημαίνει ότι η σειρά των εντολών Team1 Team2 Team3θα ξαναγίνει κμια φορά.

Στον συντάκτη δόθηκε ο ακόλουθος αλγόριθμος για εκτέλεση:

Επαναλάβετε 3 φορές

Μετακίνηση σε (3, 9)

1) Μετακίνηση σε (3, 4)

2) Μετατόπιση κατά (−5, −10)

3) Μετατόπιση κατά (−9, −12)

4) Μετατόπιση κατά (−3, −4)

4. Εκτελεστής Ο συντάκτης κινείται στο επίπεδο συντεταγμένων, αφήνοντας ένα ίχνος με τη μορφή μιας γραμμής. Ο συντάκτης μπορεί να εκτελέσει την εντολή Μετακίνηση στο (α, β)(όπου τα a, b είναι ακέραιοι), μετακινώντας τον Συντάκτη από ένα σημείο με συντεταγμένες (x, y) σε ένα σημείο με συντεταγμένες (x + a, y + b). Εάν οι αριθμοί a, b είναι θετικοί, η τιμή της αντίστοιχης συντεταγμένης αυξάνεται. εάν είναι αρνητικό, μειώνεται.

Για παράδειγμα, εάν ο Σχέδιος βρίσκεται σε ένα σημείο με συντεταγμένες (4, 2), τότε η εντολή Μετακίνηση σε (2, −3) θα μετακινήσει τον Σχέδιο στο σημείο (6, −1).

Επαναλάβετε k φορές

Team1 Team2 Team3

Τέλος

σημαίνει ότι η σειρά των εντολών Team1 Team2 Team3θα ξαναγίνει κμια φορά.

Στον συντάκτη δόθηκε ο ακόλουθος αλγόριθμος για εκτέλεση:

Επαναλάβετε 3 φορές

Εντολή 1 Μετακίνηση στο (3, 2) Μετακίνηση στο (2, 1) Τέλος

Μετακίνηση σε (−9, −6)

1) Μετατόπιση κατά (−6, −3)

2) Μετακίνηση στο (4, 3)

3) Μετατόπιση κατά (−2, −1)

4) Μετακίνηση στο (2, 1)

5. Εκτελεστής Ο συντάκτης κινείται στο επίπεδο συντεταγμένων, αφήνοντας ένα ίχνος με τη μορφή μιας γραμμής. Ο συντάκτης μπορεί να εκτελέσει την εντολή Μετακίνηση στο (α, β)(όπου τα a, b είναι ακέραιοι), μετακινώντας τον Συντάκτη από ένα σημείο με συντεταγμένες (x, y) σε ένα σημείο με συντεταγμένες (x + a, y + b). Εάν οι αριθμοί a, b είναι θετικοί, η τιμή της αντίστοιχης συντεταγμένης αυξάνεται. εάν είναι αρνητικό, μειώνεται.

Επαναλάβετε k φορές

Team1 Team2 Team3

Τέλος

σημαίνει ότι η σειρά των εντολών Team1 Team2 Team3θα ξαναγίνει κμια φορά.

Στον συντάκτη δόθηκε ο ακόλουθος αλγόριθμος για εκτέλεση:

Επαναλάβετε 2 φορές

Εντολή 1 Μετακίνηση στο (3, 3) Μετακίνηση στο (1, −2) Τέλος

Μετατόπιση κατά (4, −6)

1) Μετατόπιση κατά (6, −2)

2) Μετατόπιση κατά (−8, 5)

3) Μετατόπιση κατά (−12, 4)

4) Μετατόπιση κατά (−6, 2)

6. Εκτελεστής Ο συντάκτης κινείται στο επίπεδο συντεταγμένων, αφήνοντας ένα ίχνος με τη μορφή μιας γραμμής. Ο συντάκτης μπορεί να εκτελέσει την εντολή Μετακίνηση στο (α, β)(όπου τα a, b είναι ακέραιοι), μετακινώντας τον Συντάκτη από ένα σημείο με συντεταγμένες (x, y) σε ένα σημείο με συντεταγμένες (x + a, y + b). Εάν οι αριθμοί a, b είναι θετικοί, η τιμή της αντίστοιχης συντεταγμένης αυξάνεται. εάν είναι αρνητικό, μειώνεται.

Επαναλάβετε k φορές

Team1 Team2 Team3

Τέλος

σημαίνει ότι η σειρά των εντολών Team1 Team2 Team3θα ξαναγίνει κμια φορά.

Στον συντάκτη δόθηκε ο ακόλουθος αλγόριθμος για εκτέλεση:

Επαναλάβετε 4 φορές

Εντολή 1 Μετακίνηση στο (1, 3) Μετακίνηση στο (1, −2) Τέλος

Μετατόπιση κατά (−4, −12)

1) Μετατόπιση κατά (1,−2)

2) Μετακίνηση σε (12, 4)

3) Μετακίνηση στο (2, 11)

4) Μετατόπιση κατά (−1, 2)

7. Εκτελεστής Ο συντάκτης κινείται στο επίπεδο συντεταγμένων, αφήνοντας ένα ίχνος με τη μορφή μιας γραμμής. Ο συντάκτης μπορεί να εκτελέσει την εντολή Μετακίνηση στο (α, β)(όπου τα a, b είναι ακέραιοι), μετακινώντας τον Συντάκτη από ένα σημείο με συντεταγμένες (x, y) σε ένα σημείο με συντεταγμένες (x + a, y + b). Εάν οι αριθμοί a, b είναι θετικοί, η τιμή της αντίστοιχης συντεταγμένης αυξάνεται. εάν είναι αρνητικό, μειώνεται.

Επαναλάβετε k φορές

Team1 Team2 Team3

Τέλος

σημαίνει ότι η σειρά των εντολών Team1 Team2 Team3θα ξαναγίνει κμια φορά.

Στον συντάκτη δόθηκε ο ακόλουθος αλγόριθμος για εκτέλεση:

Επαναλάβετε 4 φορές

Εντολή 1 Μετακίνηση στο (3, 2) Μετακίνηση στο (2, 1) Τέλος

Μετακίνηση σε (−12, −8)

1) Μετατόπιση κατά (−8, −4)

2) Μετατόπιση κατά (−2, −1)

3) Μετακίνηση στο (7, 5)

4) Μετακίνηση στο (2, 1)

8. Εμπρός n Δεξιά m

Επανάληψη 9 [Εμπρός 50 Δεξιά 60]

1) κανονικό εξάγωνο

2) κανονικό τρίγωνο

3) ανοίξτε τη διακεκομμένη γραμμή

4) κανονικό εξάγωνο

9. Εκτελεστής Η χελώνα κινείται στην οθόνη του υπολογιστή, αφήνοντας ένα ίχνος με τη μορφή μιας γραμμής. Σε κάθε συγκεκριμένη στιγμή είναι γνωστή η θέση του ερμηνευτή και η κατεύθυνση της κίνησής του. Ο εκτελεστής έχει δύο εντολές: Εμπρός n(όπου n είναι ένας ακέραιος αριθμός), αναγκάζοντας τη Χελώνα να μετακινήσει n βήματα προς την κατεύθυνση της κίνησης. Δεξιά m(όπου m είναι ακέραιος), προκαλώντας αλλαγή στην κατεύθυνση της κίνησης κατά m μοίρες δεξιόστροφα. Ρεκόρ Επανάληψη k [Command1 Command2 Command3]σημαίνει ότι η ακολουθία των εντολών σε αγκύλες θα επαναληφθεί k φορές.

Στη χελώνα δόθηκε ο ακόλουθος αλγόριθμος για να εκτελέσει: Επανάληψη 7 [Εμπρός 70 Δεξιά 120]. Τι σχήμα θα εμφανιστεί στην οθόνη;

1) κανονικό εξάγωνο

2) ανοίξτε τη διακεκομμένη γραμμή

3) κανονικό επτάγωνο

4) κανονικό τρίγωνο

10. Εκτελεστής Η χελώνα κινείται στην οθόνη του υπολογιστή, αφήνοντας ένα ίχνος με τη μορφή μιας γραμμής. Σε κάθε συγκεκριμένη στιγμή είναι γνωστή η θέση του ερμηνευτή και η κατεύθυνση της κίνησής του. Ο εκτελεστής έχει δύο εντολές: Εμπρός n(όπου n είναι ένας ακέραιος αριθμός), αναγκάζοντας τη Χελώνα να μετακινήσει n βήματα προς την κατεύθυνση της κίνησης. Δεξιά m(όπου m είναι ακέραιος), προκαλώντας αλλαγή στην κατεύθυνση της κίνησης κατά m μοίρες δεξιόστροφα. Ρεκόρ Επανάληψη k [Command1 Command2 Command3]σημαίνει ότι η ακολουθία των εντολών σε αγκύλες θα επαναληφθεί k φορές.

Στη χελώνα δόθηκε ο ακόλουθος αλγόριθμος για να εκτελέσει: Επανάληψη 9 [Εμπρός 70 Δεξιά 90]. Τι σχήμα θα εμφανιστεί στην οθόνη;

2) κανονικό εξάγωνο

3) κανονικό οκτάγωνο

4) κανονικό τετράπλευρο

11. Εκτελεστής Η χελώνα κινείται στην οθόνη του υπολογιστή, αφήνοντας ένα ίχνος με τη μορφή μιας γραμμής. Σε κάθε συγκεκριμένη στιγμή είναι γνωστή η θέση του ερμηνευτή και η κατεύθυνση της κίνησής του. Ο εκτελεστής έχει δύο εντολές: Εμπρός n(όπου n είναι ένας ακέραιος αριθμός), αναγκάζοντας τη Χελώνα να μετακινήσει n βήματα προς την κατεύθυνση της κίνησης. Δεξιά m(όπου m είναι ακέραιος), προκαλώντας αλλαγή στην κατεύθυνση της κίνησης κατά m μοίρες δεξιόστροφα. Ρεκόρ Επανάληψη k [Command1 Command2 Command3]σημαίνει ότι η ακολουθία των εντολών σε αγκύλες θα επαναληφθεί k φορές.

Στη χελώνα δόθηκε ο ακόλουθος αλγόριθμος για να εκτελέσει: Επανάληψη 5 [Εμπρός 80 Δεξιά 60]. Τι σχήμα θα εμφανιστεί στην οθόνη;

1) κανονικό πεντάγωνο

2) κανονικό τρίγωνο

3) κανονικό εξάγωνο

4) ανοίξτε τη διακεκομμένη γραμμή

12. Εκτελεστής Η χελώνα κινείται στην οθόνη του υπολογιστή, αφήνοντας ένα ίχνος με τη μορφή μιας γραμμής. Σε κάθε συγκεκριμένη στιγμή είναι γνωστή η θέση του ερμηνευτή και η κατεύθυνση της κίνησής του. Ο εκτελεστής έχει δύο εντολές: Εμπρός n(όπου n είναι ένας ακέραιος αριθμός), αναγκάζοντας τη Χελώνα να μετακινήσει n βήματα προς την κατεύθυνση της κίνησης. Δεξιά m(όπου m είναι ακέραιος), προκαλώντας αλλαγή στην κατεύθυνση της κίνησης κατά m μοίρες δεξιόστροφα. Ρεκόρ Επανάληψη k [Command1 Command2 Command3]σημαίνει ότι η ακολουθία των εντολών σε αγκύλες θα επαναληφθεί k φορές.

Στη χελώνα δόθηκε ο ακόλουθος αλγόριθμος για να εκτελέσει: Επανάληψη 5 [Εμπρός 80 Δεξιά 90]. Τι σχήμα θα εμφανιστεί στην οθόνη;

1) ανοίξτε τη διακεκομμένη γραμμή

2) κανονικό εξάγωνο

3) κανονικό πεντάγωνο

4) κανονικό τετράπλευρο

Θεωρητικές πληροφορίες

Παραδείγματα επίλυσης προβλημάτων

Εργασίες για εκπαίδευση

Θεωρητικές πληροφορίες

Παραδείγματα επίλυσης προβλημάτων

Εργασίες για εκπαίδευση

Θεωρητικές πληροφορίες

Παραδείγματα επίλυσης προβλημάτων

Εργασίες για εκπαίδευση

Θεωρητικές πληροφορίες

Παραδείγματα επίλυσης προβλημάτων

Εργασίες για εκπαίδευση

Θεωρητικές πληροφορίες

Παραδείγματα επίλυσης προβλημάτων

Εργασίες για εκπαίδευση

Θεωρητικές πληροφορίες

Παραδείγματα επίλυσης προβλημάτων

Εργασίες για εκπαίδευση

Θεωρητικές πληροφορίες

Παραδείγματα επίλυσης προβλημάτων

Εργασίες για εκπαίδευση

Θεωρητικές πληροφορίες

Παραδείγματα επίλυσης προβλημάτων

Εργασίες για εκπαίδευση

Θεωρητικές πληροφορίες

Παραδείγματα επίλυσης προβλημάτων

Εργασίες για εκπαίδευση

Η λέξη "αλγόριθμος" προέρχεται από το όνομα του Άραβα μαθηματικού του 9ου αιώνα al-Khwarizmi, ο οποίος διατύπωσε τους κανόνες για την εκτέλεση αριθμητικών πράξεων.

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

Παραδείγματα: καθημερινή ρουτίνα, σειρά μαγειρέματος, οδηγίες κ.λπ.)

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

Σύστημα εντολών εκτελεστή- αυτό είναι ολόκληρο το σύνολο εντολών που ο εκτελεστής ξέρει πώς να εκτελεί (καταλαβαίνει). Ο αλγόριθμος μπορεί να κατασκευαστεί μόνο από εντολές που περιλαμβάνονται στο σύστημα εντολών του εκτελεστή.

Για παράδειγμα, εκτελεστής Το ρομπότ μπορεί να εκτελέσει εντολές προς τα εμπρός, προς τα πίσω, αριστερά, δεξιά, ζωγραφική. Κινείται σε ένα κυτταρικό πεδίο που οριοθετείται από έναν τοίχο και περιέχει τοιχώματα. Το ρομπότ δεν μπορεί να περάσει από τον τοίχο.

Ιδιότητες αλγορίθμου:

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

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

3.Αιτιοκρατία(βεβαιότητα, ακρίβεια) – κάθε εντολή πρέπει να καθορίζει μοναδικά τη δράση του εκτελεστή.

4.Κατανοησιμότητα– η εντολή πρέπει να είναι γραμμένη σε γλώσσα κατανοητή από τον υπολογιστή.

5.Διακριτικότητα– χωρισμός του αλγόριθμου σε ξεχωριστές εντολές.

Τρόποι για να γράψετε τον αλγόριθμο:

1) Σε φυσική γλώσσα – καταγραφή με τη μορφή ξεχωριστών εντολών σε γλώσσα κατανοητή από τον άνθρωπο.

2) Γραφικά – στη γλώσσα των διαγραμμάτων ροής, χρησιμοποιώντας γεωμετρικά σχήματα (οβάλ, ορθογώνιο, παραλληλόγραμμο, ρόμβος).

3) Σε μια αλγοριθμική γλώσσα - μια γλώσσα για τη σύνταξη αλγορίθμων για τη διδασκαλία του προγραμματισμού. Οι εντολές είναι γραμμένες στα ρωσικά.

4) Σε γλώσσα προγραμματισμού - πρόγραμμα. Γλώσσες προγραμματισμού: Basic, Pascal, C, Visual Basic.

B7.Βασικές αλγοριθμικές δομές: ακολουθώντας, διακλάδωση, βρόχος; εικόνα σε μπλοκ διαγράμματα. Ανάλυση εργασιών σε δευτερεύουσες εργασίες. Βοηθητικούς αλγόριθμους.

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

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

Καλείται ένας αλγόριθμος στον οποίο οι εντολές εκτελούνται διαδοχικά η μία μετά την άλλη γραμμικός αλγόριθμος.

Έτσι φαίνεται ένας γραμμικός αλγόριθμος στη γλώσσα του μπλοκ διαγράμματος:

Παράδειγμα: αλγόριθμος για την ενεργοποίηση του υπολογιστή:

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

Σε αυτόν τον αλγόριθμο, όλες οι ενέργειες πρέπει να εκτελούνται διαδοχικά η μία μετά την άλλη: δεν μπορείτε να ξεκινήσετε να εργάζεστε εάν η τροφοδοσία ή η οθόνη δεν είναι ενεργοποιημένη.

Στην αλγοριθμική δομή " διακλάδωση" περιλαμβάνεται κατάσταση, ανάλογα με την αλήθεια της συνθήκης, εκτελείται η μία ή η άλλη ακολουθία εντολών (σειρά).

Συνθήκη είναι μια δήλωση που μπορεί να είναι αληθής ή ψευδής. Στη συνθήκη, δύο αριθμοί, δύο συμβολοσειρές, δύο μεταβλητές ή εκφράσεις συμβολοσειρών συγκρίνονται μεταξύ τους χρησιμοποιώντας τελεστές σύγκρισης (>,<, =, >=, <=).

Εγγραφή σε αλγοριθμική γλώσσα: IfCondition Τότε Σειρά 1 (Αν Κατάστασηαλήθεια, τότε αλήθεια Επεισόδιο 1, Αν Κατάσταση false, τότε δεν εκτελείται τίποτα). Παράδειγμα: Αν σήμερα είναι Κυριακή, τότε δεν χρειάζεται να πάτε σχολείο. Πλήρης μορφή διακλάδωσης

Σε αλγοριθμικές δομές κύκλος περιλαμβάνει μια σειρά από εντολές που εκτελούνται επανειλημμένα. Αυτή η ακολουθία εντολών ονομάζεται σώμα του βρόχου.

Υπάρχουν δύο τύποι κυκλικών αλγοριθμικών δομών:

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

Βρόχος με μετρητή– χρησιμοποιείται όταν είναι γνωστό εκ των προτέρων πόσες επαναλήψεις του σώματος του βρόχου πρέπει να γίνουν.