Головна

Основні принципи РОЗРОБКИ І АНАЛІЗУ АЛГОРИТМІВ

  1. B. Основні ефекти
  2. I. Завдання семіотики і передумови, необхідні для її розробки
  3. I. Основні завдання
  4. I. Основні завдання ЗОВНІШНЬОЇ ПОЛІТИКИ
  5. I. Основні лінії зв'язку педагогіки з соціологією. Мікро- та макроанализ 1 сторінка
  6. I. Основні лінії зв'язку педагогіки з соціологією. Мікро- та макроанализ 2 сторінка
  7. I. Основні лінії зв'язку педагогіки з соціологією. Мікро- та макроанализ 3 сторінка

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

При дедуктивному підході розглядається окремий випадок общеізвестнихалгорітміческіх моделей. Тут при заданих припущеннях відомий алгоритм пристосовується до умов розв'язуваної задачі. Наприклад, багато обчислювальні задачі лінійної алгебри, зокрема, нелінійні рівняння, системи рівнянь алгебри і т.п., можуть бути вирішені з використанням відомих методів і алгоритмів, для яких існує безліч спеціальних бібліотек підпрограм, модулів. В даний час набули поширення спеціалізовані пакети, що дозволяють вирішувати багато завдань (Mathcad, Eureka, Reduce- Autocad і т.п.).

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

Одним із системних методів розробки алгоритмів є структурне програмування. Принципи структурної алгоритмізації раніше викладалися в гл. 1 (п. 1.8). Повторимо їх більш формально з упором на реалізацію в практично програмуванні.

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

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

Мал. 3.5. Функціональні (а), предикатні (Б) і об'єднують (в) вершини

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

begin S1; S2; end

Мал. 3.6. Структура «композиція»

альтернатива - це конструкція розгалуження, що має предикатную вершину. Конструкція розгалуження в алгоритмах може бути представлена ??у вигляді розвилки (а), неповної розвилки (б) і вибору (В) (Мал.3.7).

Мал. 3.7. Структура «альтернатива». Тут В - умова (логічний вираз)

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

Кожна з розглянутих структур має один вхід і один вихід. Тому будь-яка комп'ютерна програма може бути представлена ??блок-схемою, сформованої з представлених трьох керуючих структур.

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

Мал. 3.8. Структура «ітерація»

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

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

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

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

Приклад 1. Технологія розробки програми вирішення квадратного рівняння.

На рис. 3.9 проілюстрована покрокова деталізація процесу побудови алгоритму. Зауважимо, що для початкового кроку розробки програми маємо в якостей вихідних даних коефіцієнти а, b, з квадратного рівняння ax2 + Bx + з = 0, а на виході - значення двох коренів х 1, х2.

Приклад 2. Розглянемо більш складний і повчальний приклад структурної програмування, відомий в літературі як «тур шахового коня». У задачі необхідно відповісти на питання, чи існує при заданому положенні шахового коня послідовність його ходів, один раз містить всі клітини шахового поля.

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

Однією з евристичних стратегій алгоритму може бути наступна. Haчіная з довільного поля i, j (на рис.3.10 i = 4, j = 4), намагаємося піти на поле * 1, якщо неможливо, то на поле * 2; при невдачі - на поле * 3 і т.д.По годинниковою стрілкою

Мал. 3.9. Покрокова деталізація побудови алгоритму

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

Отже, вихідні дані завдання - довільні початкові координати коня i, j від 1 до 8. Результат - можливий маршрут коня із заданого поля. Вдалим вважається маршрут, який містить всі 64 ходу, тобто повний тур коня.

F Рис.3.10. Ілюстрація до задачі «тур шахового коня»

Ініціалізація дошки передбачає завдання двовимірного масиву розміром 8х8 з нульовими елементами. Надалі елемент a [iJ] приймає значення номера чергового ходу. Роздрукувати результат - означає вивести таблицю а [1..8,1..8]. Наріс.3.12 показаний один з результатів можливого маршруту коня з початкового поля i = l, j = l.

Мал. 3.11. Покрокова деталізація побудови алгоритму до прикладу 2

Мал. 3.12. Можливий результат маршруту коня з поля (1.1)

програма 35

Program Tur_Konja;

var a: array [1..8,1..8] of integer;

im, jm: array (l..8] of integer;

i, j, k, n, inac, jnac: integer;

inext, jnext: integer;

begin (--- ініціалізація шахівниці ---}

for i: = l to 8 do for j: = l to 8 do a [i, j]: = 0;

im [l]: = - 2; jm [l]: = l .; im [2]: = - 1; jm [2]: = 2; im [3]: = 1; jm [3]: = 2;

im [4]: ??= 2; jm [4): = l; im [5]: = 2; jm [5]: = - !; im [6]: = 1; jm (6]: = - 2;

im [7]: = - l; jm [7]: = - 2; im [8]: = - 2; jm [8]: = - l;

write ( 'введи початкові координати коня 0

readln (inac, jnac);

a [inac, jnac]: = 1; i: = inac; j: = jnac; n: = 2; k: = l;

while k <= 8 do

begin inext: = i + im (k]; jnext: = j + jm (k];

if (inext 8) or (jnext

(Jnext> 8) or (a [inext, jnext] <> 0)

then k: = k + l

else begin a (inext, jnext]: = n; n ^ n + l; i: «- inext;

j: «jnext; k: = l;

end;

end;

{--- Висновок результату проходу ---)

for i: = l to 8 do

begin writeln; writeln; for j: = l to 8 do write (a (i, j]: 2, '')

end;

writeln; write ( 'кількість кроків =', n-l); readln;

end.

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

 




ВСТУП | ОСНОВНІ КОНСТРУКЦІЇ МОВИ | СТРУКТУРИ ДАНИХ | ПРОЦЕДУРИ І ФУНКЦІЇ | РОБОТА З ФАЙЛАМИ | Динамічні ІНФОРМАЦІЙНІ СТРУКТУРИ | Деякі відомості про драйвери н визначених ними режимах | Приклади графічних програм | ТУРБО-ОБОЛОНКИ. ВЕРСІЇ Паскаль | КЕРІВНИЦТВО КОРИСТУВАЧУ ТУРБО-Паскаль |

© um.co.ua - учбові матеріали та реферати