asyan.org
добавить свой файл
1 2 ... 5 6
Готуємося до олімпіади 2008-2009

Тематика підготовки

1. Базові структури алгоритмів:

- слідування (запис арифметичних виразів, використання операцій DIV i MOD)

Задача 1. Записати трицифрове число в зворотному порядку.

program pr1;

var n,c1,c2,c3,m:integer;

begin

readln(n);

c3:=n mod 10;

c2:=n div 10 mod 10;

c1:=n div 100 mod 10;

m:=c1+c2*10+c3*100;

writeln(m);

end.

- розгалуження (запис умови, логічні операції AND, OR)

Задача 2. Коло на площині задане координатами центру і радіусом. Прямокутник заданий координатами верхнього лівого і нижнього правого кутів, сторони прямокутника паралельні осям координат. Перевірити, чи лежить коло цілком усередині прямокутника і навпаки

program PR2;

var x1,y1,x,y,x2,y2,r:real;

begin

readln(x,y,r,x1,y1,x2,y2);

if (x-x1

writeln('kolo vseredyni');

if (sqr(x1-x)+sqr(y1-y)<=sqr(r))and(sqr(x2-x)+sqr(y2-y)<=sqr(r))then

writeln('prjfmokutnyk vseredyni');

end.

- цикл (FOR, WHILE, REPEAT), числові ряди (арифметична, геометрична прогресії, прості числа, числа Фвбоначі, числа Каталана)

Задача 3. Скількома способами можна піднятись на N сходів, якщо можна підніматися по одній і через одну сходинку (числа Фібоначі).

program pr3;

var k1,k2,k3,n,i:integer;

begin

readln(n);

k1:=1;

k2:=1;

for i:=2 to n do begin

k3:=k1+k2; k1:=k2; k2:=k3;

end;

writeln(k2);

end.

- підпрограми (процедури, функції, рекурсія)

Задача 4. Скількома способами можна правильно розставити 2*N дужок (числа Каталана )

program pr4;

var n:integer;

k:longint;

function f(i:integer):longint;

begin

if i=1 then f:=1 else f:=i*f(i-1);

end;

begin

readln(n);

k:=f(2*n) div (f(n)*f(n+1));

writeln(k);

end.

^ 2. Структуровані типи даних (масиви, рядки, файли)

Задача 5. З файлу зчитуються рядки тексту, що складаються з слів, що закінчуються символом # і містять лише великі латинські літери. Підрахувати кількість різних слів в тексті.

^ PROGRAM PR5;

var ch:char;

s:array[1..1000] of string[50];

f1,f2:text;

n,i:integer;

poisk:boolean;

begin

assign (f1,'text.txt');

reset(f1);

n:=0;

poisk:=true;

while not(eof(f1)) do begin

read(f1,ch);

if ch in ['A'..'Z'] then begin

if poisk then n:=n+1;

s[n]:='';

while ch in ['A'..'Z'] do begin s[n]:=s[n]+ch;read(f1,ch); end;

end;

poisk:=true;

for i:=1 to n-1 do

if s[n]=s[i] then poisk:=false;

end;

if not(poisk) then n:=n-1;

close(f1);

assign(f2,'rez.txt');

rewrite(f2);

writeln(f2,n);

close(f2);

end.


3. Методика складання алгоритмів та їх аналіз (обчислювальна геометрія, довга арифметика, комбінаторні об’єкти і повний перебір, методи пошуку і сортування, теорія графів (пошук в глибину, ширину, жадібні алгоритми))

Задача 6. В таблиці розміром N*N, де N<13, клітинки заповнені випадковим чином цифрами від 0 до 9. Запропонувати алгоритм, який дозволяє знайти шлях із клітинки (1,1) в клітинку (N,N) і які задовольняють наступні умови:   

1. будь-які дві послідовні клітинки в шляхові мають спільну сторону; 
2. кількість клітинок шляху мінімальна; 
3. сума цифр в клітинках шляху  максимальна.

program pr6;

const n=8;

var a:array[0..13,0..13] of byte;

i,j:integer;

begin

randomize;

for i:=1 to n do begin

for j:=1 to n do begin

a[i,j]:=random(10); write(a[i,j],' ');

end;

writeln;

end;

for i:=1 to n do

for j:=1 to n do

if a[i-1,j]>a[i,j-1] then a[i,j]:=a[i,j]+a[i-1,j] else a[i,j]:=a[i,j]+a[i,j-1];

for i:=1 to n do begin

for j:=1 to n do begin

write(a[i,j],' ');

end;

writeln;

end;

i:=1;j:=1;

write(i,',',j,' ');

while (i<>n) or (j<>n) do begin

if a[i+1,j]>a[i,j+1] then i:=i+1 else j:=j+1;

write(i,',',j,' ');

end;

writeln;

end.

Задача 7. Аналогічна до задачі6. Але з заданої клітинки i,j набрати найбільшу суму за k ходів.

Задача 8. Пошук шляху в лабіринті (метод зафарбовування клітинок).

Задача 9. Пошук шляху в графі (рекурсивний пошук).
ІІ ЕТАП ВСЕУКРАЇНСЬКОЇ УЧНІВСЬКОЇ ОЛІМПІАДИ З ІНФОРМАТИКИ, 2007-2008 Н.Р.

Теоретичний тур
1. Числа (NUMBER) - 20 балів

Знайдіть перші десять пар натуральних чисел K и N таких, щоб сума натуральних чисел менших K рівна сумі чисел більших K і менших або рівних N.

Наприклад 6 і 8: 1+2+3+4+5 = 7+8

Розв’язок

Сума арифметичної прогресії (1..N) згідно з формулою,

, . Пошук здійснюємо в циклах по k i n.



следующая страница >>