Интерпол картотекасы

Кiрiспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...4

1. Есептiң қойылымы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..5
2. Қолданылған әдістер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...6
2.1. Iздеу алгоритмдерi ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 6
Сызықты iздеу ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..6
Тосқауылы бар iздеу ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 7
Екiлiк (бинарлы) iздеу ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .8
2.2. Сорттау алгоритмдерi ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 10
Таңдау арқылы сорттау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .10
Айырбаспен сорттау (“көбiкше” тәсiлiмен) ... ... ... ... ... ... ... ... ... ... ... ... 11
Шейкерлi сорттау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 12
Қосу арқылы сорттау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .13
Хоар сорттауы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 15
3. Есептің алгоритмі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..17
4. Бағдарламаның баяндалуы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...19
4.1. Жалпы мағлұматтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...19
4.2. Функциялдық тағайындалуы (қолдануы) ... ... ... ... ... ... ... ... ... ... ... ... 19
4.3. Логикалық құрылымның баяндалуы ... ... ... ... ... ... ... ... ... ... ... ... ... ... 20
4.4. Шақыру және жіктеу ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 4.5. Қажетті техникалық жабдықтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
4.6. Кіріс мәләметтер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
4.7. Щығыс мәліметтер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . Қорытынды ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... Қолданылған әдебиеттер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..

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

1. Фаронов В.В. Turbo Pascal 7.0. Начальный курс: Учебное пособие.-Москва.:Нолидж, 1998
2. Культин Н.Б. Turbo Pascal в задачах и решениях.-
СПб.:БХВ-Петербург, 2003
3. Муртазина А.У., Тусупова Б.Б. Основы программирования на языках Паскаль и Си. Методические указания к лабораторным работам по курсу “Языки и технология программирования”.- Алматы: КазНТУ, 2000

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

ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ

БIЛIМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛIГI

Қ.И. Сәтбаев атындағы
ҚАЗАҚ ҰЛТТЫҚ ТЕХНИКАЛЫҚ УНИВЕРСИТЕТI

Ақпараттық Технoлогиялар Институты

Техникалық кибернетика кафедрасы

КУРСТЫҚ ЖОБАҒА ТҮСIНIК

Тақырыбы:
Интерпол картотекасы

Орындаған: ВП(б)-04-6к тобының
студентіСраилов Рысжан
Тексерген:
Рахатова Қ.Н.

Алматы 2004

Мазмұны

Кіріспе
1. Есептің қойылымы
2. Қолданылған әдістер
3. Есептің алгоритмі
4. Бағдарламаның баяндалуы
1. Жалпы мағлұматтар
2. Функциялдық тағайындалуы (қолдануы)
3. Логикалық құрылымның баяндалуы
4. Шақыру және жіктеу
5. Қажетті техникалық жабдықтар
6. Кіріс мәліметтер (енгізу)
7. Шығыс мәліметтер (шығару)
5. Қортынды
6. Қолданылған әдебиеттер

Мазмұны

Кiрiспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ... ..4

1. Есептiң
қойылымы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ..5
2. Қолданылған
әдістер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ..6
2.1. Iздеу
алгоритмдерi ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... 6
Сызықты
iздеу ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ...6
Тосқауылы бар
iздеу ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... .7
Екiлiк (бинарлы)
iздеу ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... ..8
2.2. Сорттау
алгоритмдерi ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... 10
Таңдау арқылы
сорттау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... 10
Айырбаспен сорттау (“көбiкше”
тәсiлiмен) ... ... ... ... ... ... . ... ... ... ... ... ...11
Шейкерлi
сорттау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... 12
Қосу арқылы
сорттау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... 13
Хоар
сорттауы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... 15
3. Есептің
алгоритмі ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ...17
4. Бағдарламаның
баяндалуы ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... 19
4.1. Жалпы
мағлұматтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ..19
4.2. Функциялдық тағайындалуы
(қолдануы) ... ... ... ... ... ... . ... ... ... ... ... ...19
4.3. Логикалық құрылымның
баяндалуы ... ... ... ... ... ... .. ... ... ... ... ... ... ... ..20
4.4. Шақыру және
жіктеу ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... 4.5. Қажетті техникалық
жабдықтар ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..

4.6. Кіріс
мәләметтер ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ..
4.7. Щығыс
мәліметтер ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ...
Қорытынды ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ... ... .. Қолданылған
әдебиеттер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
... ... ... ... ...

Кiрiспе

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

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

Берілген курстық жұмыста тор көзді шаршының ішіне шашыранды
(реттелмеген) түрде енгізілген латын алфавиті әріптерін алфавит бойынша
реттеу қарастырылған:
“Айнымалы квадрат”. 4 х 4 өлшемді тор көзді квадрат берлген. Онда
кездейсоқ сандар датчигі көмегімен A-дан P-ға дейін дейін әріптер
қойылған. Алфавит бойынша квадратқа әріптерді реттеу.

2. Қолданылған әдістер
2.1. Iздеу алгоритмдерi

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

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

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

Program Sizikty1;
Const n=10;
Var a: array[1..n] of integer;
B, i:integer;
Begin
Writeln ('Массивтi енгiзiңiз');
For i:=1 to n do
Read (a[i]);
Writeln('Iзделiнетiн санды енгiзiңiз'); Read(B);
i:=1;
{i:=0;}
While (i=n) and (a[i]B) do
i:=i+1;
{repeat i:=i+1; until (in) or
(a[i]=B);}
If i=n then write(' a массивiне ', i,' орында', B ,' санының б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]B) do i:=i-1;
{repeat
i:=i-1; until (i1) or (a[i]=B);}
If i=1 then write(' a массивiне ', i,' орында', B ,' санының соңғы кiруi
')
else write('тапқан жоқпыз');

Тосқауылы бар 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 Toscaul1;
Const n=10;
Var a:array[1..n] of integer;
B,i:integer;
Begin
Writeln ('Массивтi енгiзiңiз');
For i:=1 to n do
Read (a[i]);
Writeln ('Iзделiнетiн санды енгiзiңiз');
Read(B);
a[n+1]:=B; {қосымша элемент арқылы
тосқауыл қою}
i:=1; {i:=0;}
While a[i]B do
i:=i+1;
{repeat i:=i+1; until a[i]=B;}
If i=n then
write(' a массивiне ', i,' орында', B ,' санының бiрiншi кiруi ')
else write('тапқан жоқпыз');
end.

Program Toscaul2;
Const n=10;
Var a:array[1..n] of integer;
B, i, y:integer;
Begin
Writeln ('Массивтi енгiзiңiз');
For i:=1 to n do
Read(a[i]);
Writeln ('Iзделiнетiн санды енгiзiңiз');
Read(B);
y:=a[n];
{соңғы элементтi сақтау}
a[n]:=B; {тосқауылды массивтiң соңғы
орнына орнату}
i:=1;
{i:=0;}
While a[i]B do i: =i+1;

{repeat i:=i+1; until a[i]=B;}
if (in) or (y=B) then
write(' a массивiне ', i,' орында', B ,' санының бiрiншi кiруi ')
else write('тапқан жоқпыз');
a[n]:=y; {массивтiң оңғы
элементiн қалпына келтiру}
end.

Ек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лед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 негiзi бар N логарифмдi дәрежеге тең, мұндағы N – массив
элементтерiнiң саны.

Мысалы: Х санының өсу ретiмен орналасқан массивке енуiн iздеу
Program Binarly3a;
Const n=10
Var a:array[1..n] of integer;
B, Sol, On, i, c : integer;
Begin
Writeln('өсу ретiмен массив енгiзiңiз');
For i:=1 to n do
Read(a[i]);
Writeln(‘өз элементiңдi енгiз’);
Read(B);
Sol:=1;
On:=n; {iздеуге арналған сол және оң шекара
фрагменттерi}
While SolOn do
Begin
c:=(Sol + On) div 2;
{кiшi жаққа
қарай дөңгелектелiнген орта}
If Ba[c] then
{егер массив кему ретiмен
енгiзiлсе, онда If Ba[c]}
Sol:=c+1
{Sol ауыстыра отырып ортасыз
оң жағын аламыз}
else right:=c;
{right ауыстыра отырып ортасыз сол
жағын аламыз }
End;
if B=a[Sol] then {мұндағы Sol = On, бiрақ
әрқашан емес = c}
Writeln(' a массивiне ', Sol,' орында', B ,' санының соңғы кiруi ')
else writeln('тапқан жоқпыз');
End.

2.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з.

Таңдау арқылы сорттау

Тәс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.
Таңдау арқылы сорттаудың есептеу қиындығы - n*n шамасының өлшемi,
әдетте оны O(n*n) деп жазады. Бұл салыстырулар саны бiрiншi максимумды
iздегенде n-1 - ге тең, содан кейiн n-2, n-3 және т.с.с. 1-ге дейiн,
сонымен n*(n-1)2 болумен түсiндiрiледi.

Мысалы: a массивiнiң n бүтiн сандарының өсуi бойынша таңдау арқылы
сорттау.
Program Tandau_S1;
Const n=10
Var a:array[1..n] of integer;
i, m, k, B : integer;
Begin
Writeln('Массивтi енгiзiңiз');
For i:=1 to n do
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 орындарымен
ауыстырамыз}
B:=a[m];
a[m]:=a[k];
a[k]:=B;
End;
For i:=1 to n do
write(a[i],' '); {реттелген массив} end.

Мысалы: Жоғарыдағы есеп, бiрақ бiр мезеттегi max пен min таңдау
арқылы.
Program Tandau_S2;
Const n=10
Var a : array[1..n] of integer;
i, m, k, B, p : integer;
Begin
Writeln('Массивтi енгiзiңiз');
For i:=1 to n do
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 орындарымен
ауыстырамыз }
B:=a[p];
a[p]:=a[k];
a[k]:=B;
If m=k then m:=p;
{егер max k орында тұрса,
ендi ол p орында тұр }
{ m және n-k+1 номерлi элементтердi орындарымен
ауыстырамыз }
B:=a[m];
a[m]:=a[n-k+1];
a[n-k+1]:=B;
End;
For i:=1 to n do
write(a[i],' ');
{реттелген массив}
end.

Айырбаспен сорттау (“көб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 өту
қажет болады. Айырбаспен сорттаудың есептеу қиындығы O(n*n).

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

Program Aiyrbas_S;
Const n=10;
Var a:array[1..n] of integer;
i, k, B : integer;
Begin
Writeln('Массивтi енгiзiңiз');
For i:=1 to n do
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
B:=a[i];
a[i]:=a[i+1];
a[i+1]:=B; end;
For i:=1 to n do
write(a[i],' '); {реттелген массив}
end.

Шейкерлi сорттау

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

Мысалы: n бүтiн сандардан құралған a массивiн Шейкерлi сорттау арқылы
өсу ретiмен орналастыру.
Program Shaker_S;
Const n=10;
Var a:array[1..n] of integer;
i, k, B, j, d : integer;
Begin
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 – ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.