Алгоритмдер теориясы және берілгендер құрылымы


Жоспар:

Кіріспе

1 тарау Алгоритмдер теориясы және берілгендер құрылымы
1.1. Алгоритмдер. Алгоритмдерді талдау. Алгоритмдер құру
1.2. Программа құру тілі. Программа құрылымы. Енгізу және шығару командалары.
1.3. Программа құру тілі. Программа құрылымы. Енгізу және шығару командалары.

2 тарау Іздеу алгоритмдері
2.1. Сызықты іздеу.
2.2. Екілік іздеу.
2.3. Қатарда іздеу. Кнут . Морис . Пратт алгоритмі.
2.4.Қатарда іздеу. Боуер .Мура алгоритмі
2.5. Іздеу алгоритмдерінің таралымына есептер шығару мысалдары
2.6. Есептер
Кіріспе
Бағдарлама тілдері есептерді шешу алгоритмдерін электрондық есептегіш машинасына арналған бағдарлама түрінде жазуға арналған. Бастапқы мәліметтерді алған бағдарлама ақпаратты өңдеу жөніндегі команданың соңғы әрекет саны ішінде белгілі бір нәтиже беруі тиіс. Тілді зерттеп оқу үшін бұл тіл бағдарламалаудың жеті негізгі түсініктерін жүзеге асыратынын түсіну керек, ол
1) түрлі типтегі мәліметтерді беру және оперативті жадыдан оларға орын бөлу;
2) мәліметтерді енгізу, яғни ақпаратты клавиатурадан немесе сыртқы мәлімет таратушыдан оқу;
3) пайдаланушы үшін (аралық және шығыс) нәтижелерін беру немесе сыртқы мәлімет таратушыға жазу;
4) мәліметтерді өңдеу жөніндегі операциялар мен командаларды бірінен соң бірі ретімен орындау;
5) (тармақталған алгоритмдерді ұйымдастыру үшін) операциялар мен командаларды берілген шарт бойынша орындау;
6) командаларды белгіленген есе рет берілген шарт бойынша орындау (циклдық алгоритмдерді ұйымдастыру);
7) атаулы кіші бағдарламаға арап командалар тобын бөлу және оған программадан және кіші программадан қатынау (бағдарламалаудың модульдік принципін жүзеге асыру).
Бағдарламалаудың осы базалық элементтерімен дамыған алгоритмдік тілдер мүмкіндіктері шектелмейді, бірақ оларды зерттеп үйрену жаңа тілді тез үйреніп, ол тілде бағдарлама жазуға көмектеседі. Паскаль мен Си бағдарлама тілдері ең әйгілі және кең таралған алгоритм тілдері. Олар 70жылдың басында бір уақытта, бірақ түрлі мақсатта құрылған.
Паскаль тілін Цюрихтегі Швейцария техникалық институтының профессоры Никлаус Вирт Алгол-60 тілі негізінде қазіргі кездегі құрылымдық бағдарламалау принципіне үйрету үшін жасаған. Қарапайымдылығы мен тілінің түсініктілігі тез үйренуге мүмкіндік береді. Мәліметтер құрылымын көрсету құралы алгоритмдік күрделі бағдарлама құруға мүмкіндік береді, сондықтан бұл тіл түрлі қолданбалы мәліметтерді шешуге қолайлы. Оқулық тіл ретінде құрылған бұл тіл қатаң қатаң типтелген. Бұл: транслятор барлық “айнымалылар бір мәліметтер типіне жатқызылып, бағдарламада өз маңызына сәйкес пайдаланылуын бақылайды” дегенді білдіреді. Сөйтіп, бағдарламаның сенімділігі артады. Транслятордың оңтайландырушы қасиеттері тиімді бағдарлама құруға рұқсат етеді, сондықтан, Паскальді жүйелі бағдарламалау тілі ретінде пайдалануға болады. Бағдарламалаудағы жаңа идеяларды тез қабылдау қасиеті Паскальдің оқулық тілден кәсіби бағдарламалау тіліне дамуына ықпал етті. Бұл Паскальдің бағдарлама құрудың интеграцияланған ортасында жұмыс істейтін Турбо Паскаль атты дербес электронды есептегіш машинаға арналған түріне қатысты болады.
Борланд фирмасы жасаған Турбо орта бағдарламаларды толық өңдеуге арналған және файлдармен жұмыс істеу құралдары, редактор, бағдарламаны жөнге келтіруші, компилятор, модульдік бағдарлама құру құралы, кіші программа (библиотекасы) кітапханасы, нығыздауыштан тұрады. АҚШ-та әзірлеген Паскаль тілі ЭЕМ бағдарламалық қамтамасыз етілуін әзірлеуге арналған. Онда машинаға бағдарланған Ассемблер тілі (жады ұяшығына тікелей қатынау және биттерді пайдалану) мен структуралық бағдарлама құрудың басқарушы конструкциялары кіретін процедуралық бағытталған тіл арасындағы өзара келісім болады.
Паскаль тілінің ұғымды, қуатты, икемді болуы кәсіби бағдарламашыға модульдік бағдарлама құру принципі мен құралдарын пайдаланып структураланған үлкен бағдарлама құруға мүмкіндік береді. Дербес электрондық есептегіш машинада Турбо ортада жұмыс істейтін Турбо Си тілінің Турбо Си тілінің нұсқалары іске асырылған. Сонымен, Паскаль және Си тілдері-структураланған, модульді компилирленген, әмбебап тілдер, олардың арасында ортақ белгілер де бар, айырма да көп. Паскаль реттелген және құрылымдық тіл, ал Си еркін де икемді тіл. Паскаль Сиге қарағанда пайдаланушы үшін қолайлы және бағдарлама құру негізін оқуға ыңғайлы.
Турбо Паскаль мен Турбо Си мүмкіндіктері жөнінен Си мен Паскальға қарағанда бірі біріне жақынырақ. Турбо Си Сиге кейбір құрылымдарды қосады, ал Турбо Паскаль Паскальға икемділік береді. Турбо Паскальді игерген пайдаланушы Турбо Си мүмкіндігін үйреніп, бағдарламаларды тез жаза бастай алады.Турбо Симен жұмыс істеуші пайдаланушыға компилятор бағдарламаға Турбо Паскаль тілінде жазылған модульді енгізуге мүмкіндік береді, сондықтан ол Паскаль бағдарламалары қалай құралатынын білуі тиіс.
Мақсаты-Турбо Паскаль мен Турбо Си тілдерін салыстырып, мәліметтер құрылымы мен тіл құрылымдарын көрсету ұқсастығы мен айырмасын анықтап, бірдей мысалмен бағдарламалық мәтіндерді бейнелеу болып табылады.
Тілдер версиялары ретінде Турбо Паскаль 5,0 және Турбо Си 2,0 пайдаланамыз, бұл Американдық ұлттық стандарттар институты (ANSI) ұсынған Паскаль тілі стандарт жобасын қолдайды.

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




Жоспар:
Кіріспе
1 тарау Алгоритмдер теориясы және берілгендер құрылымы
1.1. Алгоритмдер. Алгоритмдерді талдау. Алгоритмдер құру
1.2. Программа құру тілі. Программа құрылымы. Енгізу және шығару
командалары.
1.3. Программа құру тілі. Программа құрылымы. Енгізу және шығару
командалары.
2 тарау Іздеу алгоритмдері
2.1. Сызықты іздеу.
2.2. Екілік іздеу.
2.3. Қатарда іздеу. Кнут - Морис - Пратт алгоритмі.
2.4.Қатарда іздеу. Боуер -Мура алгоритмі
2.5. Іздеу алгоритмдерінің таралымына есептер шығару мысалдары
2.6. Есептер

Кіріспе
Бағдарлама тілдері есептерді шешу алгоритмдерін электрондық есептегіш
машинасына арналған бағдарлама түрінде жазуға арналған. Бастапқы
мәліметтерді алған бағдарлама ақпаратты өңдеу жөніндегі команданың соңғы
әрекет саны ішінде белгілі бір нәтиже беруі тиіс. Тілді зерттеп оқу үшін
бұл тіл бағдарламалаудың жеті негізгі түсініктерін жүзеге асыратынын түсіну
керек, ол
1) түрлі типтегі мәліметтерді беру және оперативті жадыдан оларға орын
бөлу;
2) мәліметтерді енгізу, яғни ақпаратты клавиатурадан немесе сыртқы
мәлімет таратушыдан оқу;
3) пайдаланушы үшін (аралық және шығыс) нәтижелерін беру немесе сыртқы
мәлімет таратушыға жазу;
4) мәліметтерді өңдеу жөніндегі операциялар мен командаларды бірінен соң
бірі ретімен орындау;
5) (тармақталған алгоритмдерді ұйымдастыру үшін) операциялар мен
командаларды берілген шарт бойынша орындау;
6) командаларды белгіленген есе рет берілген шарт бойынша орындау
(циклдық алгоритмдерді ұйымдастыру);
7) атаулы кіші бағдарламаға арап командалар тобын бөлу және оған
программадан және кіші программадан қатынау (бағдарламалаудың
модульдік принципін жүзеге асыру).
Бағдарламалаудың осы базалық элементтерімен дамыған алгоритмдік тілдер
мүмкіндіктері шектелмейді, бірақ оларды зерттеп үйрену жаңа тілді тез
үйреніп, ол тілде бағдарлама жазуға көмектеседі. Паскаль мен Си бағдарлама
тілдері ең әйгілі және кең таралған алгоритм тілдері. Олар 70жылдың басында
бір уақытта, бірақ түрлі мақсатта құрылған.
Паскаль тілін Цюрихтегі Швейцария техникалық институтының профессоры
Никлаус Вирт Алгол-60 тілі негізінде қазіргі кездегі құрылымдық
бағдарламалау принципіне үйрету үшін жасаған. Қарапайымдылығы мен тілінің
түсініктілігі тез үйренуге мүмкіндік береді. Мәліметтер құрылымын көрсету
құралы алгоритмдік күрделі бағдарлама құруға мүмкіндік береді, сондықтан
бұл тіл түрлі қолданбалы мәліметтерді шешуге қолайлы. Оқулық тіл ретінде
құрылған бұл тіл қатаң қатаң типтелген. Бұл: транслятор барлық “айнымалылар
бір мәліметтер типіне жатқызылып, бағдарламада өз маңызына сәйкес
пайдаланылуын бақылайды” дегенді білдіреді. Сөйтіп, бағдарламаның
сенімділігі артады. Транслятордың оңтайландырушы қасиеттері тиімді
бағдарлама құруға рұқсат етеді, сондықтан, Паскальді жүйелі бағдарламалау
тілі ретінде пайдалануға болады. Бағдарламалаудағы жаңа идеяларды тез
қабылдау қасиеті Паскальдің оқулық тілден кәсіби бағдарламалау тіліне
дамуына ықпал етті. Бұл Паскальдің бағдарлама құрудың интеграцияланған
ортасында жұмыс істейтін Турбо Паскаль атты дербес электронды есептегіш
машинаға арналған түріне қатысты болады.
Борланд фирмасы жасаған Турбо орта бағдарламаларды толық өңдеуге арналған
және файлдармен жұмыс істеу құралдары, редактор, бағдарламаны жөнге
келтіруші, компилятор, модульдік бағдарлама құру құралы, кіші программа
(библиотекасы) кітапханасы, нығыздауыштан тұрады. АҚШ-та әзірлеген Паскаль
тілі ЭЕМ бағдарламалық қамтамасыз етілуін әзірлеуге арналған. Онда машинаға
бағдарланған Ассемблер тілі (жады ұяшығына тікелей қатынау және биттерді
пайдалану) мен структуралық бағдарлама құрудың басқарушы конструкциялары
кіретін процедуралық бағытталған тіл арасындағы өзара келісім болады.
Паскаль тілінің ұғымды, қуатты, икемді болуы кәсіби бағдарламашыға
модульдік бағдарлама құру принципі мен құралдарын пайдаланып
структураланған үлкен бағдарлама құруға мүмкіндік береді. Дербес
электрондық есептегіш машинада Турбо ортада жұмыс істейтін Турбо Си тілінің
Турбо Си тілінің нұсқалары іске асырылған. Сонымен, Паскаль және Си тілдері-
структураланған, модульді компилирленген, әмбебап тілдер, олардың арасында
ортақ белгілер де бар, айырма да көп. Паскаль реттелген және құрылымдық
тіл, ал Си еркін де икемді тіл. Паскаль Сиге қарағанда пайдаланушы үшін
қолайлы және бағдарлама құру негізін оқуға ыңғайлы.
Турбо Паскаль мен Турбо Си мүмкіндіктері жөнінен Си мен Паскальға
қарағанда бірі біріне жақынырақ. Турбо Си Сиге кейбір құрылымдарды қосады,
ал Турбо Паскаль Паскальға икемділік береді. Турбо Паскальді игерген
пайдаланушы Турбо Си мүмкіндігін үйреніп, бағдарламаларды тез жаза бастай
алады.Турбо Симен жұмыс істеуші пайдаланушыға компилятор бағдарламаға Турбо
Паскаль тілінде жазылған модульді енгізуге мүмкіндік береді, сондықтан ол
Паскаль бағдарламалары қалай құралатынын білуі тиіс.
Мақсаты-Турбо Паскаль мен Турбо Си тілдерін салыстырып, мәліметтер
құрылымы мен тіл құрылымдарын көрсету ұқсастығы мен айырмасын анықтап,
бірдей мысалмен бағдарламалық мәтіндерді бейнелеу болып табылады.
Тілдер версиялары ретінде Турбо Паскаль 5,0 және Турбо Си 2,0
пайдаланамыз, бұл Американдық ұлттық стандарттар институты (ANSI) ұсынған
Паскаль тілі стандарт жобасын қолдайды.

1 тарау Алгоритмдер теориясы және берілгендер құрылымы
1.1. Алгоритмдер. Алгоритмдерді талдау. Алгоритмдер құру.

Алгоритмдер математикалық логика – алгоритмдер теориясына жалғасатын
ғылыми пәндер математика мен информатика арасындағы шектеулерді жүйелі
зерделеу объектісі болып табылады.
Жағдайдың ерекшелігі мынада, ЭЕМ-да іске асыру үшін алгоритмдер
әзірлеуге ұйғарылған практикалық міндеттерді шешу кезінде және сонымен
қатар практикада ақпараттық технологияларды пайдалану кезінде, негізінен
бұл ұғымның жоғары формальдылығына сүйенбеген жөн. Сондықтан алгоритм
ұғымының мәнін мазмұнды түсіндіру және оның негізгі қасиеттерін қарастыру
негізінде алгоритмдермен және алгоритмизациялаумен танысқан дұрыс болады.
Мұндай тәсіл кезінде алгоритмдеу берілген тілдік құралдар шеңберінде
белгілі бір практикалық тәсілдердің, ұтымды ойлаудың ерекше өзіндік
дағдыларының жиынтығы ретінде алға шығады. Ақпаратты өлшеуде мұндай жағдай
мен жоғарыда қарастырылған тәсілдің арасында ұқсастықты жүргізуге болады:
“кибернетикалық” тәсіл кезіндегі жіңішке математикадлық құрулар
компьютермен практикалық жұмыс кезінде барынша қарапайым “көлемді” тәсілді
қолдану кезінде аса қажет емес.
“Алгоритм” сөзінің өзі ІХ ғасырдың ұлы математигі әл-Хорезмидің
атының латын тіліндегі algorithmi жазылуынан шыққан, ол арифметикалық
амалдарды орындау ережесін қалыптастырған. Бастапқыда алгоритм ретінде
көпмәнді санды төрт арифметикалық амалды орындау ережесі арқылы түсінді.
Алгоритм ұғымын алгоритмнің интуитивтік мағынадағы ұғымы деп айтуға
болады. Ол анық емес, формальсыз сипатта болады және кейбір дәл
анықталмаған, бірақ интуитивті түсінікті заттарға сүйенеді. Мысалы алгоритм
қасиеттерін анықтау және талқылау кезінде біз алгоритмдерді кейбір
орындаушылардың мүмкіндігін көздедік. Оның бар екені болжалды, бірақ ол
туралы ештеңе анық белгілі болмады. Математика тілімен айтқанда ешқандай
аксиоматикалық, мүлтіксіз конструктивті орындаушы анықтамасын бере алмадық.

Өткен параграфта белгіленген алгоритмдер қасиеттерін эмперикалық деп
атаған жөн. Олар әртүрлі және қолданбалы сипаттағы алгоритмдер қасиетін
қорыту негізінде анықталған. Бұл қасиеттерді практикалық программалау үшін,
компьютерлер, ЧПУ станоктері, өнеркәіптік роботтар үшін программалардың кең
тобын құру үшін жеткілікті. Алайда фундаментальды ғылыми ұғым ретінде
алгоритм барынша мұқият зерделеуді талап етеді. Ол “алгоритм” ұғымын
нақтыламай, оны барынша қатаң бейнелемей, басқаша айтқанда формализациялау
мүмкін емес.
“Алгоритм” ұғымын формализациялаудың бірнеше тәсілдері белгілі:
- ақырлы және ақырсыз автоматтар теориясы;
- есептелетін (рекурсивті) функциялар теориясы;
- Черчтің λ есептеуі.
Осы туындаған бір біріне тәуелсіз тәсілдер нәтижесінде эквивалентті болып
шықты. Алгоритм ұғымын формализациялаудың басты мақсаты мынадай: әртүрлі
математикалық есептердің алгоритмдік шешімділігінің проблемаларын шешуге
жақындау, яғни сұраққа жауап беру, есептерді шешуге әкелетін алгоритм
құрастырылуы мүмкін бе? Біз осы проблеманың қойылуын,т есептердің
алгоритмдік шешілімділік теориясының кейбір нәтижелерін қарастырамыз, бірақ
алдымен Пост, Тьюринг машиналарының мысалында автоматтар теориясында
алгоритм ұғымын формализациялауды, сондай-ақ Марковтың қалыпты
алгоритмдерін, ал содан кейін реурсивті функцияларды теория негізінен
талқылаймыз. Черчтың λ есептеу идеясы LISP программалау тілінде іске
асырылған (3 тарау).
Сонымен қатар, блгілі тәсілдердің кез келгенімен формальды анықталған
алгоритм практикалық программалауда біз өткен параграфтарда алгоритмдер деп
атағандарды алмастыра алмайды. Негізгі себеп мынада, формальды
анықтауқарастырылатын есептер шеңберін бірден қысқартады және көптеген
практикалық маңызды есептерді қарау үшін қол жетпейтін етеді.

1.2. Программа құру тілі. Программа құрылымы. Енгізу және шығару
командалары.
Қазіргі кезде программалау тілінің түрлері көп. Солардың ішіндегі ең
танымалысы Паскаль программалау тілі. Өйткені компьютерлік сауаттылық пен
программалауды алғашқы кезеңде үйретуге ең қолайлы тіл. Паскаль тілі
алгоритмдік тіл ішіндегі кеңінен тараған тілдердің бірі болып табылады.
Қарастырылатын Паскаль программалау тілінде программа екі бөліктен тұрады:
1. берілгендерді сипаттау;
2. алгоритмдік амалдарды бейнелеу немесе операторлық бөлік.
Берілгендер бейнелеу арқылы жазылса, амалдар оператор арқылы жазылады.
Синтаксистік жағынан Паскаль программасын екі бөлікке бөлуге болады:
программа тақырыбы, блок.
Программа құрылымы төмендегіше болады:
Program программаның аты;
Блок: 1. Модульдерді қосу.
2. Белгілерді бейнелеу бөлігі.
3. Тұрақтыларды бейнелеу бөлігі.
4. Типтерді анықтау бөлігі.
5. Айнымалыларды бейнелеу бөлігі.
6. Функцияларды және процедураларды бейнелеу бөлігі
7. Операторлар бөлігі.
Program аты (пайдаланылатын файлдар аттарының тізімі);
бейнелеу бөлігі
Begin
Оператор бөлігі
End.
Программа құрылымының Паскаль тілінде жазылуы:
Program аты (input,output);
Uses – модульдерді қосу;
Label – Белгі бөлігі;
Const – Тұрақтылар бөлігі;
Type – Тип бөлігі;
Var – айнымалы бөлігі;
Procedure, Function – процедура және функция бөлігі;
Begin
1- Оператор;
2- Оператор;
... ... ... ... ... ..
n- оператор;
End.
Бейнелеу бөлігіндегі программада пайдаланылатын белгілерге, тұрақтыларға,
типтерге, айнымалыларға сипаттама беріліп (берілгендер атауы, олардың
типтері, мәндері және т.б.), олар хабарланады. Бейнелеу бөлігіндегі
көрсетілген бөліктердің бәрі бірдей бар болуы шарт емес. Бейнелеудің жеке
бөліктеріне қысқаша тоқталайық:
Uses –бұл жолда программада пайдаланылатын модульдер тізімінен тұрады.
Модульдер стандартты және пайдаланушының құрған модульдері болуы мүмкін.
Турбо Паскаль жүйесінде бірнеше стандартты модульдер бар. Олардың
негізгілері: SyStem – Паскаль тілінің процедуралары мен функцияларын, Турбо
Паскаль тілінің қосымша командаларын сүйемелдейді;
DOS- Паскаль тілінің DOS командаларын пайдалануды сүйемелдейді; CRT –
Тексттік режимде экранды басқарады; OVERLAY – оверлейлік программаларды,
PRINTER – принтерді пайдалануды, GRAPH – экранның графикалық режимінің
жұмысын сүйемелдейді. Бұлардың барлығы TURBO.TPU, GRAPH.TPU файлында
орналасқан. SyStem модулі тізімде көрсетуді қажет етпейді, ол автоматты
түрде қосылады. Программаның орындалу нәтижесін экраннан көру үшін экран
бетін кідіріс жасап, ұстап тұруды ұйымдастыру қажет. Кідірісті үш тәсілмен
ұйымдастыруға болды: 1) Readln операторымен; 2) символдық
айнымалы:=ReadKey операторымен; 3) While NOT Keypressed DO операторымен.
Label –белгі ретінде кез келген бүтін оң сан, символ, символдар тіркесі
пайдаланылады. Белгі операторды немесе программаның бөлігін табу үшін
қолданылады. Белгі оператор алдында орналасады да, қос нүте арқылы
ажыратылады. Қажеттіоператорға, программаның бөлігіне оралу белгі арқылы
жүзеге асырылады. Мысалы, Label 5,12,45,Sum, AB.
Берілген мәндерді айнымалыға жазу үшін меншіктеу операторын
пайдалануға болады. Мысалы, А:=15, BC:=-16.4.Программаны әмбебап етіп
жасау үшін айнымалылардың мәндерін өзгертетін түрде жазу қажет, бұл
жағдайда программа айнымалының әр түрі мәндері үшін дұрыс болады. Ол үшін
енгізу операторы READ пайдаланылады. Енгізу операторының жалпы түрі
READ(а1, а2,...,аn). Мұндағы а1, а2,...,аn – айнымалы атаулары, оларды
енгізу операторының параметрлері деп атайды. READ операторы орындалғанда
параметрлер өздеріне сәйкес мәндерді қабылдайды, бұл міндетті енгізу файлы
INPUT(енгізу) арқылы жүзеге асырылады.
Паскаль тілінде нәтижені экранға шығару үшін WRITE (жазу) операторы
пайдаланылады. WRITE(а1, а2,...,аn). Мұндағы а1, а2,...,аn – жай
айнымалылар немесе апострофтар ішіне алынған символдар тобы болуы мүмкін.
Мысалы, егер В=17,15 болып, write (‘B=’,B) командасы орындалғанда, экранға
В=17,15дерегі көрінеді. Бүтін және нақты сандарды шығару үшін сандардың
форматын беру қажет. Формат айнымалы атынан соң қос нүкте арқылы жазылады.
Нақты сан форматы екі саннан тұрады: 1-сан – санға берілетін орын, 2-сан –
үтірден кейін алынатын бөлшек бөлік саны.

1.3. Программа құру тілі. Программа құрылымы. Енгізу және шығару
командалары.
Қазіргі кезде программалау тілінің түрлері көп. Солардың ішіндегі ең
танымалысы Паскаль программалау тілі. Өйткені компьютерлік сауаттылық пен
программалауды алғашқы кезеңде үйретуге ең қолайлы тіл. Паскаль тілі
алгоритмдік тіл ішіндегі кеңінен тараған тілдердің бірі болып табылады.
Қарастырылатын Паскаль программалау тілінде программа екі бөліктен тұрады:
3. берілгендерді сипаттау;
4. алгоритмдік амалдарды бейнелеу немесе операторлық бөлік.
Берілгендер бейнелеу арқылы жазылса, амалдар оператор арқылы жазылады.
Синтаксистік жағынан Паскаль программасын екі бөлікке бөлуге болады:
программа тақырыбы, блок.
Программа құрылымы төмендегіше болады:
Program программаның аты;
Блок: 1. Модульдерді қосу.
8. Белгілерді бейнелеу бөлігі.
9. Тұрақтыларды бейнелеу бөлігі.
10. Типтерді анықтау бөлігі.
11. Айнымалыларды бейнелеу бөлігі.
12. Функцияларды және процедураларды бейнелеу бөлігі
13. Операторлар бөлігі.
Program аты (пайдаланылатын файлдар аттарының тізімі);
бейнелеу бөлігі
Begin
Оператор бөлігі
End.
Программа құрылымының Паскаль тілінде жазылуы:
Program аты (input,output);
Uses – модульдерді қосу;
Label – Белгі бөлігі;
Const – Тұрақтылар бөлігі;
Type – Тип бөлігі;
Var – айнымалы бөлігі;
Procedure, Function – процедура және функция бөлігі;
Begin
3- Оператор;
4- Оператор;
... ... ... ... ... ..
n- оператор;
End.
Бейнелеу бөлігіндегі программада пайдаланылатын белгілерге, тұрақтыларға,
типтерге, айнымалыларға сипаттама беріліп (берілгендер атауы, олардың
типтері, мәндері және т.б.), олар хабарланады. Бейнелеу бөлігіндегі
көрсетілген бөліктердің бәрі бірдей бар болуы шарт емес. Бейнелеудің жеке
бөліктеріне қысқаша тоқталайық:
Uses –бұл жолда программада пайдаланылатын модульдер тізімінен тұрады.
Модульдер стандартты және пайдаланушының құрған модульдері болуы мүмкін.
Турбо Паскаль жүйесінде бірнеше стандартты модульдер бар. Олардың
негізгілері: SyStem – Паскаль тілінің процедуралары мен функцияларын, Турбо
Паскаль тілінің қосымша командаларын сүйемелдейді;
DOS- Паскаль тілінің DOS командаларын пайдалануды сүйемелдейді; CRT –
Тексттік режимде экранды басқарады; OVERLAY – оверлейлік программаларды,
PRINTER – принтерді пайдалануды, GRAPH – экранның графикалық режимінің
жұмысын сүйемелдейді. Бұлардың барлығы TURBO.TPU, GRAPH.TPU файлында
орналасқан. SyStem модулі тізімде көрсетуді қажет етпейді, ол автоматты
түрде қосылады. Программаның орындалу нәтижесін экраннан көру үшін экран
бетін кідіріс жасап, ұстап тұруды ұйымдастыру қажет. Кідірісті үш тәсілмен
ұйымдастыруға болды: 1) Readln операторымен; 2) символдық
айнымалы:=ReadKey операторымен; 3) While NOT Keypressed DO операторымен.
Label –белгі ретінде кез келген бүтін оң сан, символ, символдар тіркесі
пайдаланылады. Белгі операторды немесе программаның бөлігін табу үшін
қолданылады. Белгі оператор алдында орналасады да, қос нүте арқылы
ажыратылады. Қажеттіоператорға, программаның бөлігіне оралу белгі арқылы
жүзеге асырылады. Мысалы, Label 5,12,45,Sum, AB.
Берілген мәндерді айнымалыға жазу үшін меншіктеу операторын
пайдалануға болады. Мысалы, А:=15, BC:=-16.4.Программаны әмбебап етіп
жасау үшін айнымалылардың мәндерін өзгертетін түрде жазу қажет, бұл
жағдайда программа айнымалының әр түрі мәндері үшін дұрыс болады. Ол үшін
енгізу операторы READ пайдаланылады. Енгізу операторының жалпы түрі
READ(а1, а2,...,аn). Мұндағы а1, а2,...,аn – айнымалы атаулары, оларды
енгізу операторының параметрлері деп атайды. READ операторы орындалғанда
параметрлер өздеріне сәйкес мәндерді қабылдайды, бұл міндетті енгізу файлы
INPUT(енгізу) арқылы жүзеге асырылады.
Паскаль тілінде нәтижені экранға шығару үшін WRITE (жазу) операторы
пайдаланылады. WRITE(а1, а2,...,аn). Мұндағы а1, а2,...,аn – жай
айнымалылар немесе апострофтар ішіне алынған символдар тобы болуы мүмкін.
Мысалы, егер В=17,15 болып, write (‘B=’,B) командасы орындалғанда, экранға
В=17,15дерегі көрінеді. Бүтін және нақты сандарды шығару үшін сандардың
форматын беру қажет. Формат айнымалы атынан соң қос нүкте арқылы жазылады.
Нақты сан форматы екі саннан тұрады: 1-сан – санға берілетін орын, 2-сан –
үтірден кейін алынатын бөлшек бөлік саны.

2 тарау Іздеу алгоритмдері
2.1. Сызықты іздеу.

Программалауда ең жиі кездесетін амалдардың бірі – іздеу. Ол түрлі
деректер құрылымын олардың пайда болуына қарай байқап көруге болатын жан-
жақты есеп болып табылады. Осы тақырыптың бірнеше негізгі вариациясы бар
және олар үшін көптеген түрлі алгоритмдер құрылған. Алға қарай қарау
кезінде біз осындай принципті жорамалға сүйенеміз: берілген элементті іздеу
қажетті деректер тобы белгіленген. N элементтердің жиыны мынадай а жиымы
түрінде берілген деп есептейміз:
ARRAY [0 .. N - 1] OF item;
Әдетте item типі кілттің рөлін атқаратын кейбір өрісі бар жазбаны
суреттейді. Есеп кілті х “іздеу аргументіне” тең элементті іздеуден
тұрады. Нәтижесінде алынған a \i\.key = х шартын қанағаттандыратын г
индексі табылған элементтің басқа өрістеріне қатынауды қамтамасыз етеді.
Өйткені бізді бірінші кезекте, анықталған деректер емес, іздеу процесінің
өзі қызықтырады, онда біз item типі тек қана кілттен тұрады, яғниол кілт
(key) деп есептейтін боламыз.
Егер ізделіп отырған деректер туралы ешқандай қосымша ақпарат
болмаса, онда айқын тәсіл – оның қажетті элемент табылмаған бөлігінде қадам
сайын көбейте отырып жиымды тізбекті қарау болып табылады. Мұндай әдіс
сызықтық іздеу деп аталады. Іздеуді аяқтау шарты мынадай:

1. Элемент табылды, яғни ai = х.
2. Барлық жиым қаралды және сәйкестік анықталған жоқ.
Бұл бізге сызықтық алгоритм береді:
I:=0
WHILE (i N) and (a[i] # x) DO i := i+1 END,
Логикалық өрнекте элементтердің реті елеулі мәнге ие болатынына
назар аударыңыз. Циклдың иварианты, яғни і индексін әрбір арттырудың
алдында орындалатын шарт былайша көрсетіледі:

Ол барлық і-ге қарағанда аз к мәндері үшін сәйкестік болған жоқтығын
айтады. Осыдан іздеу циклдың басында шарттың жалғандығы жағдайында ғана
аяқталатыны анық, нақты шешім шығаруға болады:
((i = N) OR (аi = x)) &
Бұл шарт тек қана қажетті нәтижені көрсетпейді, одан егер элемент
табылса, онда ол ең төменгі мүмкін индекспен бірге табылғаны шығады, яғни
бұл мұндай элементтердің бірншісі. i = N теңдігі сәйкестік жоқ екенін
куәландырады.
Циклдың соңы кепілдендірілгені анық, өйткені әрбір қадам сайын і
мәні артып отырады, демек ол N шегі қадамдарының соңғы санына жетеді; іс
жүзінде егер сәйкестік болмаса бұл N қадамдарынан кейін болады.
Әрбір қадамда индексті арттыру және логикалық өрнекті есептеу талап
етілетіні анық. Ал осы жұмысты ықшамдауға және осылайша іздеуді тездетуге
бола ма? Жалғыз ғана мүмкіндік - логикалық өрнектің өзін ықшамдауға
тырысу, өйткені ол екі мүшеден тұрады. Демек, барынша қарапайым шешімге
келудегі жалғыз ғана мүмкіндік – біздің күрделіге барабар (немесе тең)
қарапайым шарт қалыптастыру. Мұны егер сәйкестік барлық уақытта болатынына
кепілдік берсек орындауға болады. Бұл үшін жиымның соңына х мәні бар
қосымша элемент орналастырса жеткілікті. Мұндай көмекші элементті барьерлер
деп атаймыз, өйткені ол бізді жиымнан тыс шығып кетуден қорғайды. Енді
жиым былайша суреттелетін болады:
a: ARRAY [0..N] OF INTEGER
және барьерлі сызықтық іздеу алгоритмі мына түрде көрсетіледі:
a[N] := х; i := 0:
WHILE a[i] х DO i := i+1;
Осы инварианттан шығарылған нәтижелегіш шарт, бұрынғыша:

i =0 теңдігі сәйкестік болмағанын (егер барьермен сәйкестікті
есептемегенде) болмағанын куәландырады.

2.2. Екілік іздеу.

Егер арасында іздеу жүріп жатқан деректер туралы қандай да бір
ақпарат жоқ болса, іздеуді шапшаңдатудың басқа тәсілдері жоқ екені анық.
Егер деректер реттелген болса іздеуді едәуір тиімді етуге болатыны
жақсы таныс. Көз алдыңызға фамилиялар рет-ретімен орналастырылмаған
телефон анықтамалығын елестетіңіз. Бұл мүлдем пайдасыз нәрсе. Сондықтан
біз а жиымы реттелген алгоритмді келтіреміз, яғни ол мына шартты
қанағаттандырады:
Ak:1≤k≤N:a k-1≤ak
Негізгі идея - кездейсоқ кейбір элементті таңдау, оны aм деп аламыз
және х іздеу аргументімен салыстырыңыз. Егер ол х-қа тең болса, онда
іздеу аяқталады, ал егер ол х-тан кем болса, онда біз м-нан кем немесе тең
индекстері бар барлық элементтерді одан әрі іздеуден шығарып тастауға
болады деп тұжырым жасаймыз; егер ол х-тен артық болса, онда м-ға тең
немесе артық индекстер алып тасталады. Бұлай ойлау бізді келесі алгоритмге
алып келеді (ол қақ ортасынан бөліп іздеу деп аталады). Мұнда L және R екі
индексті айнымалылар қажет болып отырған элемент тағы қай жерден табылуы
мүмкін болатын а жиымы секциясының сәйкесінше сол және оң соңын атап
көрсетеді.
L : = 0 R:= N-1; ... жалғасы
Ұқсас жұмыстар
Алгоритмдер теориясы. Анықтамасы. Қасиеттері. Түрлері. Алгоритмді жазу әдістері. Алгоритм модельдері
Алгоритмдер және оларды сипаттау тәсілдері
Access-берілгендер базасын басқару жүйесі
Берілгендер қорын басқару жүйесі
Алгоритмдер теориясына кіріспе
Берілгендер қорындағы кестеледі біріктірудің теориялық негіздері
Delphi-де берілгендер қорын басқару жүйелері
АЛГОРИТМНІҢ ПРАКТИКАЛЫҚ АСПЕКТІЛЕРІ. АВТОМАТТАР ТЕОРИЯСЫ
Графтар теориясы және оның элементтері
Менеджмент теориясы және тәжірибесі
Пәндер

Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор №1 болып табылады.



WhatsApp: 777 614 50 20
Email: info@stud.kz
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь