Аператар паўтарэння repeat

А ператар паўтарэння REPEAT складаецца з загалоўка цыкла (REPEAT), це­ла цыкла і ўмовы заканчэння (UNTIL).

Работа аператара: спачатку выконваецца цела цыкла, потым пра­вя­ра­ец­ца ўмова выхаду з цыкла. Пасля атрымання FALSE цела ак­ты­ві­зу­ец­ца яшчэ раз; пасля атрымання TRUE адбываецца выхад з цыкла. Гэты апе­ратар вы­кон­ва­ец­ца не менш як 1 раз! Аператарныя дужкі тут адсут­нічаюць. Па мен­шай меры адзін з аператараў цела цыкла павінен уплы­ваць на зна­чэн­не ўмовы, інакш цыкл будзе выконвацца бясконца ці толькі 1 раз.

Задача. Падлічыць у некаторым тэксце на рускай мове, які скла­да­ец­ца з малых літар і заканчваецца «.» (кропкай), колькасць зычных літар.

PROGRAM Letters;

VAR ch : Char;

s : Integer;

BEGIN

s:=0;

REPEAT

Read (ch); {пасімвальна ўводзіцца тэкст}

IF ch IN ([′б′..′щ′]–[′е′,′и′,′о′,′у′]) THEN s=s+1;

UNTIL ch=′.′;

Writeln (′колькасць зычных =′, s:3);

END.

Тут мы скарысталі канстанты – элементарныя мноствы. Гэтую за­да­чу можна запраграміраваць пры дапамозе аператара CASE.

Аператар паўтарэння while

А ператар WHILE падобны аператару REPEAT, але ўмова выканання це­ла цыкла правяраецца ў самым пачатку работы аператара.

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

WHILE true DO Write(′бясконцы цыкл′);

WHILE true = false DO Write(′пусты цыкл′);

Цыклы REPEAT і WHILE працуюць з рознымі ўмовамі. У цыкла REPEAT – умова заканчэння цыкла, а ў цыкла WHILE – умова працягу цык­ла.

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

Задача. Зададзены сапраўднае А і натуральнае k. Падлічыць не выкарыстоўваючы аперацыю ўзвядзення ў ступень.

Разгледзім звычайныя алгарытмы (іх як мінімум два):

а) CONST k=...; а=...;

...

b:=1; FOR i:=1 TO k DO b:=b*a;

б) CONST k:Byte=...; а=...;

...

b:=1;

WHILE k>0 DO

BEGIN b:=b*a; dec(k) END;

Аднак існуе больш танны алгарытм, які называецца хуткая ступень.

Хуткая ступень

Вышэй мы разглядалі просты алгарытм

(1)

У канцы атрымаецца

Аднак калі k – цотнае, тады мае месца тоеснасць Зна­чыць, можна зрабіць замену і зноў прымяніць алгарытм (1).

Атрымаем наступную праграму:

PROGRAM Quikstep;

VAR x, a, b : Real;

k, n : Integer;

BEGIN

Writeln(′a, k -′); Readln(x, n);

Write(x, ′^′, n, ′=′);

k := n;

b := 1;

a := х;

WHILE k>0 DO

BEGIN

IF Odd(k) THEN b := b * a;

k := k DIV 2;

a := a * a;

END;

Writeln (b);

END.

Тут скарысталі скарочаную форму аператара іf, таму што пасля ня­цот­на­га k := k-1 будзе ісці цотнае k, і выйдзем на k := k DIV 2, а гэ­та можна рабіць і не памяншаючы .

Праверым правільнасць работы праграмы пры

Вынік атрымаем за тры праходы:

Ітэрацыйныя алгарытмы вышэйшай матэматыкі

Як ужо адзначалася, пры дапамозе аператара FOR праграміруюцца цык­лы з зададзеным лікам паўтарэнняў, а аператары REPEAT … UNTIL ці WHILE … DO выкарыстоўваюцца тады, калі колькасць паўтарэнняў на­пе­рад невядома, а зададзена некаторая ўмова яго заканчэння (ці пра­цяг­ван­ня).

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

Прыклад 1. У час паўтарэнняў цела цыкла ўтвараецца пас­ля­доў­насць значэнняў якая імкнецца да ліміту а:

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

Цыклы, якія рэалізуюць такую паслядоўнасць набліжэнняў (ітэ­ра­цый), называюць ітэрацыйнымі.

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

дзе – дапушчальная хібнасць падліку выніку.

Тады вынік атаясамліваюць са значэннем г. зн. лічаць, што

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

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

Напішам праграму знаходжання з дакладнасцю

Рашэнне. Зыходнымі данымі з’яўляецца лік , з якога трэба зда­быць корань, і значэнне , якое з’яўляецца некаторым грубым на­блі­жэн­нем кораня (яго можна падлічыць, напрыклад, графічна).

В ынікам будзем лічыць той , калі (гэта вынікае з ліміту паслядоўнасці). Для захавання элементаў пас­ля­доў­нас­ці будзем выкарыстоўваць адну пераменную u.

Праграма, якая рэалізуе алгарытм на мове Pascal:

PROGRAM Newton;

VAR

a, y0, u, v : Real;

n : Integer;

BEGIN

Writeln('a, y0 =');

Readln(a, y0);

u := y0;

n := 0;

REPEAT

v := 0.5 * (a / u - u);

Inc(n);

u := u + v;

UNTIL (Abs(v) < 1E-3) ОR (n > 100);

Writeln('корань з', а : 8 : 3, '=', u);

END.

Заўвага. У такіх задачах, калі дрэнна па­даб­ра­на пачатковае прыбліжэнне , можа адбыцца «за­цыкліванне», таму трэба прадугле­дзець падлік кро­каў, і калі іх стала многа (напрыклад, та­ды працэс перарываем, друкуем v, u, n, а по­тым ацэньваем, ці правільна быў здзейсне­ны вы­бар пачатковага прыбліжэння.

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

Рад – гэта бясконцая сума віду

(1)

Складаемыя называюцца членамі рада, а сумы канечнага ліку чле­наў рада – частковымі сумамі рада па­рад­ку n.

Адрозніваюць лікавыя і функцыянальныя рады.

Прыклад лікавага рада: або сума геа­мет­рыч­най прагрэсіі калі

Членамі функцыянальнага рада з’яўляюцца функцыі.

Прыклад функцыянальнага рада:

Рад (1) называецца збежным, калі збягаецца паслядоўнасць яго част­ко­вых сум . У гэтым выпадку ліміт называецца сумай ра­да. Калі ліміт не існуе, тады рад разбежны.

Існуюць адзнакі збежнасці радоў. Адну з іх выкарыстоўваюць пры лікавых падліках сумы рада.

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

Нагадаем, што ўсе трыганаметрычныя функцыі, а таксама лагарыфмічная і экспаненцыяльная функцыі ў мовах праграміравання падлічваюцца пры дапамозе раскладання іх у рад.

Разгледзім падрабязнасці падліку частковых сум віду

Звычайна формула агульнага члена сумы належыць да аднаго з наступных трох тыпаў:

а) – атрыманне здабытку;

б) – здабытак адсутнічае зусім;

в) – здабытак прысутнічае часткова.

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

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

Напрыклад:

Тут мае від б), а – від а).

Задача. Для зафіксаванага x падлічыць з хібнасцю значэнне функцыі выкарыстоўваючы вядомае (з даведнікаў) рас­кла­дан­не функцыі у наступны рад:

дзе

Рашэнне. Будзем падлічваць да таго часу, пакуль або

Папярэдняя класіфікацыя падказвае, што агульны член нашага рада на­лежыць да тыпу а). Значыць, будзем шукаць залежнасць паміж сусед­ні­мі складаемымі.

Няхай зафіксавана нейкае Тады ,

дзе

І можам атрымаць

Фрагмент праграмы, якая рэалізуе алгарытм на мове Pascal:

{Тут аб'яўленне пераменных і пачатак праграмы}

S := 0;

a := 1;

k := 1; {n := 0;}

y := -x * x;

REPEAT

S := S +a;

a := a * y / k / ( k+ 1);

{a := -a * Sqr(x) / ((2 * n + 1) * (2 * n + 2));}

k := k + 2; {n := n + 1;}

UNTIL abs(a) < eps;

{надрукаваць вынік}

Для аптымізацыі цыкла пры запісе праграмы адразу палепшылі вы­лі­чаль­ную схему алгарытму. Перад цыклам уводзім дапаможныя пе­ра­мен­ныя і пры Цыкл з крокам 1 па пераменнай за­мя­няем на цыкл з крокам 2 па пераменнай

–x * x  y

2 * n + 1  k

n = 0, 1, 2, …  k = 1, 3, … (крок 2)

Астатнія аператары дапішыце самастойна.