B. J. Boltayev, A. R. Azamatov, G. A. Azamatova, B. S. Xurramov nazariya, algoritm, dastur toshkent 2013

DKS={echkini o‘tkaz; bo‘rini o‘tkaz; karamni o‘tkaz; suzib o‘t}
Birinchi bo‘lib qaysi yo‘lovchini olib o‘tish kerak? Tushunarliki, bo‘rini
o‘tkazib bo‘lmaydi – bu holda echki karam bilan bir qirg‘oqda qoladi va uni yeb
qo‘yadi. Shunday sababga ko‘ra karamni ham olib o‘tib bo‘lmaydi. Ammo ech-
kini bemalol olib o‘tish mumkin (bo‘rilar karam yemaydi). Shundan keyin dehqon
bo‘sh qayiq bilan qaytadi – echkini qaytarib olib kelishning ma’nosi yo‘q.
Demak, masala yechimining birinchi ikki qadami quyidagicha:

Qadam
Ko‘rsatma

Chap qirg‘oq
O‘ng qirg‘oq
0
–
Dehqon, bo‘ri, echki, karam
–
1
echkini o‘tkaz
bo‘ri, karam
Dehqon, echki
2
suzib o‘t
Dehqon, bo‘ri, karam

Shundan keyin dehqonda ikkita imkoniyat bor:

1. bo‘rini o‘tkazish
2. karamni o‘tkazish
Agar u bo‘rini o‘tkazib qo‘yib chap qirg‘oqqa qaytsa, u holda bo‘ri va echki
o‘ng qirg‘oqda qoladi, bu esa echki uchun o‘ta xavfli. Lekin bo‘ri o‘rniga karamni
o‘tkazib qo‘yib chap qirg‘oqqa qaytsa, o‘ng qirg‘oqda echki va karam yuqoridagi
singari karam uchun xavfli holatda qoladi. Bu holatlar masalaning yechimi yo‘q
degan tasavvur hosil qiladi. Lekin, unday emas. Ya’ni, masalan, dehqon bo‘rini
o‘tkazib qo‘yib orqaga bo‘sh qaytmasin, o‘zi bilan echkini olib o‘tsin! Keyingi
qadamlar o‘z-o‘zidan ko‘rinib turgani uchun masala yechimini ko‘rsatmalar orqali
yozish mumkin:

Qadam
Ko‘rsatma

Chap qirg‘oq
O‘ng qirg‘oq
0
–
Dehqon, bo‘ri, echki,
karam
–
1
echkini o‘tkaz
bo‘ri, karam
Dehqon, echki
2
suzib o‘t
Dehqon, bo‘ri, karam
echki
3
bo‘rini o‘tkaz
Karam
Dehqon, bo‘ri, echki

---

55
4

echkini o‘tkaz
Dehqon, echki, karam
bo‘ri
5
karamni o‘tkaz
Echki
Dehqon, bo‘ri, karam
6
suzib o‘t
Dehqon, echki
bo‘ri, karam
7
echkini o‘tkaz
–
Dehqon, bo‘ri, echki,
karam

Masalani yechimi yagonadek tuyulishi mumkin, lekin agar dehqon 3-qadamda

bo‘rini emas karamni olib o‘tsa, u holda shu qadamdan boshlab algoritmni davom
ettirib ikkinchi yechim algoritmini hosil qilish mumkin.
Algoritmni so‘z orqali tasvirlashni to‘laroq tushunib olish uchun quyidagi ma-
salani qaraymiz.
۩
. Bo‘g‘irsoq uchun “oldindagi” katak qal-
poqchasi ko‘rsatayotgan katakdir, masalan u o‘ngga
burilganda
ko‘rinishda bo‘ladi. Bo‘g‘irsoq bitta
oldindagi katakka yura oladi yoki turgan katagida
o‘ngga yoki chapga burila oladi. Bo‘g‘irsoq bir
katakdan bir necha marta o‘tishi ham mumkin.
Bo‘g‘irsoq o‘zi turgan katakdan
bilan belgilangan
katakka biror yo‘l bilan bora oladigan bo‘lsa, zaruriy
ko‘rsatmalar ketma-ketligini yozing.
Masala shartiga asoslanib ijrochi Bo‘g‘irsoqning ko‘rsatmalar sistemasini yo-
za olamiz, ya’ni BKS={oldinga; o‘ngga; chapga}. Endi masala yechimi sifatida
quyidagi algoritmlardan birini olish mumkin:

Qadamlar soni

1-algoritm
2-algoritm
3-algoritm
4-algoritm
1
2
3
4
5
6
7
8
9
10
11
12
1) chapga;
2) oldinga;
3) oldinga.
1) o‘ngga;
2) o‘ngga;
3) o‘ngga;
4) oldinga;
5) oldinga.
1) oldinga;
2) chapga;
3) oldinga;
4) oldinga;
5) chapga;
6) oldinga.
1) o‘ngga;
2) oldinga;
3) oldinga;
4) chapga;
5) oldinga;
6) chapga;
7) oldinga;
8) oldinga;
9) oldinga;
10) oldinga;
11) chapga;
12) oldinga.

Shu ikki masalani tahlil etishning o‘zi quyidagi natijaga olib keladi: