Bo’lib tashla va xukmronlik qil

Laboratoriya mashg’uloti №11-12. “Bo’lib tashla va xukmronlik qil” tamoyilidagi algoritmlar sinfi. Rekurent munosabatlar

Ishdan maqsad: Talabalarda “Bo’lib tashla va hukmronlik qil” tamoyilidagi algoritmlarni asimptotik tahlil qilish bo’yicha ko’nikmalar hosil qilish.

Nazariy qism:

Dasturlashda, bo’lib tashla va hukmronlik qil — bu algoritmik paradigma bo’lib, bu paradigmaning asosiy g’oyasi algoritmik masalalarni bosh masalaga o’xshash kichik qismlarga bo’lib tashlab, ularni rekursiv hal qilishdan iborat. Bu paradigmada masala qismlarga bo’linganligi sababli, qism masalalar bosh masalaga qaraganda kichikroq bo’lishi va bu bo’linish to’xtashi uchun asos holat bo’lishi kerak. Barcha turdagi bo’lib tashla va hukmronlik qil algoritmlari 3 ta bosqichdan iborat bo’ladi:

1.