linkedin facebook linkedin facebook nod32

Olimpiada misollarini yechish usullari II- bosqich

Muallif: Mengliyev Sh.

Qo`shilgan sana: 2015-04-08

Olimpiada misollarini yechish usullari II – bosqich

82-misol. Fransuz fizigi М. Mersen (1588 - 1648) shunga e’tibor berdiki,  ko'pgina tub sonlar quyidagi ko'rinishga ega bo'lar ekan: 
2p - 1
bu yerda p ham tub son. Bunday ko’rinishdagi barcha sonlar Mersen sonlari deyiladi. Berilgan oraliqda Mersen sonlarini topuvchi dastur tuzing.  

Algoritm
Dasturni tuzish uchun yaratilgan eng sodda algoritm quyidagicha bo’ladi:
birinchidan, bizga oldingi masalalardan tanish bo’lgan  tub sonlarni aniqlovchi prosedura zarurdir;
ikkinchidan, natural ko’rsatkichli natural sonning darajasini hisoblovchi prosedura kerak (bu prosedurani  siz oldingi vazifalarni bajarayotgan paytingizda tuzgan bo’lishingiz kerak).
Tub sonni aniqlash prosedurasi:
Procedure Probleme_number(p : longint; var v : longint);
var
i, k : longint;
begin
if p = 2 then v := p
else if p mod 2 <> 0
then
begin
i := 3; k := 0;
while i <= trunc(sqrt(p)) do
begin
if p mod i = 0 then k := k + 1;
i := i + 2
end;
if k = 0 then v := p
end
end;

Natural ko’rsatkichli natural sonning darajasini hisoblovchi prosedura (extent - daraja):
Procedure extent(a, n : integer; var s : longint);
var
i : integer;
begin
s := 1;
for i := 1 to n do s := s*a
end;

Dasturning asosiy qismida oraliqdagi har bir sonning tub yoki tub emasligini tekshirish kerak, buning uchun esa probleme_number(i, p) prosedurasiga murojaat qilish zarur.
Agar tub son olinsa, u holda 2 ni shu songa teng darajaga ko’tarish kerak, buning uchun esa, extent(2, p, m) prosedurasiga murojaat etish zarur.  
Nihoyat, olingan natijaning ham, tub yoki tub emasligini tekshirish kerak. Agar tub bo’lsa, u holda biz Mersen soniga ega bo’lamiz.  
Hammasi yaxshi ketayotgandek tuyular-ku, ammo bizni oldinda ko’plab muammolar kutmoqda.
Birinchi muammo! 3 soni tanlangan, probleme_number(i, p) prosedurasi uni tub son deb belgiladi va uning qiymati p o’zgaruvchiga berildi. Tanlangan oraliqdagi keyingi son 4, probleme_number(i, p) prosedurasi uni tub emasligini aniqladi va uning qiymati p o’zgaruvchiga berilmadi. U holda p ning qiymati nechaga teng degan savol tug’iladi. U o’z-o’ziga,  ya’ni 3 ga - oldingi kelgan tub songa teng bo’lib qolganligi ma’lum bo’ladi.  
Dasturda jarayonni davom ettiraversak, qiymatlar takrorlanib qoladi. Shunga o’xshagan takrorlanish Mersen soni deb qabul qilingan qiymatning tub yoki tub emasligini tekshirish paytida ham kuzatiladi.
Bunday muammolarni bartaraf etish uchun, birinchidan  har bir tekshirishdan so’ng, olingan tub sonlarning qiymatlarini yangi o’zgaruvchilar xotirasiga kiritish kerak, masalan: p1 := p; m1 := m; n1 := n, so’ngra esa darajani hisoblash va tub sonlarni tekshirish prosedurasiga takroran murojaat qilishdan avval, bu qiymatlar oldingilarning huddi o’zi emasligini tekshirish kerak.
Asosiy dasturning bu qismi quyidagicha:
                    for i := 2 to b do
                       begin
                          probleme_number(i, p);
                          if p <> p1 then extent(2, p, m);
                          if m <> m1 then probleme_number(m-1, n);
                          if n <> n1 then write(n, ' ');
                          n1 := n; p1 := p; m1 := m
                       end;

Dastur

Program L82; { Mersen sonlari }
uses Crt;
var
b, p, p1, m, m1, n, n1, i : longint;
Procedure Probleme_number(p : longint; var v : longint);
var
i, k : longint;
begin
if p = 2 then v := p
else if p mod 2 <> 0
then
begin
i := 3; k := 0;
while i <= trunc(sqrt(p)) do
begin
if p mod i = 0 then k := k + 1;
i := i + 2
end;
if k = 0 then v := p
end
end;
Procedure extent(a, n : integer; var s : longint);
var
i : integer;
begin
s := 1;
for i := 1 to n do s := s*a
end;
begin
write('Dar. ko’r.qiym. chap cheg. kiriting’); readln(b);
write('Mersen sonlari: ');
for i := 2 to b do
begin
probleme_number(i, p);
if p <> p1   then extent(2, p, m);
if m <> m1 then probleme_number(m - 1, n);
if n <> n1   then write(n,'; ');
n1 := n; p1 := p; m1 := m
end;
writeln
end.

 83-misol. Shunday eng kichik n natural sonni topingki, 2n-2 n ga bo’linmasin,  3n-3 n ga bo’linsin.
(Natural ko’rsatkichli natural sonning darajasini hisoblovchi prosedurani tuzing va undan foydalaning).

Program L83;
uses Crt;
var
n, s, s1 : integer;
Procedure extent(a, n : integer;  var s : integer);
var
i : integer;
begin
i := 1;
s := 1;
repeat
s := s*a;
i := i+1
until i=n
end;
begin
n := 1;
repeat
n := n+1;
extent(2, n, s);
extent(3, n, s1);
until ((s-2) mod (n-1)<>0) and ((s1-3) mod (n-1)=0); 
writeln('Qidirilayotgan son= ', n-1)
end.

84-misol. Agar n ta (n>1) raqamlardan iborat bo’lgan sonning n darajaga ko’tarilgan raqamlar yig’indisi sonning o’ziga teng bo’lsa u Armstrong soni deyiladi.
Masalan, 153 va 1634 Armstrong sonlaridir, zero 
153 = 13 + 53 + 33,  1634 = 14 + 64 + 34 + 44.
Barcha n-xonali Armstrong sonlarini topuvchi dastur tuzing (n –kiritiladigan ma’lumot,  jumladan n<10).

Masalaning matematik tahlili

Foydalanuvchi tomonidan sonning n ta xonasi, ya’ni sonda bo’lishi kerak bo’lgan raqamlar soni kiritiladi. Masalan, u 5 sonini kiritishi mumkin. Dastur barcha besh xonali sonlar ichidan Armstrong sonlarini topishi kerak, albatta bunday sonlar bo’lsa. 
Buning uchun dasturda eng kichik n-xonali sonni aniqlash kerak, buni 1 dan n-1 gacha bo’lgan siklni tashkil etib, avvaldan o’rnatilgan o’zgaruvchini (uning boshlang’ich qiymati 1) 10 ko’paytirgan  holda amalga oshirsa bo’ladi. Eng katta n-xonali sonni aniqlash uchun eng kichik n-xonali sonni 10 ga ko’paytirib, hosil bo’lgan sondan 1 ni ayirib tashlash yetarli. Masalan, 5 xonali sonlar ichida eng kichigi 10000, eng kattasi esa  100000-1=99999  bo’ladi.
Eng kichik va eng katta n-xonali sonni aniqlash uchun quyidagi prosedurani tashkil qilamiz:
Procedure minmax(n : longint; var min, max : longint);
var
i : longint;
begin
min := 1;
for i := 1 to n - 1 do min := min*10;
max := min*10 - 1
end;

Sonning har bir raqamini n-darajaga ko’tarish kerak bo’ladi, buning uchun esa darajaga ko’tarish prosedurasiga zarurat tug’iladi. Bu prosedura bizga oldingi masalalardan ma’lum:  
  Procedure extent(a, n : longint; var s : longint);
var
i : longint;
begin
s := 1;
for i := 1 to n do s := s*a
end;

Asosiy dasturda bittadan raqam ajratishga to’g’ri keladi, biz bu jarayon bilan ham tanishmiz (10 ga bo’lganda chiqqan qoldiq - oxirgi raqam, 10 ga butun bo’lish orqali oxirgi raqamni tashlab yuborgan holda sonni 10 baravar kamaytirish).
Har bir raqam darajaga ko’tariladi va natijalar qo’shiladi, so’ngra ko’rib chiqilayotgan son bilan solishtirish jarayoni olib boriladi, agar tenglik bajarilsa, unda ko’rib chiqilayotgan son - Armstrong sonidir.

       for x := min to max do
begin
p := x; s := 0;
for i := 1 to n do
begin
extent(p mod 10, n, k);
s := s + k;
p := p div 10
end;
if s = x then write(x, ' ')
end;

Dastur

Program L84; { Armstrong sonlari }
uses Crt;
var
n, min, max, x, p, s, i, k : longint;
Procedure extent(a, n : longint; var s : longint);
var
i : longint;
begin
s := 1;
for i := 1 to n do s :=  s*a
end;
Procedure minmax(n : longint; var min, max : longint);
var
i : longint;
begin
min := 1;
for i := 1 to n - 1 do min := min*10;
max := min*10 - 1
end;
begin
write('Sondagi raqamlar miqdorini kiriting'); readln(n);
writeln(n, '-xonali Armstrong sonlari');
minmax(n, min, max);
for x := min to max do
begin
p := x; s := 0;
for i := 1 to n do
begin
extent(p mod 10, n, k);
s := s + k;
p := p div 10
end;
if s = x then write(x, ' ')
end;
writeln
end.

 

85-misol. 1 dan n gacha bo’lgan sonlarning har biriga o’zining bo’luvchilarini chop etuvchi dasturni tuzing. Masalan, 1 5 7 35 lar 35 sonining bo’luvchilari. Shunga o’xshash bo’luvchilar ro’yxati 1 dan kiritilgan n gacha bo’lgan sonlar uchun chop etilishi kerak.

Algoritm

Dastur juda oson tuziladi. Buning uchun sonning bo’luvchilarini aniqlash prosedurasini tashkil etish (dasturni biz oldingi misollarda tahlil qilib chiqqan edik) va berilgan oraliqdagi har bir son uchun unga murojaat qilish kerak.
Quyidagi sodda dastur hosil bo’ladi. Bitta qo’shimcha. Prosedurada bo’luvchiar sonini aniqlashda sonning bo’luvchilari uning butun yarmigacha (n div 2) tekshiriladi, lekin biz bilamizki, sonning bo’luvchilari uning kvadrat ildizigacha bo’ladi va ularni trunc(sqrt(n)) gacha topgan edik. Bu faqatgina ko’rish maqsadida qilingan bo’lib - birinchi holda bo’luvchilar ekranga o’sib borish tartibida chiqariladi va bu chiroyliroq ko’rinadi.
Program L85;
uses Crt;
var
i, n : integer;
Procedure math_divisor(n : integer);
var
d : integer;
begin
for d := 1 to n div 2 do
if n mod d=0 then write(d, ' ');
writeln(n)
end;
begin
write('Oraliqning o’ng chegarasini kiriting'); readln(n);
for i := 1 to n do
begin
write( i, ' soning bo’luvchilari quyidagilar:');
math_divisor(i)
end
end.

86-misol. n soning to’g’ri boluvchilarining yig’indisini hisoblovchi prosedurani yozing. n soning to’g’ri bo’luvchilari deb o’zidan tashqari barcha bo’luvchilariga aytiladi. Masalan, agar n 12 ga teng bo’lsa, u holda to’g’ri bo’luvchilar yig’indisi 1 + 2 + 3 + 4 + 6 = 16. Ushbu prosedura ishining to’g’riligini tekshirish uchun berilgan [a; b]  oraliqdan n ning turli xil qiymatlarini hisoblab topuvchi asosiy dasturni yozing.

Program L86; { To’g’ri bo’luvchilar soni}
uses Crt;
var
i, a, b, s : integer;
Procedure math_divisor(n : integer;  var s : integer);
var
d : integer;
begin
s := 0;
for d := 1 to n div 2 do
if n mod d = 0 then s := s + d
end;
begin
write('1 dan katta bo’lgan oraliqning chap qismini kiriting '); readln(a);
write('Oraliqning o’ng qismini kiriting '); readln(b);
for i := a to b do
begin
math_divisor(i, s);
write(i 'sonining to’g’ri bo’luvchilari yig’indisi’,);
writeln(‘teng’,  s)
end
end.

87-misol. n natural soni bo’luvchilar soni toq bo’lgandagina aniq kvadrat hisoblanadi. Isbotlang.

Program L87; { Aniq kvadrat va bo’luvchilar soni }
uses Crt;
var
i, n, k : integer;
Procedure number_division(n : integer;  var k : integer);
var
d : integer;
begin
k := 0;
for d := 1 to n div 2 do
if n mod d = 0 then k := k + 1;
k := k + 1
end;
begin
write('Oraliqning o’ng qismini kiriting '); readln(n);
for i := 1 to n do
begin
write( i*i, ' soning bo’luvchilar soni= ');
number_division(i*i, k);
write(k);
if k mod 2 <> 0  then writeln(' – toq son')
else writeln(' – juft son')
end
end.

88-misol. Kitob betlarini nomerlash. Kitobdagi barcha betlarini nomerlash uchun nechta raqam kerak bo’lishini aniqlovchi dastur tuzing. 

Yechish

Matematik yechimni xususiy misolda ko’rib chiqamiz, so’ngra esa umumiy xulosa chiqaramiz.
Bizga 357 ta betni nomerlash uchun kerak bo’ladigan raqamlar sonini aniqlash zarur bo’lsin.
Mulohazalar quyidagichadir: bir xonali raqamlar 9 ta, demak ular 9 betni nomerlashadi; ikki xonali sonlar 90 ta - ular 90 ta betni nomerlashadi va 90 . 2 = 180 ta raqamdan foydalanishadi; uch xonali sonlar  900 ta - ular 900 ta betni nomerlab 2700 ta raqamdan foydalanishadi. Demak, berilgan 357 ta betni nomerlash uchun barcha bir xonali va ikki xonali sonlar va uch xonalilarning ma’lum bir qismi kerak bo’ladi. Nechta uch xonali son kerak bo’lishini aniqlash uchun berilgan sondan “ishlatilgan” bir xonali va ikki xonali sonlarni ayirib tashlash kerak: 357 - (9 + 90) = 258.
Shunday qilib, bizga hammasi bo’lib shuncha raqam kerak bo’ladi: 9*1=9 90*2=180 258*3=774 .....

. . . . . . . . . . .
Jami: 9 + 180 + 774 = 963 raqam.
Endi mulohazalarimizni umumlashtiramiz. c raqamdan iborat n betlar soni berilgan bo’lsin. U holda nomerlash uchun quyidagi raqamlar kerak bo’ladi:
1 - xonalilarga; kerak bo’ladiganlari:     9 x 1 = 9 ta raqam;
2 - xonalilarga;                                    90 x2 = 180 ta raqam;
3 - xonalilarga;                                    900x3 = 2700 ta raqam;
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
c-1 -xonalilarga;                            9....0 (c-1)  . . .  ta raqam,
huddi 357 ta betni nomerlashda uch xonalilarning ma’lum bir qismigina kerak bo’lganligi kabi, c-xonali sonni yozish uchun kerak bo’ladigan raqamlarning hammasi ko’plik qiladi.
c-xonali sonni yozish uchun qancha raqamlar kerak  bo’lishini aniqlash maqsadida berilgan sondan ishlatilib bo’lingan bir, ikki,

n-(9+90+900+9.....0) uch va h.k,. c-1 xonalilarning raqamlarini ayirib tashlash kerak: so’ngra olingan natijani sonning xonasi - c ga ko’paytirish kerak. Sarf bo’lgan raqamlarni qo’shib, biz yakuniy qiymatga ega bo’lamiz.
Ushbu mulohazalar asosida dastur tuzib ko’ramiz.
Avvalambor, kiritilgan betlar sonida nechta raqam borligini aniqlovchi prosedurani tuzaylik. Bunday dasturga biz oldin ham duch kelganmiz: 
  
Procedure number(n : integer; var k : integer);
begin
k := 0;
repeat
k := k + 1;
n := n div 10
until n = 0
end;

Keyingi prosedurada qidirilayotgan raqamlar soni joylashadi. Unda, m o’zgaruvchi raqamlar sonini bir, ikki, uch, c-xonali sonlarda (9, 90, 900, ..., 9...0) ifodalashga xizmat qiladi.
c o’zgaruvchi sonda - betning nomerida mavjud raqamlar sonini ko’rsatiadi, z o’zgaruvchida qidirilayotgan natija to’planib boriladi, s yig’indi esa bizga hisoblash uchun jami nechta n-xonali son ishlatilganini ifodalaydi. 
Boshlang’ich qiymatlar: m := 9; z := 0; s := 0, sondagi raqamlar soni esa  number(n, c) prosedurasidan olinadi va c o’zgaruvchiga beriladi: 
m := 9; number(n, c); z := 0; s := 0;
Endi sikl  kiritilgan betlar sonining 1 dan c-1 gacha bo’lgan raqamlar miqdori bo’yicha bo’ladi. Sikl o’zgaruvchisi i.

              for i := 1 to c - 1 do
begin
z := z + m*i; {Raqamlar yig’indisi}
s := s + m;
m := m*10
end;

Siklda raqamlar yig’indisi (z := z + m*i), foydalanilgan bir xonali, ikki xonali va h.k raqamlarning yig’indisi hisoblanadi.
Sikl tugatilganidan so’ng z yig’indiga qolgan c-xonali raqamlar qo’shiladi:
z := z + (n - s) xc {n - s qolgan c-xonadan iborat raqamli betlar}

Prosedura

  Procedure Page(n : integer; var z : integer);
var
i, m, c, s : integer;
begin
m := 9;
number(n, c); z := 0; s := 0;
for i := 1 to c - 1 do
begin
z := z + m*i; {Raqamlar yig’indisi}
s := s + m;
m := m*10
end;
z := z + (n - s)*c
end;

Va nihoyat, dasturning to’la ko’rinishi:

Program L88; { Betlarni nomerlash uchun kerak bo’ladigan raqamlar soni }
uses Crt;
var
n, c : integer;
Procedure number(n : integer; var k : integer);
begin
k := 0;
repeat
k := k + 1;  n := n div 10
until n = 0
end;
Procedure Page(n : integer; var z : integer);
var
i, m, c, s : integer;
begin
m := 9; number(n, c); z := 0; s := 0;
for i := 1 to c - 1 do
begin
z := z + m*i; {Raqamlar yig’indisi}
s := s + m;  m := m*10
end;
z := z + (n - s)*c {n - s qolgan c-xonadan iborat raqamli betlar }
end;
begin
write('Betlar sonini kiriting'); readln(n);
page(n, c);
writeln('Nomerlash uchun zarur bo’ladigan raqamlar soni=', c)
end.

108-misol. Ko’llar zanjiri bo’ylab oq g’ozlar galasi uchib ketmoqda edi. Har bir ko’lga g’ozlarning yarmi va yana yarim g’oz qo’nar edi, qolganlari esa yo’llarini davom ettirishardi. Barcha g’ozlar yettita ko’lga qo’nishdi. Galada nechta g’oz bor edi?

Yechim

Matematik usulda bu masala og’zaki ravishda ancha qiziq usul bilan yechiladi.
Oq g’ozlar galasi bilan birga yana bir kulrang g’oz uchmoqda deylik. Agar ma’lum bir ko’lga m ta oq va kulrang g’oz uchib kelsa, u holda bu ko’lga m/2+1/2=(m+1)/2-kulrang bilan birgalikda barcha g’ozlarning teng yarmi qo’nadi. Shuning uchun har bir ko’ldan keyin uchayotgan g’ozlar soni teng ikkiga kamayadi. Yetti ko’ldan keyin u  27 = 128 marta kamayadi, osmonda esa faqatgina kulrang g’oz qoladi. Demak boshida 128 ta g’oz bo’lgan, ulardan 127 tasi-oq.
Endi masalani yechish uchun quyidagi mulohazalarni keltiraylik.
xk orqali oldinda k ta ko’l bo’lganda, osmonda uchayotgan oq g’ozlar sonini belgilaymiz. U holda masalaning sharti quyidagicha yoziladi


Bu yerdan (xk) ketma-ketlik uchun rekurrent munosabat hosil qilamiz

Buni bilgan holda rekursiv prosedurani tuzish oson:
Procedure goose(x, k : integer);
begin
if k = 1 then writeln(x) else goose(2*x + 1, k - 1)
end;

Proseduraga atiga ikkita o’zgaruvchi kiritiladi: x-qidirilayotgan g’ozlar soni; k-ko’llar soni. Prosedura g’ozlar 7 ta ko’ldan uchib o’tganligiga asoslanib tuzilgan, demak boshlang’ich qiymat sifatida  x uchun 1, k uchun 7 qiymat kiritish kerak. Prosedurada k soni 1 ga kamayishi kerakligi hisobga olingan bo’lib, prosedurani tugatishning tayanch sharti k ning 1 ga teng bo’lishidir, bundan keyin esa ekranga g’ozlar sonining qiymatini chiqarish kerak:
if k = 1 then writeln(x)
Tayanch shart boshqacha ham bo’lishi mumkin, agar k ning boshlang’ich qiymati 1 ga teng bo’lsa, u holda proseduraga takroran murojaat qilishda k ning qiymatini 1 ga kamaytirmasdan, oshirish kerak (k + 1), bu holda tayanch shart bo’lib k = 7 hisoblanadi.

 

Quyida bu masalani yechishning tugallangan dasturi keltirilgan:

Program L108;
uses Crt;
var
k : integer;
Procedure goose(x, k : integer);
begin
if k = 1 then write(x) else goose(2*x + 1, k - 1)
end;
begin
write('Ko’llar sonini kiriting'); readln(k);
write('Galada');
goose(1, k);
writeln(' ta g’oz bor edi')
end.

Ushbu mulohazalarga amal qilgan holda quyidagi masalani yeching.

Mustaqil yechish uchun vazifa

109-misol. Studentlar oqimi 5 marta bir xil oraliq topshirgan (oraliq topshira olmaganlar keyingi kuni kelishar edi). Har kuni kelgan studentlarning uchdan bir qismi va yana bir stundentning uchdan bir qismi oraliqni yaxshi topshirardi. 5 martada ham oraliq topshirmagan studentlarning eng kam soni qancha? 

Agar masalalar arifmetik yoki geometrik progressiyalar, umuman n-hadi formulalari hamda rekurrent munosabatlar bilan berilgan ketma-ketliklar (ularga keyinroq qaytamiz) bilan bog’liq bo’lsa, u holda rekursiv proseduralarni tuzish oson.
Quyida rekursiv prosedurali yana bir nechta dasturlar keltirilgan.

Avval, jiyan n-tug’ilgan kunda necha pul olishini hisoblovchi dasturni tuzaylik. 
Yana rekursiv prosedurani tuzib ko’ramiz, lekin masalani boshqa tomonlama ham yechish mumkin.
Belgilash kiritamiz: k – jiyan yoshining soni , p – amakisi har tug’ilgan kunda beradigan pullar qiymati, s - jiyan umri davomida olgan pullarning qiymati, n dan (n foydalanovchi tomonidan kiritiladi) to 1 gacha teskari tartibda hisoblaydigan tug’ilgan kunlar soni hisoblagichi.
Prosedura

    Procedure uncle(k, p, s, n : longint); {uncle – amaki}
begin
if n = 1 then write(s)
else
begin
k := k + 1;
p := 2*p + k;
uncle(k, p, s + p, n - 1)
end
end;

Proseduraning rasmiy parametrlariga boshlang’ich qiymatlar beriladi: k:=1; p:=1; s:=1;  n – foydalanovchi tomonidan asosiy dastur orqali kiritiladi (e’tibor bergan bo’lsangiz, bu prosedurada oldingisidagidek chiquvchi parametrlar va proseduraning o’zida o’zgaruvchilar yo’q, lekin bu holatni o’zgartirish mumkin). 
Yoshlar soni ortib boradi: k := k + 1; k-nchi tug’ilgan kunga berilgan sovg’a miqdori hisoblanadi:  p := 2*p + k; s olingan pullar yig’indisini p ga orttiradigan va tug’ilgan kunlar sonini 1 ga kamaytiradigan prosedura chaqiriladi:
uncle(k, p, s + p, n - 1)
So’ngra n 1 ga teng bo’lib qolmagunicha butun jarayon takrorlanadi.
Dastur

Program L110; { rich man - boy}
uses Crt;
var
n : integer;
Procedure uncle(k, p, s, n : longint); {uncle - amaki}
         begin
if n = 1 then write(s)
else
begin
k := k + 1;
p := 2*p + k;
uncle(k, p, s + p, n - 1)
end
end;
begin
write('Jiyanning yoshlar sonini kiriting'); readln(n);
write('Men', n, '-chi tug’ilgan kunimga ');
uncle(1, 1, 1, n);
writeln(' dollar olaman')
end.

Shartning ikkinchi qismida olingan pullar yig’indisi 100 dollarga teng bo’lganda yoki 100 dollardan oshib ketganida yoshlar sonini aniqlash kerak. Buning uchun prosedurada tayanch sharti o’zgaradi: if  s >= 100  then write(n), qolgan hamma narsa esa o’zgartirilmaydi.

Program L110a;
uses Crt;
var
n : integer;
Procedure uncle1(k, p, s, n : longint);
begin
if s >= 100  then write(n)
else
begin
k := k + 1;
p := 2*p + k;
uncle1(k, p, s + p, n + 1)
end
end;
begin
write('Sovg’aning yig’indisi ');
uncle1(1, 1, 1, 1);
writeln(' –chi tug’ilgan kunda 100 dollardan oshadi')
end.

Keyingi masalalar shu tarzda yechiladi, shuning uchun ularni o’zingiz mustaqil yeching. Rekursiv proseduralardan foydalaning.

111-misol. Har kuni Bilmasvoy oldingi ikki kunda o’rganilgan chet tillaridagi so’zlari yig’indisining yarmini va yana ikkita so’zni o’rganadi. Bilarvoyning fikricha, Bilmasvoyning kuchi kuniga 50 ta so’z o’rganish kerak bo’lganida butunlay yetmay qoladi. Bilmasvoy birinchi ikki kunda bittadan so’z o’rgangan bo’lsa, uning kuchi necha kundan keyin butunlay tugab qolishini hisoblovchi  dastur yozing.

 

Program L111; { ignoramus – nodon, bilimsiz}
uses Crt;
Procedure expert(n1, n2, n : integer); {expert - bilimdon}
var
a : integer;
begin
if n2 = 50 then write(n)
else
begin
a := n1;
n1 := n2;
n2 := (a + n2) div 2 + 2;
expert(n1, n2, n + 1)
end
end;
begin
write('Bilmasvoyning kuchi');
expert(1, 1, 1);
writeln(' kundan keyin tugaydi')
end.

112-misol. Kumush navbatdagi kitobni talqin etayotgan paytda, o’qilgan betlar nomerlarining yig’indisini hisoblab ko’rdi. Bu yig’indini Q orqali belgilaymiz. Oxirgi o’qilgan betning nomerini aniqlovchi dastur yozing.
Program L112;
uses Crt;
var
q : integer;
Procedure page(n, q, s : integer);
begin
if s >= q then writeln(n - 1)
else  page(n + 1, q, s + n)
        end;
{----------------------------------------------------------------------------------------}
begin
write('O’qilgan betlar nomerlarining yig’indisini kiriting ');  readln(q);
write('Kumush o’qigan oxirgi betning nomeri');
page(1, q, 0)
end.

 

113-misol. Qurbaqa har kuni oldingi kunga qaraganda 20% ko’proq va yana 2 ta chivin yeydi. Agar qurbaqa birinchi kunda 12 ta chivin yegan bo’lsa, u holda necha kundan keyin yeyilgan chivinlar  soni 100 tadan oshishini aniqlovchi dastur tuzing.  

Program L113; { frog - qurbaqa }
uses Crt;
Procedure frog(n : real; k : integer);
begin
if trunc(n) > 100  then write(k)
else frog(n + 0.2*n + 2, k + 1)
end;
begin
write('Qurbaqa ');
frog(12, 1);  writeln('kuni 100 tadan ko’proq chivin yeydi')
end.

Mustaqil yechish uchun vazifa

114-misol. Vinni Pux har tug’ilgan kunda oldingi 2 ta tug’ilgan kunida yeyilgan ovqatni yeydi. Pyatachok va Quyonning birinchi ikkita tug’ilgan kunida u 100 g ovqat yedi. Vinni Pux 15-chi tug’ilgan kunda necha kilogramm ovqat yeyishini aniqlovchi dasturni tuzing.

115-misol. Bir hujayrali amyoba har 3 soatda 2 ta hujayraga bo’linadi. 3,6,9,12,…,24 soatdan keyin nechta hujayra bo’lishini aniqlovchi dastur tuzing.

Program L115;
uses Crt;
var
i : integer;
{----------------------------------------------------------------------------------------}
Procedure ameba(n, i, k : integer); {Amyobaning bo’linishi}
begin
if k = i then write(' ', n, ' ')
else ameba(2*n, i, k + 3)
end;
{----------------------------------------------------------------------------------------}
begin
writeln(‘3, 6, 9, ..., 24 soatdan keyin hujayra soni');
i := 0;
repeat
i := i + 3;
ameba(1, i, 0)
        until i = 24;
writeln;
end.

Mustaqil yechish uchun vazifa

116-misol. Sportchi mashg’ulotlarni boshlagandan so’ng, birinchi kuni 10 km yugurdi. Har kuni u kunduzgi normani oldingi kun normasiga qaraganda 10% ga oshirar edi. Sportchi 7 kunda jami qancha yo’lni yugurib o’tadi.  

Dasturni tuzish uchun rekursiv prosedura qo’llanilishi kerak bo’lgan yanada qiyinroq masalani ko’rib chiqaylik.

117-misol. Katta sonlarni bir-biriga ko’paytirish natijasida xotira to’lib qolishi  mumkin. Shuning uchun, berilgan butun tur (integer yoki longint) ning eng katta chegaraviy sonidan oshib ketuvchi ko’paytmani chop etish maqsadida tabiiy vositalardan foydalanish kerak.
Eng katta chegaraviy sondan oshib ketuvchi ikki son ko’paytmasini chop etish uchun dastur tuzamiz.

Yechish

Multiplication prosedurasu a sonini b soninig birlar xonasidagi raqamidan boshlab, har bir raqamiga ko’paytirib chiqamiz. Xotirada mavjud bo’lgan  ko’paytmasiga qo’shishdan olingan ko’paytmaning oxirgi raqami chop etiladi, qolgan raqamlar esa xotiraga kiritiladi - multiplication prosedurasiga rekursiv murojaat etishda o’zgaruvchilar sifatida qabul qilinadi. Oxirida  b soning birinchi (chap) raqamiga ko’paytirish jarayoni amalga oshiriladi. Shu bilan ko’paytirish tugaydi. U holda natijaning boshi - oxirgi raqamini hisobga olmagan holda (s div 10) to’plangan  ko’paytma, undan keyin esa rekursiyadan qaytishda- ko’paytmaning qolgan barcha raqamlari (s mod 10) rekursiyaga kirish paytida ularning hisoblanishiga nisbatan teskari tartibda chop etiladi.  

Program L117; { Katta ko’paytma }
uses Crt;
var
x, y : longint;
{----------------------------------------------------------------------------------------}
Procedure multiplication(a, b, s : longint);
begin
if b <> 0 then
begin
s := s+a*(b mod 10);
multiplication(a, b div 10, s div 10);
write(s mod 10:1)
end
else if s <> 0 then write(s)
end;
{----------------------------------------------------------------------------------------}
begin
write('Birinchi ko’paytuvchini kiriting '); readln(x);
write(‘Ikkinchi ko’paytuvchini kiriting '); readln(y);
write(x,'*',y:1,' = ');
if ((x < 0) and (y > 0)) or ((x > 0) and (y < 0)) then write('-');
multiplication(abs(x), abs(y), 0);
writeln
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.Дагене В.А. и др. 100 задач по программированию: Кн. для учащихся: Пер. с лит./В.А. Дагене, Г.К. Григас, К.Ф. Аугутис. - М.: Просвещение, 1993.Джонс Ж., Харроу К. Решение задач в системе Турбо Паскаль/Пер. с англ.; Предисл. Ю.П. Широкого. - М.: Финансы и статистика, 1991.

Епанешников А., Епанешников В. Программирование в среде Turbo Pascal 7.0. - м.: "ДИАЛОГ-МИФИ", 1993.

Есаян В.И. Ефимов, Л.П. Лапицкая и др Информатика. Учеб. пособие. для пед. спец. высш. учеб. заведений/А. Р.. - М.: Просвещение, 1991.

Журналы "Информатика и образования", 1986-1994 гг. 17. Журналы "Квант", 1986-1994 гг.

Заварыкин В. М. и др. Численные методы: Учеб. пособие для студентов физ.-мат. спец. пед. ин-тов/В.М. Заворыкин, В.Г. Житомирский, М.П. Лапчик. - М.: Просвещение, 1990.

Зубов В. С. Программирование на языке Turbo Pascal. "Фтлинъ". Москва. 1997г.

Офицеров Д.В., Старых В.А. Программирование в интегрированной среде Турбо-Паскаль: Справ. пособие. - Мн.: Беларусь, 1992.

Очков В. Ф., Пухначев Ю.В. 128 советов начинающему программисту. - М.: Энергоатомиздат, 1991.

Перминов О. Н. Программирование на языке Паскаль. "Радио и связь". Москва, 1988 г.

Скопец и др. Дополнительные главы по курсу математики. Учеб. пособие по факультативному курсу для учащихся 10 кл. Сборник статей. Сост. З.А.. Изд. 2-е, перераб. М., "Просвещение", 1974.

Тарасов Л.В. Мир, построенный на вероятности: Кн. для учащихся. - М.: Просвещение, 1984.

Тумасонис В., Дагене В., Григас Г. Паскаль. Руководства для программиста: Справочник: Пер. с литовск. - М.: Радио и связь, 1992.

Фаронов В. В. Турбо Паскаль (в 3-х книга). Книга 1. Основы Турбо Паскаля. - М.: Учебно-инженерный центр "МВТУ-ФЕСТО ДИДАКТИК", 1992.

Федоров А., Рогатин Д. Borland Pascal в среде Windows. "Диалектика", Киев, 1993 г.

3341 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
счетчик посещений