Algoritmlash

Ko'rsatma Son 729

1 ni ayir 728

2 ga bo‘l 364

^{2 ga bo‘l} 182

....

4.6-ma.shq

Algoritmni mustaqil tugating.

Os Endi Kamaytiruvchi uchun algoritm tayyor boMgach, uni hiruvchi uchun o‘zgartiramiz.

fa Buning uchun algoritmni ‘quyidan yuqoriga yozib boramiz,

2 qat 1 ni ayir o‘rniga 1 ni qo sh ko'rsatmasini, 2 ga bo‘l o'rniga

al ga ko‘paytir ko'rsatmasini yozamiz.rNatijada quyidagi ikkita

Ogoritm hosil bo‘ladi, biri Kamayti uvchi uchun ikkinchisi

shiruvchi uchun.

^{Qadamlar Kamaytiruvchi} Osbinivchi

^{soni ko'rsatmalari Son} ko'rsatmalari <sup>Son

0</sup> 729 0

^{1 1 ni ayir 728 1 ni qo‘sh} 1

71

2 2 ga bo‘1 ^{364 2 ga ko'paytir 2}

3 2 ga bo‘l 182 2 ga ko'paytir 4

4 2 ga bo'l 91 ^{1 ni qo'sh 5}

5 1 ni ayir 90 2 ga ko'paytir ¹⁰

6 2 ga bo‘l ^{45 1 ni qo'sh 11}

7 1 ni ayir 44 2 ga ko'paytir 22

8 2 ga bo‘l 22 2 ga ko'paytir ⁴⁴

9 2 ga bo‘l ^{11 1 ni qo'sh} 45

10 ^{1 ni ayir 10 2 ga ko paytir 90}

11 2 ga bo‘l 5 ^{1 ni qo'sh} 91

12 1 ni ayir 4 2 ga ko'paytir 182

13 2 ga bo‘l 2 2 ga ko'paytir ³⁶⁴

14 2 ga bo‘l 1 2 ga ko'paytir 728

15 1 ni ayir 0 1 ni qo'sh 729

Bu algoritmlarda qadamlar soni bor-yo‘g‘i 15ga teng!

4.12- masala

1000 dan kichik har qanday sonni 0 sonidan ko‘pi bilan 20 qadamda hosil qilish mumkinligini ko'rsating.

Yo'llanma. Agar qadamlar soni 20 tadan ko‘p bo'lsa, ikkilantirishlar soni nechta? — ... dan kam emas.

Oshiruvchi uchun eng «qulay» sonlar —ikkining darajalaridir, ya’ni 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,... Ularni qo'shish

amalisiz faqat ikkilantirish orqali hosi! qilishimiz mumkin. Oshiruvchi uchun eng «noqulay» sonlar —ikkining darajasidan bittaga kam sonlar, ya'ni 1, 3, 7, 15, 31, 63, 127, 255, 511,

1023...

bittBu sonlarnir hosil qilish uchun har ikkilantirishdan so'ng

aga kamayti ib hosil qilish mumkin (tekshirib ko'ring!).

4.13- masala

Oshiruvchi uchun 0 sonidan 14 ta qadamda hosil qilib boMmaydigan sonni toping.

Javob: 255.
72




4.14- masala

bo Oshiruvchis uchun 0 sonidan 15 ta qadamda hosil qilib

‘lmaydigan onni toping.

Javob: 256+127 = 383.

4.15- masala

engKamaytiruvchi uchunt 729 sonidan 17 sonini hosil qiluvchi

samarador algoritm uzing.

Oshiruvchi uchun algoritmni yaxshilash

bo Berilgan a sonidan b sonini hosil qilish algoritmi tuzilgan 'lsin. Agar a bo‘lsa, u holda quyidagilar o'rinli ekanini

isbotlang:

• agar algoritmda birinchi a ta ko'rsatma 1 ni qo‘sh boMsa, u holda ularni 2 ga ko‘paytir ko‘rsatmasi bilan almashtirish mumkin;

• agar algoritmda ketma-ket kelgan quyidagi ko‘rsatmalar guruhi bor bo‘lsa:

2 ga ko‘paytir

1 ni qo‘sh

1 ni qo‘sh

u holda ular o'rniga quyidagi ko'rsatmalar guruhini almashtirib, algoritmni yaxshilash mumkin:

1 ni qo‘sh

Masa^{2 ga ko'paytir} ni hosil qilish algoritmini yozamiz:

lan, 3 dan 10

1 ni qo‘sh !-*{ 2 ga ko‘paytirl f 1 ni qo‘sh 1 ni qo‘sh 1 ni qo‘sh t 1 ni qo‘sh

1 ni qo‘sh j 1 ni qo‘sh

^{1 ni qo‘sh 1 ni qo‘sh} 1 ni qo‘ sh J

1 ni qo‘sh 1 ni qo‘sh

1 ni qo‘sh

1 ni qo‘sh

Oxirgi algoritmni yaxshilab boMmaydi.

Nazorat savollari va topshiriqlar

1. Sikl deganda nima tushuniladi?

2. Samaradoriik deganda nimani tushunasiz? Misollar bitan izohtang

3. Murakkahlik deganda nimani tushunasiz?Misollar bilan izohlang.

73

4. Siklik tuzilishii algoritmiaming sintaksis qoidalari qanday?

5. Qanday algoritmlar universal deyitadi?

6. Qanday tuzdmaiar universai deyiladi?

7. Ijrochi Kamaytiruvchi ko ‘rsatmalar ro ‘yxati haqida so ‘zlab bering.

8. Ijrochi Kamaytiruvchi uchun sodda amallami yozib chiqing.

9. Ijrochi Kamaytiruvchi uchun bor bo ‘Isa kamida bitta INKOR holatniyozjng.

10. Hayotingizdan sikliarga misollar keltiring.

11. Bobda keltirilgan barcha mashqlami bajaring.

Qo‘shimcha masalalar

qir M-1. Daryo qirg‘og‘iga 60 ta askar keiishdi. Ular daryoning narigi yug‘og‘iga o'tishlari kerak. Q irg 'o q yaqinida to'rtta qiz qayiqda suzib ribdi. Qayiq shunchaiik kichkinaki, faqat ikkita askarni ko'tarishi

mumkin. Daryo oqimi juda tez bo‘lganidan qayiq ag‘darilib ketmasligi

uchun qayiqda ikkitadan kam qiz bo‘Iishi murnkin emas. Qanday qiiib askarlar daryodan o‘tib oiishadi va qayiqni qizlarga qaytarib berishadi? Ijrochi uchun ko‘rsatmalar ro'yxatini ishlab chiqing va algoritm tuzing.

Chigirtka (3;2) bo‘ya ko'rsatmasini bajarishni o'rgandi.

alg Ch-1. Chigirtka boshlang'ich holati —0 tartib raqamli kvadrat. Quyidagi oritmlar bajarilgandan keyin natijada qanday farq bo'ladi?

^{1- algoritm} 2- algoritm

oldinga 3 bo‘ya

^bo‘ya oldinga 3

quyCh-2. Chigirtka -1 tartib raqamli kvadratdan harakatni boshladi va idagi algoritmni bajardi:

oldinga 3 bo‘ya oldinga 3

orqaga 2 bo‘ya

U qaysi orqaga 2mi bo‘yagan?

kvadratla

danCh-3. Chigirtka 0 tartib raqamli kvadratda turibdi. U 0 dan katta 500 kichik har uchinchi kvadratni bo‘yash algoritmini tuzing.

danCh-4. Chigirtka 0 tartib raqamli kvadratda turibdi.iU 0 dan katta 500 kichik har to‘rtinchi kvadratni bo'yash algoritmin tuzing.

500Ch-5. Chigirtka 0 tartib raqamli kvadratda turibdi va uni bo‘yadi. U - tuzi dan katta va 500 dan kichik har to'rtinchi kvadratni bo'yash algoritmini

ng.

V bob. MANTIQ ELEMENTLARI VA SHARTLAR

Manliq elementlari

Har bir dasturlash tilida biror-bir shartni tekshirish imkoni bor. Shartni tekshirish deganda biror narsani da’vo qilib, uni rost-yolg‘onligini aniqlashni tushunamiz. Masalan, biz son juft deb da'vo qildik deylik, agar son haqiqatan ham juft bojsa, u holda da'vomiz ROST, aks holda da'vomiz YOLG'ON boMadi. Demak, shartni tekshirish degani juft son da'voyimiz o'rinlimi, degan savol berish kabi ekan. Faqat bu savolga HA deb yoki YO‘Q deb javob beriladi. Shu sababli blok-sxemada, awal ko'rganingizdek, quyidagi ko'rinishdagi blok qaraladi:

ol Agar da'vomiz shartning qisqa ko‘rinishi ekanligini hisobga tesak,ru holda oddiy ko‘rinishi qanday bojadi? Mana bunday: kshi ilayotgan shart o‘rinli. Endi bu da'vo rost yoki yolg'onligi

haqida fikr yuritish mumkin bojadi.

Hayotimizda juda ko‘p bu kabi da'volarni aytamiz. Masalan:

«Bugun havo issiq», «0 soni juft», «Qishda qor yog‘adi», «Men algoritmikani yaxshi ko‘raman» va hokazo. Bu barcha da'volar ROST bo‘lavermaydi, boshqacha aytganda, sharoitga bogjiq bo‘ladi. Haqiqatan, birinchi gapni qishning barcha kunlarida, uchinchi gapni esa Afrika qishida, to'rtinchi gapni esa ham- mamiz ham ayta olmaymiz. Faqatgina ikkinchi gap doimo ROST bojadi.

ya’E'tibor qilgan bo jsangiz, bu gaplarning har biri darak gapdir,

Y ni bizga axborot bermoqda. Bu gaplarning ROST yoki

y OLG‘ON bo'lishi jmazmunan berilayotgan axborotmiqROST

oki YOLG‘ON bo ishi bilan o‘zaro bir qiymatli bogji .

ber Ko'pincha darakagaplarda biz ikki va undan, ortiq axborot

bu amiz yoki biror n rsani inkor etamiz.aMasalan «Bugun havo

lut va yomg‘ir yog‘yapti», «2 juft v tub son», «Kurashda

75

men yutaman yoki sen yutasan*, «Men imtihondan o‘taman yoki imtihondan yiqilaman», «Oynani sindirgan men emas» va hokazo. «Va» hamda «yoki» hog'lovchili gaplarni alohida ajratish mumkinmi, ya'ni alohida da’vo sifatida qarash mumkinmi? Agar ularning ma'nosini yo'qotishni istamasak, ajratishimiz mumkin emas. U holda hu kabi murakkab da'volar shart sifatida qanday qo'llaniladi? Bu savolga javob quyida keltirilgan.

— Murakkab (birikkan) shartlarni yozish uchun juda qulay vosita

mantiqiy amallar o‘ylab topilgan. Ular uchta: