Бақылау сұрақтары. Бір өлшемді массивтерді өңдеудің типтік алгоритмдері

Бір өлшемді массивтерді өңдеудің типтік алгоритмдері. Іздеу алгоритмдері. Іздеу алгоритмдері

Бұл жұмыста массивтерді өңдеудің келесі алгоритмдері қарастырылатын болады:

• Массивті толтыру (ендіру), массив элементтерін экранға шығару;
• Элементтердің қосындысы, көбейтіндесі;
• Шарт бойынша таңдау;
• Максимум (минимум) элемент;
• Элементтерді кірістіру, жою;
• Инверттеу (массив элементтерін кері тәртіппен орналастыру)

Келесі кестеде бір өлшемді массивтердің типтік алгоритмдерінің қолданылуы берілген: 2.1-кесте

Типтік алгоритм	Бейсик тілінде	Паскаль тілінде	Си тілінде
Массивті толтыру (ендіру)	input ndim a(n)for i=1 to ninput a(i)next i	const n=10;Var a: array [1..n] of integer;beginfor i:=1 to n do readln (a[i]);…	# define N 10void main(){ int a[N];for(i=0;i<=N-1;i++) cin>>a[i];…
Массивті бір қатарға шығару	…for i=1 to nprint a(i); " ";next i	…for i:=1 to n do write (a[i]);…	…for(i=0;i<=N-1;i++) cout<<a[i];…
Элементтердің қосындысы мен көбейтіндісі	…p=1for i=1 to ns=s+a(i)p=p*a(i)next i	…s:=0; p:=1;for i:=1 to n do begins:=s+a[i]); p:=p*a[i]);end; …	…s=0; p=1;for(i=0;i<=N-1;i++) {s+=a[i]; p*=a[i];}…
Шарт бойынша таңдау	…p=1for i=1 to nif <шарт> then k=k+1:s=s+a(i):p=p*a(i)next i	…k:=0; s:=0; p:=1;for i:=1 to n do if <шарт> then begink:=k+1; s:=s+a[i]; p:=p*a[i];end;…	…k=0; s=0; p=1;for(i=0;i<=N-1;i++) if (<ШАРТ>) { k++; s+=a[i]; p*=a[i];}…
Максимум (минимум) элементті табу	…max=a(1): min=a(1)for i=2 to nif a(i)>max then max=a(i)if a(i)<min then min=a(i)next i	…max:=a[1]; min:=a[1];for i:=1 to n do beginif a[i] > max then max:=a[i];if a[i] < min then min:=a[i];end;	…max=a[0]; min=a[0];for(i=0;i<=N-1;i++) {if (a[i]>max) max=a[i];if (a[i]<min) min=a[i];}…
x-ті k-шы позицияға кірістіру	dim a(n + 1)…for i=n to k step -1a(i+1)=a(i)nexta(k)=x	Var a: array [1..n+1] of……for i:=n downto k do a[i+1]:=a[i];a[k]:=x;…	{ …int a[N+1];…for(i=N; i>=k; i--) a[i+1]=a[i];a[k]=x;…
k-шы элементті жою	... for i=k to n-1a(i)=a(i+1) next	…for i:=k to (n-1) do a[i]:= a[i+1];…	…for(i=k;i<=n-1;i++) a[i]=a[i+1];…
Элементтерді инверттеу	. . . for i=1 to n/2swap a(i), a(n-i+1) next	…for i:=1 to (n div 2) do beginх:=a[i];a[i]:= a[n-i+1];a[n-i+1] :=х;end…	…for(i=1;i<=n/2;i++) { х=a[i];a[i]= a[n-i+1];a[n-i+1]=х;}…

Түсіндірме:

• Шарт бойынша таңдау. <ШАРТ> ретінде көптеген логикалық өрнектерді орналастыруға болады. Мысалы, массив элементінің жұптылығы, қандай да бір санға еселілігі, оң (теріс) таңбалылығы, массивтің тақ позициясындағы элементтері, т.с.с.

· Максимум (минимум) элемент. Көбінесе, максимум элементпен бірге оның реттік нөмірі (индексі) де сұралады:

if a[i]>max then beginmax:=a[i]; imax:=i;end;

• X-ті k-шы позицияға кірістіру. Элементтердің орны соңынан бастап ауыстырылады: ең соңғы элемент бос орынға сырғытылады, ал оның орнына соңғы элементтің алдыңғысы көшіріледі және т.с.с. Цикл k-шы позицияға дейін қайталанады және ол біткен соң k-шы орынға х саны қойылады.
• Элементтерді инверттеу. Цикл n div 2 рет орындалады, өйткені әр қадамда екі элементтің орындары ауыстырылады.

Мысалдар.

1-есеп: Жазықтықта N тіктөртбұрыш кескінделген (2.1-сурет). Олардың әрқайсысының сол жақтағы төменгі және оң жақтағы жоғарғы төбелерінің координаттары берілген. Тіктөртбұрыштардың ортақ (қиылысатын) бөлігі бар ма? Бар болса оның ауданы неге тең?

Сурет 2.1

Шешу:

Егер:

· тіктөртбұрыштардың сол жақтағы төменгі төбелерінің Х осі бойынша максимум координатасы оң жақтағы жоғарғы төбелерінің минимум координатасынан кем болса ЖӘНЕ

• сол жақтағы төменгі төбелерінің У осі бойынша максимум координатасы оң жақтағы жоғарғы төбелерінің минимум координатасынан кем болса, онда
• тіктөртбұрыштардың ортақ (қиылысатын) бөлігі бар.

Есепті шешу кезінде массивтің максимум және минимум элементтерін табу алгоритмін пайдаланамыз. Ал, фигуралардың ортақ бөлігінің ауданын есептеу үшін келесі айырымдардың көбейтіндісін табу керек:

• тіктөртбұрыштардың сол жақтағы төменгі төбелерінің Х осі бойынша максимум координатасынан оң жақтағы жоғарғы төбелерінің минимум координатасының айырмасы ЖӘНЕ
• тіктөртбұрыштардың сол жақтағы төменгі төбелерінің У осі бойынша максимум координатасынан оң жақтағы жоғарғы төбелерінің минимум координатасының айырмасы.

Бейсиктегі программасы:

input "тіктөртбұрыштар саны:"; ndim x1(n), x2(n),y1(n), y2(n)for i=1 to n input x1(i), x2(i), y1(i), y2(i)nextxmax=x1(1)xmin=x2(1)ymax=y1(1)ymin=y2(2)for i=1 to n if x1(i) > xmax then xmax=x1(i) if x2(i) < xmin then xmin=x2(i) if y1(i) > ymax then ymax=y1(i) if y2(i) < ymin then ymin=y2(i)nextif xmax<xmin and ymax<ymin then print "ортақ бөлігі бар оның ауданы: ", abs(xmax-xmin)*abs(ymax-ymin) else print " ортақ бөлігі жоқ"

Паскальда:

var x1, x2, y1, y2: array [1..10] of integer; n, i, xmax, xmin, ymax, ymin: integer;begin writeln (' тіктөртбұрыштар саны:'); readln (n); for i:=1 to n do readln (x1[i], y1[i], x2[i], y2[i]); xmax:=x1[1]; xmin:=x2[1]; ymax:=y1[1]; ymin:=y2[1]; for i:=1 to n do begin if x1[i] > xmax then xmax:=x1[i]; if x2[i] < xmin then xmin:=x2[i]; if y1[i] > ymax then ymax:=y1[i]; if y2[i] < ymin then ymin:=y2[i]; end; if (xmax<xmin) and (ymax<ymin) then writeln ('ортақ бөлігі бар,оның ауданы: ', abs(xmax-xmin)*abs(ymax-ymin)) else writeln (' ортақ бөлігі жоқ');end.

Тест:

Берілгені:	1,1,9,5 2,3,5,6 4,2,7,4	2,2,5,4 4,3,7,6 6,1,11,2 6,4,12,8
Нәтиже:	ортақ бөлігі бар	ортақ бөлігі жоқ

2-есеп: Латын квадраты қатарлары мен бағандарында бірдей элементтері жоқ массивті айтады. Экранға өлшемі N´N болатын латын квадратын шығару керек.

Шешуі: Өлшемі N´N квадрат массивтің 1-ші қатарын 1,2...,N сандарымен толтырамыз. Екінші қатарды бірінші қатардағы элементтерді 1 орынға циклді сырғыту арқылы толтырамыз және т.с.с. (2.2-кесте). Циклдік сырғытуды КІРІСТІРУ-ЖОЮ типтік алгоритмін пайдаланып іске асыруға болады (циклдік сырғытудың бағытына қарай).

2.2-кесте. Латын квадратын массив элементтерін циклдік сырғыту арқылы толтыру

Бейсикте:

input "Массив өлшемі="; ndim a(n,n)for j=1 to n a(1,j)=jnextrem=====сырғыту=========for i=2 to n rem===алдыңғы қатарды келесісіне көшіру=== for j=1 to n a(i,j)=a(i-1,j) next x=a(i,n) for j=n to 2 step -1 a(i,j)=a(i,j-1) next a(i,1)=xnextrem====шығару==========for i=1 to n for j=1 to n print a(i,j); next printnext

Паскальда:

var a: array [1..10,1..10] of integer; n,i,j,x: integer;begin writeln ('Массив өлшемі='); readln (n); for j:=1 to n do a[1,j]:=j; {======сырғыту======} for i:=2 to n do begin {===алдыңғы қатарды келесісіне көшіру===}for j:=1 to n do a[i,j]:=a[i-1,j]; x:=a[i,n]; for j:=n downto 2 do a[i,j]:=a[i,j-1]; a[i,1]:=x; end; {======шығару======} for i:=1 to n do begin for j:=1 to n do write(a[i,j]); writeln; end;end. Солға сырғыту үшін программадағы белгіленген кодты келесі түрде жазу керек: x:=a[i,1]; for j:=1 to n-1 do a[i,j]:=a[i,j+1]; a[i,n]:=x;

Кілттік сөздер

• Бір өлшемді массив – жадта бірінен соң бірі орналасатын бір типті элементтердің реттелген жиынтығы; элементтердің әрқайсысына индекстер арқылы қол жеткізіледі.
• Латын квадраты - әрбір қатары мен бағанында ұқсас элементтері жоқ екі өлшемді массив.
• Массив элементтерін циклді сырғыту – массивтің барлық элементтерін оңға (солға) сырғыту. Массивтің соңғы элементі бірінші позицияға ауысады (массивтің бірінші элементі соңғы позицияға ауысады).

Тапсырмалар

• 10 элементтен тұратын бір өлшемді массивтің жұп элементтерінің көбейтіндісін, теріс элементтерінің қосындысын, нөлдік элементтерінің санын анықтау керек.
• m(10) бүтін массивінің максимум элементін жойып, минимум элементтен соң 0 санын кірістіру керек.

Бақылау сұрақтары

• Массив элементтерін инверттеу барысында элементтер индексінің циклдік параметрге тәуелділігі қалай анықталады?
• Массив элементтерін инверттеу алгоритмінде цикл n-ге дейін айналса не болады?
• Кірістіру алгоритмінде элементтерді і-ші позициядан (і+1)-ші позицияға көшіруді массив соңынан емес, кірістірілетін элементтің орнынан бастаса не болады?