Algoritmlash

AGAR M<=tl(i) YA tl(i)<=K

{buyum miqdori oraliqda bo'lishi}

175



U HOLDA

o‘tkaz S+tl(i), S TAMOM

TAMOM

9.6- mashq

Saralovchi M Nia tokchali tl(*) ni buyumlari miqdori M\a /(orasida bo'lgan tokchalarini barcha buyumlari miqdorining ko'paytmasini S tokchaga o'tkazsin.

9.5-masala

Saralovchi M N ta tokchali tl(*) ni buyumlari miqdori M va K orasida boMgan tokchalarining barcha buyumlarini Sl tokchaga, qolganlarini S2 tokchaga yig'sin.

Yechim. Ha, mana, Bek uchun iqtidoriga yarasha qiziqarliroq masala. Takrorlash va tarmoqlanish aralashgan algoritm shunday:

bo‘shat S1 bo‘shat S2

TAKRORLANSIN N MARTA AGAR M<=tl(i) VA tl(i)<=K

U HOLDA {buyum miqdori oraliqda bo'lishi}

o‘tkaz S l+ tl(i), S1

_{AKS HOLDA} {buyum miqdori oraliqda boMganlar}

o‘tkaz S2+tl(i), S2

TAMOM {buyum miqdori oraliqda boMmaganlar}

TAMOM

9.7- mashq

Saralovchi M N ta tokchali tl(*) ni buyumlari miqdori A/dan kichik boMgan tokchalarining barcha buyumlarini S1 tokchaga, qolganlarini S2 tokchaga yig'sin.

9.8- mashq

Saralovchi M N ta tokchali tl(*) ning buyumlari miqdori M dan kichik boMgan tokchalarining barcha buyumlarini S1 tokchaga, N ta tokchali 11(*) ni buyumlari miqdori M va K orasida boMgan tokchalarining barcha buyumlarini S2 tokchaga va qolganlarini S3 tokchaga yig'sin.

176

9.9- mashq

Saralovchi M Nia tokchali tl(*) ning tartib raqamlari M dan kichik bo‘lgan tokchalarining barcha buyumlarini S1 tokchaga, N'ta tokchali 11(*) ni tartib raqamlari A/va Aforasida bo'lgan tokchalarining barcha buyumlarini S2 tokchaga va qolganlarini S3 tokchaga yig‘sin

9.6- masala

juftSaralovchi A/juft a;V ta tokchaliatl(*) ningrtartib raqamlari

yig'sboMgan tokchal rining barch buyumia ini S tokchaga

in.

Yechim. Bek ham charchamaydigan bola ekan-da, masalalarni yechmay turganda ozgina dam olardik. Bu masalani yecha olmasa kerak, chunki Saralovchi M juft degan tushunchani ham, juft degan shartini ham tushunmaydi va tekshira olmaydi. Uning ixtiyorida hammasi bo'lib to‘rt arifmetik amal va bob boshida bayon etilgan shart tekshirishlar bor. Juft degan shartni tekshirish uchun, odatda, sonni 2 ga bo‘lganda qoldiq qolmasligi orqali (son mod 2 = 0) yoki sonni 2 ga boMganda butun chiqish talabi ([son/2]

= son/2) orqali tekshiriladi. Bek mana qanday algoritm tuzibdi: hn'shat S

TAKRORLANSIN N/2 MARTA

TAMOM o‘tkaz S+tl(2-i), S

ber Qoyil, buning ham yo‘lini topdi. Algoritm mazmuniga e’tibor

h ing: imasalaoshartida N juft natural son va ,shuning uchun

I am un 2 ga b Mganda natural sonlhosil boMadi ya'ni sanashda

NKOR yuzaga kelmaydi. Takror anishda sanoq i = 1 boMsa:

2 • i = 2 —birinchi juft son; sanoq i = 2 boMsa: 2 ■ i = 4 —ikkinchi juft son; sanoq i = 3 boMsa: 2 • i = 6 —uchichi juft son; ...; sanoq i = N/2 boMsa: 2 • i = N —oxirgi juft son hosil boMadi.

9.10- mashq

Saralovchi M toq N ta tokchali 11(*) ning tartib raqamlari toq bo'lgan tokchalarining barcha buyumlarini S tokchaga yig'sin.

9.7- masala

bo Saralovchi M N ta tokchali tl(*) ning tartib raqamlari juft

Mgan tokchalarining barcha buyumlarini S tokchaga yig'sin.

Yechim. Bu masalada N ning toqligi ham juftligi ham ma'lum emas. Endi bu vaziyatdan qanday chiqib ketish mumkin? Qarri Bek tuzgan algoritmni qarab chiqaylik-chi:

^{12 — Azamalov, A.R.} 177



boShat S

TAKRORLANSIN N MARTA AGAR 2*i<=N

(juft sonni yuqori chegaradan oshib ketmaslik sharti} U HOLDA

TAMo‘tkaz S+tl(2 i), S

TAMOM OM

be Nima ham derdik, 'lalgoritm nmasalae shartiga to‘liq javob

radi. Agar N juft bo sa N/2 atural kanligi, N toq bo‘lsa

(N -l)/2 natural ekanligini hisobga olsak, quyidagi jadval algoritmni tushunishga oydinlik kiritadi: