8 ферзь

Кіріспе
1. Есептің қойылымы
2. Әдіс . тәсілдерді баяндау
2.1.Сұрыптау тәсілдерінің класификациясы
2.1.1.Сұрыптау тәсілдері
2.1.2.Таңдау сұрыптау
2.2.Көпіршік тәсілі
2.2.1.Көпіршік тәсілімен сұрыптау
2.3.Бинарлық кірістіру
2.4.Шел тәсілі
2.5.Бірігу тәсілі
2.6.Мәліметтер структурасы
2.7.Қосалқы ішкі программалар
2.8.Модуль GRAPH
2.9.Модуль CRT
3. Есептің алгоритмі
4. Программаның блок.схемасы
5. Логикалық құрылымның баяндалуы
6. Қорытынды
7. Қолданылған әдебиеттер
8. Қосымша

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

1) Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск Москва, Мир,1978
2) Зуев Е.А.
Язык программирования Turbo Pascal 6.0 Москва,Унитех 1992
3) Фаронов В.В. Turbo Pascal 7.0, Москва,Нолидж,1990
4) Гусева А.И. Учимся программировать: Turbo Pascal. Москва, Диалог-Мифи,2000
5) Е.М.Епанешников, В.А.Епанешников
Turbo Pascal 7.0,Москва,Диалог-Мифи,2000

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

Тақырыбы: 8 ФЕРЗЬ

Мазмұны

Кіріспе
1. Есептің қойылымы
2. Әдіс – тәсілдерді баяндау
2.1.Сұрыптау тәсілдерінің класификациясы
2.1.1.Сұрыптау тәсілдері
2.1.2.Таңдау сұрыптау
2.2.Көпіршік тәсілі
2.2.1.Көпіршік тәсілімен сұрыптау
2.3.Бинарлық кірістіру
2.4.Шел тәсілі
2.5.Бірігу тәсілі
2.6.Мәліметтер структурасы
2.7.Қосалқы ішкі программалар
2.8.Модуль GRAPH
2.9.Модуль CRT
3. Есептің алгоритмі
4. Программаның блок-схемасы
5. Логикалық құрылымның баяндалуы
6. Қорытынды
7. Қолданылған әдебиеттер
8. Қосымша

Кіріспе

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

1. Есептің қойылымы
Шахмат тақтасыында сегіз ферзьді бір-біріне қауіп төндірмейтіндей етіп
орналастыру керек. Яғни, екі ферзь бір вертикальда, бір горизонтальда және
диагональ бойынша орналаспауы қажет. "Сегіз ферзь" ойынын құру үшін ферздің
денесін және 8*8 шахмат тақтасын бейнелеу керек.
Есептің шарты:
1. Ферзь денесін белгілі бір фигураға лайықтап жасау керек.
2. Ферзь жүргеннен кейін артында із қалдырмау керек.
3. Шахмат тақтасын жасап , оның шекараларын белгілеу керек және ферз осы
шахмат тақтасының сыртына шығып кетпеуі керек.
4. Программа сегіз ферздің бір-біріне қауіп төндірмейтін барлық
варианттарын қарастырып шығу керек.

2.Әдіс-тәсілдерді баяндау
Компьютерлік есептерді шешкенде, компьютерлік ойындар құрастырғанда
көптеген әдістер қолданады. Бұл әдістер жылдан жылға көбейіп келеді және
бұрынғысынан гөрі дами түскен. Бірақ, сол көп жылдар бойы қалыптасқан
әдістер осы күнге дейін кең қолданады.
Есеп шығарғанда сұрыптау әдістерін (методы сортировки), іздеу әдістерін
(методы поиска) қолдануға болады. Бұл әдістер біздің есебімізді жеңілдетеді
және түсінкіті болады
2.1.Сұрыптау тәсілдерінің классификациясы
Сұрыптау (реттеу) – бұл берілген жиын элементтердің белгілі бір ретпен
орналасуы: кілттердің кему немесе арту ретінде. Сұрыптау үшін жиындар -
массив элементтері немесе файлдар болуы мүмкін. Ал кілт - сұрыптау болып
жатқан жазба элементі болуы мүмкін, және сұрыпталған жиындағы іздеу болуы
мүмкін. Мысалы, стунденттердің фамилиясы немесе сынақ кітапшасының
номерімен сұрыптауға болады.
Сұрыптау мынау үшін керек:
1. үлкен мәліметтерде оңай жұмыс істеуді қамтамасыз ету (мысалы, іздеу);
2. адамдардың массив мәліметтеріне оңай анализ жасау үшін, мысалы
студенттер тізімі;
3. үлестіру мәліметтеріне гистограмма жасау.
Сұрыптау – бұл мәліметтерді өңдеудегі ең қызықты да және маңызды
процедура. Мәліметтерді өңдеу есептеріндегі мәліметтерді сұрыптау уақыты
жалпы өңдеу уақытының 35-70% құрайды.
2.1.1.Сұрыптау тәсілдері
Кестелермен жұмыс істегенде – оның негізгі опреациялары – ол жазбаларды
реттеу және берілген шарт бойынша жазба кестелерінде барлау жасау. Сұрыптау
- бұл кейбір критерийлері бойынша жазбаны кестелерде нақты бір тәртіппен
реттеу операциясы. Сұрыптау барлық жазбалар кілттерінің мәндерімен сәйкес
іске асады (мыс,. Алфавит бойынша аттарын реттеу немесе сандарды өсу
бойынша реттеу). Сұрыптаудың көптеген бір – бірінен айрықша тәсілдері бар.
Егер де кесте бүтіндей ЭЕМ – нің жедел жадында орналастырса, онда оның
реттелуі ішкі деп аталады. Ал егер де реттелген мәліметтерді сақтау үшін
сыртқы есте сақтау құрылғысы пайдаланса, онда бұндай реттелу сыртқы деп
аталады. Операцияларды салыстырудың орташа саны, сұрыптаудың тәсілінен
байланысты, және де рационалды тәсілді таңдаған кезде кейбір минимумға
жетеді. Ішкі сұрыптау тәсілдерін екі топқа бөлуге болады:
• Разервтік жадыны қажет ететін тәсілдер
• Резервтік жадыны қажет етпейтін тәсілдер
Бірінші топқа таңдау, енгізу, көпіршік (пузырька), Шелл тәсілдері
жатса, екінші топқа квадраттық таңдау, қосылу тәсілі және т.б. Қарапайым
сұрыптау тәсілдері (таңдау, енгізу, ауыстыру) шамамен n**2 салыстыруын
талап етеді. Әдетте одан да қиынырақ алгоритмдер орташа n*log2(n)
салыстыруларында нәтиженің берілуін қамтамасыз етеді. Бірақ та кез келген
жағдайларда қолайлы сұрыптау жоқ, себебі олардың тиімділігі кестедегі
кілттердің түріне және олардың алдын ала реттелуіне байланысты. Ішкі
сұрыптаудың ең кең қолданылатын тәсілдерінің алгоритмін қарастырайық:
2.1.2.Таңдау сұрыптауы
(тік таңдау, сызықты таңдау)
Осы метод бойынша, кестедегі бірінші жазбадан бастап, ең кішкентай мәні
бар кілттің элементтерін іздеуге болады. Осындай орын-ауыстырудың
нәтижесінде, кілттің ең кішкентай мәні бар жазбаны кестедегі бірінші
позицияға орналасытырылады. Одан кейін кестедегі екінші элементтен бастап,
екінші ең кіші мәні бар кілттің ізденуі жүзеге асады. Табылған элемент
кестедегі екінші элементпен орын ауыстырады. Бұл процесс кілттің кодтары
өсу реті бойынша реттелмейінше тоқтамайды. Осы тәсілдегі салыстыру саны n(n-
1)2 –ге тең, мұндағы n – кестедегі жазбалардың саны. Осындай сұрыптау
кезінде орын ауыстырудың ең үлкен саны (n-1) – ге тең. Келесі кілттердің
мәндері бар кесте үшін алгоритмдік қадамдарын мысал ретінде қарастырамыз:
23 11 4 56 9 35 7

Берілген кесте әртүрлі кезеңіндегі реттелуін көрсетеді

(орын ауыстыратын элементтердің асты сызылған):
23 11 4 56 9 35 7
4 11 23 56 9 35 7
4 7 23 56 9 35 11
4 7 9 56 23 35 11
4 7 9 11 23 35 56

2.2.Көпіршік тәсілі
Осы тәсілді пайдаланған кезде (n-1) – дің ең үлкен өтулері керек.
Кестенің бірінші өтуі кезінде бірінші және екінші жазбаның К1 және К2
кілттері салыстырылады, егер де олардың арасындағы тәртіп бұзылса, онда
R1және R2 жазбалары орындарын ауыстырады. Содан кейін осы процесс R2 және
R3, R3 және R4 т.с.с. үшін қайталанады. Осы тәсіл аз кілттері бар
жазбаларды қозғалтуға және білінуге мәжбүр етеді. Бірінші өтүден кейін ең
көп мәні бар жазбадағы кілт кестенің n-ші позициясында тұрады. Әрбір
келесі өтулер кезінде ең көп мәндері бар келесі жазбалардағы кілттер n-1,
n-2, ...,2 позицияларында орналасады, нәтижесінде сұрыпталған кесте шығады.
Әрбір өтулерден кейін осы өтулер кезінде ауыстырулар болда ма, жоқ па
деген тексеруді да істеуі мүмкін. Егер де ауыстырулар жоқ болса, онда ол
кесте сұрыпталғаны екені және де одан арғы өтулерді қажет етпейтінін
білдіреді. Сонымен қатар, соңғы ауыстырудың индексін есте сақтауға болады.
Бұл келесі қадамдағы қарайтын қосалқы кестені кішірейтуге мүмкіндік береді.
Көпіршік тәсілімен сұрыптағандағы сипаттамасы ең болмағанда n(n-1)2
салыстыруларын және n(n-1)2 ауыстыруларын құрайды. Салыстырудың және
ауыстырудың орташа саны n**2 рет.
Паскаль және Си тілдеріндегі Көпіршік тәсілін іске асыратын процедура
төменде келтірілген:

Type
Rec=Record
f1 : char;
f2 : integer;
f3 : integer
End;
Table = Array[1..100] Of Rec;
procedure bubble(var T:Table;
*t,int n);
n:integer);
{ T - кесте; n – оның өлшемі }
*
{ f3 ауданы бойынша сұрыптау}
сұрыптау *

var
i:integer;
temp:Rec;
switch:boolean;
begin
repeat
for i:=1 to n-1 do
if T[i].f3T[i+1].f3 then
begin
switch:=true;
temp:=T[i];
T[i]:=T[i+1];
T[i+1]:=temp
end
until not(switch)
end

2.2.1.Көпіршік тәсілімен сұрыптау
Бұл тәсіл ауыстыру тәсілімен сұрыптауды пайдаланады. Ол салыстыру
операцияларының циклында орындалуында және көршілес тұрған элементтерін
ауыстыруға қажеттігіне негізделген. Оның аталуы сумен толтырылған
резервуардағы көпіршіктердің қозғалу кезіндегі процесске ұқсас болғандықтан
шықты. Әрбір көпіршік өз жиегін табады. Төменде көпіршік тәсілімен
сұрыптаудың ең қарапайым программаның формасы көрсетліген:

{Көпіршік тәсілімен сұрыптаудың басталуы}
procedure Bubble(var item: DataArray; count:integer);
var
i,j: integer;
x: DataItem;
begin
for i := 2 to count do
begin
for j := count downto i do
if item[j-1]item[j] then
begin
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
end;
end;
end; { Көпіршік тәсілімен сұрыптаудың аяқталуы }
Бұл мысалда берілген item Dataitem элементінің массиві болып табылады.
Ол сұрыпталады да, ал берілген count массивінде элементтердің саны бар.
Көпіршік тәсілімен сұрыптаудың екі циклі бар. Массив элементінің саны
count айнымалымен берілгендіктен, сыртқы цикл count массивінің қаралуын !
рет ғана шақырады. Бұл процедура аяқталғаннан кейін әрбір элементтің өз
позициясында тапқанын қамтамасыз етеді. Ішкі цикл салыстыру және ауыстыру
операцияның шындығымен орындалатынына негізделген. Көпіршік тәсілімен
сұрыптаудың осы версиясы символдық массивтегі элементтердің мәндерін өсу
реті бойынша сұрыптай алады.
Көпіршік тәсілімен сұрыптауының бір ерекшелігі бар: массивтің соңындағы өз
орнында тұрмаған элемент (мысалы, dcab массивіндегі а элементі) бір өту
арқылы өз орнына жетеді, ал массивтің басында орналасқан элемент (мысалы,
d элементі), өз орнына өте баяу жетеді. Барлық қарауларын бір бағытта
істеу міндетті емес. Оның орнына әрбір келесі қарауын қарама-қарсы бағытта
істеуге болады. Бұл жағдайа өз орнынан қатты алыстап кеткен элементтер тез
арада өз орнына жылжиды.

2.3.Модификацияланған енгізу тәсілі (бинарлық кірістіру)
Тура қосу тәсілін жақсарту үшін, кестенің кезекті элементін реттелген
қосалқы кестеге енгізу, оны бинарлық іздеу тәсілінің (дихотамикалық,
екілік, логарифмдік) көмегімен жүзеге асыруға болады.
Сұрыптаудың j-ші қадамы:
5 6 8 10 14 18 9 2 ¦ i = 62 = 3; 9 8
~~~ ~~~~~~ ~~ ¦
тасталынады қарасытырлады ¦
--¬ ¦
. . . 10 14 18 9 2 ¦ i = (4+6)2 = 5;
~~ ~~~~~ ¦ 9 14
тасталынады қарасытырлады ¦
. . . 9 10 14 18 2 ¦ i = 4; 9 10

2.4.Шелл тәсілі

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

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