Зертханалық жұмыс

жүктеу 1,28 Mb.

бет	27/38
Дата	23.01.2020
өлшемі	1,28 Mb.
	#27192

1 ... 23 24 25 26 27 28 29 30 ... 38

Тапсырма 1

Ферзи, бір - бірін соқпайды: бұтақ орнын тексеру.

Бірінші бөлімде біз бір үлгідегі бірнеше есептер қарастырғанбыз: "Кей

жиымның барлық элементтерін атап шығыныз". Шешім сызбасы мынадай:

жиымында белгілі тәртіп енгізілді және бастапқы элементтін

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

Тапсырма 2

ферзидерді шахматтық тақтасында

ді

- ға қойғандағы барлық әдістерін анықтаныз (олар бір –бірін соқпаған жағдайда)

Шешімі. Әр

горизонтальнда бір ферзидан тұру керек.

–ны позиция дейміз - (

, үшін

) ферзилердің

төменгі горизонтында (ферзилар бір-бірін соғуы мүмкін). Салайық "бұтақ орыны": оның түбірі 0-орыны болады, әр

-орынан

жоғары қарай көтерілейік

- орынына. Бұл

орындары ферзилардың

-ші горизонталында орналасумен ерекшелінеді.

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

Бұл бұтақтың орындары арасынан біз

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

-орынының ферзилері бір-бірін соқса, онда қалған ферзилерді қоюдың мағынасы жоқ.

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

Нақтырақ,

-орының жетімді дейміз, егер жоғары ферзиді жойса, қалғандары бір-бірін соғады. Біздің бағдарлама рұқсат етілген орындарды ғана қарастырады.

Есепті екі бөлікке бөлейік: (1) бұтақты ерікті айналамыз және (2) бұтақтарды рұқсат етілген орыннан іске асыру.

Ерікті ағашты айналудың есебін құрастырайық. Бізде робот бар деп есептейік, ол әр ауқыт сайын бұтақтын төбесінде орналасуы мүмкін.

Ол берілген тапсырмаларды орындай біледі:

жоғары солға (жоғары бағдаршадан шығатын сол жақ бойынша)

оңға (көрші оң жақтағы төбеге көшу)

төмен (бір деңгейге төмен түсу)

жоғары солға

оңға

төмен
Әр команданы сәйкесінше орындау үшін "жоғары бар", "сол жақта бар", "төмен бар" (соңғы тексеру барлық жерде тиімді, түбірден басқасы). Көңіл бөліңіз, "оңға" командасы тек қана "туған ағасына" ғана көшуге мүмкіндік береді.

Роботта "өңдеу" деген командасы бар оның міндеті – барлық парақтарды (биіктік, оларды ішінде жоғары бағдаршасы жоқ, "жоғары бар ").

Біздің шахматтық есебін шығару үшін команда ферзи орынындағы басылым мен тексерісі сәйкесінше өңделеді.

Бағдарламаны ары қарай дұрыс қолданудың мынадай анықтамасы беріледі. Роботтың бір бұтақтын төбесінде жағдайын бекітсін.Сол жағдайда бұтақтын барлық парақтары үш категорияға бөлінеді: Робот үстінде, Роботтан солға қарай және роботтан оңға қарай. (Түбірден параққа Роботпен төбе арқылы өтеді, солға қарай бұрылу, оған жетпей оңға қарай бұрылу.) (ОЛ) арқылы жағдайды белгілеймі"Роботтан солға қарай барлық парақтар өңделген ", а (ОЛН) арқылы - жағдайы "барлық парақтар солға қарай және Робот үстінде өңделген".

Бізге мынадай процедура қажет:

procedure тірелгенге дейін жоғары және өңдеу

| {берілген: (ОЛ), керек: (ОЛН)}

begin

| {инвариант: ОЛ}

| while жоғарыда бар do begin

| | жоғары солға;

| end

| {ОЛ, Робот парақта}

| өңдеу;

| {ОЛН}

end;
Негізгі алгоритм:

берілген: Робот түбірде,парақтары өңделмеген

керек: Робот түбірде, парақтары өңделген
{ОЛ}

тірелгенге дейін жоғары және өңдеу;

{инвариант: ОЛН}

while төмен бар do begin

| if оң жақта бар then begin {ОЛН, оң жақта бар }

| | оңға;

| | {ОЛ}

| тірелгенге дейін жоғары және өңдеу;

| end else begin

| | {ОЛН, оң жақта емес төмен жақта}

| | төмен;

| end;

end;

{ОЛН, Робот түбірде=> барлық парақтар өңделген}

Роботтың келесі қасиеттерін пайдалану ғана қалды. (жоғары қарай шарттары көрсетілген, онда төмен-оны орындау нәтижесі туралы анықтама командасы орындалады):

(1) {ОЛ, жоғары емес} (2) {ОЛ}

жоғары солға өңдеу

{ОЛН} {ОЛ}

(3) {оң жақта бар, ОЛН} (4) {оң жақта емес ОЛН}

оңға қарай төмен

{ОЛ} {ОЛН}

жүктеу 1,28 Mb.

Достарыңызбен бөлісу:

1 ... 23 24 25 26 27 28 29 30 ... 38