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

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:
2^p - 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 hisoblovchiprosedura (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.