Σκεφτείτε το πρόβλημα:

Η είσοδος στο πρόγραμμα είναι ένας φυσικός αριθμός που δεν υπερβαίνει το 2 * 10 9 . Προσδιορίστε το άθροισμα των ψηφίων αυτού του αριθμού.

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

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

Ο βρόχος while

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

• nc αντίο όρος
• loop_body

Η συνθήκη που γράφεται μετά τη λέξη υπηρεσίας είναι μια λογική έκφραση.

Ο βρόχος εκτελείται ως εξής:

1. Η τιμή της λογικής έκφρασης αξιολογείται.
2. Εάν το αποτέλεσμα του υπολογισμού είναι όχι , τότε ο βρόχος τελειώνει και ο Kumir μετακινείται στην πρώτη εντολή μετά τον βρόχο while. Εάν το αποτέλεσμα του υπολογισμού είναι ναι, τότε εκτελείται το σώμα του βρόχου, μετά το οποίο η τιμή της παράστασης υπολογίζεται ξανά με μια νέα τιμή.

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

Τώρα ας χρησιμοποιήσουμε τον βρόχο while για να λύσουμε το πρόβλημά μας.

• εισαγωγή αριθ
• nc ενώ num > 0
• άθροισμα:= άθροισμα + mod(αριθμός, 10 )
• num:= div(αριθμός, 10)
• ποσό ανάληψης

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

Μέχρι τότε κύκλος

Στο Idol, υπάρχει μια άλλη παραλλαγή ενός βρόχου υπό όρους, που ονομάζεται βρόχος μέχρι, που έχει την ακόλουθη μορφή:

• loop_body
• kc υπό συνθήκες

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

Η εργασία του βρόχου μέχρι τότε προχωρά ως εξής:

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

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

(Απόσπασμα κώδικα προγράμματος)

• εισαγωγή αριθ
• αν ο αριθμός 0
• τότε k:= k + 1
• kts στο num = 0
• έξοδος k

Αλγόριθμος για τη σχεδίαση μιας σπείρας:

χρησιμοποιήστε το συρτάρι
αλγ
νωρίς
. μετακινηθείτε σε ένα σημείο(3,3)
. χαμηλώστε το στυλό
. πηνίο (1); πηνίο (3); πηνίο (5); πηνίο (7); πηνίο (9)
. σηκώστε το στυλό
ενάντιος
alg turn (arg w)
νωρίς
. μετατόπιση κατά διάνυσμα(α, 0)
. μετατόπιση κατά διάνυσμα(0, -a)
. μετατόπιση κατά διάνυσμα(-a-1,0)
. μετατόπιση κατά διάνυσμα(0, a+1)
ενάντιος

Δώστε προσοχή στο μπλοκ εντολών:

Πηνίο (1); πηνίο (3); πηνίο (5); πηνίο (7); πηνίο (9)

Ο βοηθητικός αλγόριθμος “coil(arg thing)” καλείται 5 φορές, αλλά δεν μπορεί να κληθεί στον βρόχο “N times”, γιατί κάθε φορά καλείται με διαφορετική τιμή ορίσματος.

Αλλά μπορείτε να δείτε ότι οι τιμές του ορίσματος αλλάζουν από 1 σε 9, κάθε φορά αυξάνοντας κατά 2. Έτσι, μπορούμε να βοηθήσουμε βρόχος με μετρητή. Επίσης, ένας τέτοιος κύκλος ονομάζεται κύκλος "για".

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

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

Γενική άποψη του κύκλου με μετρητή:

nc για<счетчик>από<нач. знач.>πριν<кон. знач.>[βήμα<знач.>]
<тело цикла (последовательность команд)>
kts

Δεν είναι απαραίτητο να υποδειχθεί το βήμα, εάν δεν προσδιορίζεται, τότε θεωρείται ίσο με ένα.

Τώρα μπορούμε να ξαναγράψουμε τον αλγόριθμο "σπιράλ" με αυτόν τον τρόπο:

χρησιμοποιήστε το συρτάρι
αλγ
νωρίς
. μετακινηθείτε σε ένα σημείο(3,3)
. χαμηλώστε το στυλό
. ολόκληρο το μέγεθος
. nc για μέγεθος 1 έως 9 βήμα 2
. . πηνίο (μέγεθος)
. kts
. σηκώστε το στυλό
ενάντιος
alg turn (arg w)
νωρίς
. μετατόπιση κατά διάνυσμα(α, 0)
. μετατόπιση κατά διάνυσμα(0, -a)
. μετατόπιση κατά διάνυσμα(-a-1,0)
. μετατόπιση κατά διάνυσμα(0, a+1)
ενάντιος

Σε αυτό το παράδειγμα, η μεταβλητή μετρητή "size" θα λάβει τις τιμές: 1, 3, 5, 7, 9. Δηλαδή, Ο βρόχος θα εκτελεστεί 5 φορές. Για κάθε τιμή της μεταβλητής «μέγεθος», το σώμα του βρόχου θα εκτελεστεί μία φορά, στο παράδειγμά μας, αυτή είναι μια κλήση στον βοηθητικό αλγόριθμο «πηνίο (πράγμα arg)».

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

Το μπλοκ διάγραμμα ενός τέτοιου αλγορίθμου μοιάζει με αυτό:

Ας δούμε ένα άλλο παράδειγμα:

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

Ο αλγόριθμος θα μπορούσε να είναι ο εξής:

alg τετράγωνο (arg x, y, πλευρά)
νωρίς
. μετακινηθείτε σε ένα σημείο(x, y)
. μετατόπιση κατά διάνυσμα(-πλευρά/2, πλάγια/2)
. χαμηλώστε το στυλό
. μετατόπιση κατά διάνυσμα(πλευρά, 0)
. μετατόπιση κατά διάνυσμα(0, -πλευρά)
. μετατόπιση κατά διάνυσμα(-πλευρά, 0)
. μετατόπιση κατά διάνυσμα(0, πλευρά)
. σηκώστε το στυλό
ενάντιος

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

Για να το κάνουμε αυτό, χρησιμοποιούμε τον βρόχο "για". Μελετήστε το παράδειγμα προγράμματος:

χρησιμοποιήστε το συρτάρι
alg σχήμα 1
νωρίς
. ακέραιος z
. nc για z από 2 έως 10 βήμα 2
. . τετράγωνο(0, 0, z)
. kts
ενάντιος
alg τετράγωνο (arg x, y, πλευρά)
νωρίς
. μετακινηθείτε σε ένα σημείο(x, y)
. μετατόπιση κατά διάνυσμα(-πλευρά/2, πλάγια/2)
. χαμηλώστε το στυλό
. μετατόπιση κατά διάνυσμα(πλευρά, 0)
. μετατόπιση κατά διάνυσμα(0, -πλευρά)
. μετατόπιση κατά διάνυσμα(-πλευρά, 0)
. μετατόπιση κατά διάνυσμα(0, πλευρά)
. σηκώστε το στυλό
ενάντιος

Σε αυτό το παράδειγμα, η μεταβλητή "z" θα λάβει τις τιμές: 2, 4, 6, 8, 10. Ο βρόχος θα εκτελεστεί 5 φορές. Για κάθε τιμή "z", το σώμα του βρόχου θα εκτελεστεί μία φορά, στο παράδειγμά μας, αυτή είναι μια κλήση στον αλγόριθμο του βοηθητικού τετραγώνου.

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

Όπως παρατηρήσατε, ο αλγόριθμος χρησιμοποίησε όχι μόνο αριθμούς, αλλά και αλγεβρικές εκφράσεις, τύπους, για παράδειγμα "-side/2". Στην επιστήμη των υπολογιστών, αυτές οι εκφράσεις ονομάζονται αριθμητική. Οι κανόνες της γλώσσας επιτρέπουν, όταν γράφετε αλγόριθμους, όπου μπορείτε να γράψετε έναν αριθμό, να γράψετε μια αυθαίρετη αριθμητική έκφραση.

Κάρτες εργασιών

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

Σας δίνονται δύο αυθαίρετοι αριθμοί. Εφόσον το προϊόν τους είναι μικρότερο από 100, αυξήστε κάθε αριθμό κατά 2 και εμφανίστε τους τελικούς αριθμούς στην οθόνη

Εισάγονται διαδοχικά n -ακέραιοι αριθμοί. Βρείτε τον αριθμό των πέντε σε μια ακολουθία

Εισάγονται διαδοχικά n -ακέραιοι αριθμοί. Βρείτε τη διαφορά μεταξύ των μέγιστων και ελάχιστων τιμών των δεδομένων αριθμών

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

Σας δίνονται δύο αυθαίρετοι αριθμοί. Εφόσον το προϊόν τους είναι μικρότερο από 100, αυξήστε κάθε αριθμό κατά 2 και εμφανίστε τους τελικούς αριθμούς στην οθόνη

Εισάγονται διαδοχικά n -ακέραιοι αριθμοί. Βρείτε τον αριθμό των πέντε σε μια ακολουθία

Εισάγονται διαδοχικά n -ακέραιοι αριθμοί. Βρείτε τη διαφορά μεταξύ των μέγιστων και ελάχιστων τιμών των δεδομένων αριθμών

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

Σας δίνονται δύο αυθαίρετοι αριθμοί. Εφόσον το προϊόν τους είναι μικρότερο από 100, αυξήστε κάθε αριθμό κατά 2 και εμφανίστε τους τελικούς αριθμούς στην οθόνη

Εισάγονται διαδοχικά n -ακέραιοι αριθμοί. Βρείτε τον αριθμό των πέντε σε μια ακολουθία

Εισάγονται διαδοχικά n -ακέραιοι αριθμοί. Βρείτε τη διαφορά μεταξύ των μέγιστων και ελάχιστων τιμών των δεδομένων αριθμών

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

Σας δίνονται δύο αυθαίρετοι αριθμοί. Εφόσον το προϊόν τους είναι μικρότερο από 100, αυξήστε κάθε αριθμό κατά 2 και εμφανίστε τους τελικούς αριθμούς στην οθόνη

Εισάγονται διαδοχικά n -ακέραιοι αριθμοί. Βρείτε τον αριθμό των πέντε σε μια ακολουθία

Εισάγονται διαδοχικά n -ακέραιοι αριθμοί. Βρείτε τη διαφορά μεταξύ των μέγιστων και ελάχιστων τιμών των δεδομένων αριθμών

Ένθετοι βρόχοι και κλάδοι στο σύστημα KUMIR

Μία από τις θεμελιώδεις έννοιες στην επιστήμη των υπολογιστών είναι η έννοια του αλγορίθμου. Η προέλευση του όρου «αλγόριθμος» συνδέεται με τα μαθηματικά. Αυτή η λέξη προέρχεται από το Algorithmi - τη λατινική ορθογραφία του ονόματος του Muhammad al-Khwarizmi (787 - 850), ενός εξαιρετικού μαθηματικού της μεσαιωνικής Ανατολής. Στο βιβλίο του «On the Indian Account» διατύπωσε τους κανόνες για τη γραφή φυσικών αριθμών χρησιμοποιώντας αραβικούς αριθμούς και τους κανόνες για την εργασία μαζί τους σε μια στήλη.

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

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

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

Αυτές οι ιδιότητες είναι:

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

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

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

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

Τρόποι σύνταξης αλγορίθμων

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

Υπάρχουν οι ακόλουθοι κύριοι τρόποι σύνταξης αλγορίθμων:

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

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

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

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

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

Σύστημα προγραμματισμού KUMIR

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

Το KuMir (Σύνολο Εκπαιδευτικών MIR) είναι ένα σύστημα προγραμματισμού που έχει σχεδιαστεί για να υποστηρίζει στοιχειώδη μαθήματα πληροφορικής και προγραμματισμού στη δευτεροβάθμια και ανώτερη εκπαίδευση.

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

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

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

Ρομπότ Γραφίστας

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

Γραφίσταςείναι το αντικείμενο ελέγχου. Ενα πακέτοθα τους κυβερνήσουμε.

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

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

R
Το bot μπορεί να εκτελέσει εντολές : πάνω, κάτω, δεξιά, αριστερά, βάψιμο.

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

Βασικές Αλγοριθμικές Δομές

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

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

Γραμμική δομή

Γραμμική δομή είναι η απλούστερη οργάνωση αλγορίθμων - οι εντολές εκτελούνται διαδοχικά η μία μετά την άλλη

Παράδειγμα:

Κυκλική δομή (κύκλος)

Κυκλική δομή (κύκλος) παρέχει πολλαπλή εκτέλεση των ίδιων εντολών. Υπάρχουν διάφοροι τύποι κυκλικών δομών.

Οποιαδήποτε κυκλική δομή αποτελείται από δύο μέρη -επί κεφαλήςκαι κυκλικά σώματα.

Το σύνολο των εντολών που επαναλαμβάνεται κατά την εκτέλεση του βρόχου καλείταισώμα του κύκλου.

επί κεφαλής καθορίζει τον αριθμό των επαναλήψεων του σώματος του βρόχου.

Βρόχος για τον αριθμό των επαναλήψεων (φορές)

nc Ν μια φορά

<команда>

kts

Π Παράδειγμα:

χρήση Ρομπότ
αλγ στήλη

νωρίς
. nc 5 μια φορά
. . ζωγραφίζω
. . πάνω
. kts

ενάντιος

Βρόχος με προϋπόθεση (ακόμα)

(σημειογραφία σε αλγοριθμική γλώσσα)

nc αντίο <условие>

<команда>

προς την ντο

Παράδειγμα:

χρήση Ρομπότ
αλγ Γραμμή

νωρίς

nc αντίο πάνω χαλαρό
ζωγραφίζω
πάνω
kts

ενάντιος

Βρόχος με μετασυνθήκη (στο)

(σημειογραφία σε αλγοριθμική γλώσσα)

n ντο

<команда>

cc_at <условие>

Παράδειγμα:

χρήση Ρομπότ
αλγ Γραμμή

νωρίς
nc

Βαφή πάνω? πάνω

cc_at έμεινε ελεύθερος

ενάντιος

Δομή κλάδου.

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

Για την υλοποίηση της δομής «διακλάδωσης», χρησιμοποιούνται δύο δομημένες εντολές του σχολικού EL - εάν και επιλογή, καθεμία από τις οποίες μπορεί να είναι πλήρης και ελλιπής.

Σε διαγράμματα ροής και σχολική γλώσσα<условие>είναι μια δυαδική έκφραση που μπορεί να οδηγήσει σε μία από τις δύο πιθανές τιμές -αληθήςή Ψευδής. Στη γλώσσα του σχολείου, αυτές οι τιμές γράφονται ως ναι και όχι. Οι γλώσσες προγραμματισμού χρησιμοποιούν συχνά τιμέςΑληθήςκαι Ψευδής. Ο υπολογιστής αποθηκεύει αυτές τις τιμές ως 1 και 0.

Πλήρες υποκατάστημα

(σημειογραφία σε αλγοριθμική γλώσσα)

μι αν <условие>
. . έπειτα <команда1>
. . σε διαφορετική περίπτωση <команда2>
όλα

Παράδειγμα:

χρήση Ρομπότ
αλγ διακλάδωση_πλήρης

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

ενάντιος

ατελής διακλάδωση

(σημειογραφία σε αλγοριθμική γλώσσα)

μι αν <условие>
. . έπειτα <команда1>
όλα

Παράδειγμα:

χρήση Ρομπότ
αλγ διακλάδωση_μη ολοκληρωμένη

νωρίς
. αν πάνω χαλαρό
. . έπειτα πάνω
. όλα

ενάντιος

Βοηθητικός αλγόριθμος (διαδικασία)

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

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

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

χρήση Ρομπότ
αλγ
νωρίς
πολύ κάτω

τετράγωνο
πολύ κάτω

πολύ κάτω
ενάντιος

alg τετράγωνο
νωρίς
ζωγραφίζω

σωστά

ζωγραφίζω

πολύ κάτω

ζωγραφίζω

αριστερά

ζωγραφίζω
ενάντιος

Φωλιασμένοι βρόχοι και κλαδιά

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

ντο ένα ucl ονομάζεται ένθετο αν τοποθετηθεί μέσα σε άλλο βρόχο.

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

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

Το σώμα του βρόχου είναι το τμήμα του βρόχου που επαναλαμβάνεται όταν εκτελείται ο βρόχος.

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

Όταν το σώμα του βρόχου είναι ένας άλλος βρόχος ή κλάδος, ονομάζονται ένθετα.

ένθετο βρόχο

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

Φωλιασμένο κλαδί

Εξετάστε τη λύση του προβλήματος με ένθετα κλαδιά και βρόχους:

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

χρήση Ρομπότ αλγ νωρίς
. nc αντίο στα δεξιάΜε ελευθερώς
nc αντίο κάτω χαλαρό
.ζωγραφίζω πάνω?σωστά
. . kts
. . σωστά
. kts ενάντιος ΑΠΟ
αφήνουμε τον αλγόριθμο για την επίλυση του προβλήματος με έναν εξωτερικό βρόχο while και έναν ένθετο βρόχο while.

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

Ας λύσουμε το ίδιο πρόβλημα με έναν εξωτερικό βρόχο while και έναν ένθετο βρόχο while.

Ρομπότ ελέγχου εκτελεστών στο σύστημα KUMIR

Το ρομπότ υπάρχει σε ένα συγκεκριμένο περιβάλλον (ορθογώνιο καρό πεδίο). Οι τοίχοι μπορούν να βρίσκονται ανάμεσα σε ορισμένα κελιά του πεδίου. Ορισμένα κελιά ενδέχεται να είναι σκιασμένα (Εικ. 3.11).

Το ρομπότ καταλαμβάνει ακριβώς ένα κελί του πεδίου.

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

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

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

Ο
λάθη: 1 συντακτικό; 2. λογικό

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

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

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

ΔΙΑΔΙΚΑΣΙΑ ΛΕΙΤΟΥΡΓΙΑΣ:

1. 
   Παρακαλώ περιβάλλον εκκίνησηςσύμφωνα με την εργασία:

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

2. Προσδιορίστε τον Ανάδοχο:

Εισαγωγή μενού → Χρήση ρομπότ

3. Γράψτε έναν αλγόριθμο για την επίλυση του προβλήματος.

4. Εκτελέστε τον αλγόριθμο (Μενού Εκτέλεση → Συνεχής εκτέλεση / F9)

Το σύστημα εντολών του ρομπότ εκτελεστή στο σύστημα KUMIR

Ομάδα	Δράση
πάνω	Το ρομπότ ανεβαίνει 1 κελί
πολύ κάτω	Το ρομπότ κινείται προς τα κάτω 1 κελί
αριστερά	Το ρομπότ μετακινεί 1 κελί προς τα αριστερά
σωστά	Το ρομπότ μετακινεί 1 κελί προς τα δεξιά
ζωγραφίζω	Το ρομπότ ζωγραφίζει το κελί στο οποίο βρίσκεται
δικαίωμα δωρεάν	Το ρομπότ ελέγχει την εκτέλεση του αντίστοιχου απλόςόροι
έμεινε ελεύθερος	↓
πάνω χαλαρό	↓
κάτω χαλαρό	↓
το κελί είναι σκιασμένο	↓
κλουβί καθαρό	↓

Κυκλικοί αλγόριθμοι

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

Σώμα βρόχου -ένα σύνολο επαναλαμβανόμενων ενεργειών.

Κατάσταση - Boolean έκφραση (απλή ή σύνθετη (σύνθετη))
Τύποι κύκλου:

1.Βρόχος "Επανάληψη n φορές" 2. Επανάληψη "Αντίο"
nc n φορές nts αντίο
. . Σώμα βρόχου. . Σώμα βρόχου
kts kts

Παράδειγμα: nts αντίοδικαίωμα δωρεάν

Γενική προβολή του κύκλου "Επανάληψη n φορές:

ΕΠΑΝΑΛΗΨΗ n ΦΟΡΕΣ

ΤΟ ΤΕΛΟΣ
kts

Γενική άποψη του βρόχου while:

ΕΝΩ ΝΑ ΚΑΝΟΥΜΕ

ΤΟ ΤΕΛΟΣ
Σύνθετες συνθήκεςσχηματίζονται από μία ή περισσότερες απλές συνθήκες και λέξεις υπηρεσίας ΚΑΙ, Ή, ΟΧΙ.

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

Αφήστε τον Α - δωρεάν στην κορυφήΣΤΟ - δωρεάν στα δεξιάτότε η σύνθετη συνθήκη Α και Β- δωρεάν στην κορυφή ΚΑΙ δωρεάν στα δεξιά.

Σύνθετη κατάσταση Α Ή Β ικανοποιείται όταν ικανοποιείται τουλάχιστον μία από τις δύο απλές προϋποθέσεις που περιλαμβάνονται σε αυτήν: επάνω δωρεάν Ή δικαίωμα δωρεάν
Σύνθετη κατάσταση ΔΕΝ ΕΙΝΑΙ- πληρούται όταν δεν πληρούται η προϋπόθεση Α.

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

Π Έλεγχος της συνθήκης της ένωσης ΟΧΙ Α:

α) Α - έγινε, ΟΧΙ Α (ΟΧΙ σκιασμένο) - δεν έγινε.

β) Α ​​- δεν έγινε, ΟΧΙ Α (ΟΧΙ σκιασμένο) - έγινε.

Εντολή υποκαταστήματος

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

Γενική άποψη της εντολής IF:

ΑΝ ΕΠΕΙΤΑ ΣΕ ΔΙΑΦΟΡΕΤΙΚΗ ΠΕΡΙΠΤΩΣΗ

ΤΟ ΤΕΛΟΣ

Στη γλώσσα KUMIR:

Πλήρης διακλάδωση: Μερική διακλάδωση:
αν έπειτα αν έπειτα

σε διαφορετική περίπτωση

όλα όλα

Βοηθητικός αλγόριθμος- ένας αλγόριθμος που λύνει κάποιο υποπρόβλημα του κύριου προβλήματος.

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

ΣΤΟ έρευνες και εργασίες

1. Δώστε όλους τους αλγόριθμους των τριών εντολών που θα μετακινήσουν το Ρομπότ από την αρχική του θέση στο κελί Β.

Υπάρχει αλγόριθμος για αυτήν την εργασία, κατά την οποία το ρομπότ κάνει:

α) δύο βήματα β) τέσσερα βήματα. γ) πέντε βήματα. δ) επτά βήματα;

1. 
   Ο Petya έφτιαξε έναν αλγόριθμο που μεταφέρει το ρομπότ από το κελί Α στο κελί Β με μερικά κελιά ζωγραφισμένα. Τι πρέπει να κάνει ο Κόλια με αυτόν τον αλγόριθμο για να αποκτήσει έναν αλγόριθμο που θα μεταφέρει το ρομπότ από το Β στο Α και θα γεμίσει τα ίδια κελιά;

7. Είναι γνωστοί δύο βοηθητικοί αλγόριθμοι ρομπότ

Σχεδιάστε τι συμβαίνει όταν το ρομπότ εκτελεί τους ακόλουθους βασικούς αλγόριθμους:

ένα) nc 5 φορές πρότυπο_1 σωστά; σωστά;	σι) nc 7 φορές πρότυπο_2 σωστά; σωστά
σε) σωστά; σωστά; σωστά πάνω; πάνω σωστά; σωστά; σωστά πολύ κάτω; πολύ κάτω	ΣΟΛ) σωστά; σωστά σωστά; σωστά

8. Δημιουργήστε αλγόριθμους με τους οποίους το ρομπότ θα ζωγραφίσει πάνω από τα καθορισμένα κελιά:

9. Είναι γνωστό ότι κάπου στα δεξιά του Ρομπότ υπάρχει ένας τοίχος. Δημιουργήστε έναν αλγόριθμο, υπό τον έλεγχο του οποίου το Ρομπότ θα ζωγραφίσει πάνω από μια σειρά από κελιά μέχρι τον τοίχο και θα επιστρέψει στην αρχική του θέση.

10. Είναι γνωστό ότι κάπου στα δεξιά του Ρομπότ υπάρχει ένα σκιασμένο κελί.

ΑΠΟ αφήστε τον αλγόριθμο, υπό τον έλεγχο του οποίου το Ρομπότ θα ζωγραφίσει έναν αριθμό κελιών μέχρι το σκιασμένο κελί και θα επιστρέψει στην αρχική του θέση.

11. Είναι γνωστό ότι το Ρομπότ βρίσκεται κοντά στην αριστερή είσοδο του οριζόντιου διαδρόμου.

12. Είναι γνωστό ότι το Ρομπότ βρίσκεται κάπου στον οριζόντιο διάδρομο. Κανένα από τα κελιά του διαδρόμου δεν είναι βαμμένο.

Δημιουργήστε έναν αλγόριθμο, υπό τον έλεγχο του οποίου το Ρομπότ θα ζωγραφίσει όλα τα κελιά αυτού του διαδρόμου και θα επιστρέψει στην αρχική του θέση.

13. Σε μια σειρά δέκα κελιών στα δεξιά του ρομπότ, ορισμένα κελιά είναι σκιασμένα.

ΑΠΟ αφήστε τον αλγόριθμο που ζωγραφίζει τα κελιά:

α) κάτω από κάθε σκιασμένο κελί.

β) πάνω και κάτω από κάθε σκιασμένο κελί.

14. Τι μπορεί να ειπωθεί για την ορθότητα του παρακάτω τμήματος του αλγορίθμου;

nts αντίοτο κελί είναι σκιασμένο

ΑΝδικαίωμα δωρεάν ΕΠΕΙΤΑ

σωστά; ζωγραφίζω

προς την
ντο

15. Γράψτε ένα πρόγραμμα με το οποίο το Ρομπότ μπορεί να φτάσει στο κελί Β και στους τρεις λαβύρινθους.

16. Γράψτε ένα πρόγραμμα, μετά από το οποίο το Ρομπότ θα μπορεί να πάει κατά μήκος του διαδρόμου από την κάτω αριστερή γωνία του χωραφιού προς την επάνω δεξιά. Ο διάδρομος έχει πλάτος ενός κελιού και εκτείνεται προς την κατεύθυνση από αριστερά-κάτω-δεξιά-επάνω. Ένα παράδειγμα πιθανού διαδρόμου φαίνεται στο σχήμα.

W

adachi GIA

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

1. 
   Προς την
   Απαραίτητη

   Δεδομένος
   διάδρομος 2. Το ρομπότ βρίσκεται στο πάνω κελί ενός στενού κάθετου διαδρόμου. Το πλάτος του διαδρόμου είναι ένα κελί, το μήκος του διαδρόμου μπορεί να είναι αυθαίρετο.

Μια πιθανή παραλλαγή της αρχικής θέσης του ρομπότ φαίνεται στο σχήμα (το ρομπότ υποδεικνύεται με το γράμμα "P")

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

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

H


Απαραίτητη

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

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

1. 
   Υπάρχει ένας μακρύς κάθετος τοίχος στο ατελείωτο χωράφι. Το μήκος του τοίχου είναι άγνωστο. Το ρομπότ βρίσκεται σε ένα από τα κλουβιά που βρίσκονται ακριβώς στα δεξιά του τοίχου. Η αρχική θέση του ρομπότ είναι επίσης άγνωστη. Μία από τις πιθανές θέσεις του ρομπότ φαίνεται στο σχήμα (το ρομπότ σημειώνεται με το γράμμα "P"): Γράψτε έναν αλγόριθμο για εργασία που ζωγραφίζει όλα τα κελιά δίπλα στον τοίχο: στα αριστερά, ξεκινώντας από την κορυφή άβαφο και μέσα από ένα? στα δεξιά, ξεκινώντας από κάτω σκιασμένο και μέσω ενός. Το ρομπότ πρέπει να ζωγραφίζει μόνο τα κελιά που πληρούν αυτήν την προϋπόθεση. Για παράδειγμα, για το παραπάνω σχήμα, το ρομπότ πρέπει να συμπληρώσει τα ακόλουθα κελιά (βλ. εικόνα): Η τελική θέση του ρομπότ μπορεί να είναι αυθαίρετη. Ο αλγόριθμος πρέπει να λύσει το πρόβλημα για ένα αυθαίρετο μέγεθος τοίχου και οποιαδήποτε έγκυρη αρχική θέση του ρομπότ. Κατά την εκτέλεση του αλγόριθμου, το ρομπότ δεν πρέπει να συμπτύσσεται.

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

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

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

		R

1. 
   Υπάρχει ένας μακρύς κάθετος τοίχος στο ατελείωτο χωράφι. Το μήκος του τοίχου είναι άγνωστο. Το ρομπότ βρίσκεται σε ένα από τα κλουβιά που βρίσκονται ακριβώς στα αριστερά του τοίχου. Η αρχική θέση του ρομπότ είναι επίσης άγνωστη. Μία από τις πιθανές θέσεις του ρομπότ φαίνεται στο σχήμα (το ρομπότ σημειώνεται με το γράμμα "P"):

Γράψτε για εργασία έναν αλγόριθμο που ζωγραφίζει όλα τα κελιά που βρίσκονται δίπλα στον τοίχο:

• 
  όλα στα αριστερά?
• 
  στα δεξιά, ξεκινώντας από το πάνω άβαφο και μέσα από ένα.

Το ρομπότ πρέπει να ζωγραφίζει μόνο τα κελιά που πληρούν αυτήν την προϋπόθεση.

σι
1102_GIA2011

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

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

ΣΤΟ
1103_GIA_2011

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

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