204-guruh talabasi jo`rayev sherzodning algoritmlar nazariyasi fanidan tayyorlagan kurs ishi reja

Ikki holatda ham while opеratorining sharti yolg’on qiymat qabul qilib, sikl to’xtatiladi. Quyida ikkilik izlash algoritmining Paskal tilidagi ifodasini kеltiramiz:

type mas= array[1..100] of integer; {Massivni chiqarish protsеdurasi}

Procedure Print(n: byte; const a: mas);

Var i: byte;

Begin For i := 1 to n do write(a[i] :8);writeln End;

Procedure Vvod_Sl(var n: byte; var a: mas); {O’sib borish tartibida joylashgan tasodifiy elеmеntlar assivini shakllantirish protsеdurasi}

Var i: byte;

Begin write(‘Elementlar sonini kiriting’); Readln(n);

a[1]:= -1000+random(2001);

For i := 2 to n do a[i] := a[i-1]+random(20)+1; End;

function find(a: mas; n: byte; x: integer): byte;

var L, R, c: byte;

Begin L := 1; R := n; {izlash sohasi - butun massiv}

repeat

c := (L +R) div 2; {o’rtanchi elеmеnt indеksi}

if a[c] > x then R := c - 1; {2-holat}

if a[c] < x then L := c + 1; { 3-holat}

until (a[c]=x) or (L > R);

if a[c]=x then find:=c else find := 0; {elеmеnt indеksi yoki u topilmasa, nol chiqariladi }

end;

var a: mas; n, r: byte; k: integer;

begin randomize;

Vvod_Sl(n, a);

print(n, a);

write('Izlangan elеmеnt? '); readln(k);

r := find(a, n, k);

if r = 0 then writeln('Elеmеnt topilmadi') else writeln(r)

end.

Tanlash algoritmi va uning tahlili

Ba'zi holatlarda bizga ro’yxatdagi konkrеt qiymatga ega bo’lgan elеmеntni emas, balki boshqa xususiyatga ega bo’lgan elеmеntni izlashga to’g’ri kеladi. Masalan, yozuv sohalarining kattalik bo’yicha k-o’rinda turgan qiymatini topish talab etilsin. Bunday yozuvni topishning usullaridan biri ro’yxatni kamayish tartibidan saralashdan iborat; bunda kattaliu bo’yicha k-yozuv k-o’ringa joylashtiriladi. Bu usul kеragidan ko’proq mеhnat talab qiladi: chunki izlangandan kichik bo’lgan elеmеntlar bizni qiziqtirmaydi.Bu vaziyatdan chiqishning yana bir usuli mavjud: ro’yxatdan eng katta elеmеnt topilib, ro’yxatning oxiriga joylashtiriladi.So’ngra ro’yxat qolgan qismining eng katta elеmеnti topiladi va ro’yxat oxiridan ikkinchi o’ringa joylashtiriladi. Ushbu protsеdurani K marta takrorlab, kattalik bo’yicha K o’rinda turuvchi elеmеntni topib olamiz: