Потопахін Віталій Валерійович
Мова алгоритмів
Всі ми розуміємо, що для запису алгоритмів нам потрібен спеціальний мову. Повторимо коротко, чому ми так думаємо:
Слова і тим більше пропозиції природної мови можуть мати кілька значень.
У природній мові сенс пропозицій і фраз може мати відтінки і залежати від інтонації мовця.
Необхідно враховувати можливості виконавця. Може так статися, що команда алгоритму не входитиме в систему команд, а отже виявиться виконавцю незрозумілою.
Тому, ми зараз займемося створенням спеціальної мови і спробуємо учёсть всі висловлені зауваження. Відразу домовимося про те хто буде нашим Виконавцем. Нехай, поки це буде людина розуміє сенс будь-яких російських слів і пропозицій. І в якості основи для нашої мови будемо використовувати російську мову.
Головна наша проблема, це багатозначність слів і пропозицій. Щоб її вирішити введемо деякі нескладні правила побудови алгоритмічних пропозицій.
Правило 1: Пропозиція алгоритмічного мови повинно бути односкладових.
Чи не правильний приклад
Правило 3: Не можна користуватися іносказаннями. (Як з гусака вода, За тридев'ять земель)
Важливе зауваження: Можна ще навести приклади таких правил. Всі вони розкривають одне єдине, але найважливіша: зміст речення алгоритмічного мови повинен бути єдиним.
Правило 4: Пропозиція алгоритмічного мови повинно бути командою до дії.
Поганий приклад: Трикутник - це геометрична фігура. Ця пропозиція як алгоритм не містить в собі ніякого сенсу.
Правило 5: Якщо пропозиція алгоритмічного мови може мати багато значень, то вибирається той який використовується найбільш часто (загальновживану). Це правило як би суперечить визначенню алгоритму з якого випливає, що сенс може бути тільки один. Справа в тому, що зараз ми знаємо занадто мало, щоб забезпечити це властивість алгоритмів і нам доведеться деякий час робити погані алгоритми.
Що таке команда алгоритму: Команду алгоритму визначимо, як правильно побудоване речення алгоритмічної мови. Тоді алгоритм можна визначити як послідовність команд. Такими простими командами можуть бути наприклад такі: Йти вперед, взяти, покласти, купити.
Однак простих команд нам буде недостатньо. Розглянемо задачу:
Дано відро яблук. Потрібно перекласти всі яблука в холодильник.
Для вирішення потрібні дві прості команди: взяти яблуко з відра і покласти яблуко в холодильник. Виконавши цю пару команд ми наблизимося до вирішення завдання, але не вирішимо її. Для повного вирішення потрібно виконати цю пару команд багато разів. Нехай тепер нам відомо, що в відрі 100 яблук. Тоді наш алгоритм буде складатися з 200 команд. Це звичайно багато. Щоб спростити завдання введемо складну команду, яка буде вказувати скільки разів виконувати прості команди. Запишемо з її допомогою наш алгоритм перекладання яблук:
Взяти яблуко з відра
Покласти яблуко в холодильник.
кінець
Назвемо цю складну команду циклом. З'явилися нові слова "Початок" і "Кінець" потрібні для того, щоб виділити групу команд входять в цикл. Така група команд називається складною командою.
А тепер ускладнити ситуацію. Припустимо, ми не знаємо скільки в відрі яблук. Тоді команда "робити сто разів" не спрацює. Тепер потрібно перевіряти чи є у відрі яблука. Наш алгоритм можна записати так:
Поки в відрі їсти яблука робити
Взяти яблуко з відра
Покласти яблуко в холодильник
Підкреслена словосполучення ця умова, поняття для нас нове, тому розглянемо його докладніше.
Визначення: Умова, - це припущення є або істинним або хибним:
Вище ми показали приклади простих умов, але умови можуть бути і складними, як би складаються з декількох простих. Ось кілька прикладів складних умов:
Яблука та груші в холодильнику.
Відро не порожнє.
У відрі лежать яблука чи груші.
Умова 1 як би складається з двох умов: "Все яблука в холодильнику" і "Все груші в холодильнику". Ці дві умови об'єднані логічною зв'язкою "і". В цьому випадку складну умову є істинним тоді коли обидва простих умови істинні ..
Умова 2 виходить з умови "Відро пусте" добавкою приставки "не". Приставка "не" називається запереченням. Умова з запереченням є протилежним умові без заперечення і тому воно істинне, коли умова без заперечення брехливо і навпаки.
Умова 3 той же як би складається з двох простих сполучених зв'язкою або. Воно істинно тоді коли істинним є хоча б одне з простих умов. Наше складну умову істинно буде тоді коли в відрі є або яблука чи груші.
За допомогою цих трьох зв'язок "і", "або", "не" (вони ще називаються складними умовами) і простих умов складаються найрізноманітніші складні умови.
Висновок: Отже, нам потрібні два типи конструкції циклу. Перший тип циклу називається циклом з параметром застосовується тоді коли точно відомо скільки разів потрібно повторювати циклічні дії. Другий тип циклу ми назвемо циклом за умовою. Він виконується до тих пір поки умова істинна.
А зараз для прикладу напишемо алгоритм складання 100 послідовних чисел з використанням як першого типу циклу так і другого:
Цикл по параметру
Цикл за умовою