Жоғары деңгейлі тілдерінде программалау

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 17 бет
Таңдаулыға:

МАЗМҰНЫ

Кіріспе 4

1 Есептің қойылымы 6

2 Сұрыптау алгоритмі 6

3 Таңдау арқылы сұрыптау 7

4 Айырбастау арқылы сұрыптау 8

5 Шейкерлі сұрыптау 9

6 Қосу арқылы сұрыптау 10

7 Хоар сұрыптауы 11

8 Іздеу алгортмдері 13

9 Сызықты іздеу 13

10 Тасқауылы бар іздеу 14

11 (Екілік) бинарлы іздеу 15

12 Әдістің баяндалуы 16

13 Есептің алгоритмін жасау 16

14 Программаның алгоритмі 16

15 Паскаль тіліндегі программа 20

16 Программаның блоксхемасына түсінік 24

17 Программаның баяндалуы 26

Қорытынды 27

Пайдаланылған әдебиеттер 28

Кіріспе

Жазылған программа курстық жұмыс болып табылады. Бұның орындалуы “Жоғары деңгейлі тілдерінде программалау” пәнінің соңғы қадамы болып есептеледі. Студент өз мүмкіндіктерін қорыта келе бір бағытта түпкілікті жұмыс істей алады. Курстық жұмыс жасау уақытысында студент іс жүзінде есепті шығара отырып, тәжірибе жинауы тиіс. Ол өзінің үйренгенін қорыта отырып, программалауға арналған оқулықтарды дұрыс пайдалануын, есеп шығару кезінде жаңа және тиімді тәсілдерді ойлап табуын, алгоритмді дұрыс құруын, Си және Паскаль тілдерінің көптеген операторларын үйренуі қажет.

Курстық жұмыстың басты мақсаты: студенттің практикада санау жүйесімен танысып, ойындар, күрделі есептер орындауда тәжрибе жинақтауына негізделген. Алдыға қойған мақсат студенттің өзіндік жұмысы арқылы және Паскль тілінде алгоритмді дұрыс құру, операторларды орынды пайалану арқылы жүзеге асады.

Бұл курстық жұмысты “Жоғары деңгейлі тілдерінде программалау” пәнінен үйренгенімді көрсету мақсатымен ойлап шығардым.

Қазіргі уақытта ғылыми техникалық дамуының жетістіктеріне сай, алдыңғы қатарлы ЭЕМ өміріміздің әр түрлі саласында кеңінен қолданылуда. Осыған орай ЭЕМ-да жұмыс істеу реттерін программа арқылы басқара алатын систематехника инженеріне сұраныс көп.

ЭЕМ-сымен арақатынас қалыптастыруда керекті алгоритмдік тілдер: Фортран, Паскаль, Бейсик, Си, және т. б. компьютерде есептерді белгілеп, нәтижесін шығаруға бейімделген.

Соның ішіндегі программалау технологиясы мен алгоритмдік тілдерді оқытып үйретуге ыңғайлысы Паскаль тілі туралы қысқаша айта кетелік.

Паскаль тілінде Цюрих технологиялық институтының профессоры Никлоус Вирт алғашқыда жалпы программалауды оқыту мақсатымен құрастырған. Бұл тіл 1975 жылы Швецарияда ұсынылған болатын. ЭЕМ-ң түсінуіне, орындауына қолайлы тіл ретінде сол кездегі алдыңғы қатарлы тілдердің жақсы мүмкіндіктерінің барлығын бойына сіңірген болатын.

Pascal тілі әйгілі профессионалдық программалау тілдерінің арасынан әлі өз позициясын жоғалтқан жоқ. Бұл тіл басқа программалау тілдері мүмкіншіліктерінің бәрін бойына сіңіре отырып, сонымен қатар ол программистке басқа да көптеген мүмкініліктерді береді, жады ұяшығына және компьютер регистрлеріне қатынас құруға мүмкіндік береді. Ол үшін компьютер ерекшеліктерін бөлуді қажет етеді.

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

Әрбір ЭЕМ алдын ала берілген алгоритммен, яғни жоспармен жұмыс істейді. Алгоритмді белгілі бір заңдылық бойынша, реттелген амалдар жиыны арқылы көрсетілген, кезекпен орындалатын операциялар тізімі деп ұғынсақ дұрыс болады. Бұл ұғым қазіргі кезде кеңінен қолданылып жүр.

Бұл крстық жұмыста ойын жазу қарастырылған. Ойын ерте заманнан келе жатқан ең қызықты уақыт өткізудің бір түрі. Жалпы ойынның шығуы адам өмірімен тығыз байланысты. Ойындар адамның демалуына әсер етеді. Әлемде әр түрлі ойындар бар. Физикалық қимылдарды көп талап етпейтін логикалық ойындар да өте көп.

Ғылыми техникалық прогреспен қатар біздің өмірімізде компьютерлік ойындар пайда болған. Компьютерлік ойындар өзінің спецификациясына байланысты біздің өмірімізде басқа ойындардан гөрі ерекше орын алады. Өйткені программист өз қолымен жасап алған, өмірде кездеспейтін және оған ұнайтын ешкімге тәуелді емес заңдылықтарды жасай алады. Менің біліумше компьютердің мүмкіншіліктері шексіз. Сондықтан компьютерлік ойындар күрт дамып, шектік туралы ұғымды жоққа шығарды. Сөйтіп ойындардың көп түрлері пайда болды.

1 Есептің қойылымы

Қазіргі уақытта есептеуіш техника адамзат өміріндегі барлық әрекет өрісіне енді. Көбінесе бұл жағдай - мини әсіресе микро ЭЕМнің қарқынды дамуымен түсіндіріледі. Қазір компьютерлерді университет лабораторияларында ғана емес, сонымен бірге мектеп сыныптарында да көруге болады. Біздің уақытта компютерлерге көптеген адамдардың, мамандығы программист болмаса да, қолы жететін мүмкіндіктері пайда болды. 1980 жылдары барлық ойындар және оқытатын программалар MS-DOS операциялық жүйеге арнап жазылған болатын, оның себебі - графикалық редакторлардың әлсіздігі және де жадының жетіспеушілігі. Кейін жаңа WINDOWS операциялық жүйелерінің пайда болды да, олардың графикалық редакторлары мықты болып, оқытатын программалар барлық ғылыми және техникалық мекемелерінде пайда болды, сонымен қатар кішкентай балаларды оқытатын ойын программалары пайда болды.

Жұмыстың мақсаты берілген 1, 2, 3, 4, 5, 6, 7, 8, 9 сандарын квадрат таблицасына келесі тәртіппен орналастыру керек:

горизонталь бағытта;
вертикаль бағытта;
диагоналі бойынша сандардың қосындылары 15-ке тең болуы қажет.

Бұл орналастырудан шыққан квадрат- магиялық квадрат деп аталады.

Алдымен программа іске қосылғанда, “graph” модулі арқылы интерфейс жасалады. Экранның жоғарғы жағында “Rasstanovka”, ортасында “*9*”, астынғы жағында “chisel” жазулары бар. Ойын басталғанда экранға үш таяқша шығады. Олардың біріншісінде бірнеше диск орналасқан. Есептің шарты бойынша дискілердің диаметрі жоғары қарай кішірейеді. Осыдан кейін ойыншы іске қосылуы керек. Сонан соң ғана дискілерді бір таяқшадан келесі таяқшаға көшіреміз.

2 Сұрыптау алгоритмдерi

Бұл айтылған пікірлердің барлығы программалаудың ең бір қажетті мүмкіндіктері сұрыптау мен іздеуге арналған. Сұрыптау мен іздеуді кез-келген программада қолдануға болады. олардың мүмкіндіктері шексіз. Осы мүмкіндіктерді пайдалана отырып, программа алгоритімін қарапайым жолмен жеңілдетуге болады. Негізінен сұрыптау мен іздеудің түрлері өте көп.

Кез-келген күнделікті жағдайда біз сұрыптау және іздеу үрдістерімен жұмыс жасаймыз. Әр адамда неліктен деген сұрақ туады. Жауап өте қарапайым. Себебі бұл үрдістермен жұмыс жасау өте ыңғайлы. Тіпті өзіміздің күнделікті қолданып жүрген персоналды компьютерімізде сол принциппен жұмыс істейді. Олар сіз енгізген мәліметтерді сұрыптап қояды да сіз оларды іздегенде лезде тауып бере қояды. Сұрыптау мен іздеу тәсілдерін кеңінен қолданады. Бұл тәсілдерді қарапайым студентте кәсіпқой программистте қолдана алады. Жалпы алғанда кез-келген программа сұрыптаудан басталады. Ал тез сұрыптап қажет элементті табу үшін сұрыптау және іздеу тәсілдерін жетік білген жөн. Сондықтан сұрыптау мен іздеу тәсілдерін қарастырып көрейік.

Сұрыптаудың ең қарапайым есебi массив элементтерiнiң өсу не кему ретiмен орналастыру болып табылады. Басқа есеп болып, берiлген белгiлер бойынша массив элементтерiн реттеу. Әдетте мұндай белгi ретiнде аргументi массив элементтерi болып табылатын белгiлi функция мәнi болып табылады. Бұл функцияны реттеушi функция деп атау қабылданған.

Сұрыптаудың әр түрлi тәсiлдерi бар. Әрбiр тәсiлдi N бүтiн сандардан өспелi массивтi сұрыпттау мысалында көрсетемiз.

3 Таңдау арқылы сұрыптау

Тәсiл идеясы массивтiң максималды элементiн тауып, оны соңғы элемент (N номерлi) орнымен ауыстырылады. Содан кейiн максималды элемент N-1 орынға дейiн iзделiп, сол N-1 орынға қойылады және т. с. с. Максимум емес, минимум элемент iзделiп, оны бiрiншi, екiншi және т. с. с. орынға қоюға болады. Сонымен қатар бұл әдiстiң модификацияланған түрi - бiр мезетте максимум және минимум элементтердi iздеу қолданылады. Бұл жағдайда сыртқы циклдың қадамдар саны N div 2.

Мысалы : a массивiнiң N бүтiн сандарының өсуi бойынша таңдау арқылы сорттау.

Program Sort_Tandau1;

Var a:array[1. . 20] of integer;

N, i, m, k, x : integer;

Begin

write('Массив элементтерiнiң саны') ;

read(N) ;

For i:=1 to n do

writeln('Массивтi енгiзiңiз') ;

read(a[i] ) ;

For k:=n downto 2 do { k - max-ты iздеуге қажеттi элементтер саны }

begin

m:=1; { m - max орны}

For i:=2 to k do if A[i] >A[m] then m:=i;

{ m және k номерлi элементтердi орындарымен ауыстырамыз}

x:=a[m] ; a[m] :=a[k] ; a[k] :=x;

end;

for i:=1 to n do write(a[i], ' ') ; {реттелген массив}

end.

Мысалы: Жоғарыдағы есеп, бiрақ бiр мезеттегi max пен min таңдау арқылы.

Program Sort_Tandau2;

Var a :array[1. . 100] of integer;

N, i, m, k, x, p : integer;

Begin

write('Массив элементтерiнiң саны') ;

read(N) ;

For i:=1 to n do

writeln('Массивтi енгiзiңiз') ;

read(a[i] ) ;

For k:=1 to n div 2 do { k - max және min жұбының орны }

Begin

m:=k; { m - max орны }

p:=k; { p - min орны }

{max және min k-дан n-k+1 элементтер арасында iзделедi }

For i:=k+1 to n-k+1 do

if a[i] >a[m] then m:=i

else if a[i] <a[p] then p:=i;

{ p және k номерлi элементтердi орындарымен ауыстырамыз }

x:=a[p] ; a[p] :=a[k] ; a[k] :=x;

if m=k then m:=p;

{егер max k орында тұрса, ендi ол p орында тұр }

{ m және n-k+1 номерлi элементтердi орындарымен ауыстырамыз }

x:=a[m] ; a[m] :=a[n-k+1] ; a[n-k+1] :=x;

end;

for i:=1 to n do write(a[i], ' ') ; {реттелген массив}

end.

4 Айырбаспен сұрыптау (“көбiкше” тәсiлiмен)

Тәлiл идеясы рет бойынша массивтiң көршiлес жұптары тексерiлуiнде құрылған. Егер олар олар керектi реттiлiкте болмаса, онда көршiлес элементтер жұбын орындарымен ауыстырамыз. Мұндай бiр өтуден кейiн N номерi орынында максимал элемент орналасады (бiрiншi көбiкше “қалқып” шықты) . Келесi өту N-1 элементке дейiн қарастыру керек және т. с. с. Барлығы N-1 өту қажет болады.

Мысалы : a массивiнiң N бүтiн сандарының өсуi бойынша айырбаспен сұрыптау. (Негiзгi вариант)

Program Sort_Auis1;

Var a:array[1. . 20] of integer;

N, i, k, x : integer;

Begin

write('Массив элементтерiнiң саны') ;

read(N) ;

For i:=1 to n do

writeln('Массивтi енгiзiңiз') ;

read(a[i] ) ;

For k:=n-1 downto 1 do { k - салыстырылатын жұптар саны }

For i:=1 to k do

If a[i] >a[i+1] then

{көршiлес элементтердi орындарымен ауыстырамыз}

Begin x:=a[i] ; a[i] :=a[i+1] ; a[i+1] :=x;

End;

For i:=1 to n do

write(a[i], ' ') ; {реттелген массив}

end.

5 Шейкерлi сұрыптау

Бұл алгоритм негiзiнен айырбас арқылы сұрыптаудың модификациясы болып табылады. Айырмашылығы айырбас арқылы сұрыптауда өтулер бiр жақты ғана болса, мұнда бағыт әрбiр рет сайын өзгерiп отырады. Сонымен қатар шейкерлi сұрыптауда айырбас фактi мен айырбастың соңғы орнын анықтауға болады. Негiзгi алгоритмде екiлiк өтулер саны N div 2-ге тең.

Мысалы: N бүтiн сандардан құралған А массивiн Шейкерлi сорттау арқылы өсу ретiмен орналастыру.

Program Shaker;

Var a:array[1. . 20] of integer;

N, i, k, x, j, d : integer;

Begin

write('Массив элементтерiнiң саны') ;

read(N) ;

For i:=1 to n do

writeln('Массивтi енгiзiңiз') ;

read(a[i] ) ;

d:=1; i:=0;

For k:=n-1 downto 1 do { k - салыстырылатын жұптар саны }

Begin

i:=i+d;

For j:=1 to k do

Begin

If (a[i] -a[i+d] ) *d>0 then

{көршiлес элементтердi орындарымен ауыстыру}

Begin x:=a[i] ; a[i] :=a[i+d] ; a[i+d] :=x; end;

i:=i+d;

end;

d:=-d;

{қозғалыс бағытын қарама-қарсыға өзгертемiз}

end;

For i:=1 to n do write(a[i], ' ') ; {реттелген массив}

end.

6 Қосу арқылы сұрыптау

Бер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.

Мысалы : N бүтiн сандардан құралған А массивiн сызықты iздеуi бар қосу арқылы сұрыптау арқылы өсу ретiмен орналастыру.

Program Sort_Include1;

Var a:array[1. . 20] of integer;

N, i, k, x : integer;

Begin

write('Массив элементтерiнiң саны ') ;

read(N) ;

writeln('Массивтi енгiзiңiз') ;

read(a[1] ) ; {For i:=1 to n do read(a[i] ) ; }

{k - массивтiң реттелген бөлiгiндегi элементтер саны}

For k:=1 to n-1 do

Begin

read(x) ; {x:=a[k+1] ; }

i:=k;

while (i>0) and(a[i] >x) do

begin

a[i+1] :=a[i] ;

i:=i-1;

end;

a[i+1] :=x;

end;

For i:=1 to n do write(a[i], ' ') ; {реттелген массив}

end.

Мысалы: N бүтiн сандардан құралған А массивiн екiлiк iздеуi бар қосу арқылы сұрыптау арқылы өсу ретiмен орналастыру.

Program Sort_Include2;

Var a :array[1. . 20] of integer;

N, i, k, x, c, left, right : integer;

Begin

write('Массив элементтерiнiң саны') ;

read(N) ;

writeln('Массивтi енгiзiңiз') ;

read(a[1] ) ; {For i:=1 to n do read(a[i] ) ; }

{k - массивтiң реттелген бөлiгiндегi элементтер саны }

For k:=1 to n-1 do

Begin

read(x) ; {x:=a[k+1] ; }

left:=1; right:=k;

{iздеуге керектi фрагменттiң оң және сол шекарасы}

while left<right do

{соңғы кiрудiң екiлiк iздеуi}

begin

c:=(left+right+1) div 2;

{ үлкен жаққа дөңгелектенген ортасы }

if x>=a[c] then left:=c

{ортасы мен оң жағын аламыз}

else right:=c-1; {ортасыз сол жағын аламыз}

end;

if x>=a[left] then left:=left+1;

{х қосылуға орын босата отырып, массивтi 1 орынға оңға жылжытамыз}

for i:=k downto left do a[i+1] :=A[i] ;

a[left] :=x;

end;

For i:=1 to n do write(A[i], ' ') ; {реттелген массив}

end.

7. Хоар сұрыптауы

Бұл сұрыптауды жылдам сұрыптау деп те атайды. Әдiстi 1962 жылы Оксфорд университет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 элементтер санына пропорционал.

Мысалы : N бүтiн сандардан құралған А массивiн жылдам сұрыптау арқылы өсу ретiмен орналастыру.

Program Quick_Sort;

Var a:array[1. . 20] of integer;

N, i : integer;

{Процедураға сұрыпталатын үзiндiнiң оң және сол шекаралары берiледi}

Procedure QSort(L, R:integer) ;

Var X, y, i, j:integer;

Begin

X:=a[(L+R) div 2] ;

i:=L; j:=R;

while i<=j do

Begin

while a[i] <X do i:=i+1;

while a[j] >X do j:=j-1;

if i<=j then

Begin

y:=a[i] ; a[i] :=a[j] ; a[j] :=y;

i:=i+1; j:=j-1;

end;

if L<j then QSort(L, j) ;

if i<R then QSort(i, R) ;

end;

Begin

write('Массив элементтерiнiң саны') ;

read(N) ;

For i:=1 to n do

writeln('Массивтi енгiзiңiз') ;

read(a[i] ) ;

QSort(1, n) ; {бiрiншiден n-шiге дейiнгi элементтердi реттеу}

for i:=1 to n do

write(a[i], ' ') ; {реттелген массив}

end.

8 Iздеу алгоритмдерi

Iздеу алгоритмдерi мысалы массивте белгiлi қасиеттерi бар элементтердi табу үшiн қолданылады. Әдетте элементтiң алғашқы және соңғы кiрулерiн iздеудегi есеп берiлгендерiмен ажыратады. Төменде келтiрiлген барлық алгоритмдерде N бүтiн санды a массивiнде Х-қа тең элемент iздеу керек деп есептеледi.

9 Сызықты iздеу

Сызықты iздеу екi еселi шарты бар циклмен ( while немесе repeat - until ) орындалады. Бiрiншi шарт индекстiң массивке тиiстiлiгiн тексередi, мысалы, (i<=N) . Екiншi шарт - бұл iздеудiң шарты. Бiздiң жағдайда while циклiнде бұл iздеудi жалғастыру шарты: (A[i] <>X), ал repeat - until циклiнде бұл iздеудi аяқтау шарты: (A[i] =X) . Цикл денесiнде әдетте тек жалғыз оператор: массивтегi индекстiң өзгеруi ғана жазылады.

Циклдан шыққаннан кейiн қай шарт бойынша шыққанымызды тексеруiмiз керек. Әдетте if операторында циклдiң бiрiншi шартын қайталайды. Бұл шарт орындалуын while циклi жағдайында шарттың орындалуын, ал repeat - until циклiмен оның бұзылуы кезiнде сәттi iздеу деп айтуға болады.

Мысалы: Сызықты iздеу.

Program Poisk1;

Var a:array[1. . 20] of integer;

N, X, i:integer;

begin

read(N) ; {N<=20}

For i:=1 to N do

writeln('Массивтi енгiзiңiз') ;

read(a[i] ) ;

writeln('Iзделiнетiн санды енгiзiңiз') ;

read(X) ;

i:=1; {i:=0; }

while (i<=N) and (a[i] <>X) do i:=i+1;

{repeat i:=i+1; until (i>N) or (a[i] =X) ; }

if i<=N then write(' a массивiне ', i, ' орында', X, ' санының бiрiншi кiруi ')

else write('тапқан жоқпыз') ;

end.

Соңғы кiрудi iздеу кезiнде енгiзгеннен кейiн келесi операторлар жүру керек.

i:=N; {i:=N+1; }

while (i>=1) and (a[i] <>X) do i:=i-1;

{repeat i:=i-1; until (i<1) or (a[i] =X) ; }

if i>=1 then write(' a массивiне ', i, ' орында', X, ' санының соңғы кiруi ')

else write('тапқан жоқпыз') ;

10 Тосқауылы бар iздеу

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

Ендi тек iздеу шарты ғана қалып, табылған элементте немесе тосқауылда циклдан шығуға болады. Мұндай жағдайда циклдан шыққаннан кейiн бiз тосқауылды тапқан жоқ па екендiгi тексерiледi. Тосқауылы бар iздеудi есептеу қиындығы сызықтыға қарағанда төмен, бiрақ сондай тiзбектi өлшемiдi, N - массив элемент саны бар.

Тосқауылды орнатудың екi тәсiлi бар: қосымша элемент немесе массивтiң ең шеткi элементiнiң орнына.

Мысалы: Тосқауылы бар iздеу

Program Poisk2a;

Var a:array[1. . 20] of integer;

N, X, i:integer;

Begin

read(N) ; {N<=20}

for i:=1 to N do

writeln('Массивтi енгiзiңiз') ;

read(a[i] ) ;

writeln('Iзделiнетiн санды енгiзiңiз') ;

read(X) ;