Algoritmlash

B o s h la n g 'ic h h o la td a k u b la r soni 49 12 1 ⁷ 3

Davom etamiz:

Tashqi Ichki Sbart Shart _HO^U _{A Ek} sikl i ^{0 ‘tkazish Ek} sikl j ^{tekshirish qiymati} _o'tk^LD _h

azis

₂ I2=t(2)-

_->Zt=l2 2 3 l2=ZtYOLG'ON — ²

4 ^{l2=ZtYOLG'ON — 2}

5 ^{l2=ZtYOLGON — 2}

12=t(2)-

—>t(2)= 12

12=Zt

—>t(2)= 12

163

Hech narsa o‘zgarmadi, davom etamiz:

^Tashqi _{0 ‘tkazish Ek} Ichki Shart Shart UHOLDA Ek ^{sikl i} sikl j ^{tekshirish qiymati} o‘tkazish

l=t(3)-» l=Zt

3 _{Zt= 1} 3 4 ₌₇ ROST 7=t(4)->Zt=7 4

₅ 7=Zt— ₄

=3 ‘ON

l=t(3)-» t(4)=1

7=Zt

—>t(3)=7

joy Endidbu amallardan keyin tokchalarda kublar quyidagicha lasha i:

^{Tokcba tartib raqami} 1 ² 3 4 5

B o s h la n g 'ic h h o la td a k u b la r soni 4 9 12 7 1 3

Va nihoyat oxirgi jarayon:

Tashqi ^{Ichki Shart} Shart U HOLDA

^{sikl i O'tka/ish Ek sikl j} tekshirish qiymati o‘tkazish <sup>Ek

1—1(4)—» l=ZtJ

4 _Zt=! 4 5 ₌₃ ROST _NII 5</sup>

!

1“ t(4)—>

t(5)=l

3=Zt-> t(4)=3

Va nihoyat kerakli tartib o‘rnatildi:

Tokcha tartib raqami 1 2 3 4 ₅

B o s lila n g 'ic h h o la td a k u b la r soni 4 9 12 7 3 1

Charchab ketdingiz-a! Lekin, Bek ham Siz bilan birga ishiayotganini unutmang. Cho‘chimang, kichkinagina bola o‘zlashtirayotgan usullar sizga ham bo‘ysunadi.

To'liqlik uchun yana bir usulni ko‘rib chiqamiz. IJni oddiy almashtirish yoki «pufakcha» usuii deb atashadi. Boshqa har qanday saralash usullart biz ko‘rib chiqayotgan uchala usulning hosilasi boiar ekan.

164









od 8.14-masaladagi kamayish tartibida saralash talab qilinganda diy almashtirish usuli quyidagicha:

qos1- adi, takrorlanishda: I-tokcha va 2-tokchadagi kublar soni taq-

o‘t lan ladi agar I-tokchadagi kublar soni kam bo‘lsa 2-tokchaga

to kazi ag , aksl holda i hech narsa qilinmaydi; 2-tokcha va 3-

s kchad i kub ar sonctaqqoslanadi, agar 2-tokchadagi kublar

oni kam bo‘lsa 3-tok haga o‘tkaziladi, aks holda hech narsa

qilinmaydi va hokazo, (/V- l)-tokcha va jV-tokchadagi kublar soni taqqoslanadi, agar (N- 1)-tokchadagi kublar soni kam bo‘lsa A^-tokchaga o‘tkaziladi, aks holda hech narsa qilinmaydi. Natijada kublari soni eng kam bo‘lgan tokcha N-tokchaga

o‘tkazilgan bo‘ladi.

qos2- adi,takrorlanishda: 1-tokcha va 2-tokchadagi kublar soni taq-

o't lanladi,agar 1-tokchadagi kublar soni kamibo'lsa 2-tokchaga

to kazi agi aksl holda hech narsa qilinmayd ; 2-tokcha va 3-

kchad kub ar soni taqqoslanadi, agar 2-tokchadagi kublar

soni kam bo'lsa 3-tokchaga o‘tkaziladi, aks holda hech narsa qilinmaydi va hokazo, ( Af-2)-tokcha va (N- l)-tokchadagi kublar soni taqqoslanadi, agar (A^j-tokchadagi kublar soni kam bo'lsa (N- !)-tokchaga o‘tkaziladi, aks holda hech narsa qilinmaydi. Demak, oxirgi A'-tokcha endi qaralmaydi. Natijada AMokchadan oldingi tokchalardan kublari soni eng kam bo‘!gan tokcha (N- l)-tokchaga o‘tkazilgan bo'ladi.

taq 3-slan takrorIanishda: c l-tokcha vaa 2-tokchadagi kublar soni

tokqo ga adi, agar , l-tok hadagic kubl r soni kam ; bo‘lsa 2-

va cha k o‘tkaziladi aks holdathe h narsa qilinmaydio 2-tokcha

ku 3-to chadagi kublar soni c aqqoslanadi,aagar 2-t kchadagi

n blar soni kam bo‘Isa, 3-tok haga o‘tkazil di, aks holda hech

karsa qilinmaydi va hokazo, (A/-3)-tokcha va ( Af-2)-tokchadagi

bublarsoni taqqoslanadi, agar (A^-3)-tokchadagi kublarsoni kam

qo‘lsaa (A/-2)-tokchaga io‘tkaziladi,e aks qholda hech anarsa

ilinm ydi. Demak, oxirg 2 ta tokcha ndi aralmaydi. N tijada

(N- l)-tokchadan oldingi tokchalardan kublari soni eng kam bo‘lgan tokcha (A^j-tokchaga o‘tkaziladi.

jad Shu tariqaq davom ettirilsa, ( N-1 )-takrorlanishda kerakli

valni hosil ilamiz.

harMasalada kamayish tartibida saralash so'ralgani r uchun

rayaqadamda tokchalardan kam sonlisini o‘ngga su ib bo-

pmiz.

Oddiy almashtirish usulining algoritmi quyidagicha:

165



TAKRORLANSIN N-1 MARTA

1 DAN N-i GACHA BAJAR

AGAR tokcha(j) U HOLDA

o‘tkaz tokcha(j+I), Zt o‘tkaz tokcha(j), tokcha(j+l)

_TAMo'tkaz Zt, tokcha(j)

OM

TAMOM TAMOM

Algoritmdan ko'rinadiki, tashqi sikl faqat ko'riladigan tokchalar sonini kamaytirish uchun xizmat qilmoqda.

o‘z Har doimgidek, «pufakcha» usulidaaham faqat sikllarning

i necha qadamligini jadval yordamid hisoblab ko'ramiz:

8.6-jadvaI

Tashqi Ichki Takrorlanishlar sikl i ^{sikl j soni}

1 da 1 dan N-l gacha |-(N -n=N -l ta

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

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

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

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

N-l da 1 dan 1 gacha 1*(N-(N-1)) =1 1= 1 ta

Hammasi sikllardagi bo'lib 1+2+3+.. ,+(N-3)+(N-2)+(N-l)= qadamlar soni N-(N-l):2 ta

8.14-mashq

8.1-, 8.4-jadvallardagi tokchalar uchun algoritmni jadval yordamida tekshiring.

7-sharh

Tokchalardagi kuhlar saralanganidan keyin engko ‘p kubliyoki eng kam kubli tokchani topish masalasijuda ham oson ishga aylanganini ko ‘rish mumkin. Haqiqatan, hu masalalaming yechimlari saralangan tokchalardagi kubli tokchalardan yoki o ‘ng tomondagi oxirgi tokchasi yoki chap tomondagi oxirgi tokchasi bo 'ladi.

166

«p Uchala usulning sikldagi qadamlar sonini taqqoslab,

ufakcha» usulining boshqa usullarga nisbatan samaradorligi

kam emasligini, murakkabligi esa eng kam ekanligini ko‘rish mumkin.

baja Ko'rilgan uchala usulning samaradorligini aniqlash uchun

ko riladigan amallar sonining yuqori chegarasini hisoblaymiz -

'paytirish amali):

1) Joylashtirish usulida:

2) Amallar soni)= (N -1)+2*((N-1)+(N-2)+...+1)+((N-l)+(N-

+... + l)+ (N -l =

=2*(N-l)+3*((N-l)+(N-2)+...+ l)=2*(N-l)+3*N*(N-l):2=

=(4*(N-1)+3*N*(N-I)):2=(4+3*N)*(N-1):2 ta

2) Oddiy tanlov usulida:

Amallar soni =(N-l)+2*((N-l)+(N-2)+...+ l)+2*(N-l) =

(6 = )3*(N-1) + 2* N*(N -I):2= (6*(N -1) + N*(N-1)):2 =

+N *(N-l):2 ta

3) Oddiy almashtirish usulida:

2* Amallar soni =4*((N-l) + (N-2) + ...+ l)=4*N*(N-l):2 =

N*(N-I)