Дастурлашни ўҚитиш муаммолари: рекурсияни массивларга татбиқ Қилиш

Юқоридаги дастурнинг иккинчи сатрини мос равишда m=7 ва n=7 га ўзгартириб ишга туширилди ва қуйидаги маълумотлар киритилди

1 2 3 4

Bog'liq
dasturlashni oqitish muammolari rekursiyani massivlarga tatbiq qilish

Юқоридаги дастурнинг иккинчи сатрини мос равишда m=7 ва n=7 га ўзгартириб ишга туширилди ва қуйидаги маълумотлар киритилди:
1 0 1 1 0 1 0
1 0 0 1 0 1 1
1 1 0 1 1 0 1
1 0 0 0 1 1 0
1 0 1 0 1 0 1
1 1 1 0 1 1 1
0 1 1 0 1 1 0
i, j:= 4 4
Бу маълумотлар учун компьютер ушбу натижани берди:
1,2 <- 2,2 <- 2,3 <- 3,3 <- 4,3 <- 4,4 <-

Бир ўлчовли A[N] жадвал берилган бўлсин. Унинг элементларини ўсиш тартибида тартибланг.
Ғояси. Массивнинг ўртасидаги элементни танлаб олиб, уни В билан белгилаймиз. Сўнгра массив элементларини навбатма-навбат чапдан-ўнгга ва ўнгдан-чапга қараб чиқамиз. Чапдан-ўнгга қарашда В дан катта ёки тенг бўлган А[i] ни излаймиз ва унинг тартиб рақамини эслаб қоламиз. Ўнгдан-чапга қараб чиқишда эса В дан кичик ёки тенг бўлган A[i] аниқлаб, унинг ҳам тартиб рақамини эслаб қоламиз. Топилган элементларнинг ўринларини алмаштирамиз.

Ушбу жараён i ва j индекслар устма*уст тушиб қолмагунча давом эттирилади. Шу билан 1-босқич тугайди. Бунда массив В га нисбатан икки қисмга ажраб, биринчисида В дан кичик ёки тенг элементлар, иккинчисида эса В дан катта ёки тенг элементлар жойлашган бўлади, бошқача айтганда массивнинг элементлари В га нисбатан тартибланади. .
Кейинги босқичда аввалги босқич массивнинг ўнг ва чап қисмлари учун амалга оширилади ва оқибатда массив нисбатан тартибланган тўртта қисмга ажралади. Кўрсатилган бу жараён то тартибланаётган қисмнинг узунлиги 1 га тенг қолмагунча давом эттирилади.
Ҳар бир босқичда массивнинг турли интекслар диапазони учун бир ҳил амалларнинг бажарилиши жараённи рекурсив ифодалашга имкон беради.

Download 77.1 Kb.

Do'stlaringiz bilan baham:

1 2 3 4