загрузка...
загрузка...
На головну

Алгоритми і виконавці

  1. Алгоритми діагностики найбільш поширених моногенних ННСТ.
  2. Алгоритми накопичення суми і твори
  3. алгоритми навчання
  4. алгоритми проектування
  5. Алгоритми роботи з двійковими впорядкованими деревами (деревами пошуку)
  6. Алгоритми роботи зі списками

1. Алгоритми і исполнители....................................................................................................... 4

2 Що таке алгоритм?............................................................................................................. 4

2 Исполнители......................................................................................................................... 4

2 Старовинні задачи................................................................................................................ 6

2 Які бувають алгоритмы?.................................................................................................. 6

2 Программы............................................................................................................................ 7

2 Завдання про перевозчике........................................................................................................... 8

2 Ханойські вежі (рекурсивні алгоритми) ........................................... ........................ 9

2. Виконавець Робот.................................................................................................................. 11

2 Посеред Робота....................................................................................................................... 11

2 Основні команди Робота............................................................................................... 11

2 Найпростіша програма (завдання z1.maz) ......................................... .................................. 12

2 Які помилки можуть бути у Робота? .......................................... ..................................... 12

2 Робота в системі Исполнители......................................................................................... 12

2 Задачи.................................................................................................................................. 13

3. Циклы..................................................................................................................................... 15

2 Що таке цикл (завдання z2-3.maz)? ..................................... ............................................... 15

2 Правила використання оператора циклу ............................................. .......................... 15

2 Вкладені цикли (завдання z3-3.maz) ....................................... ......................................... 16

4. Алгоритми зі зворотним связью.......................................................................................... 17

2 Що таке зворотний зв'язок і навіщо вона потрібна? ........................................ ......................... 17

2 Як Робот використовує зворотний зв'язок? ........................................... ................................ 17

2 Цикл з условием................................................................................................................. 18

2 Правила використання циклу Бувай.................................................. ............................. 18

2 Задачи.................................................................................................................................. 20

5. Умовний оператор............................................................................................................. 22

2 Що таке умовний оператор (завдання z5-3.maz)? .................................... ....................... 22

2 Правила використання умовного оператора ............................................. ................... 23

2 Скорочена форма........................................................................................................... 23

2 Що таке складні умови (завдання z6-3.maz)? .................................... ........................... 24

2 Правила використання складних умов ............................................. ........................ 24

6. Змінні і арифметичні вирази ............................................ ....................... 26

2 Навіщо потрібні змінні (завдання z7-3.maz)? ..................................... ............................ 26

2 Що таке переменная?....................................................................................................... 27

2 Оголошення переменных................................................................................................... 27

2 Правила роботи з переменными...................................................................................... 28

2 Арифметичні выражения............................................................................................ 29

2 Цикл з параметром............................................................................................................. 30

2 Задачи.................................................................................................................................. 31

7. Діалогові программы..................................................................................................... 32

2 Що таке діалогова программа?.................................................................................... 32

2 Висновок на екран (завдання z8-3.maz) ...................................... ............................................... 32

2 Правила використання оператора виведення ............................................. ........................ 33

2 Введення данных....................................................................................................................... 33

2 Правила використання оператора введення ............................................. ........................... 34

2 Задачи.................................................................................................................................. 34

2 Обчислення з циклами...................................................................................................... 35

2 Задачи.................................................................................................................................. 36

8. Процедуры............................................................................................................................. 37

2 Навіщо потрібні процедуры?................................................................................................. 37

2 Як ввести нову команду (завдання z10-3.maz)? .................................... .......................... 37

2 Правила використання процедур .............................................. ..................................... 39

2 Процедури з параметрами (завдання z11-3.maz) ...................................... .......................... 40

2 Правила використання процедур з параметрами ............................................ ............. 41

9. Методи складання программ......................................................................................... 43

2 Метод "зверху вниз".......................................................................................................... 43

2 Метод "знизу вверх".......................................................................................................... 43

2 Комбінований способ................................................................................................ 44

2 Приклад складання программы...................................................................................... 44

10. Виконавець Черепаха.................................................................................................... 49

2 Як працює Черепаха?..................................................................................................... 49

2 Які команди розуміє Черепаха? ............................................ ................................... 49

2 Як управляти Черепахой?................................................................................................ 49

2 Як розфарбувати рисунок?................................................................................................... 49

2 Окружности........................................................................................................................ 50

2 Циклы.................................................................................................................................. 51

2 Вкладені циклы............................................................................................................. 52

2 Процедуры.......................................................................................................................... 52

2 Процедури з параметрами................................................................................................ 55

2 Переменные........................................................................................................................ 58

11. Виконавець Чертежник................................................................................................ 65

2 Прямокутна система координат .............................................. .................................... 65

2 Як управляти Чертежником?........................................................................................... 65

2 Використання процедур.................................................................................................. 67

2 Процедури з параметрами................................................................................................ 68

2 Цикли і переменные......................................................................................................... 69

2 Порівняння креслярем і Черепахи ............................................. .................................... 70

2 Змінні і використання пам'яті ............................................. ................................ 71

2 Цикл з параметром............................................................................................................. 72

2 Задачи.................................................................................................................................. 73

1. Алгоритми і виконавці

2 Що таке алгоритм?

"Перш, ніж що-небудь зробити, треба скласти план", - говорила Аліса з казки Льюїса Керролла. І в житті ми весь час складаємо плани наших дій, наприклад, вранці більшість з нас діє за таким планом:

встати

одягнутися

вмитися

поснідати

вийти з дому в школу або на роботу

У такому ж вигляді можна записати план для того, щоб заварити чай, зробити бутерброд з ковбасою, купити собі морозиво, вимити брудні руки, ...

В інформатиці план дій називають алгоритмом. Алгоритм складається з окремих кроків - Команд. Жодну з них не можна пропустити, найчастіше ніякі команди не можна поміняти місцями (що при цьому станеться?).

Для кожного кроку цього алгоритму можна запропонувати більш докладний план. Наприклад, для дії "поснідати":

закип'ятити чайник

зробити бутерброд

з'їсти бутерброд з чаєм

вимити посуд

І тут кожен крок, в свою чергу, теж можна розшифрувати - скласти більш детальний план. Де ж зупинитися? Відповідь проста - це залежить від виконавця - Того, хто буде виконуватицей алгоритм. Треба зупинитися на такому плані, в якому виконавцю буде зрозуміло, як виконати кожен крок.

2 Виконавці

4 Що таке виконавець?

Виконавці часто зустрічаються в казках. В одній з них Іван-Царевич каже Хатинці-На-Курячих-ніжки: "Хатинка, хатинка! Встань до лісу задом, до мене передом!". При цьому команда повинна бути задана дуже точно,щоб виконавець її зрозумів. У казці "Алі-Баба і сорок розбійників" чарівна двері відкривалися по команді "Сезам, відкрийся!". Жадібний Касим, таємно проник в печеру, забув цю фразу і не зміг вийти з печери.

І Хатинка-На-Курячих-ніжки, і чарівна двері мають багато спільного: вони вміють розуміти і виконувати деякі точно задані команди, тобто є виконавцями.

? виконавець - це той, хто вміє розуміти і виконувати деякі команди.

? Середа виконавця - це предмети, які оточують виконавця і з якими він працює.

? Список (або система) Команд Виконавця (СКІ) -набір команд, зрозумілих виконавцю. Виконавець може виконати тільки ті команди, які входять в його СКІ.

Виконавцями можуть бути

· люди:учень, робочий, учитель, бригада;

· тварини:дресирована собака (санітар, розшукова, мисливський), кішка;

· машини:верстати, роботи, комп'ютери;

Взагалі кажучи, виконавцями можуть бути навітьрослини:соняшник (розгортається на сонці), латаття (закриваються на ніч).

Людина як виконавець відрізняється від всіх інших виконавців декількома ознаками, наприклад:

1. Чи розуміє команди в різних варіантах (наприклад "Сядь!", "Сідай!", "Сядь!").

2. Виконуючи команди, «домислює» їх з урахуванням свого досвіду.

3. Чи може відмовитися виконувати команду, якщо вона йому не подобається ( "Їж манну кашу!", "Вистріли в вікно з рогатки!"). Тобто людина має волю і відповідає за свої дії.

Для вирішення більшості завдань недостатньо віддати одну команду виконавцю, треба скласти для нього алгоритм - план дій, який складається з команд, які йому зрозумілі (входять в його СКІ). Таким чином, можна дати визначення алгоритму.

? алгоритм -це точно визначений план дій виконавця, спрямований на розв'язання якоїсь задачі. В алгоритм можна включати тільки ті команди, які є в СКІ виконавця.

4 Помилки при роботі виконавців

Робота виконавця не завжди проходить гладко - іноді зустрічаються помилки. Існує три види помилок виконавців.

 "НЕ РОЗУМІЮ"  Заданої команди немає в списку команд виконавця, і він її не зрозумів. Ймовірно, ми помилилися в запису тексту команди.
 "НЕ МОЖУ"  Виконавець зрозумів команду, але не може її виконати. Наприклад, роботу дана команда "вперед", а попереду стоїть стінка, і він не може йти. Або собаці скомандували "Сидіти!", А вона вже сидить.
 ЛОГІЧНІ ПОМИЛКИ  Виконавець зрозумів команду і виконав її, але зробив не те, що ми від нього хотіли. Причина цього - наша помилка в складанні завдання (алгоритму).

4 Як ввести нового виконавця?

Введемо тепер нового виконавця, якого назвемо дядько Федір(Як у Е. Успенського). Щоб ввести нового виконавця треба:

· задати середу виконавця - клас, столи, стільці;

· скласти СКІ:

a встану

a сядь

a піднято РУКУ

a опустив руку

a стрибну

a МЯУКНІ

· Визначити, як передаються команди виконавцю (голосом, жестом, письмово, по рації або якось інакше);

· Визначити, як виконавець виконує команди;

· Визначити, в яких випадках виникає помилка "НЕ МОЖУ".

2 Старовинні завдання

переправа. Селянинові треба переправити через річку вовка, козу і капусту. Але крім людини човен вміщує тільки чи вовка, або козу, або капусту. Залишити на березі без нагляду вовка з козою чи козу з капустою можна (з'їдять!). Як селянину переправити свій вантаж?

переправа сім'ї. Батько, мати і двоє дітей хочуть переправитися через річку. Всі вміють гребти, але човен витримує або одного дорослого, або двох дітей. Як вони можуть переправитися на інший берег?

фальшиві монети. З 9 монет однакової гідності одна фальшива (легша). Як її знайти за два зважування за допомогою чашкових ваг без гир?

2 Які бувають алгоритми?

4 Лінійний алгоритм

У лінійному алгоритмі команди виконуються послідовно, одна за одною. Прикладом лінійного алгоритму може служити алгоритм заварки чаю:

закип'ятити воду

сполоснути чайник для заварювання гарячою водою

насипати заварку

залити заварку окропом

закрити чайник чимось теплим

почекати 5 хвилин

... Тепер можна пити чай

4 Розгалужуються алгоритм

У алгоритмів, що розгалужуються порядок проходження команд може бути різний залежно від того, яка навколишнє оточення. Прикладом разветвляющегося алгоритму може служити алгоритм переходу вулиці:

підійти до пішохідного переходу

якщо є світлофор, то

чекати зеленого світла

перейти вулицю

інакше

чекати, поки зліва не буде машин

перейти вулицю до середини

чекати, поки впоратися не буде машин

перейти другу половину вулиці

4 Циклічний алгоритм

У циклічному алгоритмі деякі дії повторюються кілька разів (в інформатиці кажуть, що виконується цикл). Існують два види циклічних алгоритмів. В одному з них ми знаємо заздалегідь, скільки разів треба зробити ці дії, в іншому ми повинні зупинитися лише тоді, коли виконається деяка умова.

прикладом циклу першого типу є наше життя в робочі дні (від понеділка до суботи) - ми виконуємо 6 разів майже одні й ті ж дії.

приклад циклу другого типу - Алгоритм розпилювання колоди: ми не можемо заздалегідь сказати, скільки разів нам треба провести пилкою від себе і на себе - це залежить від щільності дерева, якості пилки і наших зусиль. Однак ми точно знаємо, що треба закінчити роботу, коли чергове відпиляну поліно впаде на землю.

       
 
 / * Кількість кроків відомо * / повторити 6 разпроснутьсявстатьпозавтракатьпойті в школувернуться домойпообедатьсделать урокіпоіграть в футболлечь спати / * програма на неділю * / спати ...
 
 / * Кількість кроків невідомо, але обмежена умовою * / покласти колоду на козлинаметіть місце распілапока поліно НЕ отвалітсяпіліть від себяпіліть на себяположіть поліно в стіс
 


2 Програми

Людина здатна розуміти сенс команди і часто може «додумати», що від нього хотіли навіть тоді, коли команда задана неточно. Для того, щоб алгоритм був зрозумілий роботу, комп'ютера або іншій машині, недостатньо тільки написати команди, треба ще й оформити алгоритм в такому вигляді, в якому його розуміє машина, тобто записати в формальному вигляді.

У формальної записи алгоритму можна використовувати тільки ті команди, які входять в СКІ виконавця. Крім того, треба дотримуватися спеціальні правила оформлення, які дозволять виконавцю розпізнати команди і визначити послідовність їх виконання.

 / * Ця назва алгоритму * /

 
 


/ * Ця дужка позначає початок алгоритму * /

 
 


посадити ріпку / * команда закінчується знаком; * /

виростити ріпку;

намагатися витягти ріпку;

покликати Бабку; намагатися витягти ріпку;

покликати Онуку; намагатися витягти ріпку;

покликати Жучку; намагатися витягти ріпку;

покликати Кішку; намагатися витягти ріпку;

покликати Мишку; витягнути ріпку;

 / * Тут алгоритм закінчується * /

Виконавцем для цього алгоритму є дід - саме він повинен виконувати ці команди.

4 Правила запису алгоритмів для комп'ютерів

Алгоритм можна записати різними способами і навіть на різних мовах. Хоча при цьому виконавець може, звичайно, їх не зрозуміти. Ви знаєте, що є спеціальні види виконавців алгоритмів - комп'ютери. вони виконують програми.

? програма - Це алгоритм, записаний у формі, зрозумілою комп'ютера.

Існують спеціальні правила запису програм для комп'ютерів. На малюнку вгорі сторінки їх характерні елементи виділені в рамках:

1. будь-який алгоритм має назва;

2. алгоритм починається з відкриває фігурної дужки "{ "і закінчується закриває фігурної дужки "} "; команди, розташовані між цими дужками, називаються тілом алгоритму;

3. в алгоритм можуть входити тільки ті команди, які є в СКІ виконавця;

4. кожна команда закінчується знаком "; ", Який позначає кінець команди;

5. для того, щоб нам було легше розбиратися в програмах, використовують коментарі - текстові пояснення, які починаються знаками / * і закінчуються знаками * /; виконавець не звертає уваги на коментарі в алгоритмі.

2 Завдання про перевізника

Давно відома старовинна задача про селянина, якого треба перевезти на інший берег річки вовка, козу и капусту на човні, в яку поміщається сам селянин та на одне вільне місце він може взяти або вовка, або козу, або капусту. Складність полягає в тому, що коза і вовк поводяться пристойно тільки в присутності селянина, в його відсутність коза з'їсть капусту, а вовк з'їсть козу.

Коли селянин їде на інший берег в перший раз, він може взяти козу, так як тільки вовк і капуста можуть залишитися наодинці.

Потім він повертається і бере з собою вовка (або капусту - другий варіант вирішення). Але він не може залишити вовка (або капусту) з козою на іншому березі і тому змушений взяти з собою козу назад.

Повернувшись назад і висадив козу, він забирає вовка (або капусту) і перевозить його. Тепер на іншому березі знову залишаться вовк з капустою і селянину залишиться тільки забрати козу.

 Перевіз-1 {перевезти козу; повернутися; перевезти вовка; повернутися з козою; перевезти капусту; повернутися; перевезти козу; }    Перевіз-2 {перевезти козу; повернутися; перевезти капусту; повернутися з козою; перевезти вовка; повернутися; перевезти козу; }

2 Ханойські вежі (рекурсивні алгоритми)

 Одна з улюблених дитячих іграшок - пірамідка з кольоровими кільцями різного діаметру, насадженими на стрижень.

Однак є країни, де в цю гру грають шановні й поважні старці. Придумали її ченці стародавнього Ханоя (тепер це територія В'єтнаму). У них була одна повна пірамідка з 64 кільцями і два порожніх стрижня. Вважалося, що коли все кільця вдасться перенести на інший стрижень, дотримуючись усіх правил (див. Нижче), настане кінець світу.

4 Правила гри

Потрібно перенести пірамідку з одного стрижня на інший, використовуючи третій стрижень в якості проміжного і дотримуючись таких правил:

· За одну дію можна переносити тільки одне кільце;

· Кільце можна укладати або на вільний стержень, або на більше кільце.

Вирішимо спочатку найпростіше завдання - для пірамідки з двох кілець.

Позначимо стрижні номерами:

1лівий стрижень, на якому знаходиться пірамідка на початку гри

2середній стрижень, допоміжний

3правий стрижень, на нього треба перенести пірамідку

Будемо позначати ходи стрілками. У підстави стрілки писатимемо номер вихідного стрижня, з якого беремо кільце, а у вістря - номер стрижня, на який його переносимо.

       
 
 Ханой-2 {1 a 2; 1 a 3; 2 a 3; }
   
 
   
 


Трохи складніше вирішити задачу для пірамідки з трьох кілець. Зауважте, що нижнє кільце можна класти тільки на порожній стрижень. А для цього нам треба верхні два кільця перекласти на середній стрижень, скориставшись алгоритмом Ханой-2. Потім переносимо велике кільце на третій стрижень і, знову використовуючи алгоритм Ханой-2, Переносимо два менших кільця на третій стрижень.

           
 
 Ханой-3 {/ * переносимо два кільця * // * на другий стрижень * / 1 a 3; 1 a 2; 3 a 2; / * переносимо велике кільце * // * на третій стрижень * / 1 a 3; / * переносимо два маленьких кільця * // * з другого на третій * / 2 a 1; 2 a 3; 1 a 3; }
   
 
   
 
   
 


У цьому алгоритмі ми два рази використовували алгоритм Ханой-2, Але при цьому різні стрижні виступали в якості кінцевого і допоміжного.

Рішення для піраміди з n кілець можна записати в такому вигляді:

Ханой (n, початковий, допоміжний, кінцевий)

{

якщо n> 1, то

Ханой (n-1, початковий, допоміжний, кінцевий);

початковий a кінцевий;

якщо n> 1, то

Ханой (n-1, допоміжний, кінцевий, початковий);

}

Тут в якості початкового, кінцевого і допоміжного можна використовувати будь-які стрижні. алгоритм Ханой фактично пропонує вирішувати задачу для n кілець через два завдання для меншого числа кілець (n-1). Такий прийом в програмуванні називається рекурсія.

4 Що таке рекурсія?

? рекурсія - спеціальний прийом в програмуванні, коли алгоритм рішення задачі містить алгоритм вирішення такого завдання, але з іншими вихідними даними.

Тепер ми познайомилися з четвертим видом алгоритмів - рекурсивним алгоритмом.Зауважимо, що для перенесення пірамідки з двухколец потрібно всього 3 ходу, для трьох кілець - вже 3 + 1 + 3 = 7 ходів, для чотирьох - 15 і т.д. Можна показати, що для перенесення пірамідки з n кілець нам буде потрібно  ходів. У ченців древнього Ханоя була пірамідка з 64 кілець і вони вірили, що коли вдасться перенести всю пірамідку на третій стрижень, настане кінець світу. Звичайно це легенда, але число  справді дуже велике і для того, щоб зробити стільки ходів, не вистачить кількох людських життів.

Рекурсію має сенс використовувати тоді, коли в результаті вихідна задача зводиться до більш простий. Доведено, що будь-який рекурсивний алгоритм можна замінити алгоритмом без рекурсії (який іноді може бути дуже громіздким). Так як використання рекурсії в реальних програмах пов'язано з деякими технічними проблемами, краще її не застосовувати, якщо є простий нерекурсивний алгоритм.

2. Виконавець Робот

2 серед роботів

Навчальний виконавець Робот призначений для того, щоб без участі людини садити квіти в підготовлені для них грядки. У програмі, з якою ви будете працювати, Робот зображений у вигляді машинки, яка їздить по полю. Поле розмічено на квадрати, кожен з яких може бути: 1) вільним місцем  ; 2) грядкою  або 3) стінкою  . Робот може переходити з клітини в клітину по грядках або за вільними клітинам, ходити по клумбах з квітами забороняється. Він повинен посадити квіти на всіх грядках і повернутися на Базу, позначену значком  , Для поповнення запасів.

Робот може рухатися вперед і назад, а також розвертатися на 90 і 180 градусів вліво або вправо. Звичайно, в реальній обстановці на Робота впливає вітер, дощ, нерівність землі і т.п., але ми їх не будемо враховувати. Таке спрощене уявлення називається моделлю Робота.

2 Основні команди Робота

Як і будь-який виконавець, Робот розуміє тільки обмежений набір команд, які входять в його СКІ (список команд виконавця). Поки нам вистачить кількох команд, перерахованих нижче:

? СКІ Робота:

направо; повернутися на 90 градусів вправо

ліворуч; повернутися на 90 градусів вліво

кругом; розвернутися кругом (на 180 градусів)

вперед (n); перейти на n клітин вперед

назад (n); перейти на n клітин назад

посади; посадити квіти на грядці в тому місці, де стоїть Робот

Пізніше ми трохи розширимо СКІ і додамо в нього нові команди. Робот не може ходити по діагоналі, проходити крізь стіни і топтати квіти на клумбах.

2 Найпростіша програма (завдання z1.maz)

 ТріКлумби {вперед(3);посади;направо;вперед(2);налево;вперед(2);налево;вперед(1); посади; вперед (2); посади; вперед (1); наліво; вперед (1); }

Ім'я програми повинно складатися з одного «слова», зверніть увагу, що всередині немає прогалин. Кожна команда закінчується крапкою з комою. Можна записувати кілька команд в одну строчку.

2 Які помилки можуть бути у Робота?

1. Синтаксичні ( "НЕ РОЗУМІЮ")- З'являються при помилках в написанні команд, наприклад

вліво;

Вперет (3);

направо (2);

2. Відмови ( "НЕ МОЖУ") - з'являються, наприклад, якщо Роботу наказують йти прямо на стінку або садити квіти там, де немає грядки.

3. Логічні - Виникають тоді, коли Робот розуміє команди і робить все, що йому сказали, але результат зовсім не той, який ми очікували.

Синтаксичні помилки і відмови виявляє сам виконавець. Коли ви будете працювати з комп'ютером, ви побачите повідомлення про таких помилках. Найскладніші помилки - логічні - доведеться шукати самим.

2 Робота в системі Виконавці

 Щоб перевірити програму і подивитися виконавця робот в роботі, ми будемо використовувати систему виконавці, Встановлену на комп'ютерах. Знайдіть на робочому столі ярлик програми і двічі клацніть по ньому. Коли програма запуститься, ви побачите вікно, показане на малюнку справа.

Вікно складається з трьох частин: верху розташовані меню і кнопки для управління виконавцем, зліва - редактор програми, а праворуч - поле виконавця.

Спочатку завантажте завдання для Робота, натиснувши кнопку  і вибравши заданий файл.

Потім треба набрати програму в поле редактора. Для того, щоб прискорити введення команд, зручно використовувати меню Шаблони.Там є все команди мови програмування і команди виконавцяробот.

Для того, щоб комп'ютер вирівняв всі рядки програми (привів програму в «пристойний» вигляд), можна натиснути клавішу F6 або клацнути по кнопці  на панелі інструментів.

Коли програма готова, запишіть її на диск, натиснувши клавішу F2 або кнопку  на панелі інструментів. У відповідь на це при першому записі файлу на диск з'являється вікно для введення імені файлу, де вам треба ввести будь-яке ім'я і потім клацнути на кнопку ОК. При записі файлу в наступний раз ім'я вже відомо, тому система перейменує стару версію, зробивши у неї розширення *.bak, А нову запише з тим же ім'ям.

Для виконання програми треба натиснути клавішу F9 або кнопку  на панелі інструментів. Якщо в програмі немає синтаксичних помилок, які машина виявляє, ви побачите, як Робот (у вигляді машинки) виконує програму.

Якщо помилки є, червоним кольором буде виділена рядок, в якій виявлена ??помилка, і виведено повідомлення на екран. Подивіться уважно на цей рядок і на попередню, натисніть на клавішу Enter і виправте помилку.

Якщо помилок немає, але Робот не виконав завдання, в програмі є логічна помилка. Для її виявлення скористайтеся режимом налагодження: При натисканні на клавішу F8 виконавець виконує один рядок програми і зупиняється. Такий режим називається покроковим. Таким чином, можна визначити, в який рядку програма починає виконуватися не так, як вам хочеться. Знайшовши помилку, натисніть клавішу Esc для виходу з режиму відладки. Коли все вийшло, запишіть новий варіант на диск і закінчите роботу, натиснувши кнопку  в правому верхньому куті вікна або натиснувши клавіші Alt + F4.

Якщо ви забули якусь команду або хочете дізнатися те, що вам ще не розповідали, клацніть на кнопці  або натисніть клавішу F1, Щоб увійти в довідкову систему.

Якщо включення програми дороблена і записана на диск, ви зможете в наступний раз завантажити стару програму, натиснувши на клавішу F3 або натиснувши кнопку  . Щоб почати нову програму і очистити поле редактора, натисніть на кнопку .

2  завдання

1.Визначте, чого не вистачає в умові цієї задачі. Доповніть умову і вирішите задачу.

2.Відомо, що Робот вийшов з деякою точки А і туди ж прийшов після виконання завдання. Відновити бракуючу рядок (або рядки) в програмі.

       
 
 Навколо {вперед (2); ... вперед (2); наліво; }
 
 Вокруг2 {вперед (2); ... наліво; вперед (3); }


3.Ізвестна програма переходу Робота з однієї клітини в іншу. Опишіть, як скласти програму зворотного ходу Робота.

4. Перевести Робота на Базу усіма можливими способами з трьох команд. Чи можна зробити це в 2 кроки (в 5 кроків? 10 кроків? 15 кроків? Тисячі дев'ятсот дев'яносто один крок?).

5. Скласти і вирішити своє завдання для Робота (придумати цікаву назву).

3. Цикли

2 Що таке цикл (завдання z2-3.maz)?

Часто виконавцю треба виконати якусь послідовність команд кілька разів. Наприклад, в завданні на малюнку Робот повинен підійти до ряду клітин, які треба зафарбувати, і потім виконати 6 разів команди вперед (1) и посади.

В даному випадку ці команди треба повторити тільки 6 рази і можна легко 6 раз написати однакові команди. Але уявіть, що треба зробити однакові операції 100 або 200 разів! У програмуванні в таких випадках використовується спеціальна команда (оператор циклу), Яка говорить виконавцю, що якусь частину програми треба зробити кілька разів.

? цикл - Це багаторазове повторення однакових дій

? тіло циклу - Це команди, які виконуються кілька разів.

? крок циклу - Це одноразове виконання тіла циклу.

Для нашої задачі підходить цикл повтори (або repeat), В якому з відомим числом кроків. Програма з використанням оператора циклу виглядає так:

ряд

{

вперед (1); / * Підійти до місця роботи * /

повтори (6)

{

вперед (1);

посади;

}

}

2 Правила використання оператора циклу

1. Цикл повтори (або repeat) Використовується тоді, коли число кроків наперед відомо чи може бути обчислено.

2. Оператор циклу починається заголовком циклу - ключовим словом повтори, За яким в дужках вказується потрібну кількість кроків.

3. Тіло циклу починається відкриває фігурною дужкою {і закінчується закриває }.

4. Якщо тіло циклу включає всього один оператор, дужки можна не ставити.

5. Для того, щоб легше розбиратися в програмі, застосовують спеціальну систему запису з відступами: Тіло циклу зміщують вправо на 2-3 символи - це дозволяє відразу бачити, де починається і де закінчується цикл. Для того, щоб комп'ютер автоматично зробив відступи в програмі, можна натиснути клавішу F6.

2 Вкладені цикли (завдання z3-3.maz)

Розглянемо задачу для Робота, в якій потрібно садити квіти в багатьох місцях майданчика (на малюнку праворуч).

 Як би таке завдання вирішувалася в реальних умовах? Можна запропонувати такий варіант: Робот спочатку садить квіти в першому (верхньому) ряду, потім в другому і т.д.

Для обробки одного ряду можна використовувати цикл повтори (4). У програмі треба обробити 3 ряди, тобто написати три однакових циклу. Тоді виходить, що можна знову використовувати цикл повтори (3) для трьох рядів, але всередині нього також буде знаходитися цикл.

? вкладений цикл - Це такий цикл, який знаходиться всередині іншого циклу.

 Нижче подано два можливих вирішення цього завдання. Вони показують, що внутрішній і зовнішній цикли можна переставляти, якщо порядок обробки грядок байдужий. Головне - перевести Робота в потрібну клітину і в потрібне положення перед тим, як почнеться наступний цикл. Крім того, не можна забувати, що Робот не може ходити по клумбах.

4. Алгоритми зі зворотним зв'язком

2 Що таке зворотний зв'язок і навіщо вона потрібна?

До сих пір ми наказували Роботу виконати якесь завдання, припускаючи, що обстановка повністю відома: ми точно знаємо скільки кроків до стінок, яку вони мають форму і де розташовані. Ми не аналізували результати дій Робота і обстановку на полі. Такий підхід нагадує дії начальника, який віддає накази, але не перевіряє їх виконання, або шофера, який веде машину з закритими очима, покладаючись на своє знання дороги.

При вирішенні складних завдань ситуація часто відома не повністю і треба аналізувати обстановку, яка змінюється під час роботи виконавця. Людина дуже часто не знає, скільки кроків йому треба пройти і не замислюється про це, тому що він знає, куди він іде, тобто знає, де (за якої умови) Зупинитися.

? Зворотній зв'язок - це інформація про навколишнє оточення, яку виконавець використовує для вибору потрібного варіанту виконання алгоритму ..

Дія зворотного зв'язку можна описати такою схемою:

Зворотній зв'язок дає нам можливість контролювати результати дій виконавця під час його роботи і стежити за раптовими змінами обстановки. Якщо обстановка і мета не збігаються, то блок порівняння виробляє сигнал помилки, на основі якого виконавець отримує команду на подальші дії. Після виконання чергової команди обстановка змінюється і знову порівнюється з бажаним результатом.

2 Як Робот використовує зворотний зв'язок?

робот має датчики, Які дозволяють йому отримувати інформацію про обстановку. Датчики визначають, наприклад, чи є стіна в якомусь напрямку. Щоб використовувати цю інформацію в програмі, в СКІ Робота є спеціальні логічні команди.

? логічна команда- Це умова, яке може бути вірним (істинним) або неправильним (хибним).

У Робота є датчики, які дозволяють визначати, що знаходиться в тій клітці, де він зараз перебуває, і в сусідніх клітках. Ось все логічні команди Робота:

справа_стена справа_клумба справа_свободно

слева_стена слева_клумба слева_свободно

впереді_стена впереді_клумба впереді_свободно

сзаді_стена сзаді_клумба сзаді_свободно

грядка база

команди грядка и база визначають, чи є грядка (або база) в клітці, де зараз знаходиться Робот.

приклад 1 (Завдання z4-3.maz). Роботу треба прийти на Базу, яка розташована на краю стінки. Відстань від Робота до стінки і довжина стінки невідомі.

Спочатку Роботу треба підійти до стінки. Якби ми управляли Роботом вручну, то треба було б чинити так:

1) видати запит впереді_свободно;

2) якщо Робот отримав від датчиків відповідь "Немає", То він виконав завдання і знаходиться біля стіни;

3) якщо отримана відповідь "Так", То зробити крок вперед і повторити весь процес.

На другому етапі Роботу повернутися направо і йти вперед, поки він не прийде на Базу. Зауважимо, що відстань до Бази також невідомо, але Робот за допомогою логічної команди база може виявити, що він вже прийшов на місце. Рішення завдання у вигляді програми дано нижче в рамці.

2  Цикл з умовою

Ми знаємо, що багаторазове виконання групи команд називається циклом. Однак тут ми не можемо застосувати цикл повтори, Так як число кроків наперед невідомо - воно визначається під час роботи програми.

Проте, є чітку умову, за якою Робот повинен закінчити роботу: якщо перед ним виявляється стіна. Таким чином, Робот повинен виконувати цикл поки попереду вільно. Для цієї мети служить спеціальний вид циклу - цикл Бувай (або while, Від англійського while - Бувай). Такий вид циклу називається циклом з умовою, Оскільки він закінчується, коли порушується умова в заголовку циклу.

Для того, щоб прийти на Базу, в програмі використовується цикл поки не база. Ця умова істинно (вірно), якщо Робот ще на прийшов на Базу і треба рухатися далі. Якщо Робот вступив в клітку, де знаходиться база, умова база стало справжнім, а умова НЕ база - Хибним, тому цикл закінчиться.

2 Правила використання циклу Бувай

1. Цикл Бувай використовується тоді, коли число повторень циклу заздалегідь невідомо, але обмежена якимось умовою.

2. Оператор циклу починається заголовком циклу - ключовим словом Бувай, За яким в дужках вказується логічна команда- Умова, при якому виконується цикл.

3. Якщо умова перестає бути вірним (істинним), Виконання циклу закінчується і виконавець переходить до наступної команди.

4. Умова перевіряєтьсяна початку циклу, Тобто якщо перед виконанням циклу умова помилково, То цикл не виконається жодного разу.

5. У циклі виконуються всі оператори, укладені у фігурні дужки;

Якщо тіло циклу включає всього один оператор, дужки можна не ставити.

5. Для того, щоб легше розбиратися в програмі, всі команди, що входять до циклу, зміщують вправо на 2-3 символи - це дозволяє відразу бачити, де починається і де закінчується цикл.

Приклад 2. При такій програмі в тій же задачі, що і в прикладі 1, Робот не буде нічого робити, так як зараз праворуч від нього немає стінки, і умова справа_стена не виконується.

нічого

{

поки (справа_стена)

вперед (1);

}

Важливо пам'ятати, що умова НЕперевіряється всередині циклу, тобто датчик спрацьовує тільки тоді, коли виконується команда в заголовку циклу.

приклад 3. У цьому прикладі програма для Робота складена так, що він вріжеться в стінку і повідомить про помилку "НЕ МОЖУ".

 Диверсія {поки (впереді_свободно) {вперед (2); }}

З циклом Бувай пов'язане одна з найбільш неприємних помилок програмістів - зациклення. Воно відбувається в тих випадках, коли умова в заголовку циклу Бувай ніколи не стає хибним.

Приклад 4. Ця програма призводить до зациклення, так як умова справа_стена виконується завжди і Робот не змінює свого місця.

 Зациклення {поки (справа_стена) {кругом; кругом; }}

Використання циклу Бувай дозволяє нам вирішувати завдання, в яких деякі дані (наприклад, довжина стінок) заздалегідь невідомі.

Приклад 5. Посадити квіти у всіх клітинах по периметру прямокутної стіни, вважаючи, що відстань до неї і її розміри невідомі.

Для вирішення цього завдання треба використовувати кілька циклів з умовою. Спочатку Роботу треба дійти до стінки, потім перейти до кута. Далі він піде «тримаючись за стінку», обходячи таким чином прямокутник і саджаючи квіти у всіх потрібних клітинах.

Оскільки при обробці кожної з 4-х стінок Роботу треба виконувати однакові команди, тут можна використовувати цикл повтори ( 4 ). тоді цикл Бувай стає вкладеним циклом.

контур

{

поки (впереді_свободно)

вперед (1); / * Підійти до стіни * /

ліворуч;

поки (справа_стена)

назад (1); / * В лівий нижній кут * /

 повтори (4) {вперед (1); / * Тепер справа стіна * / посади; / * Кутова клітина * / направо; }

 
 
 поки (справа_стена) {посади; вперед (1); }


}

2 Завдання

1.Посадіть квіти у всіх грядках клітинах між стінками і повернутися назад. Товщина стіни - 1 клітина, інші розміри вважати невідомими.


2. Посадити квіти у всіх грядках. Товщина стіни - 1 клітина, інші розміри вважати невідомими. Всі розміри вважати невідомими.


5. Умовний оператор

2 Що таке умовний оператор (завдання z5-3.maz)?

Розглянемо нову задачу для Робота. Треба посадити квіти у всіх клітинах уздовж стіни, де немає проходу, а якщо в цьому місці є прохід, увійти в нього і обробити грядку між стінок. Припускаємо, що довжина стіни і число проходів невідомі.

 
 

 Для вирішення цього завдання нам треба навчити Робота виконувати різні дії в залежності від навколишнього оточення. Це можна зобразити на схемі

Словами це можна сформулювати так: якщо є прохід (умова є прохід виконується), то виконай одну групу команд, якщо немає - виконай інші команди. У програмі для цієї мети використовується спеціальний умовний операторякщо

вибір

{

вперед (1); направо; вперед (1); / * Підійти до початку стіни * /

поки (впереді_свободно)

{

вперед (1);

 якщо (слева_свободно) {/ * увійти в прохід * / наліво; вперед (1); посади; назад (1); направо; } Інакше {посади; }

направо;

вперед (1);

}

}

Таким чином, ми визначили два варіанти дій Робота - перший працює тоді, коли виявлений прохід, а другий - коли справа стіна.

2 Правила використання умовного оператора

1. Умовний оператор складається з двох частин; перша частина починається ключовим словом якщо або if (Від англійського "якщо"), Після якого в дужках записується умова.

2. Якщо ця умова вірно (або істинно), То виконується група команд, що стоїть нижче в фігурних дужках (блок-якщо).

3. Друга частина (блок-інакше) Починається зі слова інакше або else (Від англійського "інакше") І виконується в тому випадку, коли умова в дужках помилково.

4. Не можна відокремлювати блок-якщои блок-інакше,оскільки вони становлять єдиний оператор.

5. Умова ставиться тільки в заголовку блоку-якщо.

6. Блок-інакше може бути відсутнім, якщо він не потрібен; в цьому випадку ми говоримо, що умовний оператор записаний в скороченій формі.

7. Щоб було зручніше розбиратися в програмі, використовують відступи так само, як і в циклах: тіло блоку-якщои блоку-інакшезсувається вправо на 2-3 символу.

2 Скорочена форма

Трохи змінимо завдання - нехай тепер Роботу треба обробляти тільки по 1 клітці на початку кожного проходу.

Таким чином, в блоці-інакше не залишилося жодної команди - якщо проходу немає, нічого робити не треба. Тому можна використовувати скорочену форму умовного оператора - без другої частини:

Сад2

{

вперед (1); направо; вперед (1);

поки (впереді_свободно)

{

вперед (1);

 якщо (слева_свободно) {наліво; вперед (1); посади; назад (1); направо; }

}

}


2 Що таке складні умови (завдання z6-3.maz)?

Розглянемо ще одну задачу для Робота. Йому потрібно пройти через коридор з проходами і прийти на Базу. Складність полягає в тому, що в обох стінках є проходи, скільки їх - невідомо.

Ми помічаємо, що всередині коридору немає такої клітини, у якій зліва і справа - вільні клітини. Значить, Роботу треба зупинитися, коли зліва і справа - вільно, це означає кінець коридору. Тепер можна сформулювати алгоритм проходу через весь коридор російською мовою - йди вперед, поки зліва стіна АБО праворуч стіна.

В цьому словесному алгоритмах ми об'єднували логічні команди Робота за допомогою операції АБО,отримавши з двох простих умов одне складну умову. Те ж саме можна робити і в програмі:

посадка

{

 поки (слева_стена або справа_стена) вперед (1);
 вперед (1);

ліворуч;

вперед (2);

ліворуч;

поки (НЕ база) вперед (1);

}

? Складну умову -це умова, що складається з простих умов і логічних операцій:

НЕзаперечення

Илогічне множення

АБОроз'єднання

2 Правила використання складних умов

1. Найпростішими умовами є логічні команди виконавців (наприклад, слева_стена) і логічні відносини між значеннями [1].

> <більш-менш т> 5, 2 + n

> =більше або дорівнює a> = 2 * x + 5

<=менше або дорівнює c + 2 * d <= 5 * v

==одно d = = 2 + c

<>не дорівнює a! = b

2. В умови "дорівнює" ставиться два знака рівності; щоб не заплутатися, треба запам'ятати, що якщо змінна змінюється (оператор присвоювання), То треба ставити один знак "=", а якщо не змінюється (логічне відношення), То два.

3. Складні умови складаються з декількох простих; прості умови об'єднуються за допомогою логічних операцій.

4. Операція "І"вимагає одночасноговиконання двох умов, наприклад:

сверху_стена И снізу_стена

5. Операція "АБО"позначається вимагає виконання хоча б одного з двох умов (або обох разом), наприклад:

сверху_стена АБО снізу_стена

6. Іноді зручно використовувати логічну операцію "НЕ", Яка заперечує значення логічного виразу, наприклад умови

a и НЕ (b> = a)

означають одне і те ж.

7. Встановлюється такий пріоритет(Старшинство) логічних відносин і операцій:

· Спочатку виконуються операції в дужках, потім ...

· операції "НЕ", Потім ...

· Логічні відносини (>, <,> =, <=, ==,! =), Потім ...

· операції "І"і в останню чергу

· операції "АБО".

Для зміни порядку виконання операцій використовуються дужки.

6. Змінні і арифметичні вирази

2 Навіщо потрібні змінні (завдання z7-3.maz)?

Приклад 1. Нехай Роботу треба посадити квіти на трикутної майданчику. Для кожної «рядки» можна використовувати цикл повтори. Якби довжини всіх «рядків» були рівні, можна було б використовувати вкладений цикл.

Звичайно, можна п'ять разів написати цикл повтори. Але найчастіше використовують наступний підхід.

1. Довжина «рядки» зберігається в комірці пам'яті.

2. На самому початку в цей осередок записується довжина першої «рядки».

3. У заголовку циклу повтори замість числа підставляється значення, взяте з цього осередку.

4. При переході до наступного рядка значення осередку збільшується на 1.

Подивимося, як вирішується наведена вище завдання.

ряд

{

int n; / * Виділити місце в пам'яті * /

направо;

n = 1; / * Привласнити значення змінної * /

повтори (6) / * всього 6 рядків * /

{

повтори (n) / * довжина рядків змінюється! * /

{

вперед (1);

посади;

}

направо;

вперед (1);

ліворуч;

назад (n);

n = n + 1; / * Збільшити змінну n на 1 * /

}

}

Подумайте, як можна вирішити цю задачу, використовуючи цикл Бувай замість повтори?

Приклад 2. Розглянемо ще одну задачу: Роботу потрібно обійти стінку і прийти на Базу, яка знаходиться точно під ним, але ... з іншого боку стінки, довжина якої невідома. логічну команду база використовувати не можна (відмовив датчик).

За допомогою циклу Бувай ми можемо наказати йому дійти до стінки і обігнути її, але як зупинити його саме в тому місці, де потрібно?

Щоб вирішити це завдання, треба в той момент, коли Робот спуститься вниз до стінки, якимось чином запам'ятати, де він стоїть, тобто запам'ятати відстань від нього до краю стінки. Єдиний спосіб зробити це - вважати, скільки кроків зробить Робот уздовж стінки до краю, щоб потім зробити стільки ж кроків назад, вже під стінкою.

Запам'ятати цю інформацію можна тільки в комірці пам'яті. Щоб не втратити її, цей осередок треба помітити, тобто дати їй ім'я. Вміст цього осередку потрібно можна змінювати під час виконання програми, тому така величина називається змінна.Рішення нашої задачі виглядає так:

ВнізСквозьСтену

{

int n = 0; /* оголошення змінної */

/ * Виділення комірки пам'яті * /

/ * Привласнення початкового значення * /

поки (впереді_свободно) / * вниз до стінки * /

вперед (1);

направо;

поки (слева_стена) / * вийти вліво за край стіни * /

{

вперед (1);

n = n + 1; / * Збільшуємо лічильник кроків на 1 * /

}

ліворуч; вперед (2); ліворуч;

вперед (n); / * Йдемо на потрібне число кроків * /

}

2 Що таке змінна?

Запам'ятати інформацію можна тільки в осередку пам'яті комп'ютера. Щоб не втратити її, цей осередок треба помітити, тобто дати їй ім'я. Вміст цього осередку можна змінювати під час виконання програми, тому така величина називається змінна.

? змінна -це величина, яка має ім'я, тип і значення. Значення змінної може змінюватися під час виконання програми. У комп'ютерах кожна змінна записана в свою комірку пам'яті.

2 Оголошення змінних

1. На початку процедури всі використовувані змінні необхідно оголошувати, при цьому комп'ютер виділяє під них місце в пам'яті і запам'ятовує імена змінних. Якщо змінна не оголошена, то виникає помилка "



1   2   3   4
загрузка...
© um.co.ua - учбові матеріали та реферати