|
1.8 Saralash usullari va ularga doir masalalari
Farzandlarining aqlliligidan mehri jo‘shib ketgan Bekning ota- onasi robotga ikkinchi qo‘l o‘rniga bo‘sh tokcha vazifasini o‘tay oladigan Zt tokcha (zahira tokcha) o‘rnatib berishdi. Bu holda, birinchidan, robot Zt tokchada ixtiyoriy tokchadagi buyumning asl nusxasini hosil qila olardi, ya’ni tokchadagi buyumni xuddi o‘ziga o‘xshash boshqasini zaxiradan olib kela olardi, bunda Zt tokchadagi avvalgi nusxa tashlab yuboriladi. Ikkinchidan, Zt tokchadagi nusxani asosiy tokchalarga ham o‘tkazish mumkin, bu holda ham robot zaxiradan foydalanadi. Yuqoridagi izohlarni hisobga olib, yangi Ijrochi Saralovchi II uchun quyidagi ko‘rsatmani izohlaymiz:
o‘tkaz tokcha(N), Zt
Bu ko‘rsatmada Saralovchi II N-tokchadagi buyumni Zt tokchaga olmaydi, faqat Zt tokchaga N-tokchadagi buyumning nusxasinigina oladi.
Shart tekshirish quyidagi talabga bo‘ysunadi: Saralovchi II Zt tokchadagi buyum miqdorini hamda qo‘lga olingan biror tokchadagi buyum miqdorini aniqlaydi, keyin bir-biri bilan taqqoslaydi. Bu esa Saralovchi II AGAR
U HOLDA
TAMOM
yoki
AGAR
U HOLDA
<1-ko‘rsatmalar guruhi>
AKS HOLDA
<2-ko‘rsatmalar guruhi>
TAMOM
kabi shartli tuzilmalarni bajara oladi, degani.
Avvalgi boblarda birikkan shartlar haqida ma’lumotlar berilgan edi. Saralovchi II robot ham bu ishni bajara oladi. Masalan, tokcha(1)=0 VA Zt>0 sharti talabga qarab 1-tokchadagi buyum miqdori 0 ga tengligini va Zt tokchadagi buyumning miqdori 0 dan kattaligini va rostlik jadvali asosida tekshiradi. Saralovchi II da faqat bitta qo‘l va Zt tokcha bor bo‘lgani uchun ikkita shartdan ko‘pi bilan ishlay olmaydi.
Xonada 5 ta tokcha bo‘lib, ularning ustiga turli sondagi bir xil o‘lchamdagi kublar ustma-ust taxlangan. Saralovchi II bitta tokchada eng ko‘p taxlangan kublar sonini aniqlashi kerak.
Yechim. Saralovchi II eng ko‘p taxlangan kublar sonini aniqlashi uchun Zt tokchaga shu kublarning nusxasini olishi yetarli. Buning uchun Bek quyidagicha yo‘l tutgan.
Birinchi qadamda Zt tokchaga 1-tokchadagi buyum nusxasi olindi. Demak, u hozircha eng ko‘p kublar soni 1-tokchadagi kublar soniga teng, deb oldi. Saralovchi II Zt tokchadagi kublar bilan qo‘lga olingan 2-tokchadagi kublar sonini taqqoslaydi. Agar 2-tokchadagi kublar soni ko‘p bo‘lsa, Zt tokchaga 2-tokchadagi kublarning nusxasini oladi, aks holda 3-tokchaga o‘tadi. Demak, Bekning algoritmi quyidagicha ekan: o‘tkaz tokcha(1), Zt AGAR ZtU HOLDA
o‘tkaz tokcha(2), Zt TAMOM
AGAR ZtU HOLDA
o‘tkaz tokcha(3), Zt TAMOM
AGAR ZtU HOLDA
o‘tkaz tokcha(4), Zt TAMOM
AGAR ZtU HOLDA
o‘tkaz tokcha(5), Zt TAMOM
Barakalla, Bek muammoni hal qildi. Lekin keyingi masalada nima qilar ekan?
8.7- masala
Xonada 1963 ta tokcha bo‘lib, ularning ustiga turli sondagi bir xil o‘lchamdagi kublar ustma-ust taxlangan. Saralovchi II bitta tokchada eng ko‘p taxlangan kublar sonini aniqlashi kerak.
Yechim. Bek har bir tokchaga mos taqqoslashlarni erinmasdan juda ko‘p vaqt sarflab Saralovchi II xotirasiga yozib kiritdi. Uning bu erinmasdan ishlagani uchun mukofot tarzida ota-onasi Saralovchi II dasturiga TAKRORLANSIN - MARTA tuzilmasini va quyidagi qoidani kiritishdi.
Sintaksis qoidalari:
• N, Zt, tokcha(N) nom bo‘lgani uchun bosh harflarda ham kichik harflarda ham yozilishi mumkin;
• TAKRORLANSIN k MARTA tuzilmasida tokcha(i) yozuvi takrorlanishda 1 dan k gacha sanalganda har bir songa mos tokchani anglatadi, ya’ni sanoq 1 bo‘lsa - tokcha(1) ni, sanoq 2 da - tokcha(2) ni, ... , sanoq k da - tokcha(k) ni qaralayot-ganini bildiradi.
Endi 8.7-masala yechimi Saralovchi II uchun quyidagicha bo‘ladi:
o‘tkaz tokcha(1), Zt TAKRORLANSIN 1963 MARTA AGAR ZtU HOLDA
o‘tkaz tokcha(i), Zt TAMOM TAMOM
Bu algoritm quyidagicha ishlaydi:
Birinchi qadamda Zt tokchaga 1-tokchadagi buyum nusxasi olinadi. Demak, hozircha eng ko‘p kublar soni 1-tokchadagi kublar soniga teng. Keyingi qadamda takrorlanish tuzilmasi ishlay boshlaydi. Sanoq 1 bo‘lganda Saralovchi II Zt tokchadagi kublar bilan 1-tokchadagi kublar sonini taqqoslaydi, Zt tokchada 1- tokchadagi buyum nusxasi bo‘lgani uchun shart bajarilmaydi. Sa- noq 2 bo‘lganda Saralovchi II Zt tokchadagi kublar bilan 2- tokchadagi kublar sonini taqqoslaydi. Agar6 2-tokchadagi kublar soni ko‘p bo‘lsa Zt tokchaga 2-tokchadagi kublarning nusxasini oladi va takrorlanish qadami oshadi aks holda faqat takrorlanish qadami oshadi, va hokazo.
4-sharh
E’tibor bergan bo‘lsangiz, TAKRORLANSIN - MARTA tuzil- masining bu ko‘rinishida 1-tokchadagi buyum o‘zining nusxasi bilan taqqoslandi. Bu tuzilmaning kamchiliklaridan biridir.
Saralash usullari
8.14-masala
Xonada N ta tokcha bo‘lib, ular ustiga turli sondagi bir xil o‘lchamdagi kublar ustma-ust taxlangan. Saralovchi III tokcha- lardagi kublarning o‘rnini shunday almashtirsinki, natijada tokcha- larda kublar soni kamayish tartibida joylashsin.
Avval masala shartini tushunib olaylik. Bu masalani kamayish tartibida saralash deb ham atashadi. Tokchalardagi kublar shunday joylashishi kerakki, son jihatidan qaralganda, 1-tokchaga barcha tokchalardagiga qaraganda eng ko‘p kub taxlangan tokchadagi kublarni, 2-tokchaqa qolgan (o‘tkazilgandan keyingi 1-tokchadagidan tashqari) barcha tokchalardagiga qaraganda eng ko‘p kub taxlangan tokchadagi kublarni, 3-tokchada qolgan (o‘tkazilgandan keyingi 1—
2- tokchadagilardan tashqari) barcha tokchalardagiga qaraganda eng ko‘p kub taxlangan tokchadagi kublarni va hokazo, o‘tkazish kerak.
Jadval ko‘rinishida kamayish tartibida saralashni quyidagicha tasvirlash mumkin:
Do'stlaringiz bilan baham: |
