Паскаль тілінің көмегімен сұрыптау және іздеу алгоритмдерін құрастыру

ҚАЗАҚСТАН РЕСПУБЛИКАСЫ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ

 

Қазақ мемлекеттік қыздар педагогика институты

 

Физика-математика факультеті

 

Информатика және қолданбалы математика кафедрасы 

 

 

 
 
Дипломдық жұмыс

Тақырыбы: “Паскаль тілінің көмегімен сұрыптау және іздеу алгоритмдерін құрастыру”

 

 

 

 

Қорғауға жіберілді "     "             2008ж. кафедра меңгерушісі тех.ғ.к., доцент Салғараева Г.И. ________________

Орындаған: сырттай бөлімнің (5-ж) 5-курс информатика мамандығының студенті Мухамадиева Л.Н. Ғылыми жетекші: тех.ғ.к., доцент Махметова А.М._______________

 

 

 

 

 

АЛМАТЫ, 2008

 

 

 

 

МАЗМҰНЫ

 

Кіріспе

І. Паскаль программалау тілі туралы жалпы мағлұмат

1.1 Turbo Pascal жүйесiнiң программалау ортасы

1.2 Паскаль  тіліндегі мәліметтер

1.2.1 Турбо  Паскаль тіліндегі константалар (тұрақты сандар)

1.2.2 Турбо  Паскаль тіліндегі айнымалылар

1.2.3 Турбо  Паскаль тіліндегі мәліметтер  типі

1.3 Паскаль  тіліндегі амалдар мен өрнектер

1.4 Массивтер

ІІ. Паскаль тілінің көмегімен сұрыптау және іздеу алгоритмдерін құрастыру

2.1 Іздеу алгоритмі

2.1.1 Сызықтық іздеу

2.1.2 Шектеу қою арқылы іздеу

2.1.3 Екілік немесе қақ бөліп іздеу

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

2.2.1 Таңдау бойынша сұрыптау

2.2.2 Айырбастау бойынша сұрыптау (“көбікше” әдісі)

2.2.3 Мойындық сұрыптау (шейкерлі)

2.2.4 Енгізу арқылы сұрыптау

2.2.5 Хоар сұрыптамасы

2.2.6 Индексті векторларды пайдалану арқылы сұрыптау

2.3 Дербес орындайтын  жаттығулары

 

Қорытынды

Пайдаланылған әдебиеттер тізімі

 

КІРІСПЕ

Паскаль тілін 1968-71 жылдары  Швейцарияда профессор Никлаус  Витр оқып үйренуге қолайлы программалау тілі ретінде ұсынған болатын. Паскаль тілі өзінің қарапайымдылығының және тиімділігінің арқасында дүние жүзіне өте тез тарады. Қазіргі кезде барлық дербес компьютерлер осы тілде жұмыс атқара алдады. Паскаль тілінде жазылған программаның дұрыстығы компьютерде жеңіл тексеріледі және жіберілген қате тез түзетіледі.

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

Қазіргі кезде  Паскаль тілі кез келген күрделі  есептерді шығара алатын, кең таралған стандартты оқып үйрену тіліне айналды. Сол себепті енді осы тілдің ерекшеліктерімен бірсыпыра мүмкіндіктерін қарастырып өтейік.

Техниканың  даму жетістіктеріне сай ЭЕМ –  біздің өміріміздің әр алуан салаларында  қызмет етуде. Айталық компьютердің көмегімен көптеген салалардың қызметі  жеңілдеді десек те болады. Компьютерде автоматтандырылған программа жасауға арналған жаңа технологияларға сай көптеген программалау тілдері пайда болды, солардың негізінде компьютердің қолданылу ауқымы кеңейді, себебі программалау тілдері арқылы құрылған программалар қызметкерге бұрынғыдай көптеген қағаздарды ақтарып, іздеген дерегін таба алмай шаршауынан құтылуына көмектесті. Мысалы, кітапхананы алайық, әрине кімнің болса да, картотеканы пайдалана алғаны дұрыс. Дегенмен де өзімізге керекті кітапты табу үшін оны жазған авторды білуің керек, кітаптың атын, шыққан жылын білуің керек, ал бұл кей кездері ыңғайсыздық тудырады, әсіресе ең алғаш келген адамдарға немесе кітап туралы ақпараты аз адамға қиындық әкелуі әбден мүмкін. Ал қазіргі озық технологиялармен жабдықталған кітапханаға барсаңыз ЭЕМ-ның көмегімен оп-оңай өзіңізге қажетті кітапты, оның тек жылын немесе құсас атын білу арқылы ғана табуыңызға болады.

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

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

 

І. Паскаль программалау тіліне туралы жалпы мағлұмат

 

Компьютер табиғат  құбылыстарын зерттеу, технологиялық  процестерді басқару, мультфильмдер  жасау және т.б өмірде математикамен  тікелей байланысы жоқ есептерді  шығару үшін пайдаланылады. Мысалы, қандай бір есепті шығару үшін компьютерді пайдалану қажет. Ол үшін неден бастау қажет? Алдымен берілген есепке қатысты зерттелетін объектіні немесе құбылысты толық қарастырып, талдау қажет.  Объектінің маңызды қасиеттері математикалық ұғымдар тілінде (формулалар, теңдеулер, теңсіздіктер және т.б.) жазуға болатындай тұжырымдалуы тиіс. Бұл берілген есептің математикалық моделі деп аталады. Математикалық модель зерттелетін объектпен бір мәнді анықталмайды, бірақ модель шынайы объектіге сәйкес келуі тиіс. Алынатын нәтиже таңдалынған модельдің дәлдігіне тәуелді болады. Дәлділікті арттыру үшін зерттелетін объектінің барлық қасиеттері ескерілетіндей, модельді күрделендіруге тура келеді. Математикалық модель қандай да бір жеңілдіктерге негізделеді. Шынайы объектіні оған сәйкес моделімен ауыстырғанда есепті математикалық есеп ретінде тұжырымдап, оны шығаруға математикалық құралдарды пайдалануға болатындай мүмкіндік пайда болады. Есепті талдау барысында оны шығаруды жеңілдететін болжамдар жасалып, объект жөнінде берілген ақпараттардан алғашқы мәліметтерді ерекшелеп тауып, алынатын нәтижені анықтау қажет.

Сөйтіп, есепті шығарудың матемтаикалық моделін  құра отырып:

1. математикалық модель негізделетін болжамдарды ерекшелеу;
2. алғашқы мәліметтер мен нәтижелерді анықтау;
3. нәтижелер мен алғашқы мәліметтерді байланыстыратын математикалық қатынастарды (формулалар, теңдеулер, теңсіздіктер және т.б.) жазу қажет.

Математикалық модель құру барысында мәліметтер арқылы ізделінді шамаларды айқын өрнектейтін  формулаларды тауып жазу барлық уақытта мүмкін болмайды. Мұндай жағдайларда дәл жауапты алуға мүмкіндік беретін математикалық әдістер пайдаланылады.

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

Компьютер алгоритмді адамның қатысуынсыз автоматты түрде орындайды. Ол үшін алгоритм машинаға түсінікті тілде, яғни арнайы программалау тілінде жазылуы тиіс. Программалау тілінде жазылған алгоритм программа деп аталады.  жазылуы тиіс.

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

Сонымен, компьютерде  есеп шығарудың үшінші кезеңі – программа жазып, нәтиже алу және алынған нәтижелерді талдау болып табылады. Сонымен компьютерде есеп шығару процесін төмендегідей схема түрінде көрсетуге болады:

Математикалық модель→Алгоритм→ Программа. Компьютер  жұмысының нәтижелерін талдау.

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

1.1 Turbo Pascal жүйесiнiң программалау ортасы

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

Turbo Pascal жүйес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нiң (отладчик) мүмкiндiктерi өте көп;
• экранды толық тазартып, қайта қалпына келтiруге болады.

Программалау ортасында негiзгi жұмыс пернелер тақтасы немесе тышқан көмегiмен, меню жүйесi және сұқбат терезелер арқылы жүзеге асады.

Программалау ортасында жұмыс iстеу үшiн Turbo.exe файлын орындауға жiберу керек.

 Турбо Паскаль программалау  жүйесiнде жұмыс iстеудi меңгеру үшiн, терезе және меню жұмыстарын бiлу керек.

Терезе негiзiнен меню қатарынан, жұмыс алабынан және функöионалдық пернелердiң орындайтын әрекеттерi жазылған қатардан тұрады.

Программа iске қосылып, терезе ашылғаннан кейiн, курсор жұмыс алабында тұрады.

Меню қатарына F10 пернесi арқылы шығып, ESC арқылы жұмыс алабына ораламыз.

Меню қатарының командаларын және төменгi сатылы командаларының қажеттiсiн ¬ ® ¯ ­ бағыттауыштар арқылы таңдай аламыз. Команданы орындау үшiн Enter пернесiн басамыз.

File менюiнiң командалары файлдармен негiзгi әрекеттердi орындауға мүмкiндiк бередi.  

New командасы үнсiз келiсiм бойынша NONAMEXX.PAS (ХХ-тiң орнына 0-99-ға дейiнгi сандар қойылады) атымен жаңа терезе ашады. Файлдың бұл атын өз қалауымыз бойынша өзгерте аламыз.

Open F3 сақталған файлдарды оқу мүмкiндiгiн беретiн сұхбат терезенi ашады.

Save (сақтау)- F2 екпiндi терезедегi файлды дискiге сақтайды. Егер файлдың аты NONAMEXX.PAS болса, онда …деп сақтау сұхбат терезесi ашылады.

10. Save as… (… деп сақтау) терезедегi екпiндi файлды басқа атпен, басқа құрылғыға, басқа каталогқа сақтау мүмкiндiгiн бередi. Бұл команда орындалған соң, Файлды … деп сақтау (Save File as…) сұхбат терезесi ашылады. Бұл терезеде файлдың жаңа атын терiп жазып, Ок батырмасын шерткен соң, файлдың аты өзгерiп сақталады. Егер бұрыннан бар файлдың аты терiлсе, онда, сол файлдың үстiнен жазылып қалады.

Change dir (Каталогты өзгерту) командасы Change directory сұхбат терезесiнiң көмегiмен құрылғыны таңдап, каталогты ағымдағы етуге мүмкiндiк бередi. Ағымдағы каталог деп Турбо Паскаль ортасы Файлдарды сақтау және оларды iздеу үшiн қолданатын каталогты айтады.

 Print командасы екпiндi терезенiң мазмұнын баспаға шығарады. Турбо Паскаль кестелеулердi кеңейтiп (кестелеу симâолдарын сәйкес бос орынға алмастырады), Dos-тың баспа құрылғысына жiбередi. Егер бұл команданың түсi солғын түстi болып тұрса, онда екпiндi терезенi баспаға жiбере алмаймыз. Мәтiннiң тек белгiленген бөлiгiн ғана баспаға шығару үшiн, Ctrl+K+P пернелерiн басу керек.

Printer setup командасы принтердi орнатуға мүмкiндiк беретiн сұхбат терезенi ашады.

DOS shell (DOS-қа уақытша шығу) DOS-тың командаларын немесе программаларын енгiзу үшiн уақытша Турбо Паскальдан шығуға мүмкiндiк бередi. Турбо Паскальға қайтадан оралу үшiн пернеден EXIT сөзiн теру немесе Enter басу керек.

 Exit (шығу)- Alt+X Турбо Паскаль ортасынан шығу, сақталмаған ақпараттар болса, ол жөнiнде хабарлама бередi.

11.  Edit меню командалары редактор терезесiнде программа мәтiнiн көшiру, қиып алу, енгiзу әрекеттерiн орындау  мүмкiндiгiн бередi.           

Undo  (болдырмау)- Alt+Bksp программа мәтiнiн өңдеу кезiндегi қатармен орындалған соңғы команданың орындалуын алып тастайды.

Redo Undo командасының қатармен орындаған  соңғы командасын алып тастайды.

Cut  Shift+del  Белгiленген бөлiктi буферге қиып алады (бұрынғы орнында қалмайды).

Copy Ctrl+Ins  Белгiленген бөлiктiң көшiрмесiн буферге алады (бұрынға орнында сақталады).

Paste  Shift+Ins Курсор орналасқан жерге буфердегi ақпаратты енгiзедi.

Clear  Ctrl+Del Белгiленген бөлiктi тазалау, өшiру.

Show Clipboard (буфердi ашу) редактор терезесiнде көшiрмесi алынған немесе қиып алынған мәтiндi сақтайтын терезенi ашады. Search - меню командалары программа мәтiнiн  iздеу, проöедураларды хабарлау және файлдардағы қателердiң орналасқан орнын анықтау мүмкiндiгiн бередi.

12. Find (табу) командасы табуға қажеттi және iздеу опöияларын енгiзу мүмкiндiгiн беретiн сұхбат терезенi ашады.

Replace (алмастыру), Alt+S+R- iздейтiн мәтiн мен оны алмастыратын мәтiндi енгiзу мүмкiндiгiн беретiн сұхбат терезенi ашады.

Search Again (қайтадан iздеу) Ctrl+L командасы – Find (iздеу) немесе Replace (алмастыру) командаларының соңғы әрекетiн қайталайды. 

Go to line number (нөмiр қатарына бару) – курсорды нiмiрi көрсетiлген қатарға орналастырады.