Крест пен нөл ойынын программалау

Кіріспе
Негізгі бөлім
1. Есептің математикалық қойылымы
2. Қолданылған тәсілдер
2.1 Хоар тәсілі
2.2 Көпіршік тәсілі
2.3 Іздеу
2.3.1 Бинарлық іздеу
2.4 Қосалқы программа
2.4.1 Процедураларды қолдану
2.4.2 Функцияны қолдану
2.5 Графикалық режим
3. Программаны баяндау
3.1 Жалпы түсініктер
3.2 Функцияналдық тағайындалуы
3.3 Логикалық құрылымын сипаттау
3.4 Қолданылатын техникалық жабдықтар
4.Есептің алгоритмі
Қорытынды
Пайдалынған әдебиеттер

Жаңа реттеулер енгізуден қиын, сәттілігі жағынан күдікті, жүзеге асыруы жағынан қауіпті жұмыс жоқ.
Никколо Маккеавелли (1513)

«Біз барлық автомобильдердің нөмірін қарастырып үлгермейміз»,-деді Дрейк. «Ал бізге оны істеп қажеті жоқ, Пол. Біз тек қана оларды реті бойынша қойып, олардың бірдейлерін іздейміз».
«The Case of Angry Mourner» (1951)
Паскаль қазіргі кезде ең белгілі тілдердің бірі болып табылады. Бұл тілді көбінесе, программалауды үйрену үшін қолданады. Паскаль тілінде қарапайымдылық пен жоғарғы дәрежелі өнімділік ұштастырылған.
Бұл тілді 60-ыншы жылдары Цюрих университетінің профессоры Никлаус Вирт жасаған еді. Жылдар өте келе Паскаль кең тараған тілдердің біріне айналды.
Паскальда программа жазу өте оңай. Программалаудан хабары жоқ адам аз уақыттан кейін қарапайым программалар жаза алады. Паскаль Бейсик тілінен күрделіреу, ал Си немесе Си++ тілінен әлдеқайда жеңіл.
Паскаль тілінің негізінде жоғарғы дәрежелі Delphi тілі жасалған. Бұл тілді оқу әрбір болашақ программисттің міндеті болып табылады.
Берілген есепті шығару барысында бізге көптеген айнымалылар енгізу керек болады. Олардың ішінде файлдық айнымалылар, жолдық айнымалылар және т.с.с. қолданады. Есептің жауабын файлға жазу керек болған соң, ол жерде файлмен жұмыс жасайтын процедурлар мен функцияларды пайдалану керек болады. Біздің программамыз өте ауқымды болуы да мүмкін. Сондықтан да біз осы жерде өзіміз жасаған модульдерді пайдаланғанымыз жөн деп ойлаймын. Бұған қоса программаның сыртқы келбетін сүйкімді қылу үшін стандартты модульдерді пайдаланған жөн деп ойлаймын.
Мәліметтер қорымен жұмыс болған соң, программада жазбалар мен файлдар қолданылуы қажет. Себебі, жазбаларсыз және файлдарсыз біз өзімізге керек мәліметтер қорымен жұмыс жасай алмаймыз.

1. Есептің математикалық қойылымы
Крест пен нөл ойыны кезінде, кім диогональда және жатық жолда бес крестиктерді қатарынан тізіп шықса сол жеңеді. Ойынның әртүрлі екі стратегиясын таңдап және тік бұрышты тор көзде крестик нөл ойынында екі ойыншының ойынын программалау.

2.Қолданылған тәсілдер
Практикалық тұрғыдан алғандағы сұрыптаудың қиындықтары: Төрт түрлі сұрыптау тәсілдерінің жетістіктері мен жетіспеушіліктері.
Сұрыптау тәсілдері программалаудың барлық саласында қолданылады. Ол математикалық программаларда және де база құруда да қолданылады.
Сұрыптау алгоритімін практикалық тұрғыдан үш бөлікке бөліп қарастыруға болады.
-салыстыру, элементтің жұбының ретін анықтайды;
-алмастыру, элемент жұптарының орнын ауыстырады;
-өздігінен сұрыпталатын алгоритм, ол жиыннын барлық элементі реттелгенше салыстыру мен алмастыруды жалғастыра береді;
Төменде қарастырылған сұрыптаудың төрт түрі де сондай қасиеттерге ие. Бұл сұрыптау тәсілдерін жалпы түрде атап өтейік. Бұл тәсілдерді басқалардан бөліп алған себебіміз, олар біріншіден өте жиі қолданылады, екіншіден басқа алгоритмдер осы жерде қарастырылатын тәсілдрдің модификациясы болып табылады.

1. Попов В.Б. Turbo Pascal: для школьников. -М.: Финансы и статистика, 1999. - 528б.
2. Абрамов С.А., Зима Е.В. Начала программирования на языке Паскаль.- М.: Наука, 1987. – 112б.
3. Перминов О.Н. Язык программирования Паскаль. –М.: Радио и связь, 1994.-336б.
4. Вирт Н. Алгоритмы + структуры данных = программы: Пер. С англ.- М.: Мир, 1985. – 406б.
5. Грогоно П. Программирование на языке Паскаль: Пер. с англ.- М.: Мир, 1982.- 382б.

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

Мазмұны

Кіріспе
Негізгі бөлім
1. Есептің математикалық қойылымы
2. Қолданылған тәсілдер
2.1 Хоар тәсілі
2.2 Көпіршік тәсілі
2.3 Іздеу
2.3.1 Бинарлық іздеу
2.4 Қосалқы программа
2.4.1 Процедураларды қолдану
2.4.2 Функцияны қолдану
2.5 Графикалық режим
3. Программаны баяндау
3.1 Жалпы түсініктер
3.2 Функцияналдық тағайындалуы
3.3 Логикалық құрылымын сипаттау
3.4 Қолданылатын техникалық жабдықтар
4.Есептің алгоритмі
Қорытынды
Пайдалынған әдебиеттер

Кіріспе

Жаңа реттеулер енгізуден қиын, сәттілігі жағынан күдікті, жүзеге асыруы
жағынан қауіпті жұмыс жоқ.
Никколо Маккеавелли (1513)

Біз барлық автомобильдердің нөмірін қарастырып үлгермейміз,-деді
Дрейк. Ал бізге оны істеп қажеті жоқ, Пол. Біз тек қана оларды реті
бойынша қойып, олардың бірдейлерін іздейміз.
The Case of Angry Mourner (1951)
Паскаль қазіргі кезде ең белгілі тілдердің бірі болып табылады. Бұл
тілді көбінесе, программалауды үйрену үшін қолданады. Паскаль тілінде
қарапайымдылық пен жоғарғы дәрежелі өнімділік ұштастырылған.
Бұл тілді 60-ыншы жылдары Цюрих университетінің профессоры Никлаус Вирт
жасаған еді. Жылдар өте келе Паскаль кең тараған тілдердің біріне айналды.
Паскальда программа жазу өте оңай. Программалаудан хабары жоқ адам аз
уақыттан кейін қарапайым программалар жаза алады. Паскаль Бейсик тілінен
күрделіреу, ал Си немесе Си++ тілінен әлдеқайда жеңіл.
Паскаль тілінің негізінде жоғарғы дәрежелі Delphi тілі жасалған. Бұл
тілді оқу әрбір болашақ программисттің міндеті болып табылады.
Берілген есепті шығару барысында бізге көптеген айнымалылар енгізу
керек болады. Олардың ішінде файлдық айнымалылар, жолдық айнымалылар және
т.с.с. қолданады. Есептің жауабын файлға жазу керек болған соң, ол жерде
файлмен жұмыс жасайтын процедурлар мен функцияларды пайдалану керек болады.
Біздің программамыз өте ауқымды болуы да мүмкін. Сондықтан да біз осы жерде
өзіміз жасаған модульдерді пайдаланғанымыз жөн деп ойлаймын. Бұған қоса
программаның сыртқы келбетін сүйкімді қылу үшін стандартты модульдерді
пайдаланған жөн деп ойлаймын.
Мәліметтер қорымен жұмыс болған соң, программада жазбалар мен файлдар
қолданылуы қажет. Себебі, жазбаларсыз және файлдарсыз біз өзімізге керек
мәліметтер қорымен жұмыс жасай алмаймыз.

1. Есептің математикалық қойылымы
Крест пен нөл ойыны кезінде, кім диогональда және жатық жолда бес
крестиктерді қатарынан тізіп шықса сол жеңеді. Ойынның әртүрлі екі
стратегиясын таңдап және тік бұрышты тор көзде крестик нөл ойынында екі
ойыншының ойынын программалау.

2.Қолданылған тәсілдер
Практикалық тұрғыдан алғандағы сұрыптаудың қиындықтары: Төрт түрлі
сұрыптау тәсілдерінің жетістіктері мен жетіспеушіліктері.
Сұрыптау тәсілдері программалаудың барлық саласында қолданылады. Ол
математикалық программаларда және де база құруда да қолданылады.
Сұрыптау алгоритімін практикалық тұрғыдан үш бөлікке бөліп қарастыруға
болады.
-салыстыру, элементтің жұбының ретін анықтайды;
-алмастыру, элемент жұптарының орнын ауыстырады;
-өздігінен сұрыпталатын алгоритм, ол жиыннын барлық элементі
реттелгенше салыстыру мен алмастыруды жалғастыра береді;
Төменде қарастырылған сұрыптаудың төрт түрі де сондай қасиеттерге ие.
Бұл сұрыптау тәсілдерін жалпы түрде атап өтейік. Бұл тәсілдерді басқалардан
бөліп алған себебіміз, олар біріншіден өте жиі қолданылады, екіншіден басқа
алгоритмдер осы жерде қарастырылатын тәсілдрдің модификациясы болып
табылады.

2.1 Хоар тәсілі
Бұл тәсіл лездік сұрыптау деп аталады. Ол 1962 жылы құрастырылған.
Оның құрастырушысы Charles Antony Richard Hoare.
Бұл тәсілдің басты мақсаты жиынның сұрыптауға келетін элементін табу
керек және осы элемент жиынды екі кіші элементке бөледі.
Жалпы алғанда сұрыптаудың түрлері өте көп. Оларды түгел қарастырып шығу
мүмкін емес. Сонда да мен осы курстық жобамды маңызды деген бірнеше
түрлерін қарастырып өтуге жөн көрдім. Яғни, жоғарыда аталып өткен сұрыптау
тәсілдерін толығырақ қарастырып өтейік.
Лездік сұрыптау немесе Хоар тәсілі. Сұрыптау алгоритмінің ең тамаша
бірі болып лездік сұрыптау (quicksort) болып табылады. Оның құрастырушысы
Чарльз Хоар, осы сұрыптау тәсілін 1962 жылы жарыққа шығарады. Лездік
сұрыптау арқылы қажет емес немесе артық есептеулерден арылуға болады.
Сұрыптаудың осы түрімен жұмыс істегенде массивті екіге бөлуге болады. Яғни,
үлкен элементтерін бөлек кіші элементтерін бөлек Содан кейін екі топты
рекурсивті түрде сұрыптайды. Ал оы үрдіс аяқталған кезде массив сұрыпталып
бітеді. Хоар тәсілінің алгоритмі өте қарапайым және өте тиімді. Оның
бірнеше түрлері бар. Төменде қарастырылған түрі қолдануы жағынан өте жеңіл.
Біздің quicksort функциясы бүтін санды массивті сұрыптайды:

* quicksort : сұрыптайды v[]..v[n-1]
өсу бойынша * void quicksortClrrt 0-8700-
v[], int n)
Ø {
Int i, last;
If (n=1)* ешнәрсе жасамау *
Return;
Swap (v, o,rand()%n);
Last=0;
For (i=1; in; i++)* бөліктегіш*
If (v[i]v[o])
Swap (v,++last, i);
Swap (v, o,last);* бөліктегішті сақтау*
Quicksort (v,last);* рекурсивті
Түрде сұрыптау* quicksort (v+last+l, n-last-1);
* барлық бөлігін *}
Swap операциясы quicksort функциясында үш рет кездеседі, сондықтан оны
бөлек функция ретінде жазамыз:

* Swap:
v[i] and v[j] *орындарын алмастырамыз*
void Swap(int v[], int i, int j)
{ int temp;
temp=v[i]; v[i]=v[j]; v[j]=temp;
Массивті екіге бөлгенде біріншіден, оны бөлетін элемент таңдалады. Ол
уақытша массивтің басына қойылады да, массивтің қалған элементтері
қарастырылады. Массивті бөлетін элементтен кіші элементтер (яғни, кішкентай
элементтер) массив басына қарай жылжытады (last позициясына). Ал үлкен
элементтер массив соңына қарай жылжытылады (i позицияға). Үрдістің басына
бөлетін элемент орнын ауыстырғаннан кейін last=0 және i=1 ден n-1 ге
дейінгі элементтер әлі қарастырылмаған болады. Басында 1 ден last-қа
дейінгі элементтер бөлетін элементтер қатаң түрде кіші, last+1 ден і-1 ге
дейінгі элементтер оған тең немесе үлкен. Ал і ден n-1 ге дейінгілер әлі
қарастырылмаған. V[i]=V[0] шарты бірінші рет орындалғанша, алгоритм [i]
элементін өз-өзіне ауыстыра береді.
Барлық элементтер қарастырылып болған соң бөлетін элемент өзінің соңғы
позициясына жету үшін, элемент last позициясына қойылады. Енді массив мына
түрде болады:
Осы үрдіс массивтің оң жағына да, сол жағына да қолданылады. Үрдіс
аяқталғанда массив толық сұрыпталған болады. Бұл лездік сұрыптау
қаншалықты тез жұмыс атқарады десек, оған келесі түрде жауап беруге болады.
Әдетте n элементтен тұратын массив n2 элементтен тұратындай етіп 2-ге
бөлінеді, одан әрі n2 элементтен тұратын 2 топ әрқайсысы n4 элемент
болатындай етіліп 4 топқа бөлінеді, содан соң әрбіреуінде n8 элемент
болатындай етіп 8 топқа бөлінеді, т.с.с. Үрдіс шамамен log2 n рет
қайталанады.

2.2 Көпіршік тәсілі
Бұл тәсілдің басты мақсаты оның атауында. Яғни, массивтің ең жеңіл
элементтері көтеріледі, ал ең ауыр элементтері төмен түседі. Алгоритмдік
түрде оны келесі жағдайда көтеруге болады:
Ол үшін массивті астынан үстіне қарай ттүгел қарастырамыз. Егер
қарастыру барысында астынғы элемент үстінгі элементтке қарағанда кіші
болса, онда оларды ауыстырамыз. Осындай әдіспен массивтің ең кіші
элементін жоғарыға шығарамыз. Содан кейін барлық үрдісті массивтің қалған
сұрыпталмаған N-1 элементтері үшін қайталаймыз (яғни, бірінші элементтен
төменгі элементтер үшін). Бұл сұрыптау тәсілінің алгоритімі өте қарапайым
болғандықтан өте тиімді..
Пузырек тәсілі Сұрыптаудың пузырек тәсілінің алгоритімінде екі шектес
элемент салыстырылады. Егер олар кері ретпен орналасқан болса, онда олардың
орындары ауыстырылады. Осылай барлық шектес салыстырып шығып, қажет болса
алмастырылады. Бұл үрдіс барлық қадамдардан тұрады: олардың мәндерін
ауыстыру.
1. Бірінші және екінші элементтерді ауыстыру. Қажет жағдайда
элементтердің мәндерін ауыстыру.
2. Екінші және үшінші элементтерді салыстыру. Қажет жағдайда
элементтердің мәндерін ауыстыру.
3. Осы үрдіст басқа да элементтер жұбы үшін қайталанады.
4. 1-3 қадамдары басқа элементтер реттеліп біткенше қайталау.
Сұрыптау барысында мәні кіші элементтер судағы ауа тәрізді жоғарыға
көтеріледі. Егер тізім N элементтен тұратын болса, толық сұрыптау үшін N-1
рет қайталануы қажет, ал өсу ретімен сұрыпталу келесі түрде болады:

Repeat
Sorted:=true;
For i:=1 to n-1 do begin
If data [i]data[i+1] then begin
Temp:=data[i];
Data[i]:=data[i+1];
Data[i+1]:=temp;
Sorted:=жалған.
End;
End;
Until sorted;

2.3 Іздеу

2.3.1 Бинарлық іздеу

Енді біз іздеудің екі түрі алгоритімін қарастырамыз. Олар: тізбектік
іздеу және бинарлық іздеу. Тізбектік іздеудің алгоритімінде атының айтуы
бойынша іздеу берілген элементтердің біріншісінен басталады, және де ло
бүтін элемент табылғанша жалғаса береді. Осындай іздеу түрін мысалы
телефондық анықтамаларда кеңінен қолдануға болады.
Пузырек тәсілімен сұрыптау тәрізді тізбекті іздеуді үлкен мәліметтер
үшін қолдану тиімді емес. Мысалы телефондық анықтамадан Оңалбаева деген
фамилияны табу керек болса іздеу барысында программаға бүкл анықтаманы
қарастырып шығуға тура келеді. Үлкен мәліметтер үшін тізбектей іздеуге
қарағанда, бинарлық іздеу ... жалғасы

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