linkedin facebook linkedin facebook nod32

Olimpiada misollarini yechish usullari III-bosqich

Muallif: Mengliyev Sh.

Qo`shilgan sana: 2015-04-26

Olimpiada misollarini yechish usullari III – bosqich

191-misol. Foydalanuvchi tomonidan ko’rsatilgan massiv elementini qo’shni elementlari bilan ketma-ket o’rin almashtirish orqali boshiga, ya’ni birinchi o’ringa o’tkazing.

Bu jarayonni aniq misolda ko’rib chiqaylik.
Bizga massiv berilgan bo’lsin, unda foydalanuvchi buyrug’iga ko’ra beshinchi elementni qo’shni elementlar bilan ketma-ket o’rin almashtirish yordamida birinchi o’ringa ko’chirish kerak.
3      - 12      45      16      -23        4        -5        76       -34
a[1]   a[2]     a[3]     a[4]    a[5]      a[6]      a[7]    a[8]      a[9]
Bu jarayon quyidagi ko’rinishda bo’ladi: 4-chi va 5-chi elementlarning o’rni almashtiriladi, quyidagi massiv hosil bo’ladi:
3       -12       45       -23       16       4       -5       76      -34
a[1]    a[2]     a[3]      a[4]      a[5]    a[6]     a[7]     a[8]     a[9];
3-chi va 4-chi elementlarning o’rni almashtiriladi:
3       -12      -23        45       16       4        -5        76      -34
a[1]    a[2]     a[3]       a[4]     a[5]    a[6]     a[7]      a[8]     a[9];
2-chi va 3-chi elementlarning o’rni almashtiriladi:
3      -23      -12        45        16       4        -5        76      -34
a[1]   a[2]     a[3]       a[4]      a[5]    a[6]     a[7]      a[8]     a[9];
va nihoyat, 1-chi va 2-chi elementlarning o’rni almashtiriladi:
-23     3      -12         45        16       4        -5        76      -34
a[1]   a[2]    a[3]       a[4]       a[5]     a[6]    a[7]      a[8]     a[9];
Bundan, massivning barcha elementlari bitta element o’ngga “siljigan” ligi kelib chiqdi. Bunday o’rin almashishni for sikli yordamida amalga oshirish mumkin. Elementni massiv boshiga (birinchi o’ringa) ko’chirish uchun prosedura hosil qilamiz.     
  Procedure transp_begin(n, k : integer;  var a : t);
var
           i, p : integer;
begin
for i := k downto 2 do
begin
p := a[i-1]; a[i-1] := a[i]; a[i] := p
end
end;

Bu yerda k ko’chirilayotgan element nomeri. Siklda ketma-ket oldingi va keyingi elementlarning o’rni almashadi, shu usulda massiv elementlari  asta-sekin bittadan o’ngga siljiydi. 
Nima uchun sikl 1 gacha emas, 2 gacha davom etadi? O’rin almashtirilayotgan elementlar indekslariga e’tibor bering: a[i - 1] va a[i], i=2 da ular  a[1] va a[2] qiymat qabul qilishadi, ya’ni barcha elementlar, shu jumladan birinchisi ham o’rin almashtirish jarayonida qatnashadi.
Sikl 1 gacha davom etganda edi, u holda a[0] va a[1] nomerli elementlar hosil bo’lar edi. Lekin massivda  a[0] element yo’q va bu holda dasturda xato kuzatilar edi.

Dastur

Program L191;
uses Crt;
const
          n = 20;
type
         t = array[1..n] of integer;
var
         a    : t;
i, k : integer;
{----------------------------------------------------------------------------------------}
Procedure create(n : integer;  var a : t);
var
            i : integer;
begin
randomize;
writeln('Berilgan butun sonlar massivi');
for i := 1 to n do
begin
a[i] := random(201) - 100; write(a[i], ' ')
end;
writeln
end;
{----------------------------------------------------------------------------------------}
 Procedure transp_begin(n, k : integer;  var a : t);
var
            i, p : integer;
begin
for i := k downto 2 do
begin
p := a[i-1]; a[i-1] := a[i]; a[i] := p
end
end;
{---------------------------------------------------------------------------------------}
begin
create(n, a);
write('Ko’chirilayotgan element nomerini kiriting');
readln(k);
transp_begin(n, k, a);
writeln('Elementni birinchi o’ringa o’tkazgandan so’ng hosil bo’lgan massiv ');
for i := 1 to n do write(a[i], ' '); 
writeln
end.

192-misol. Bir o’lchovli massivda foydalanuvchi tomonidan kiritilgan sonning nomerini aniqlash va uni qo’shni elementlarning o’rinlari bilan ketma-ket almashtirib, massivning birinchi o’rniga ko’chirish kerak.
Bu masalani yechish uchun, tasodifiy sonlar generatori yordamida yaratilgan massivni chiqargandan so’ng, foydalanuvchidan, u qaysi elementni boshiga ko’chirish niyatida ekanligini so’rash kerak.
Berilgan massiv foydalanuvchi uning elementlarini ko’ra olishi va unda mavjud elementlarning birontasining o’rnini almashtirishi uchun ekranga chiqarilishi kerak. Elementni “ko’r-ko’rona” tanlash oqibatida, massivda bunday element bo’lmay qolish holati ham paydo bo’lishi mumkin, bunda esa masala qiziqmas bo’lib qoladi.  
Demak, bu masalaning yangiligi - bu berilgan elementning nomerini qidirish.
Buni amalga oshirish ancha oson, buning uchun elementlar soni bo’yicha sikl ochish va massiv elementlarining har birini berilgan son bilan tekshirish kerak, agar tenglik bo’lib qolsa, u holda biron-bir o’zgaruvchining xotirasiga bu massiv elementining nomerini “kiritish” kerak. Biz quyidagi massivdagi element nomerini qidirish prosedurasiga kelib qolamiz:
Procedure search_number(d : integer; a : t;  var k : integer);
begin
k := 0;
repeat
k := k + 1
until a[k] = d
end;

Dasturning o’zini esa  uchta proseduradan: massivni yaratish - create; element nomerini qidirish - search_number va elementni massiv boshiga ko’chirish- transp_begin tuzish mumkin.

U quyidagi ko’rinishda bo’ladi:

Program L192;
uses Crt;
const
           n = 20;
type
           t = array[1..n] of integer;
var
          a         : t;
i, k, d : integer;
{----------------------------------------------------------------------------------------}
Procedure create(n : integer;  var a : t);
var
            i : integer;
begin
randomize;
writeln('Berilgan butun sonli massiv');
for i := 1 to n do
begin
a[i] := random(201) - 100; write(a[i], ' ')
end;
writeln
end;
{----------------------------------------------------------------------------------------}
Procedure search_number(d : integer; a : t;  var k : integer);
var
            i : integer;
begin
i := 0;
repeat
i := i + 1
until a[i] = d;
k := i
end;
{----------------------------------------------------------------------------------------}
Procedure transp_begin(n, k : integer;  var a : t);
var
            i, p : integer;
begin
for i := k downto 2 do
begin
p := a[i-1];
a[i-1] := a[i];
a[i] := p
end
end;
{----------------------------------------------------------------------------------------}
begin
create(n, a);
write('O’tkaziayotgan elementni kiriting'); readln(d);
search_number(d, a, k);
transp_begin(n, k, a);
writeln('Elementni boshiga o’tkazgandan so’ng hosil bo’lgan massiv’);
for i := 1 to n do write(a[i], ' ');
writeln
end.

193-misol. Dasturni shunday o’zgartiringki, u o’zining qiymati bilan berilgan elementni foydalanuvchi ko’rsatgan joyga o’tkazsin.
Tavsiyalar. Bu masalani tuzishda uchraydigan qiyinchiliklardan bittasi, ko’rsatilgan joy nomeri ko’chirilayotgan element egallagan joy nomeridan katta yoki kichkina bo’lishi mumkin.
Shu bilan bog’liq holda, siz elementni ko’chirish sikli qanday tuzilishi keraklgini o’ylab chiqishingiz kerak.
Program L193;
uses Crt;
const
n = 20;
type
t = array[1..n] of integer;
var
a : t;
i, k, d, m, s, p : integer;
{----------------------------------------------------------------------------------------}
Procedure create(n : integer;  var a : t);
var
i : integer;
begin
randomize;
writeln('Berilgan butun sonli massiv');
for i := 1 to n do
begin
a[i] := random(201) - 100;
write(a[i], ' ')
end;
writeln
end;
{----------------------------------------------------------------------------------------}
Procedure search_number(d : integer; a : t;  var k : integer);
begin
k := 0;
repeat
k := k+1
until a[k] = d
end;
{----------------------------------------------------------------------------------------}
Procedure transpose_number(n, k, m : integer;  var a : t);
var
s, p, i : integer;
begin
if m > k then s := 1 else s := -1;
i := k;
repeat
p := a[i+s];
a[i+s] := a[i];
a[i] := p; i := i+s
until i = m - s - 1;
writeln('Elementni ko’chirgandan so’ng hosil bo’lgan massiv’);
for i := 1 to n do write(a[i], ' ');
writeln
end;
{------------------------------------------------------------------------------------}
begin
create(n, a);
write('Ko’chirilayotgan elementni kiriting'); readln(d);
search_number(d, a, k);
write('Ko’ch. uchun nomerni ko’rsating'); readln(m);
transpose_number(n, k, m, a)
end.

194-misol. O’sish bo’yicha tartiblangan massivga berilgan sonni shunday joylashtiringki, massiv tartibi buzilmasin.

 Matematik tahlil va algoritm tuzish

10 ta sondan iborat bo’lgan, o’sish bo’yicha tartiblangan massiv berilgan bo’lsin:
 

 

 

12      23     34     45     56     58     78     89     90     98
1       2       3       4        5      6       7       8       9      10     11
Massivga joylashtirish kerak bo’lgan son 75 bo’lsin.
Bizga ma’lum bo’lgan tezkor qidiruv usuli yordamida, bu son massivning  6 –nomerdagi elementi, ya’ni 58 dan  keyin qo’yilishi kerakligini aniqlaymiz.
So’ngra 8 nomerdagi elementdan boshlab, barcha massiv elementlarini 1 element o’ngga ko’chirish kerak (o’rin almashtirish jarayonini biz oldin ham bajargan edik, lekin bu masalada elementning 11 nomeridagi qiymati saqlanib qolishi to’g’risida qayg’urish kerak emas, chunki uning o’zi yo’q, aniqrog’i u nolga teng, shuning uchun o’rin almashtirishni oddiy ko’chirish bilan almashtirish mumkin, ya’ni 11 nomerdagi elementga 10 nomerdagi element qiymatini, 10 ga esa 9 nikini va h.k berib qo’yish mumkin).
Undan keyin esa 7 nomerdagi element o’rniga berilgan sonni joylashtirish kerak.
Buning uchun esa massivni tariflash paytida, massiv 1 ta elementga uzun bo’lib qolishini hisobga olish, ya’ni massivni berilgan konstantaga nisbatan 1 taga katta deb ta’riflash kerakligi bizga ravshan.
r-chi elementdan boshlab elementlarni o’ngga ko’chirish uchun, quyidagi prosedurani tashkil etish yetarli:
(movement – harakat, end – yakun):

    Procedure movement_end(n, k : integer;  var a : t);
var
            i : integer;
begin
for i := n + 1 downto k + 1 do a[i] := a[i - 1]
end;

Uning ishlash jarayonini o’zingiz o’rganib chiqing.

Dastur

Program L194;
uses Crt;
const
           n = 20;
type
           t = array[1..n + 1] of integer;
var
           a        : t; 
i, p, b : integer;
{----------------------------------------------------------------------------------------}
Procedure quick_search(a : t; n, b : integer;  var p : integer);
var
           q, s : integer;
begin
p := 1;
q := n + 1;
while p < q do
begin
s := (p + q) div 2;
if a[s] < b then p := s + 1 else q := s
end
end;
{---------------------------------------------------------------------------------------}
Procedure movement_end(n, k : integer;  var a : t);
var
            i : integer;
begin
for i := n + 1 downto k + 1 do a[i] := a[i - 1]
end;
{---------------------------------------------------------------------------------------}
begin
write('O’sish bo’yicha tartiblangan a massiv');
writeln('elementlarni kiriting');
for i := 1 to n do
begin
write(i, 'chi elementni kiriting'); readln(a[i])
end;
writeln('Tartiblangan butun sonli massiv');
for i := 1 to n do write(a[i], ' '); writeln;
write('Kiritish kerak bo’lgan sonni kiriting'); readln(b);
quick_search(a, n, b, p);
movement_end(n + 1, p, a);
a[p] := b;
writeln('Sonni kiritgandan so’ng hosil bo’lgan yangi massiv’, b);
for i := 1 to n + 1 do write(a[i], ' ');
writeln
end.

Dasturda yana bitta detal paydo bo’ldi. “O’ng” chegara,  elementi nomerining boshlang’ich qiymati q ga a massiv elementlari soniga qaraganda 1 taga kattaroq n+1 ga teng qiymat beriladi.
Nega? Agar bu dasturni q := n o’zgaruvchili qiymatda bir necha marta bajarsak, u holda dastur tomonidan quyidagi holda noto’g’ri natija chiqariladi:  
O’sish bo’yicha tartiblangan massiv berilgan bo’lsin:

-92 -40 -26 -12 -7 -4 0 6 9 25 34 38 46 52 56 67 71 78 86 93.
Siz bu massivga tartiblangan massivning eng katta sonidan ham kattaroq bo’lgan 125 sonini kiritmoqchi bo’ldingiz. Shunda, dasturning ishlash jarayonida 125 soni oxiridan bitta oldingi o’ringa joylashtiriladi, ya’ni ekranda quyidagi natija hosil bo’ladi:

    -92 -40 -26 -12 -7 -4 0 6 9 25 34 38 46 52 56 67 71 78 86 125 93

Bu kamchilik juda oson yo’l bilan bartaraf etiladi. Buning uchun q := n + 1 operatoriga 1 ni qo’shish yetarli. (Sababini tushuntiring?)

195-misol. O’sish bo’yicha tartiblangan massivga tartib qoidasini buzmagan holda berilgan sonni kiriting. Oldingi masaladagi dasturni shunday o’zgartiringki, tartiblangan massivga boshqa sonli massiv qo’shilsin, yangi massiv esa tartiblangan bo’lsin.
Program L195;
     uses Crt;
     const
            n = 20; k = 10;
     type
            t = array[1..n +  k] of integer;
     var
            b : array[1..k] of integer;
            a : t;
            i, j, p : integer;
{----------------------------------------------------------------------------------------}
     Procedure quick_search(a : t; n, b : integer;  var p : integer);
         var
             q, s : integer;
         begin
            p := 1; q := n +1;
            while p < q do
                begin
                   s := (p + q) div 2;
                   if a[s] < b then p := s + 1 else q := s
                end
         end;
{----------------------------------------------------------------------------------------}
     begin
       writeln('O’sish bo’yicha tartiblangan massivni kiriting');
       randomize;
       for i := 1 to n do
          begin
             write(i, 'chi elementni kiriting'); readln(a[i])
          end;
       writeln('Berilgan tartiblangan massiv');
       for i := 1 to n do write(a[i], ' ');
       writeln;
       writeln('Brinchi massivga joylashtirish uchun massiv');
       for i := 1 to k do
          begin
             b[i] := random(101);
             write(b[i], ' ')
          end;
       writeln;
       for i := 1 to k do
          begin
             quick_search(a, n + i - 1, b[i], p);
             for j := n + i downto p + 1 do a[j] := a[j - 1];
             a[p] := b[i];
          end;
       writeln('Yangi massiv');
       for i := 1 to n + k do write(a[i], ' ');
       writeln
    end.

196-misol. Chap tomonida o’zidan kichik elementlar, o’ng tomonda esa o’zidan kattalari joylashgan “o’rta” elementni topish dasturini tuzing.  (Elementlarning o’rnini almashtirish prosedurasi va “o’rta” elementni aniqlash prosedurasidan foydalaning).

Prosedurani middle deb ataymiz (middle ning inglizchadan tarjimasi - o’rta).
Asosiy dasturdagi massivni x deb belgilaymiz.
Procedure middle (kiruvchi parametr bo’lib massiv uzunligi hizmat qilishi kerak k: integer; chiquvchi parametrlar – massiv va “o’rta” element nomeri);
      var
          l, r : integer; {Elementlarning chap va o’ng nomerlari}
      begin
Elementlarning chap va o’ng nomerlariga boshlang’ich qiymatlar 1 va k ni (massiv uzunligini) berib qo’yish kerak.
Asosiy yoki tashqi sikl o’ng va chap indekslari nomerlari o’zaro teng bo’lib qolgunicha davom etishi kerak (l = r), demak tashqi sikl repeat ni tashkil etish kerak.
So’ngra o’ng tomondan boshlab elementlarni ko’rib chiqish sikli bo’lishi kerak, u chap element o’ng elementdan kichik yoki teng bo’lguncha davom etishi, shu bilan bir qatorda chap indeks nomeri o’ngidan kichik bo’lishi kerak, bu yerda quyidagi sikl o’rinli:

     while (x[l] <= x[r]) and (l < r) do

(Siklda o’ng element indeksini kamaytirib, o’rtaga siljib borish kerak) r := r – 1.
O’ngidan katta bo’lgan chap element topilishi bilan, bu elementlarning o’rnini almashtirish kerak. Buning uchun esa elementlarning o’rnini almashtrish prosedurasiga murojaat etish kerak, uni asosiy dasturda exchange (almashuv) deb ataymiz;
Almashtirishdan so’ng, o’ng tomondagi elementlarni ko’rib chiqish kerak, buning uchun ham “bo’lguncha” siklini tashkil qilamiz:
while (x[l] <= x[r]) and (l < r) do.
Siklda elemntlarni ko’zdan kechirgan holda chapdan o’ngga siljish, buning uchun esa chap element indeksini  l := l + 1 ga oshirish kerak.
Agar o’ngidan katta bo’lgan chap element topilsa, ularning o’rnini almashtirish kerak.
Almashtirish prosedurasiga yana murojaat qilamiz.
Tashqi sikl: until l = r sharti bilan tugaydi.

 

 

Dastur

Program L196; {Massivning “o’rta” elementini qidirish}
uses Crt;
const
            n = 20;
type
t = array[1..n] of integer;
var
x      : t;
m, i : integer;
{---------------------------------------------------------------------------------------}
Procedure create(n : integer;  var x : t);
var
i : integer;
begin
randomize;
writeln('Berilgan butun sonli massiv’);
 for i := 1 to n do
 begin
x[i] := random(201)-100;
write(x[i], ' ')
end;
writeln
  end;
{----------------------------------------------------------------------------------------}
       Procedure exchange(l, r : integer);
var
p : integer;
 begin
p := x[l]; x[l] := x[r]; x[r] := p
end;
{----------------------------------------------------------------------------------------}
Procedure middle(k : integer;  var x : t;  var m : integer);
var
l, r : integer;
 begin
l := 1; r := k;
 repeat
 while (x[l] <= x[r]) and (l < r) do r := r - 1;
exchange(l, r);       {Almashtirish prosedurasi}
while (x[l] <= x[r]) and (l < r) do l := l + 1;
exchange(l, r)
until l = r;
m := l
end;
{---------------------------------------------------------------------------------------}
 begin
create(n, x);
middle(n, x, m);
write('O’rta elementli o’zgartirilgan massiv', x[m]);
writeln(m, 'chi o’rinda');
for i := 1 to n do write(x[i], ' ');
writeln
     end.

Bu dasturni bir necha marta bajarib ko’ring va “o’rta” elementning massivdagi joylashishga e’tibor bering. Siz shunga e’tibor berishingiz kerakki, har doim ham (aniqrog’i, kamdan-kam hollarda) “o’rta” element massivdagi haqiqiy o’rta joyni egallayvermaydi, lekin bu uning tezkorligiga hech qanday ta’sir qilmaydi.

197-misol. Endi oldimizga qo’yilgan maqsad shundan iboratki, biz “o’rta” dasturini shunday o’zgartirishimiz kerakki, u nafaqat “o’rta” elementni aniqlasin, balki shu usuldan foydalangan holda sonli massivni tartiblasin. 

Masalani tuzish g’oyasi quyidagicha. Birinchi bosqich - bu butun massivning “o’rta” elementini topish (biz “o’rta” elementni aniqlash jarayonini amalga oshirgan sonli massivga yana murojaat qilamiz). 
Shunday qilib, “o’rta” element topildi, u 45 ga teng va u 7-o’rinda joylashgan.
36   33   12   18   15   26   45   67   48   89
1     2     3    4    5      6    7     8     9    10

Bundan keyin, yana “o’rta” elementni aniqlash prosedurasidan foydalanamiz, lekin u hozircha 1-chidan 7-gacha (7-elementning o’zi hisobga olinmaydi) bo’lgan 7-nomerdan chap tomonda joylashgan massivning chap qismi uchun ishlatilgan.

36   33   12   18   15   26
1     2     3     4     5     6
36 va 26 ni 36 < 26 shart bo’yicha solishtiramiz. Shart bajarilmayapti, demak, 36 va 26 elementlarning o’rinlari almashtiriladi. Massivning bu qismi quyidagi ko’rinishga kiradi:

26   33   12   18   15   36
1     2     3    4     5     6

Bu yerda 36 "o’rta" element bo’lib qoldi, chunki unga nisbatan chap tomonda 36 dan kichik bo’lgan elementlar joylashgan.
36 ga nisbatan chap tomondagi massiv qismi bilan jarayonni davom ettiramiz (har doim chapga harakatlanamiz):

26   33   12   18   15   36
1     2     3     4     5     6

33 va 15 (33 < 15) ni solishtiramiz, shart bajarilmayapti, bu elementlarning o’rnini almashtirib quyidagiga ega bo’lamiz:
26   15   12   18   33   36
1     2     3     4     5     6

Yana "o’rta" element 33 5-o’rinda topildi. 1 dan 4 gacha bo’lgan 4 ta element uchun “o’rtasini” topish jarayonini boshlaymiz.

26   15   12   18   33   36
1     2     3     4     5     6

26 18 bilan solishtiriladi (26 < 18). Shart bajarilmayapti, elementlarning o’rnilari almashadi va h.k. Har doim chap qismdagi “o’rta” elementlar topiladi.
Birinchi elementga yetib kelganimizdan so’ng, chapga siljish jarayoni to’xtatiladi va asta-sekinlik bilan o’ngga siljish boshlanadi, ya’ni massivning o’ng qismlari uchun “o’rta” elementlar topiladi.
Natijada massiv tartiblangan holatga kelib qoladi. 

Bu jarayon quyidagi prosedura yordamida amalga oshiriladi:
Procedure fast(q, p : integer;  var x : t);
 var
s, l, r : integer;
begin
l := q; r := p;
s := x[l];
 repeat
 while (x[r] >= s) and (l < r) do r := r - 1;
x[l] := x[r];
while (x[l] <= s) and (l < r) do l := l + 1;
x[r] := x[l]
until l = r;
x[l] := s;
if q < l - 1  then fast(q, l - 1, x);
 if l + 1 < p then fast(l + 1, p, x)
end;

Proseduraning juda muhim xususiyatiga e’tibor bering! Uning asosiy qismi - “o’rta” elementni aniqlash jarayoni bajarilgandan so’ng ikkita shartli operator qo’yilgan:
if q < l - 1 then fast(q, l - 1, x);
if l + 1 < p then fast(l + 1, p, x)

Birnchi shartli operator chapga siljishga “majbur etadi” (buni biz misolda ko’rib chiqqan edik) va huddi o’sha prosedura-fastni chaqiradi, ya’ni o’ziga o’zi murojaat etish jarayoni kuzatiladi. Huddi shu jarayon chapga siljishni ta’minlovchi ikkinchi shartli operatorda kuzatiladi. Bu yerda ham fast prosedurasi- o’zini o’zi chaqiradi. Ya’ni bizda rekursiv prosedura hosil bo’ladi.

Mustaqil yechish uchun vazifalar

 Shu prosedura yordamida massivni tartiblashga doir to’la dasturni tuzing va uni bajaring.

197-misol. Tasodifiy sonlar funksiyasi yordamida tuziladigan, so’ngra tezkor tartiblash rekursiv prosedurasi yordamida tartiblanadigan ikkita tartiblangan massivdagi o’xshash elementlar sonini toping.

Program L197;
uses Crt;
const n = 20;
 type  t = array[1..n] of integer;
var   x : t;  i : integer;
{----------------------------------------------------------------------------------------}
Procedure create(n : integer; var x : t);
 var
i : integer;
 begin
randomize;
writeln('Berilgan butun sonli massiv');
for i := 1 to n do
begin
x[i] := random(201) - 101; write(x[i], ' ')
end;
writeln
end;
{----------------------------------------------------------------------------------------}
 Procedure fast(q, p : integer; var x : t);
var
                s, l, r : integer;
 begin
l := q; r := p; s := x[l];
                  repeat
while (x[r] >= s) and (l < r) do r := r - 1;
x[l] := x[r];
                    while (x[l] <= s) and (l < r) do l := l + 1;
x[r] := x[l]
until l = r;
x[l] := s;
 if q < l - 1 then fast(q, l - 1, x);
if l + 1 < p then fast(l + 1, p, x)
 end;
{--------------------------------------------------------------------------------}
     begin
create(n, x); fast(1, n, x);
writeln('Tartiblangan butun sonli massiv');
 for i := 1 to n do write(x[i], ' ');
writeln
end.

221-misol. Massivda nolga teng elementlar bor. Massivni o’sish bo’yicha tartiblovchi, so’ngra nolga teng elementlarni tashlab yuborish orqali massivni “ixchamlovchi” dasturni tuzing. Nollar bilan massivning oxirgi o’rinlari to’ldiriladi.

Massivni tartiblash bizga oldingi misollardan ma’lum bo’lgan jarayon - uni tezkor tartiblash prosedurasi yordamida amalgam oshirsa bo’ladi.
Bundan keyin, nolga teng elementlar massiv boshida bo’lib qoladi, masalan quyidagidek:
0   0   0   0   2   4   6   9   10   12
1   2   3   4   5   6   7   8   9     10

Endi nolga teng elementlarni massivning oxiriga ko’chirish kerak, bu esa oxir-oqibat quyidagi ko’rinishga kelib qoladi:
2   4   6   9   10   12   0   0   0   0
Nolga teng elementlarni massiv oxiriga kochirishning bir necha usullari mavjud.
Birinchi usul - bu nolga teng elementlarning sonini aniqlash, so’ngra qolgan elementlarni ularning joylashishiga ko’ra 1 dan boshlab nomerlab chiqish, qolgan elementlarga esa nol qiymat berib qo’yish kerak.
Ikkinchi usul – bu nolga teng elementlarni ketma-ket massiv oxiriga o’tkazish: birinchi nolga teng element olinib, massiv oxiriga o’tkaziladi, u n-chi, quyidagi misolda 10 elementning o’rnida bo’lib qoladi va
0   0   0   2   4   6   9   10   12   0

massiv hosil bo’ladi. Bu yerda birinchi o’rinda yana nolga teng element bo’lib qoladi, u endi oxirgi o’ringa emas, oxirgidan bitta oldingi o’ringa ko’chiriladi:  

0   0   2   4   6   9   10   12   0   0 va h.k.

Biz ikkinchi usuldan foydalanamiz, zero biz elementlarning o’rnini almashtirish usulini bir necha marta qo’llaganmiz. Lekin hozir elementlarning o’rnini almashtirish uchun rekursiv prosedura tuzamiz. (Albatta prosedurasiz ham ishni amalga oshirsa bo’ladi, lekin bizning massivli rekursiv proseduralardan foydalanishni o’rganishimiz muhim ahamiyatga ega).

Prosedura

Procedure swp(k, m : integer);
label 1;
var
v : integer;
 begin
 if k = m then goto 1;
v := a[k];
a[k] := a[k + 1];
a[k + 1] := v;
swp(k + 1, m);
1: end;

U ancha oson tuzilgan. Bu yerda qo’shni elementlarni elementar nomerlarining oshish yo’nalishiga qarab ko’chirish, ya’ni o’ng chegaraga ko’chish asos qilib olingan.  Bu sizga anchadan beri ma’lum uchta operatorlar yordamida amalga oshadi: v := a[k]; a[k] := a[k + 1]; a[k + 1] := v;

Program L221;
uses Crt;
const n = 20;
 type
t = array[1..n] of integer;
 var
a     : t;
i, d : integer;
{---------------------------------------------------------------------------------------}
     Procedure fast(q, p : integer;  var a : t);
var
                s, l, r : integer;
begin
l := q;  r := p;
s := a[l];
repeat
while (a[r] >= s) and (l < r) do r := r - 1;
a[l] := a[r];
while (a[l] <= s) and (l < r) do l := l + 1;
a[r] := a[l]
 until l = r;
a[l] := s;
if q < l - 1 then fast(q, l - 1, a);
if l + 1 < p then fast(l + 1, p, a)
end;
{---------------------------------------------------------------------------------------}
Procedure swp(k, m : integer);
label 1;
           var
v : integer;
begin
if k = m then goto 1;
v := a[k]; a[k] := a[k + 1]; a[k + 1] := v;
swp(k + 1, m);
1: end;
{---------------------------------------------------------------------------------------}
    begin
 for i := 1 to n do
begin
write(i, ‘chi elementni kiriting’);
readln(a[i])
 end;
fast(1, n, a);
d := 1;
repeat
swp(1, n - d + 1);
d := d + 1
until a[d] > 0;
swp(1, n - d + 1);
swp(1, n - d);
writeln('Oxiri nollar bilan to’ldirilgan tartiblangan massiv');
 for i := 1 to n do write(a[i],' ');
writeln
end.

222-misol. Tasodifiy sonlar funksiyasi yordamida ikkita sonli massivni tuzuvchi, ularni tezkor tartiblash rekursiv prosedurasi yordamida tartibga soluvchi, so’ngra ularni  rekursiv prosedurani yana qo’llagan holda tartiblangan alohida massivga birlashtiruvchi dastur tuzing.

Tasodifiy sonlar funksiyasi yordamida massiv tuzishni va ularni tartiblashni biz oldindan bilamiz, shuning uchun bu savollarga to’xtalib o’tmaymiz-da, bizda oldindan ikkita kamaymaslik bo’yicha tartiblangan massiv bor deb faraz qilamiz:
Misol uchun 10 ta elementdan tashkil topgan a va 15 ta elementdan tashkil topgan b massivlar berilgan bo’lsin.
a massiv:       -98 -97 -77 -47 -44 -24 11 59 75 83
b massiv:       -96 -75 -69 -69 -68 -15 -5 11 37 45 47 77 85 92 93
Massiv elementlarini ketma-ket solishtirish, eng kichigini tanlab uning qiymatini yangi massiv elementiga berib qo’yish kerak degan tabiiy fikr tug’iladi.
Bu g’oya amalda qanday qilib ro’yobga chiqishini ko’raylik: massivning birinchi elementi a, a[1]=-98;
b massivning birinchi elemnti, b[1] = -96;
a[1] < b[1] (-98 < -96),
demak yangi massivdagi birinchi elementga a massivning birinchi elementi qiymatini berib qo’yamiz:
c[1] := a[1], c[1] := -98.
Endi a massivning ikkinchi elementini olamiz, a[2]=-97 va uni b massivning birinchi elemeti bilan solishtiramiz: 
a[2] < b[1], (-97 < -96),
demak yangi massivning ikkinchi elementiga a massivning ikkinchi elementi qiymatini berib qo’yishimiz kerak:
c[2] := a[2], c[2] := -97.
a massivni ko’rib chiqishda davom etamiz, uchinchi element olinadi, a[3]=-77 va b massivning birinchi elementi bilan solishtiriladi:
a[3] < b[1], (-77 < -96),
shart bajarilmayapti, demak c massivning keyingi, uchinchi elementiga b massivning 1 qiymati beriladi:
c[3] := b[1], c[3] := -96.
Bu jarayon a yoki b massivning biron birida elementlar tugab qolmagunicha davom etadi (shuni qayd etish kerakki, a massivning elementlar soni b massivdagi elementlar soniga qaraganda kam bo’lishi, a massiv tezroq ko’rib chiqilar ekan-da degan fikrga olib kelishi kerak emas, chunki teskari holat tug’ilishi, ya’ni agar b massivning elementlari a massivdagi elementlardan kichik bo’lsa, u holda b massiv tezroq ko’rib chiqilishi mumkin). 
Program L222;
uses Crt;
const
            n = 10; m =15;
type
            t = array[1..n] of integer;
u = array[1..m] of integer;
f = array[1..n+m] of integer;
var
a : t; b : u; c : f;
i, p, q : integer;
{----------------------------------------------------------------------------------------}
 Procedure fast(q, p : integer;  var a : t);
 var
s, l, r : integer;
 begin
l := q;
r := p;
s := a[l];
                repeat
 while (a[r] >= s) and (l < r) do r := r - 1;
a[l] := a[r];
while (a[l] <= s) and (l < r) do l := l + 1;
a[r] := a[l]
 until l = r;
a[l] := s;
if q < l - 1 then fast(q, l - 1, a);
if l + 1 < p then fast(l + 1, p, a)
end;
{----------------------------------------------------------------------------------------}
 Procedure fast1(q, p : integer;  var b : u);
var
s, l, r : integer;
begin
l := q;
r := p;
s := b[l];
 repeat
while (b[r] >= s) and (l < r) do r := r - 1;
b[l] := b[r];
while (b[l] <= s) and (l < r) do l := l + 1;
b[r] := b[l]
until l = r;
b[l] := s;
if q < l - 1 then fast1(q, l - 1, b);
if l + 1 < p then fast1(l + 1, p, b)
end;
{----------------------------------------------------------------------------------------}
        Procedure new(n, m, q, p, k : integer;  var c : f);
label 1, 2;
 begin
if k = n + m + 1 then goto 1;
 if p = n then begin q := q + 1; c[k] := b[q]; goto 2 end;
if q = m then begin p := p + 1; c[k] := a[p]; goto 2 end;
 if a[p + 1] < b[q + 1]
then begin p := p + 1; c[k] := a[p]; goto 2 end
 else begin q := q + 1; c[k] := b[q] end;
2: new(n, m, q, p, k + 1, c);
1: end;
{----------------------------------------------------------------------------------------}
      begin
randomize;
 for i := 1 to n do a[i] := random(201)-100;
for i := 1 to m do b[i] := random(201)-100;
fast(1, n, a);
writeln('Berilgan tartiblangan 1-chi massiv');
for i := 1 to n do write(a[i], ' ');
writeln;
fast1(1, m, b);
writeln('Berilgan tartiblangan 2-chi massiv');
 for i := 1 to m do write(b[i], ' ');
writeln;
new(n, m, 0, 0, 1, c);
writeln('Yangi tartiblangan birlashtirilgan massiv');
 for i:=1 to n + m do write(c[i], ' ');
writeln
 end.

223-misol. 1 dan 100 gacha bo’lgan tasodifiy sonlardan m*n kattalikdagi matrisani tuzing. Ularni quyidagi chizma bo’yicha o’sib borish tartibida joylashtiring (1-rasmga qarang):

Massiv elementlarini bunday sxema bo’yicha joylashtirish va masala shartini bajarish - elementlarni o’sib borish tartibida joylashtirish uchun quyidagilar kerak bo’ladi:
1) matrisani bir o’lchovli massivga "cho’zish";
2) Olingan massivni o’sib borish tartibida joylashtirish;
3) Olingan bir o’lchovli massivdan elementlari taklif etilgan chizma bo’yicha joylashgan ustunlarni “tanlash” kerak. 
Bu algoritmning birinchi bosqichini oldingi misolga asoslanib bajarish qiyin emas.
Olingan bir o’lchovli massivni tezkor tartiblash prosedurasi yordamida tartiblash mumkin.
Uchinchi bosqich biz uchun yangi. Uni bajarish uchun biz quyidagi qonuniyatga e’tibor berishimiz kerak. Agar ikki o’lchovli massivdagi ustun toq nomerga ega bo’lsa, ya’ni 1, 3, 5 va h.k bo’lsa, u holda ustun elementlari 1-chi elementdan to n-gacha “tepadan pastga qarab” o’sib borish tartibida joylashadi. 
Agar ustun nomerlari juft, ya’ni 2, 4, 6 va h.k bo’lsa, u holda elementlar n-dan 1-gacha “pastdan tepaga qarab” joylashadi.
Program L223;
uses Crt;
 const
n = 5; m = 6;
type
s = array[1..m] of integer; t = array[1..n] of s; f = array[1..n*m] of integer;
 var
a : t;
b : f;
i, j, k, v : integer;
{----------------------------------------------------------------------------------------}
Procedure create_two(n, m : integer; var a : t);
var
i, j : integer;
 begin
writeln('Berilgan ikki o’lchovli butun sonli massiv');
randomize;
for i := 1 to n do
               begin
for j := 1 to m do
                     begin
a[i, j] := random(201) - 100;
write(a[i, j]:6, ' ')
 end;
writeln
              end
         end;
{----------------------------------------------------------------------------------------}
 Procedure sprain(n, m : integer; a : t; var b : f);
var
k, i, j : integer;
 begin
k := 0;
for i := 1 to n do
 for j := 1 to m do
                  begin
k := k + 1;
b[k] := a[i, j]
end
         end;
{----------------------------------------------------------------------------------------}
Procedure fast(q, p : integer; var b : f);
var
s, l, r : integer;
 begin
l := q; r := p;
s := b[l];
 repeat
while (b[r] >= s) and (l < r) do r := r - 1;
b[l] := b[r];
 while (b[l] <= s) and (l < r) do l := l + 1;
b[r] := b[l]
until l = r;
b[l] := s;
 if q < l - 1 then fast(q, l - 1, b);
 if l + 1 < p then fast(l + 1, p, b)
         end;
{----------------------------------------------------------------------------------------}
  begin
create_two(n, m, a);
sprain(n, m, a, b);
fast(1, n*m, b);
 for i := 1 to n*m do write(b[i], '  '); writeln;
v := 1; k := 0;
repeat
 if v mod 2 <> 0 then
for i := 1 to n do
                                          begin
k := k + 1;
a[i, v] := b[k]
end
                                    else
for i := n downto 1 do
begin
k := k + 1;
a[i, v] := b[k]
end;
v := v + 1
 until v = m + 1;
writeln('Elementlarning chizma bo’yicha joylashish massivi');
for i := 1 to n do
           begin
 for j := 1 to m do write(a[i, j]:6, ' '); writeln
end
end.

 224-misol. 1 dan 100 gacha bo’lgan tasodifiy sonlardan m*n  kattalikdagi matrisani tuzing. Ularni quyidagi chizmalar bo’yicha o’sib borish tartibida joylashting (2-rasmga qarang):
                                                       

Program L224a;
uses Crt;
const
n = 5; m =6 ;
type
s = array[1..m] of integer;
t = array[1..n] of s;
f = array[1..n*m] of integer;
var
a : t;
b : f;
i,  j,  k,  v :  integer;
{----------------------------------------------------------------------------------------}
Procedure create_two(n, m : integer; var a : t);
var
i, j : integer;
begin
writeln('Berilgan ikki o’lchovli  butun sonli massiv');
randomize;
for i := 1 to n do
begin
for j := 1 to m do
begin
a[i, j] := random(201) - 100;
write(a[i, j]:6, ' ')
end;
writeln
end
end;
{----------------------------------------------------------------------------------------}
 Procedure sprain(n, m : integer; a : t; var b : f);
var
k, i, j : integer;
 begin
k := 0;
for i := 1 to n do
 for j := 1 to m do
                  begin
k := k + 1;
b[k] := a[i, j]
end
         end;
{----------------------------------------------------------------------------------------}
Procedure fast(q, p : integer; var b : f);
var
s, l, r : integer;
begin
l := q;
r := p;
s := b[l];
repeat
while (b[r] >= s) and (l < r) do r := r - 1;
b[l] := b[r];
while (b[l] <= s) and (l < r) do l := l + 1;
b[r] := b[l]
until l = r;
b[l] := s;
if q < l - 1 then fast(q, l - 1, b);
if l + 1 < p then fast(l + 1, p, b)
end;
{----------------------------------------------------------------------------------------}
begin
create_two(n, m, a);
sprain(n, m, a, b);
fast(1, n*m, b);
v := 1; k := 0;
repeat
if v mod 2 <> 0
then
for j := 1 to m do
begin
k := k + 1;
a[v, j] := b[k]
end
else
for j := m downto 1 do
begin
k := k + 1;
a[v, j] := b[k]
end;
v := v + 1
until v = n + 1;
writeln('Elementlarning (a) chizma bo’yicha joylashish massivi');
for i := 1 to n do
begin
for j := 1 to m do write(a[i, j]:6, ' '); writeln
end
end.

 

Program L224b;
uses Crt;
const
n = 5; m = 6;
type
s = array[1..m] of integer;
t = array[1..n] of s;
f = array[1..n*m] of integer;
var
a : t; b : f;
i, j, k, v : integer;
{----------------------------------------------------------------------------------------}
Procedure create_two(n, m: integer;  var a : t);
var
i, j : integer;
begin
writeln('Berilgan butun sonli ikki o’lchovli massiv');
randomize;
for i := 1 to n do
begin
for j := 1 to m do
begin
a[i, j] := random(201) - 100;
write(a[i, j]:6, ' ')
end;
writeln
end
end;
{----------------------------------------------------------------------------------------}
 Procedure sprain(n, m : integer; a : t; var b : f);
var
k, i, j : integer;
 begin
k := 0;
for i := 1 to n do
 for j := 1 to m do
                  begin
k := k + 1;
b[k] := a[i, j]
end
         end;
{----------------------------------------------------------------------------------------}
     Procedure fast(q, p : integer;  var b : f);
var
s, l, r : integer;
begin
l := q; r := p; s := b[l];
repeat
while (b[r] >= s) and (l < r) do r := r - 1;
b[l] := b[r];
while (b[l] <= s) and (l < r) do l := l + 1;
b[r] := b[l]
until l = r;
b[l] := s;
if q < l - 1 then fast(q, l - 1, b);
if l + 1 < p then fast(l + 1, p, b)
end;
{----------------------------------------------------------------------------------------}
begin
create_two(n, m, a);
sprain(n, m, a, b);
fast(1, n*m, b);
v := n; k := 0;
repeat
if v mod 2 <> 0
then
for j := 1 to m do
begin
k := k + 1; a[v, j] := b[k]
end
else
for j := m downto 1 do
begin
k := k + 1;
a[v, j] := b[k]
end;
v := v - 1
until v = 0;
writeln(''Elementlarning (b) chizma bo’yicha joylashish massivi');
for i := 1 to n do
begin
for j := 1 to m do write(a[i, j]:6, ' '); writeln
end
end.

Foydalanilgan adabiyotlar

Sh.X.Fozilov, S.S.Jumanazarov, D.T. Muhamediyeva

Dasturlash bo’yicha olimpiada masalalari

TOSHKENT-2006

Абрамов С.А., Зима Е.В. Начала информатики. - М.: Наука. Гл. ред. физ.-мат. лит., 1989.

Брудно А.Л., Каплвн Л.И. Московские олимпиады по программированию/Под ред. акад. Б.Н. Наумова. - 2-е изд., доп. и перераб. - М.: Наука. Гл. ред. физ.-мат. лит., 1990.

Васильев Н. Б., Гутенмахер В.Л., Раббот Ж.М., Тоом А.Л. Заочные математические олимпиады. - 2-е изд., перераб. - М.: Наука. Гл. ред. физ.-мат. лит., 1997.Васюкова Н.Д., Тюляева В.В. Практикум по основам программирования. Язык ПАСКАЛЬ: Учеб. пособие для учащихся сред. спец. учеб. заведений. - М.: Высш. шк., 1991.Да

1488 marta o`qildi.

Parol:
Eslab qolish.


Ro`yhatdan o`tish

testing

+998915878681

Siz o`z maxsulotingizni 3D reklama ko`rinishda bo`lishini xohlaysizmi? Unda xamkorlik qilamiz.

3D Reklama


Рейтинг@Mail.ru
Рейтинг@Mail.ru

Besucherzahler
счетчик посещений