Практикалық жұмыс №2

Тақырыбы: Циклдiк құрылымды алгоритмдердi ұйымдастыру

Жұмыс мақсаты: циклдік алгоритмдiк құрылымдары мен информацияны өңдеудегi түрлi алгоритмдердi пайдаланып математикалық қалыптау және әр түрлi есептердi алгоритмдеудiң үйрену.

Жұмыстың орындалу тəртібі:

1. Теориялық мəліметтермен танысу.

2. Жеке нұсқада тапсырмалар орындау. Алгоритмдердi шығыр-құрылым түрiнде бейнелеу.

3. Бақылау сұрақтарына жауап беру.

4. Орындалған жұмыс туралы жазбаша есеп беру. Есепте жұмыс тақырыбы, мақсаты, тапсырманың математикалық үлгісі, алгоритмнің блок – схемасы болуы қажет.

2.1 Негізгі түсініктер

2.1.1 Циклдік алгоритм түсінігі

Алгоритмнiң көп рет қайталап орындалатын бөлiктерiн цикл деп, ал қайталану әрекеттер тiзбегiн цикл денесi деп атайды. Циклдiк алгоритмдердi пайдалану оларды кейiннен программаларда цикл операторы түрiнде қысқартып жазуға мүмкiндiк бередi. Сонымен, бiрнеше рет қайталанатын бөлiгi бар алгоритмдер тобы циклдiк алгоритмдерге жатады.

Алгоритмдегi әрекеттер өзiнiң жазылу ретiне сәйкес тiзбектелiп немесе белгiлi бiр шартқа байланысты тармақталып немесе қайталанып орындалады. Яғни, алгоритмдегi әрекеттердiң орындалу тәртiбi белгiлi бiр нұсқаулар бойынша басқарылады. Осындай нұсқауларды басқару құрылымдары деп атайды.

Кез келген алгоритмдi құруда басқару құрылымдардың маңызы зор болып табылады. Негiзгi басқару құрылым-дарына сызықтық және тармақталу құрылымдарымен қатар циклдiк құрылымды алгоритмдерi де жатады.

Сурет 2.1. Қайталану (цикл) алгоритмдерiнiң негiзгi типтерi

2.1 - суретте бейнеленген циклдiк алгоритмдерiнiң ерекшелiктерi мынада: а) бұл қайталану қурылымында - цикл денесiн құрайтын шығырлар мен цикл параметрiнiң өзгеруi циклдiң қайталануын тексеретiн шығырдан кейiн орналасқан (”Дейiн”-циклi); б) бұл қайталану қурылымында - цикл денесiн құрайтын шығырлар мен цикл параметрiнiң өзгеруi циклдiң қайталануын тексеретiн шығырға дейiн орналасқан (”әзiрше”- циклi).

Цикл қайталанған сайын өзiнiң мәнiн өзгертетiн айнымалыны басқарушы айнымалы немесе циклдiң параметрi деп атаймыз. Циклдiң параметрi – циклдiң қайталауын реттейтiн, циклдiң iшiнде қайталану мөлшерiн басқаратын айнымалы. Алгоритмнiң орындалу барысында цикл параметрi – мысалы х, өзiнiң ең алғашқы х₀ мәнiнен ең соңғы х_k мәнiне дейiн тұрақты h шамаға өзгерiп отырады. Осының нәтижесiнде цикл параметiрi төмендегi мәндердi қабылдайды:

х₀, х₀+ һ, х₀+2һ, х₀+3һ, … , х₀+(k-1)h, х_k

Циклдiк қайталану саны келесi формула арқылы есептеледi:

арқашанда бүтiн сан болады, егер ол аралас сан болса, онда оның бөлшегi алынып тасталады, өйткенi n қайталау санын анықтайтын шама оның мәнi тек бүтiн натуралдық сан болмақ.

Байқағанымыздай, белгiлi бiр мәлiметтер жиынтығы мәндерiнде сызықтық және тармақталған құбылыстар бiр-ақ реттен орындалады, ”Дейiн” –циклi болса - кем дегенде бiр рет орындалады (өйткенi цикл аяқталғаны жөнiндегi шарттың бiрiншi тексерiлуi цикл денесiнiң әрекеттерi орындалғаннан кейiн болады), ал ”әзiрше” -циклi бiр рет те орындалмауы мүмкiн. Циклдердi қолдану алгоритм шығырларының көлемiн және пограмманың ұзындығын қысқартып ықшамды түрде көрсетүге мүмкiндiк бередi.

Циклдер белгiлi бiр ережелер бойынша ұйымдастырылады. ”Дейiн”- циклiнiң табиғи тiлде жазылған алгоритмiн қарастырайық.

1. Алдымен бастапқы мән меншiктеу жүргiзiледi (цикл параметрiне бастапқы мәнi меншiктелiнедi, қосынды жинақтау үшiн бастапқы мән 0, ал көбейтiндi жинақтау үшiн бастапқы мән 1-ге тең деп алынады).

2. Циклдiң денесiнiң әрекеттерi орындалады (есептеу процесiнiң бiрнеше рет қайталанатын бөлiктерi).

3. Әр қайталымға сәйкес циклдiң параметрi өзгертiледi.

4. Цикл соңы немесе қайталану шарты тексерiледi.

5. Циклдi басқару, яғни циклдiң басына өту, егер циклдiң қайталануы қажет болса, немесе циклдiң қайталануы бiткен соң одан шығу.

Циклдiк алгоритмдерде қайталану саны алдына ала белгiлi циклдер деп және цикл денесiнiң орындалу саны алдын ала белгiсiз деп бөлуге болады. Бiрiншi жағдайда оларды реттелген циклдер деп ал екiншi жағдайда, итерациялық циклдер деп ажыратады. Қайталану саны алдына ала белгiлi циклдерде цикл параметрiнiң бастапқы және сонғы мәндер белгiлi болады. Цикл параметрiнiң мәнi белгiлi бiр айқын заңдылық бойынша, цикл қайталанған сайын өзгерiп отырады. Осы заңдылық арқылы циклдiң қайталану саны анықталады. Итерациялық циклдерде өзгеру заңы ашық түрде берiлмейдi.

2.1.2 Қосынды, көбейтiндi жинақтау және функция мәнiн кестелеу алгоритмдерi

Берiлген қосылғыштардың қосындысын табу алгоритмi циклдiк құрылымды типтiк алгоритмдерге жатады. Мұндай есептерде цикл параметрi болып қосылғыштың нөмерiн белгiлейтiн айнымалы саналады. Мiндеттi түрде циклға енбес бұрын бастапқы меншiктеулер орындалуы тиiс: цикл параметрiне бастапқы мәнi меншiктеледi, қорытынды нәтиже жинақтайтын айнымалыны 0-ге теңестiремiз. қосынды жинақтайтын алгоритмдерде циклды әр қайталанған сайын келесi әрекеттер орындалады:

а) кезектi қосылғыштың мәнi есептеледi;

б) қосындының мәнiн осы кезектi косылғышқа арттыру арқылы қосындыны жинақтау; в) цикл параметрiнiң мәнiн өзгеруi;

г) қайталанудың аяқталғанын тексеру.

Төменде көрсетiлген мысалда қосындыны табу барысында келесi рекуренттiк формула қолданып, қосындыны жинақтау әдiсi пайдаланған: S = S + y,

S – қосынды жинақтайтын нәтижелiк айнымалы;

у ( кезектi қосылғышты белгiлейтiн айнымалы.

Нәтижелiк S айнымалының бастапқы мәнi 0-ге тең, ал цикл қайталанған сайын кезектi қосылғыштың y мәнi есептелiп, S-ке қосылады (яғни қосынды жинақталады). Қосындының қорытынды нәтижесiн анықтайтын алгоритмдерiн құрудың басқа да жолдары бар, бiрақ қосындыны жинақтау арқылы есптейтiн әдiстi тиiмдi деп санаймыз. Типтiк цикл алгоритмдерiне мысалдар қарастырайық.

1 - мысал. 1-ден 99-ға дейiнгi сандар қосындысын есептеуге арналған алгортмiн құру қажет.

S = 1 + 2 +3 + 4 +5 + … + 99 =

Цикл параметрi, яғни цикл қайталануын реттейтiн айнымалы - к. Бұл мысалдың алгоритмiн құру барысында келесi үш түрлi берiлгендер кездеседi: бастапқы , қосалқы (аралық) және нәтижелiк берiлгендер.

Бастапқы берiлгендер: цикл параметрi – к; цикл параметрiнiң бастапқы мәнi - к =1; цикл парметрiнiң соңғы мәнi - к =99;

Қосалқы айнымалылар: у - әр қайталанған сайын кезектi қосылғыштың мәнiн сақтайтын (есептейтiн) айнымалы.

Нәтижелiк айнымалы : S

Есептiң алгоритмiнiң шығыр-құрылымы:

Сурет 2.2. Нәтижелiк қосынды жинақтау алгоритмiнiң шығыр-құрылымы

2 - мысал. х₀ –ден х_k -ға дейiн h қадамымен х-тың өзгеру барысында F = ax³ + sin(ax²) / 2 функциясының мәндерi бойынша кесте құрастырыңыздар. Келесi бастапқы берiлгендер бойынша: х₀ = 0; х_k = 3; h = 0.1; а – кез келген нақты сан.

Функцияның мәнiн кестелеу мәселесiнiң шешiмiн циклдiк құрылымды алгоритм түрiнде келтiруге болады. Әр қайталап есептеулерiнде өз мәнiн өзгертетiн х- айнымалысын цикл параметiрi деп аламыз. 10 а) суретте көрсетiлгендей цикл денесiн құрайтын: F функциясының жаңа мәнiн анықтайтын, F және х мәндерiн баспаға шығаратын, цикл параметрiнiң мәнiн өзгертетiн және қайталау шартын тексеретiн блоктер. Бұл блоктер х-айнымалысы өзiнiң ең соңғы х_k мәнiнен артық болғанша қайталанып орындала бередi. х-айнымалысының мәнi х_k-дан үлкен болған жағдайда алгоритмнiң циклдiк бөлiгi қайталануын тиып, басқару келесi блоққа өтедi (мысалда ол алгоритмнiң соңын бiлдiретiн блок). Әрi де осы сәтте цикл параметрiнiң ағымдық мәнi х_k-дан қадам мөлшерiне артық екенiн естерiңiзге салуды жөн санаймыз.

Бастапқы берiлгендер: х₀ = 0; х_k = 3; h = 0.1; а – кез-келген сан;

Қосалқы айнымалылар: жоқ;

Нәтижелiк айнымалылар: F, x.

А) басы Х = 0 F = ax3+sin(ax2)/2 x, F x = x+0.1 Иә соңы

Б)

Сурет 2.3. а) функцияның мәндерiн кестелеу мәселесiнiң шығыр-құрылымды алгоритмi;

б) осы мысалдың модификатор шығырын пайдаланып құрылған алгоритмi

Берiлген функцияның мәндерiн кестелеу алгоритмдерiнiң ерекшелiгi: қорытынды нәтиженi баспаға беру блогының цикл денесiнде орналасқандығы болып табылады. Яғни есептiң шарты бойынша әр қайталауда х-аргументiнiң мәнi өзгертiлiп, және осыған сәйкес F функциясының жаңа мәнi есептелiп баспаға шығарылуы тиiс.

• Қосындыны (көбейтiндiнi) жинақтау және функцияның мәндерiн кестелеу есептерiнiң алгоритмдерiнде қорытынды нәтиженi баспаға беру блоктарының ораласуын салыстырыңыздар. Олардың айырмашылығын тестiлеу барысында анықтаңыздар.

• 2.3 суреттегi а) және б) жағдайындағы алгоритмдердiң көрнектiлiгiн және орындалуын салыстырыңыздар.

2.1.3 Күрделi циклдiк құрылымдарды алгоритмдеу

3 - мысал. Кез келген N сандардың қосындысын және көбейтiндiсiн анықтайтын алгоритм құру керек (2.4 сурет).

Бастапқы берiлгендер: N – сандардың мөлшерi; A – осы сандардың мәндерi; i – санның реттiк нөмiрi (цикл санаушысы);

Қосалқы айнымалылар: жоқ;

Нәтижелiк айнымалылар: S, P .

Бұл мысалды шығару алгоритмi 2.4 суретте екi вариантында көрсетiлген. Екiншi варианты – ол алгоритмдi модификатор блогын қолданып құру.

Төменде қарастырылған алгоритмдер қағида бойынша көптеген тәжiрибелiк есептерiнiң алгоритмдерiнде құрама бөлшек ретiнде пайдаланады. Мысалы, орташа шамаларды (орташа толем ақыны, солдаттардың орташа бойын және салмағын, орташа өнiмдiлiктi, т.с.с.), қорытынды нәтижелердi, геометриялық орта т.б. есептеу барысында. Бұл есептердiң ерекшелiгi: мәлiметтердi енгiзу блогы цикл денесiнде орналасқаны болып табылады.

Сурет 2.4. Кез келген сандардың қосындысын және көбейтiндiсiн анықтайтын алгоритм

ЖЕКЕ ТАПСЫРМАЛАР НҰСҚАЛАРЫ

Вариант		Тапсырмалар
1		2
1	А	мұндағы х( [0;7], hx= 0.5
	Б
	В
	Г	Берiлген тiзбегiнде мәндерi 25 кiшi болатын элементтерiнiң көбейтiндiсiн табу керек.
2	А	мұндағы х( [0;12], hx= 1
	Б
	В
	Г	Берiлгенi: тiзбек элементтерi, келесi формула бойынша S мәнiн анықтау керек:
3	А	мұндағы х( [-1;1], hx= 0.2
	Б
	В
	Г	Берiлгенi: тiзбек элементтерi. Келесi формула бойынша S мәнiн анықтау керек:
4	А	мұндағы х( [2;5], hx= 0,25
	Б
	В
	Г	Берiлгенi: тiзбек элементтерi. Келесi формула бойынша S мәнiн анықтау керек:
5	А	мұндағы i( [1;10], hi= 1
	Б
	В
	Г	Берiлгенi: тiзбек элементтерi. Келесi формула бойынша S мәнiн анықтау керек:
6	А	мұндағы х( [0;12], hx= 1
	Б
	В
	Г	Берiлген элементтер тiзбегiнде оң элементтерiнiңS қосындысын және терiс элементтерiнiң Р көбейтiндiсiн табу керек.
7	А	мұндағы х( [-0.5;1.5], hx= 0.25
	Б
	В
	Г	Берiлгенi: тiзбек элементтерi Келесi формула бойынша S мәнiн анықтау керек:
8	А	мұндағы u( [-0.5;1.5], hu= 1
	Б
	В
	Г	Берiлген элементтер тiзбегiнде оң элементтерiнiң арифметикалық ортасын және –5 кiшi болатын терiс элементтерiнiң көбейтiндiсiн табу керек.
9	А	мұндағы х( [0.5;2.5], hx= 0.4
	Б
	В
	Г	Берiлгенi: тiзбек элементтерi. Келесi формула бойынша S мәнiн анықтау керек:
10	А	мұндағы t( [2;2.7], ht= 0.1
	Б
	В
	Г	Берiлген элементтер тiзбегiнде мәндерi 5-тен кем болатын элементтерiнiң арифметикалық ортасын табу керек.
11	А	мұндағы х( [-0.5;1], hx= 0.25
	Б
	В
	Г	Берiлгенi: тiзбек элементтерi. Келесi формула бойынша S мәнiн анықтау керек:
12	А	мұндағы х( [0.5;19], hx= 0.2
	Б
	В
	Г	Берiлген элементтер тiзбегiнде мәнi 2-ден үлкен болатын оң элементтерiнiңS қосындысын және терiс элементтерiнiң Р көбейтiндiсiн табу керек.
13	А	мұндағы х( [0;6.5], hx= 1.3
	Б
	В
	Г	Берiлгенi: тiзбек элементтерi. Келесi формула бойынша S мәнiн анықтау керек:
14	А	мұндағы х( [0.5;2], hx= 0.3
	Б
	В
	Г	Берiлгенi: тiзбек элементтерi. Келесi формула бойынша S мәнiн анықтау керек:
15	А	мұндағы х( [3;10], hx= 0.7
	Б
	В
	Г	Берiлгенi: тiзбек элементтерi. Келесi формула бойынша S мәнiн анықтау керек:

Бақылау сұрақтары

1. Циклдiк құрылымды алгоритмдерiнiң ерекшелiктерi неде?

2. Циклдiң параметрi деген не?

3. Циклдiк алгоритмдерiнiң iс-әрекеттерi қандай кезектiлiкпен орындалады (циклдарды ұйымдастыру ережелерi)?

4. Қосындыны және көбейтiндiнi жинақтау есептерiнде циклд ұйымдастырудағы әрекеттердiң кезектiлiгiн және олардың ерекшелiгiн атаңыз.

5. Функция мәнiн кестелеу есептерiнде цикл ұйымдастырудағы әрекеттер кезектiлiгiн және олардың ерекшелiгiн атаңыз.

6. Модификатор шығырының iшiнде қандай информация жарияланады?

7. Модификатор шығырының кескiн үйлесiмi және орындайтын әрекетiн түсiндiрiңiздер.

8. ”Дейiн” және ”әзiрше” циклдiк алгоритмдерiнiң орындалу ерекшелiгiн көрсетiңiздер.

9. Типтiк циклдiк құрылымды алгоритмдердi атаңыз.

10. Цикл параметрiнiң қадамы дегенiмiз не, және ол қандай мәндердi қабылдай алады?

Ұсынылатын әдебиеттер: 1, 2, 7