Olimpiada misollarini yechish usullari II- bosqich Muallif: Mengliyev Sh. Qo`shilgan sana: 2015-04-08 Olimpiada misollarini yechish usullari II – bosqich

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: