- •Уводзіны Ключавыя палажэнні
- •Развіццё моў камп’ютарнага праграміравання
- •Эвалюцыя мовы Pascal
- •Структурная метадалогія распрацоўкі праграм Алгарытм
- •Асноўныя этапы рашэння задач на эвм
- •Блок-схемы
- •Структураграмы
- •Тэсціраванне праграм
- •Адладка праграм
- •Структурнае праграміраванне і дакладнасць праграм
- •Асноўныя канструкцыі структур кіравання
- •Метады распрацоўкі праграм
- •Праграміраванне зверху ўніз (ад агульнага да асобнага)
- •Модульнае праграміраванне
- •Праграміраванне знізу ўверх
- •Структурнае кадзіраванне
- •Арыфметыка эвм Сістэмы злічэння
- •Пераклады лікаў з адной сістэмы злічэння ў другую
- •Пераклад цэлых дадатных лікаў з сістэмы злічэння з асновай «p» у сістэму злічэння з асновай «q»
- •Пераклад правільных дробаў з сістэмы злічэння з асновай «p» у сістэму злічэння з асновай «q»
- •Пераклад змешаных дробаў
- •Формы прадстаўлення даных
- •Формы прадстаўлення лікаў у персанальным камп’ютары
- •Захаванне лікаў з фіксаванай кропкай
- •Захаванне цэлых лікаў
- •Алгарытм прадстаўлення адмоўнага ліку ў адваротным кодзе
- •Прынцыпы захавання лікаў з плаваючай кропкай
- •Фарматы лікаў з плаваючай кропкай арыфметычнага супрацэсара ibm pc/aт 8087
- •Сродкі алгарытмічнай мовы Pascal Агульная характарыстыка алгарытмічных моў
- •Базавыя элементы мовы Pascal
- •Алфавіт
- •Лексічная структура мовы
- •Агульная структура Pascal-праграмы
- •Простыя даныя мовы Pascal і работа з імі Тыпы звестак
- •Канстанты і пераменныя
- •Абсалютныя пераменныя
- •Цэлалікавыя даныя
- •Бітавая арыфметыка
- •Дзеянні бітавай арыфметыкі
- •Сапраўдныя даныя
- •Аперацыі над сапраўднымі данымі
- •Выразы мовы
- •Літарныя даныя
- •Функцыі
- •Булеўскія даныя
- •Даныя адраснага тыпу
- •Даныя карыстальніцкага тыпу
- •Даныя пералічальнага тыпу
- •Даныя інтэрвальнага тыпу
- •Элементарныя сродкі па рабоце з данымі Наданне значэння даным
- •Найпрасцейшае вызначэнне працэдур і функцый
- •Параметры
- •Знаёмства з файлавай сістэмай
- •Файлавы тып
- •Тэкставыя стандартныя файлы
- •Увод даных розных тыпаў
- •Вывад даных розных тыпаў
- •Вывад сімвалаў
- •Вывад радковых даных
- •Вывад лагічных значэнняў
- •Вывад цэлалікавых значэнняў
- •Вывад даных сапраўднага тыпу
- •Базавыя аператары мовы і метады праграміравання Аператары
- •Простыя аператары
- •Аператар безумоўнага пераходу goto
- •Аператар выкліку працэдуры
- •Пусты аператар
- •Састаўны аператар
- •Аператары выбару
- •Умоўны аператар
- •Метады і прыёмы праграміравання
- •Аператар варыянта
- •Прыклады праграм
- •Аператары паўтарэння
- •Аператар паўтарэння for
- •Аператар паўтарэння repeat
- •Аператар паўтарэння while
- •Хуткая ступень
- •Ітэрацыйныя алгарытмы вышэйшай матэматыкі
- •Структуры даных і праца з імі сродкамі мовы Pascal Парадкавыя тыпы
- •Мноствы
- •Тыпізаваныя канстанты тыпу «мноства»
- •Дзеянні над масівамі
- •Дзеянні над элементамі масіву
- •Пераменныя тыпу «масіў» са стартавым значэннем, ці тыпізаваныя канстанты-масівы
- •Канстанты з тыпам «масіў»
- •Камбінаваны тып «запісы»
- •Змяненне (прывядзенне) тыпаў і значэнняў
- •Радкі сімвалаў
- •Наданне значэння радкам
- •Радковыя выразы
- •Рэдагаванне радкоў
- •Пераўтварэнне радкоў
- •Механізмы структуравання праграм Працэдуры і функцыі
- •Функцыі карыстальніка
- •Параметры
- •Параметры-значэнні
- •Параметры-пераменныя
- •Прынцып лакалізацыі
- •Пабочны эфект
- •Рэкурсія і ітэрацыі
- •Параметры без тыпу
- •Працэдуры і функцыі як параметры. Працэдурныя тыпы
- •Пераменныя – працэдуры і функцыі
- •Падпраграмы ў модулях
- •Выкарыстанне модуля
- •Стандартныя бібліятэчныя модулі
- •Працэдуры кіравання праграмай
- •Эфектыўнасць праграм
- •Аптымізацыя ў час кампілявання
- •Індэксацыя
- •Выкарыстанне цыклаў
- •Арганізацыя цыклаў
- •Аптымізацыя цыклаў
- •Літаратура
Аптымізацыя цыклаў
Існуюць некаторыя агульныя прыёмы аптымізацыі цыклаў:
1. Вынясенне інварыянтных частак з цела цыкла (а гэта тыя падвыразы, значэнні якіх не змяняюцца ўнутры цыкла).
2. Замена больш доўгіх па часе падліку аперацый на больш хуткія.
Прыклад.
Зыходная аперацыя ў цыкле |
Аптымізаваная аперацыя ў цыкле |
i := i + 1 |
inc(i) |
i := i – 2 |
dec(i, 2) |
2 * i + 1 |
k, дзе k = 1, 3, … |
x * x * x* x * x |
sqr(sqr(x)) * x |
але x * x * x* x * x больш аптымальная для падліку x5, чым exp(5*ln(x)) |
3. Аднаразовае вылічэнне аднолькавых падвыразаў або эканомія выразаў.
Прыклад. Калі ў цыкле неаднаразова выкарыстоўваецца выраз (x + 1), тады карысна ўвесці дапаможную пераменную y, якой надаць значэнне x + 1 і далей выкарыстоўваць y.
4. Выключэнне дзеянняў над канстантамі ў целе цыкла.
Прыклад. Канстантныя выразы 1/4; exp(–2) /5 і г. д. лепш падлічыць да ўваходу ў цыкл.
5. Выкарыстанне вынікаў папярэдняга кроку цыкла. Гэта самы асноўны прыём.
Задача. Саставіць эфектыўную праграму падліку шчаслівых білетаў сярод шасцізначных, васьмізначных і інш.
Рашэнне. Першы алгарытм. Вылучым пераменныя i, j, k, l, m, n, значэннямі якіх будуць лічбы 0 i 9. Білет шчаслівы, калі i + j + k = l + m + n.
Эўрыстычны падыход прыводзіць да наступнага алгарытму:
PROGRAM Heppy_Ticket_1;
VAR
i, j, k, l, m, n : Byte;
Count : Word;
BEGIN
Count :=0;
FOR i := 0 TO 9 DO
FOR j := 0 TO 9 DO
FOR k := 0 TO 9 DO
FOR l := 0 TO 9 DO
FOR m := 0 TO 9 DO
FOR n := 0 TO 9 DO
IF i + j + k = l + m + n THEN Inc(Count);
Writeln('колькасць=', Count); Readln;
END.
Надрукуецца 55252.
Аналіз. Шэсць укладзеных цыклаў здзяйсняюць перабор усіх варыянтаў, іх 106 – мільён, а знайшлі 1/18 частку ўсяго перабору. Ясна, што гэта нятанны алгарытм, неэфектыўны па часе выканання і непрыстасаваны для білетаў з іншай разраднасцю.
Распрацуем другі алгарытм, заснаваны на іншым падыходзе. Будзем падлічваць, колькі разоў атрымаецца сума лічбаў, роўная 0, 1, 2, ..., 3 9, у адной палавіне і ў другой.
PROGRAM Heppy_ticket_2;
VAR i, j, k : Byte;
Count : Word;
a : ARRAY[0..9*3] OF Word;
BEGIN
Count :=0;
FOR i := 0 TO 27 DO a[i] :=0;
FOR i := 0 TO 9 DO
FOR j := 0 TO 9 DO
FOR k := 0 TO 9 DO
Inc(a[i+j+k]);
FOR i := 0 TO 27 DO
BEGIN a[i] := a[i] * a[i];
Count := Count + a[i];
END;
Writeln('колькасць=', Count); Readln;
END.
У гэтым варыянце зэканомілі час (прыкладна ў 20 разоў), але крыху аднялі памяці. Недахоп праграмы ў тым, што яна разлічана на шасціразрадныя лікі. Калі ж трэба зрабіць падлік для нумароў, разраднасць якіх розная і можа быць вядома толькі ў час выканання праграмы, тады можна інакш запраграміраваць нашы ўкладзеныя цыклы.
Гэта можна зрабіць па прынцыпу «спідометра». Праімітуйце работу спідометра, напрыклад чатырохразраднага. Заўважаеце, што гэта схема работы ўкладзеных цыклаў? Прыменім прынцып «спідометра» і палепшым папярэднюю праграму.
PROGRAM Heppy_ticket_3;
CONST
k=4; {2*k разрадныя лікі}
VAR
i : Byte;
Sum_Digit : Byte;
Count : Longint;
a : ARRAY[0..9*k] OF Word;
Cp : ARRAY[0..k] OF Byte;
BEGIN
FOR i := 0 TO k * 9 DO a[i] := 0;
{колькасць магчымых сум лічбаў}
FOR i := 0 TO k DO Cp[i] := 0;
{занулілі спідометр}
{Cp[0] := 1 спідометр перапоўнены}
REPEAT
Sum_Digit := 0;
FOR i := 1 TO k DO
Sum_Digit := Sum_Digit + Cp[i];
{падлічылі бягучую суму лічбаў
на спідометры}
Inc(a[Sum_Digit]);
i := k;
{пераходзім на наступную
камбінацыю лічбаў спідометра}
WHILE Cp[i] = 9 DO
BEGIN
Cp[i] := 0;
Dec(i);
END;
{скінуўшы ўсе лічбы 9 у канцы
спідометра, дададзім 1
у патрэбную пазіцыю}
Cp[i] := Cp[i] + 1;
UNTIL Cp[0] = 1;
Count := 0;
FOR i := 0 TO k*9 DO
BEGIN a[i] := a[i] * a[i];
count := count + a[i];
END;
Writeln('колькасць=', Count);
Readln;
END.
Заўвагі. Для захавання паслядоўнасці лічбаў спідометра выкарысталі масіў Cp[i], i = 0 ... k, у элементах якога запісваецца бягучы набор лічбаў. Для пераходу да наступнага варыянта трэба дадаць 1 да k-й (апошняй) лічбы ліку. Але гэта можна зрабіць толькі тады, калі яна не роўная 9. Калі лічба 9, то тады трэба скінуць у 0 і дадаць 1 да папярэдняй; калі яна не роўная 9 – па папярэдняму прынцыпу. Так працуем да той пары, пакуль не знойдзем лічбу . Паслядоўнасць будзе апошняй, бо па нашым алгарытме атрымаем , а гэта прымета заканчэння цыкла.