Urdu fizika-matematika fakulteti 161-informatika guruh talabasi Salayeva Maxliyoning Informatika va at o’qitish metodikasi fanidan

Yuqori qiyinlik darajasidagi masalalar va ularni yechish usullari

Informatikadan 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 ravishda (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 h1

Else Write(i,'-oq, '); end;

0: Begin

TextColor(7);

If h2

Else Write(i,'-oq, '); end; end; end; ReadLn; End.