Баылау сратары
Жаттыулар
- NxM лшемді матрицаны р атарындаы минимум элементтерді е лкенін жне р баанындаы максимум элементтерді е кішісін табу керек.
- 7.2-суретте крсетілгендей етіп квадрат матрицаларды толтырыдар:
Сурет 7.2 – Квадрат матрицаларды толтыруа тапсырмалар
Кбік» дісімен срыптау
Бл таырыпта біртипті массивтерді типтік алгоритмдерін деумен танысуды жаластырамыз типтік алгоритмдердегі массив элементтерін срыптауды олимпиадалы тапсырмаларын арастырамыз.
Жмыс масаты: танысан типтік алгоритмдері олдану арылы классикалы есептерді шыару.
Срыптауды берілген массив элементтерін су реті бойынша срыптау арылы арастырамыз. Мысалы, 5, 8, 4, 9, 3 массивін срыптайы:
Сурет 4.1- «Кбікті» срыптау
| Паскальда программаны орындау: | C/C++-те программаны орындау: |
| for j:=n downto 2 do for i:=1 to j-1 do if a[i]>a[i+1] then begin x:=a[i]; a[i]:= a[i+1]; a[i+1]:=x; end; | for (j=n; j>=2; j--) for (i=1; i<=j-1; i++) if (a[i]>a[i+1]) { x=a[i]; a[i]=a[i+1]; a[i+1]=x; } |
Срыптау дістерін олдануа мысалдар
Мысал. Кез-келген сандар атары берілген. Оларды арасына "<" жне ">" символдарын ою арылы ретімен орналастыру керек («ара тріздес» тізбек).
Есепті шешу идеясы:Алдымен сандар атарын срыптап алып, сосын бірінші элементтен бастап рбір жпты орнын ауыстырамыз.
var a: array [1..100] of integer; i,j,n,x:integer;begin writeln ('элементтер саны: '); readln (n); for i:= 1 to n do begin writeln ('a[',i,']='); readln (a[i]); end; {=====срыптау==========} for j:=n downto 2 do for i:=1 to j-1 do if a[i]>a[i+1] then begin x:=a[i]; a[i]:= a[i+1]; a[i+1]:=x; end; for i:=1 to 5 do write(a[i]:3); writeln; j:=1; {====рбір жпты орындарын ауыстырамыз====} for i:=1 to (n div 2) do {тек циклды айталану санын анытайды} begin x:=a[j]; a[j]:= a[j+1]; a[j+1]:=x; j:=j+2; end; for i:=1 to n do write(a[i]:4);end.Тест:
| Берілгені: | 5, 2, 1, 8, 0, 67, 100 |
| Срыпталаны: | 0, 1, 2, 5, 8, 67, 100 |
| Нтижесі: | 0, 2, 1, 8, 5, 100, 67 |
2-мысал.Сандар тізбегінен атар келген сандарды ішкі тізбегін анытау керек.
Есепті шешу идеясы:сандар атарын срыптаймыз. Массив элементтерін екі крші элементті салыстыра отырып дейміз: егер оларды айырмашылыы бірге те болмаса, онда экрана жаа тізбекті шыарып бастаймыз.
var a: array [1..100] of integer; i,j,n,x: integer;begin writeln ('элементтер саны:'); readln (n); for i:= 1 to n do begin write('a[',i,']=');readln (a[i]); end; {===== массивті срыптау=============} for j:=n downto 2 do for i:=1 to j-1 do if a[i]>a[i+1] then begin x:=a[i]; a[i:= a[i+1]; a[i+1]:=x; end; {===атар орналасан тізбектерді шыару===} write (a[1]); for i:= 2 to n do begin if (a[i]-a[i-1]) <> 1 then writeln; write (a[i]:3); end;end.Тест:
| Берілгені : | N=10 2, 1, 5, 3, 7, 8, 6, 12, 9, 11 |
| Нтижесі: | 1, 2, 3 5, 6, 7, 8, 9 11, 12 |
3-мысал.Сандар тізбегіндегі атар келген сандарды е зын тізбегін тауып, оларды шыару керек.
Есепті шешу идеясы:Сандар атарын срыптаймыз. Екі крші элементті салыстыра отырып, массивті дейміз: егер оларды айырмасы 1-ге те болса, онда келесі сан осы тізбекке осылады. k шамасы арылы оны зындыын анытаймыз. Максимум элементті табуды типтік алгоритмін олданып, е зын тізбекті анытаймыз.
var a: array [1..10] of integer; max,k,number,i,j,n,x: integer;begin writeln ('элементтер саны:'); readln (n); for i:= 1 to n do begin write('a[',i,']='); readln (a[i]); end; {=====массивті срыптау================} for j:=n downto 2 do for i:=1 to j-1 do if a[i]>a[i+1] then begin x:=a[i]; a[i]:= a[i+1]; a[i+1]:=x; end; {===е зын тізбекті анытау===} max:=0; k:=1; for i:=1 to n-1 do begin if a[i+1]-a[i]=1 then k:=k+1 else k:=1; if k>max then begin max:=k; number:=i+1; end; end; writeln('Е зын тізбек элементтеріні саны=', max); writeln('Е зын тізбек:'); for i:=(number-max+1) to number do write(a[i]:3);end.Тест:
| Берілгені : | N=10 2, 1, 5, 3, 7, 8, 6, 12, 9, 11 |
| Нтижесі: | Max=5 5, 6, 7, 8,9 |
4-мысал:Берілген сйлемдегі сздерді орнын ондаы ріп саныны су ретімен ауыстыру керек.
Есепті шешу идеясы:Сйлемдегі сздерді бліп алуды типтік алгоритімін олданып, рбір сзді массив элементіне орналастырып жазамыз. Сонан со, сздер массивін ондаы сзді зындыы бойынша срыптаймыз.
var b:array[1..10] of string; a,a1,a2,x: string; n,i,j,k: integer;begin writeln ('Сйлемді ендір:'); readln (a); n:=length (a); k:=0; for i:=1 to n do if copy(a,i,1)=' ' then k:=k+1; k:=k+1; j:=1; for i:=1 to n do if copy(a,i,1)=' ' then j:=j+1 else b[j]:=b[j]+copy(a,i,1); {===== массивті срыптау ==============} for j:=k downto 2 do for i:=1 to j-1 do if length (b[i])>length (b[i+1]) then begin x:=b[i]; b[i]:= b[i+1]; b[i+1]:=x; end; { ==============================} for i:=1 to k do writeln (b[i]);end.Тест:
| Берілгені: | Мені сйікті пнім - информатика |
| Нтижесі: | - Мені пнім сйікті информатика |
Срыптау есептеріні ішінде массив элементтеріні бір блігін су ретімен жне екінші блігін кему ретімен срыптау ажеттілігі жиі кездеседі.
Мысал. Массив бліктерін срыптау керек. О жне теріс элементтері бар А массиві берілсін делік (4.2-сурет). Массивті о элементтері су реті бойынша срыпталып, ал теріс элементтерін з орнында алдыру керек.
Сурет 4.2
Есепті шешу идеясы:
· осымша В массивін енгіземіз жне оан А массивіндегі о элементтерді жазамыз (4.3-сурет):
| В |
Сурет 4.3
Содан со массивті деуді типтік алгоритімін олдану арылы, A массивіні элементтеріні индексі ретінде В массивіні элементтерін олданамыз. Бл есепті шыарылуын блек типтік алгоритм ретінде арастыруа болады.
const m=10;var a, b: array [1..m] of integer; i, j, n, x, k: integer;begin writeln('Элементтер саны:'); readln(n); for i:=1 to n do begin write('a[',i,']='); readln(a[i]); end; j:=1; k:=0; for i:=1 to n do if a[i]>0 then begin b[j]:=i; j:=j+1; k:=k+1; end; for j:=k downto 2 do for i:=1 to j-1 do if a[b[i]]>a[b[i+1]] then begin x:=a[b[i]]; a[b[i]]:=a[b[i+1]]; a[b[i+1]]:=x; end; for i:=1 to n do write (a[i],' ');end.Тест:
| Берілгені: | N=9 -3, 5, -1, 3, 6, -8, 2, -1, -3 |
| Нтижесі: | -3, 2, -1, 3, 5, -8, 6, -1, -3 |
Орытынды
· Біртекті массивтерді срыптауды «Кбікті» дісі екі крші элементті салыстыруа негізделген: егер лкен элемен кішісіні сол жаында болса, онда элементтерді орындары ауыстырылады. Массив элементіні е лкені массивті е соына орналасады. рі арай алгоритм бірінші элементтен соы элементке дейін айталанады.
· Массивті бліктерін срыптауда (Срыптауды шарттары бойынша массив бліктерін тадаймыз) срыпталатын индекстер ретінде А массивіндегі элементтерді жне осымша В массивіндегі элементтерді аламыз ( онда тадалатын массивті бастапы элементтері саталады).
Сратар.
· «Кбікті» срыптауды бірінші адамында не болады?
· «Кбікті» срыптау дісіндегі ішкі циклды санауын сырты циклды санауына туелділігін анытадар?
Тапсырмалар
· Символды жол сандардан жне латын ріптерінен трады. Оларды райсысы з орнында алатындай етіп сандарды кему реті бойынша, ріптерді алфавиттік тртіп бойынша реттеу керек.
· Натурал сандардан тратын массив берілген, ондаы жай сандарды су ретімен, ал рама сандарды кему ретімен срыптау керек.
· Сйлемдегі дауысты дыбыстарды алфавит тртіппен су реті бойынша, ал дауыссыз дыбыстарды кему реті бойынша орналастыру керек.
· Сйлемдегі сздерді орнын алфавиттік тртіппен (рбір сздегі бірінші ріп бойынша) орналастыру ажет.