Algoritmlash

1 DAN N-1 GACHA BA.IAR

o‘tkaz tokcha(i), Zt

i+1 DAN N GACHA BAJAR

AGAR Zt U HOLDA

_TAMo‘tkaz tokcha(i), Zt

TAMOM OM ko‘p kubli tokcha aniqlandi}

jeng

Ek-1 DAN i GACHA BAJAR

_{o‘tkaz tok} {Saralovchi 111 teskaricha sanayapti}

_TAMOM cha(k), tokcha(k+l) <sub>tugadi}

o‘tkaz Zt, tokc</sub> {o'ngga bitta surilish

{en ha(i) sonli kublar i-tokchaga o'tdi}

g ko‘p

KTAMOM shtirish usulida faqat sikllarni o‘zi necha qadam-

eling, joyla

ligini jadval yordamida hisoblab koTamiz:

158

8.2-jadval

^Tashqi 1-ichki 2-ichki Takrorlanishlar ^{sikl i} sikl j sikl k soni

1 da 2 dan N gacha N dan 2 gacha 2 (N -l) ta ^{2 da 3 dan N gacha} N dan 2 gacha 2 (N-2) ta ^{3da 4 dan N gacha N dan 2 gacha} 2 (N-3) ta ^{4 da 5 dan N gacha N dan 2 gacha} 2 (N-4) ta

^{N-2 da} N-1 dan N gacha N dan N -1 gacha 2 (N-(N-2)) =2-2 ta ^{N-1 da} N dan N gacha N dan N gacha 2 (N-(N-1)) =2 1 ta

^{Hammasi bc'lib sikllardagi} 2 (1+2+3+...+(N-3)+(N-2)+(N-1))= qadamlar soni N-(N-I) ta

8.10-mashq

8.2-jadvaldagi qadamlar sonini hisoblashda yuqori chegara topildi Quyidagi 8.3-jadvaldagi tokchalar uchur sikllarning qadamlari sonini hisoblang va xulosa yozing

8.3-jadval

^{Tokcha tartib raqami 1 2} 3 ⁴ 5

^{Boshlang'ich holatda kuhlar soni} ₁ 3 7 12 49

8.10-mashq

8.1-jadvaldagi tokchalar uchun algoritmni tekshiring

ra Biz algoritmni quyidagi jadvaldagi tokchalar uchun tekshi- miz:

8.4-jadval

^{Tokcha tartib raqami 1 2 3 4} 5

^{Boshlang'ich holatda kuhlar soni 7 12 I} 49 ³

yo Qisqaroq boMishi uchun jadvalda tokcha(k) o'rniga t(k) kabi zamiz.

Tashqi Ichki Shart Shart U HOLDA

^{sikl i 0 ‘tkazish Ek sikl j tekshirish} qiymati ^{o'tkazish Ek}

! ^7=KD-+ 1 2 7=Zt12=t(2)—> 2 Zt=7 Zt=12

3 12=Zt
₄ <sup>l2=Zt_ROST 4 9 = t (4) —> ₄

49 Zt=49</sup>

159

5 <sup>49=Zt YOLGON -

Yangi</sup> 0 ‘tkazish sikl k

₃ 1 = 1 ( 3 ) - »

t(4)=l

₂ 1 2 = t ( 2 ) - »

t(3)= 12

₁ 7 = t ( 1 ) -» t(2)=7

49=

Zt -> t(l)=49

Bu amallardan keyin tokchalarda kublar quyidagicha joy- lashadi:

Tokcha tartib raqami 1 ^{2 3 4 S}

Boshlang'ich holatda kublar soni 49 ^{7 12 1 3}

Davom etamiz:

Tashqi Ichki ^{Shart Shart} _H ^U_{DA Ek} sikl i ^{0 ‘tkazish Ek} sikl j ^{tekshirish qiymati OL}

o'tkazish

_{7= t( 1)—»} 12=t(3)—>

2 _Zt=7 2 3 ^7=ZtROST _Zt=l2 ³

4 !2=Zt ^YOLG'ON —

5 12=Zt <sup>YOLGON —

Yangi</sup> O'tkazish sikl k

₂ 7=t(2) ^

t(3)=l

12=Zt —> t(2)=!2

Shundan keyin tokchalarda kublar quyidagicha joy- lashadi:

Tokcha tartib raqami ^{1 2 3 4 5}

Boshlang‘ich holatda kublar soni 49 ^{12 7 1 3}

160








Keyingi qadam:

^{Tasfaqi Ichkj} Shart Shart _H ^U _{A Ek} ^{sikl i OMkarisfa Ek} sikl j tekshirish qiymati _o' ^OLD _h

tkazis

^{3 7=t(3)—>Zt~7 3 4} 7=Zt ^{1 YOLG'ON —} 3

⁵ 12=ZtYangi

_{sikl k} 0 ‘tkazish

2 —

7=Zt —>t(3)=7

Ma'Iumki, 2 dan 3 gacha teskari sanab boMmaydi. Demak, yangi ichki siklda birorta ham o'tkazish bajarilmaydi, boshqacha aytganda yangi ichki sikl ishlamaydi. Jadval o'zgarmadi,

Mana oxirgi qadam:

^{Tasfaqi Ichkj} Shart ^Shart U HOLDA

^{sikl i 0 ‘tkazish Ek sikl j tekshirish qiy-} o'tkazish ^Ek

mati

^{4 1=t(4)—>Zt=l 4 5} I=Ztt(4)=3 5

Yangi

^{sikl k} O'tkazish

⁴ l= t(4 H t(5 )= l

3=Zt —>t(4)=3

Mana endi kerakli tartib o'rnatildi:

Tokcfaa tartib raqami 1 2 3 4 ₅

Boshlang'ich holatda kublar sonj _{49 12} 7 _{3 1}

en Bek esa quyidagicha ish tutdi: Mokchadan N-tokchagacha al gako‘p ikub taxlangan tokchani topdi va 1-tokcha bilan t m shtird ; 2-tokchadan N-tokchagacha eng ko‘p kub taxlangan tokchani topdi va 2-tokcha bilan almashtirdi;t 3-tokchadan N- okchagacha eng ko‘p kub taxlangan tokchani opdi va 3-tokcha

bilan almashtirdi va shu kabi almashtirishlami (N-l)-tokcha-

gacha davom ettirdi, chunki almashtirishlar natijasida N-tok-

chada eng kam sondagi kublar turgan bo‘ladi. Bek o‘zi bilmagan holda oddiy tanlov deb ataluvchi usuldan foydalandi. Bunda u ichma-ich joylashgan sikl tashkil etdi. Tashqi va ichki sikl bir-

11 - Azamatov, A.R. ₁₆₁






biridan farqlanishi uchun tokcha tartib raqamida i va j harflardan foydalandi. Tokchaning o‘zi bilan o‘zini taqqoslamaslik uchun ichki siklni doimo bitta keyingi tokchadan boshladi, ya’ni tashqi sikldagi i-tokcha uchun ichki sikldagi sanoqni (i+l)-tokchadan boshlash to'g'ri bo'ladi:

1 DAN N-I GACHA BAJAR

o‘tkaz tokcha(i), Zt

i+1 DAN N GACHA BAJAR

AGAR Zt

o‘tkaz tokcha(i), Zt

TAMOM TAMOM

o‘tkaz tokcha(i), tokcha(Ek)

o‘tkaz Zt, tokcha(i) TAMOM

sik Joylashtirish usulidagi kabii oddiy tanlov usulida ham faqat

llarning o‘zi necha qadaml gini jadval yordamida hisoblab

ko‘ramiz:

8.5-jadval

Tashqi lcbki ^{Takrorlanisblar}

sikl i sikl j soni

1 da 2 dan N gacha l (N-I)=N-1 ta

2 da 3 dan N gacha l (N-2)=N-2 ta

3 da 4 dan N gacha 1 (N-3)=N-3ta

4 da 5 dan N gacha 1 (N-4)=N-4 ta

...

N-2 da ^{N -1 dan N gacha 1 (N-(N-2)) =1 2=2 ta}

N-l da N dan N gacha ^{1 (N -(N -1)) =1 1= 1 ta} Hammasi sikllardagi bo'lib 1+2+3+.. ,+(N-3)+(N-2)+(N-1)=N (N - qadamlar soni -l):2 ta

qar Ko‘rib turibsiz, oddiy tanlov usulida joylashtirish usuliga aganda qadamlar soni ikki marta kam ekan.

8.12-mashq

8.5-jadvaldagi qadamlar sonini hisoblashda yuqori chegara topildi. 8,3-jadvaldagi tokchalar uchun sikllaming qadamlari sonini hisoblang va xulosa yozing.

162





8.13-mashq

8.1-jadvaldagi tokchalar uchun algoritmni tekshiring.

Biz algoritmni 8.4-jadvaldagi tokchalar uchun tekshiramiz:

—

^Tash- O'tka- Ichki Shart Shart U HOLDA

^qi zish ^Ek sikl j ^tekshirish qiymati ^{o'tkazish Ek} sikl i

₁ 7=t(l)-> 7=ZtROST ^l2=t(2)->Zt=

Zt=7 ^{1 2} 12 ^{12 2}

l2=Zt3 _{= 1} YOLG ON — ²

12=ZtZt=

⁴ =49 ^ROST 49 ⁴

49=Zt

5 ₌₃ ^YOLG'ON — ⁴

7=t(l)

—»t(4)=7

49=Zt

—>t( 1)=7

las Bui amallardan keyin tokchalarda kublar quyidagicha joy- had :

Tokcha tartib raqami 1 2 3 4 5