Структурнае праграміраванне і дакладнасць праграм

Першае, што патрабуецца ад алгарытму рашэння задачы, – гэта пра­віль­на яе рэалізаваць.

Другое – патрэбна такая рэалізацыя, якая з’яўляецца лёгкай для ра­зу­мен­ня, простай для доказу правільнасці алгарытму і зручнай для ма­ды­фі­ка­цыі. Гэтыя патрабаванні важныя галоўным чынам таму, што, калі ал­га­рыт­мы становяцца ўсё больш складанымі, адпаведна расце і цяжкасць іх распрацоўкі, складанасць разумення, як яны працуюць, г. зн. цяжка вы­праў­ляць знойдзеныя ў алгарытмах памылкі, даказваць карэктнасць ал­га­рыт­му і пры неабходнасці правільна ўносіць у праграмы карэктывы.

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

На сённяшні дзень самай папулярнай методыкай распрацоўкі ал­га­рыт­му рашэння задачы з’яўляецца структурнае праграміраванне зверху ўніз, калі задача асэнсоўваецца ў цэлым, потым яна разбіваецца на падза­да­чы, якія ўжо вядома, як алгарытмізаваць сродкамі структурнага пра­гра­мі­ра­ван­ня.

Разгледзім гэтую методыку на прыкладзе ўяўлення алгарытму ў вы­глядзе блок-схем. Даволі проста даказаць, што любая праграма для ЭВМ мо­жа быць прадстаўлена блок-схемай (напрыклад, у суадносінах 1:1, калі кож­най аперацыі ставіцца ў адпаведнасць адзін блок, ці ў суадносінах N : M, дзе N – колькасць аператараў праграмы, M – колькасць блокаў).

Значыць, і любую блок-схему можна пераўтварыць у праграму для ЭВМ. Каб спрасціць працэс праграміравання, блок-схемы павінны быць больш набліжаны да мовы праграміравання, г. зн. падпарадкоўвацца ней­кім жорсткім прынцыпам.

Аператары кіравання, якія маюць сучасныя мовы праграміравання, доб­ра адлюстроўваюцца, як мы бачылі раней, дыяграмамі Насі – Шней­дэр­ма­на, ці структураграмамі. Блок-схемы, якія падпарадкаваны такім жа ўмо­вам, таксама называюцца структурнымі блок-схемамі.

Структурная блок-схема – гэта блок-схема, якая можа быць вы­ра­жа­на як кампазіцыя шасці элементарных блок-схем структур кіравання.

Асноўныя канструкцыі структур кіравання

Разгледзім шэсць элементарных блок-схем структур кіравання пад­ра­бяз­ней.

Кампазіцыя ці чаргаванне:

Выбар ці альтэрнатыва (рашэнне):

а) б)

(аператар if_then_else) (аператар if_then)

Варыянт:

В – варыянт выбару,

S1 – працэс 1,

. . .

Sm – працэс m.

(аператар case_of_end)

Паўтарэнне (цыкл) з пасляўмовай:

(аператар repeat_until)

Паўтарэнне (цыкл) з перадумовай:

(аператар while_do)

Цыкл з пералікам (параметрам):

(аператар for_to(downto)_do)

Важнай асаблівасцю ўсіх структур кіравання з’яўляецца тое, што кож­ная з іх мае адзін уваход і адзін выхад. Значыць, і ўся блок-схема будзе мець гэтую ўласцівасць, таму мы з пачатку алгарытму выйдзем на ка­нец яго.

Для кожнай з прапанаваных канструкцый у структурнай ал­га­рыт­міч­най мове існуюць пэўныя аператары: if_then_else, case_of_end, whilе_do, repeat_until, for_to(downtо)_do.

Адзначым, што існуе многа моў структурнага напрамку: Algol, Pascal, C, Ada, Modula і інш. Fortran-падобныя мовы праграміравання (напры­клад, Basic) неструктурнага напрамку, хаця Fortran‑77 ужо мае эле­мен­ты структурнага праграміравання.

Аксіёма. Любая блок-схема можа быць прадстаўлена струк­тур­най блок-схемай.

Доказ правільнасці алгарытму – гэта адзін з самых цяжкіх і cтомных эта­паў стварэння праграм. Таму дзякуючы «празрыстасці» асобных дзе­янняў лягчэй прасачыць за правільнасцю ўсіх дзеянняў па рашэнні па­стаў­ле­най задачы.

Карыстаючыся кіруючымі канструкцыямі ўжо пры распрацоўцы ал­га­рыт­му, лёгка сачыць за правільнасцю яго частак і гэтым даказваць пра­ві­ль­насць усяго алгарытму.

Найбольш агульная тактыка распрацоўкі праграм складаецца з дэ­кам­па­зі­цыі ўсёй задачы на асобныя больш простыя падзадачы, якія пры­водзяць да рашэння ўсёй задачы. Затым працэс дэкампазіцыі рас­паў­сю­дж­ва­ец­ца на падзадачы, і так да той пары, пакуль не атрымаюцца падза­да­чы, якія лёгка рэалізуюцца на мове праграміравання.

Дэкампазіцыя задачы – ітэрацыйны працэс, які не выключае зварот на­зад. Пры распрацоўцы праграмы можа аказацца, што на некаторым кро­ку прыняты нездавальняючыя рашэнні ці асобныя падзадачы, якія амаль не рэалізуюцца на мове праграміравання. У гэтым выпадку не­аб­ход­на будзе вярнуцца на некалькі крокаў назад і пераглядзець дэ­кам­па­зі­цыі нанава.

Апісаны метад прапанаваны Н. Віртам (1971) і называецца пак­ро­ка­вай дэталізацыяй.

Выкарыстоўваючы прапанаваную методыку структурнага праг­ра­мі­ра­ван­ня, разгледзім некалькі задач, якія можна назваць базавымі, і сас­та­вім структурныя блок-схемы для іх. Спачатку дадзім азначэнне масіву.

Масівам называецца сукупнасць элементаў аднаго тыпу, якія маюць ад­но імя і адрозніваюцца адзін ад аднаго нумарамі – ін­дэк­са­мі. Існуюць аднамерныя масівы (вектары), двухмерныя (матрыцы), трохмерныя ма­сі­вы і г. д.

Задача 1. Знайсці адну з наступных сум.

1.1. N першых няцотных лікаў.

1.2. N першых выпадковых лікаў.

1.3. N першых простых лікаў.

1.4. N лікаў , дзе ,

Рашэнне. Ва ўсіх выпадках трэба падлічыць

Блок-схема атрымання сумы лікаў наступная.

Аднак пры рашэнні задачы 1.1 праграма павінна адразу даць адказ:  (таму што сума паслядоўнасці лікаў ёсць ) і не арганізоўваць цыкліч­ны працэс.

Для рашэння задач 1.2–1.4 атрымаем адзіную блок-схему, у якой не кан­к­рэ­ты­за­ва­на, як атрымліваецца складаемае.

У задачы 1.2 складаемыя атрымліваюцца выклі­кам функцыі, якая вяр­тае чарговы выпадковы лік, а ў задачы 1.3 – вык­лі­кам функцыі, якая вяр­тае чарговы просты лік. Такую функцыю трэ­ба яшчэ напісаць. У за­да­чы 1.4 трэба падумаць, як больш эфектыўна ат­ры­маць наступнае скла­да­емае.

Задача 2. Знайсці індэкс найменшага элемента ў аднамерным масіве.

Алгарытм. Запамінаецца індэкс першага элемента і потым утва­ра­ец­ца цыкл на колькасць элементаў, якія засталіся. У цыкле па­раў­ноў­ва­юц­ца ўсе чарговыя элементы з элементам пад індэксам Пры зна­ход­жан­ні меншага элемента яго нумар запамінаецца ў пераменнай

Блок-схема:

Задача 3. Упарадкаваць элементы масіву па нарастанні.

Алгарытм. Пры распрацоўцы блок-схемы будзем абапірацца на за­да­чу 2. Выклічам дапаможны алгарытм пошуку індэкса найменшага эле­мен­та сярод . Затым першы найменшы абмяняем з , другі най­мен­шы – з і г. д. Такі алгарытм упарадкавання называецца сар­та­ван­нем метадам прамога выбару.

Блок-схема:

Дапаможны алгарытм пошуку індэк­са ind найменша­га эле­мен­та ся­род a_i, …, a_n

Г этую ж задачу ўпарадкавання можна ра­шыць і другім метадам. Па­чынаючы з пер­ша­га элемента масіву па­раў­ноў­ваюцца два су­сед­нія эле­менты. Калі яны не адпа­вя­даюць умо­ве на­рас­тання, тады абмень­ва­юц­ца іх зна­чэн­ні і да­лей па­раў­ноў­ваецца на­ступ­ная пара эле­мен­таў. За першым прахо­дам масіву да кан­ца са­мы цяж­кі элемент зру­шыцца ў ка­нец. Зноў cпа­чат­ку адбы­ваец­ца параўнанне су­сед­ніх эле­мен­таў. За дру­гім пра­ходам масіў праг­ля­да­ец­ца не да кан­ца, а да пе­ра­да­пош­ня­га элемента. За ( )-м пра­глядам ад­будзец­ца поўнае ўпа­рад­каван­не. Такі алгарытм упа­рад­ка­ван­ня на­зы­ваец­ца сартаваннем метадам пузырка. Блок-схе­му такога ал­га­рыт­му на­пі­шы­це самастойна.

Задача 4. Упарадкаваць элементы кожнага радка матрыцы па на­растанні.

Алгарытм. Выкарыстаем метад пакрокавай дэталізацыі. Паколькі кож­ны зафіксаваны і-ы радок матрыцы ўяўляе сабой аднамерны масіў то скарыстаем папярэдні алгарытм упарадкавання ад­на­мер­на­га масіву, блок-схему якога напішыце самастойна на месцы ка­мен­та­рыя.

Задача 5. Знайсці суму працэс на­кап­лен­ня складаемых закончыць, калі атрымаецца складаемае па модулі менш за

Рашэнне. Разгледзім суму дзе Спачатку ўспом­нім задачу падліку сумы бясконцай геаметрычнай прагрэсіі. Мы змаг­лі падлічыць суму толькі пры ўмове, што кожнае наступнае скла­да­е­мае па модулі было менш за папярэдняе. Гэты момант прысутнічае і тут.

Алгарытм. першае складаемае, калі яно па модулі больш за 10^–7, дададзім да сумы, наступнае, калі яно па модулі яшчэ больш за 10^–7, –  у суму і гэтак далей, пакуль складаемае па модулі не стане менш за 10^–7.

Атрымаць даволі проста. Паколькі то дзе

Заўвага. – элемент з нумарам Калі так пакінуць, то пад кож­ны трэба месца, а ў такой пастаноўцы задачы не­вя­до­ма, колькі будзе і не трэба гэтага ведаць, бо, дабавіўшы ў скла­да­е­мае, можна яго замяніць наступным. Перапрацуйце блок-схему з улікам гэ­тай заўвагі самастойна.

Заданне. Няхай вядомы функцыі

Пабудаваць матрыцу дзе – нейкія кан­с­тан­ты, па наступ­ным правіле: Пра­ве­рыць яе сі­ме­трыч­насць адносна галоўнай і пабочнай дыяганалей.