Masalalar va ularning yechimlari bilan tanishamiz

17-Ma’ruza: Informatika va axborot texnologiyalari fanlaridan olimpiadalar o’tkazish. Informatika va axborot texnologiyalari fanlaridan olimpiada masalalar yechish
Informatika va axborot texnologiyalari fanlaridan olimpiada masalalarini yechish
usullari.
So‘nggi yllarda informatika fanidan viloyat va respublika bosqichi olimpiadalarida berilgan
masalalar va ularning yechimlari bilan tanishamiz.
Masla-1. Agar
AA
+
BB
SBS
bo‘lsa, u holda A, B, S raqamlarni topish dasturi tuzilsin.
Yechish:
Bu masalani yechish uchun o‘nlik sanoq sistemasidagi sonlarni standart ko‘rinishini esga olish kifoya, ya’ni:
AA + BB = A*10 + A + B*10 + B = (A+B)*10 + (A+B) = (A+B)*11
SBS = S*100 + B*10 + S = S*101 + B*10.
Shartga ko‘ra A, B, S lar raqam. Shuning uchun ularning qiymati 1 dan 9 gacha bo‘lishi mumkin (nima uchun 0 bo‘lishi mumkin emasligini o‘zingiz o‘ylab ko‘ring).
Program Yigindi;
Uses Crt;
Var a,b,s:Integer;
Begin
TextColor(Yellow); TextBackGround(Blue);
ClrScr;
For a:=1 To 9 Do
Begin
For b:=1 To 9 Do
Begin
For s:=1 To 9 Do
Begin
If (11*(a+b))=(101*s+10*b) Then WriteLn('A=',a,' B=',b,' S=',s);
end;
end;
end;
ReadLn;
end.
Yuqori qiyinlik darajasidagi masalalar va ularni yechish usullariInformatikadan olimpiadaning respublika bosqichida asosan qiyinlik darajasi yuqori bo‘lgam masalalar taqdim etiladi. Quyida shunday masalalardan namunalar keltiramiz:
1. N ta kulrang va M ta oq sichqon aylana bo‘ylab o‘tirishibdi. Mushuk aylana bo‘ylab soat mili yo‘nalishida yurib, har S-sichqonni yeydi. Hisob kulrang sichqondan boshlanadi. Ma’lum vaqtdan so‘ng K ta kulrang va L ta oq sichqon qolgan bo‘lsa, boshida sichqonlar qanday tartibda o‘tirganini aniqlovchi dastur tuzing.
Yechish:
Bu masalani yechishning juda ko‘p usuli bo‘lib, ulardan birini keltiramiz. 1-qadam. Sichqonlarning I-siga rangidan qat’iy nazar SON(I) massiv elementini mos qo‘yamiz. Agar SON(I)=1 bo‘lsa I-sichqon tirik, SON(I)=0 bo‘lsa I-sichqon yeyilgan. Masalani shartiga ko‘ra boshlang‘ich vaqtda barcha sichqonlar uchun SON(I)=1.
2-qadam. Har T-sichqon yeyilsa, ya’ni SON(I)=0 bo‘lsa, ma’lum vaqtdan (ya’ni qadamdan) keyin yeyilgan sichqonlar soni N+M-K-Lga teng bo‘lishi kerak, chunki masala shartiga ko‘ra sichqonlarning umumiy soni N+Mta; tirik qolishi kerak bo‘lgan kulrang sichqonlar soni Kta, oq sichqonlar soni Lta.
3-qadam. Masala shartiga ko‘ra hisob kulrang sichqondan boshlanadi. Shuning uchun
natijani chop etishda hisobni (I=1dan boshlab) kulrang sichqonlardan boshlaymiz. H1 tirik (SON(I)=1), H2 (SON(I)=0) yeyilgan kulrang sichqonlar soni bo‘lsa, ularning soni mos ravish da (H1 va H2 noldan boshlangani uchun) K-1 va N-K-1dan oshmaydi. Qolgan sichqonlarni oq sichqon deb qaraymiz.
Program Mushuk_Sichqon;
Uses Crt;
Const nm1=100;
var n,m,s,k,l:Integer;
nm,qadam:Integer;
son:Array[1..nm1] of Integer;
del,_del:Integer;{Yeyilgan sichqonlar soni}
i,h1,h2:Integer;
Begin
TextColor(14); TextBackground(1); ClrScr;
Write('Nechta kulrang sichqon: '); ReadLn(n);
Write('Nechta oq sichqon: '); ReadLn(m);
Write('Nechta kulrang sichqon tirik qolsin: '); ReadLn(k);
Write('Nechta oq sichqon tirik qolsin: '); ReadLn(l);
Write('Nechta qadam sakrasin: '); ReadLn(s);
nm:=n+m; _del:=nm-k-l;
For i:=1 To nm Do son[i]:=1;
del:=0; qadam:=0; i:=0;
Repeat
Inc(i); If i>nm Then i:=i-nm;
If son[i]=1 Then Inc(qadam);
If qadam=s Then Begin qadam:=0; son[i]:=0; Inc(del) end;
Until del=_del;
h1:=0; h2:=0;
For i:=1 To nm Do
Begin
Case son[i] Of
1: Begin
TextColor(15);
If h1Else Write(i,'-oq, ');
end;
0: Begin
TextColor(7);
If h2Else Write(i,'-oq, ');
end;
end;
end;
ReadLn;
End.
2. Kenguru uzunligi N ta katak bo‘lgan maydonda faqat oldinga sakrashi mumkin. Kenguruninig sakrash imkoniyati ko‘pi bilan K ta katak bo‘lsin. Kenguruning maydonning boshidan oxirigacha necha xil usul bilan yetib borishi mumkinligini aniqlovchi dastur tuzing.
Masalan, N=3, K=2 bo‘lsa, usullari:
1) 1, 1, 1
2) 1, 2
3) 2, 1 Javob 3.
Yechish:
Bu masalani boshqacha talqin qilish ham mumkin: N sonini necha hil takrorlanmaydigan usul bilan qiymati Kdan oshmaydigan qo‘shiluvchilarning yig‘indisi ko‘rinishida tasvirlash mumkin? Bunday usullarning juda ko‘p bo‘lishini tushunish qiyin emas.Belgilash kiritamiz: S(I) - kenguruning maydonning boshidan I-chi katakkacha yetib borishi mumkin bo‘lgan barcha usullar soni bo‘lsin. Faraz qilamiz, birdan to I gacha bo‘lgan har bir J uchun S(J)ning qiymati ma’lum bo‘lsin. Masala shartiga kora I+1 chi katakka kenguru faqat I, I-1,…, I-K kataklardan sakrab o‘ta oladi, ya’ni
S(I+1)= S(I)+S(I-1)+...+S(I-K).
Demak, S(N)ni S(1), S(2),..., S(N-1) qiymatlarni ketma-ketlik hisoblash orqali topiladi.
Dasturi quyidagicha:
Program Kenguru;
Uses Crt;
Const nm=1000;
Var
n,k,i,j:Integer;
s:Array[1..nm] of Integer;
Begin
TextColor(Yellow); TextBackGround(Blue); ClrScr;
Write('Maydon o‘lchamini kiriting : '); ReadLn(n);
Write('Kenguru nechta katakka sakray oladi: '); ReadLn(k);
s[1]:=1;
For i:=2 To k Do s[i]:=s[i-1]*2;
For i:=k+1 To n Do
Begin
s[i]:=0;
For j:=i-k To i-1 Do s[i]:=s[i]+s[j];
end;
WriteLn('Kenguru maydonni ',s[n],' usulda bosib o‘tadi');
ReadLn;
End.
3. Lotin alifbosida yozilgan N ta so‘zdan iborat ketma-ketlik berilgan. Ketma-ketlikdagi hamma anagrammalarni chop etuvchi dastur tuzing (anagramma - bir-biridan harflarning o‘rni bilan farqlanuvchi so‘zlar).
Yechish:
Masalani yechish algoritmi quyidagicha:
1. Berilgan har bir so‘zning harflari ASCI kodi bo‘yicha o‘sish tartibida saralab
olinadi.
2. Hosil bo‘lgan yangi so‘zlar ichidan bir hillari chop etiladi.
Dasturi quyidagicha:
219
Programm Anagramma;
Uses Crt;
Const nm=100;
Var
n,len,i,j,k:Integer;
suz,anagr,an:Array[1..nm] of String[20];
_suz:String;
ch:Char;
L:Array[1..nm] Of Integer;
bor:Boolean;
Begin
TextColor(Yellow); TextBackGround(Blue); ClrScr;
Write('So‘zlar sonini kiriting : '); ReadLn(n);
For i:=1 To n Do
Begin
Write(i,'-so‘zni kiriting: '); ReadLn(suz[i]);
end;
For i:=1 To n Do
Begin
_suz:=suz[i];
len:=Length(_suz);
For k:=1 To len-1 Do
Begin
ch:=_suz[k];
For j:=k+1 To len Do
Begin
If _suz[j]Begin ch:=_suz[j]; _suz[j]:=_suz[k]; _suz[k]:=ch; end;
end;
end;
anagr[i]:=_suz;
end;
WriteLn;
For i:=1 To n-1 Do
Begin
If L[i]<>1 Then
Begin
_suz:=anagr[i]; k:=1; an[k]:=suz[i]; bor:=False;
For j:=i+1 To n Do
Begin
If (_suz=anagr[j]) and (L[j]<>1) Then
Begin Inc(k); an[k]:=suz[j]; L[j]:=1; bor:=True; end;
end;
If bor Then
Begin
For len:=1 To k Do WriteLn(an[len]);
WriteLn('---------');
end;
end;
end;
ReadLn;
End.
4. A(N,N) butun qiymatli kvadrat massiv berilgan. Uning har bir kvadrat qism massivi (massivning o‘zi ham qism massiv hisoblanadi) elementlari minimumlarini kamayib borish tartibida “JAD.TXT” fayliga, kvadrat qism massivlari sonini “AA.TXT” fayliga yozuvchi dastur tuzing.
Yechish:
Bu masalada qism massivlar soni SONni avval hisoblab olish kerak. Chunki undan dasturda foydalaniladi. Dasturi quyidagicha:Programm Kvadrat_massiv;
Uses Crt;
Const
nn=100;
nm=10000;
var
a:Array[1..nn,1..nn] of Integer;
b:Array[1..nm] of Integer;
n,i,j,t,min:Integer;
k,n1,m1:Integer;
son:Integer;
Myfile:Text;
Procedure Kvadrat2;
begin
b[t]:=a[n1+1,m1+1];
For i:=n1+1 To n1+k Do
begin
For j:=m1+1 To m1+k Do If a[i,j]end;
Inc(t);
If m1+kIf n1+kend;
BEGIN
TextColor(14); TextBackground(1); ClrScr;
Write('Massiv o‘lchamini kiriting: '); ReadLn(n);
WriteLn('Massiv elementlarini kiriting‘);
For i:=1 To n Do
Begin
For j:=1 To n Do
Begin
Write('A(',i,',',j,')='); ReadLn(a[i,j]);
end;
end;
son:=0;
For i:=1 To n Do son:=son+i*i;
Assign(Myfile,'aa.txt');
ReWrite(Myfile);
WriteLn(Myfile,son);
Close(Myfile);
t:=0;
For i:=1 To n Do
Begin
For j:=1 To n Do
221
Begin
Inc(t); b[t]:=a[i,j];
end;
end;
Inc(t); b[t]:=a[1,1];
For i:=1 To n Do
Begin
For j:=1 To n Do If a[i,j]end;
Inc(t);
For k:=2 To n-1 Do
Begin
n1:=0; m1:=0;
Kvadrat2;
end;
For i:=1 To son-1 Do
Begin
For j:=i+1 To son Do
Begin
If b[i]>b[j] Then Begin min:=b[j]; b[j]:=b[i]; b[i]:=min; end;
end;
end;
Assign(Myfile,'Jad.txt');
ReWrite(Myfile);
For i:=1 To son Do WriteLn(Myfile,b[i]);
Close(Myfile);
End.