Сайт підготовки до олімпіади з інформатики

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

Приклад 1

Дано послідовність з N чисел, котра містить різні числа від 0 до N. Визначити, якого числа не існує в  даній послідовності.

1 спосіб.

Посортувати і відшукати  різницю, рівну два між сусідніми елементами.

n=5

0 2 1 5 3

0 1 2 3 5

4

2 спосіб.

Перевірити, чи  існує кожне з чисел від 0 до N у послідовності, використовуючи два вкладених цикли.

3 спосіб.

Скористатися формулою суми арифметичної прогресії.

Приклад:

N=5;

Послідовність А[1..N]  4 2 3 0 5

Сума елементів послідовності рівна S1=4+2+3+0+5=14

Сума арифметичної прогресії (0..N) 0 1 2 3 4 5 згідно з формулоюS=(A_n+A₁)*n/2

S2=(5+0)*15/2

Результат R=S2-S1=15-14=1

Отже, не існує числа 1.

Приклад 2

                Аналогічний приклад можна навести і на більш складніший числовий ряд чисел Фібоначі.

Спосіб 1

Кожне наступне знаходити як суму двох попередніх.

1 1 2 3 5 8 ...

k1 перше число

k2 друге число

k3:=k1+k2;

k1:=k2;

k2:=k3;

Спосіб 2

Використаємо рекурентну формулу  чисел Фібоначі.

http://e-maxx.ru/algo/fibonacci_numbers

Кожне число Фібоначі знаходять за формулою:

x^y exp(y*ln(x))

Приклад 3

Перестановка значення змінної місцями

a,b 2,3 3,2

c=a;a=b;b=c;

c=2;a=3;b=2;

a=a+b; b=a-b; a=a-b;

a=5;b=5-3=2;a=5-2=3;

2.    Розгалуження

Приклад 3

Скласти програму знаходження найбільшого з трьох чисел a,b,c, введених з клавіатури.

Існують різні способи розв’язку даного завдання

1 спосіб 

var a,b,c,max:integer;

begin

readln(a,b,c);

if (a>=b && a>=c) max=a;

if (b>=a)and(b>=c) then max:=b;

if (c>=a)and(c>=b) then max:=c;

writeln(max);

end.

2 спосіб

Вкладені розгалуження

IF умова THEN IF умова THEN оператори ELSE оператори ELSE оператори

var a,b,c,max:integer;

begin

readln(a,b,c);

if a>b then if a>c then max:=a else max:=c else if b>c then max:=b else max:=c;

writeln(max);

end.

3 спосіб

var a,b,c,max:integer;

begin

readln(a,b,c);

max:=a;

if b>max then max:=b;

if c>max then max:=c;

writeln(max);

end.

Третій спосіб найраціональніший

C++

max(a, max(b,c);

3.   Цикл

Приклад 3

                Знайти найбільший спільний дільник

 (HCD)  a,b,

 HCD(0,0)=0

 HCD(a,0)=(a)

HCD(а,в)=HCD(b,r₁)=HCD(r₁,r₂)=HCD(r_n-1,r_n)=|rn-1|, де r_і- остача від ділення?

 Знайти найменше спільне кратне (HCD) цілиx чисел аШ0,вШ0

                HCK(a,b)=a*b/HCD(a,b)

 HCD(а,в)=HCD(b,r1)=HCD(r1,r2)=HCD(rп-1,rn)=|rn-1| 

     4.Знайти досконалі числа на проміжну [1,n].

6=1+2+3 (досконале - рівне сумі всіх своїх дільників, крім останнього)

45 15  ------- 2 3 4 5 6 7 8 9 10 11 12 13 14 15

45 % 15=0

15

15 25

1. b

15%25=25

25 % 15=10

15 %10 =5

10%5=0

5

0

while (b>0)

{temp=a%b;

a=b;

b=temp;

}

nsd=a

Алгоритм Евкліді

Приклад 4

Знайти дільники числа.

Знайти кількість дільників числа.

Практикум

$11.   Фібоначі

Турнір «Методика складання алгоритмів – 24» Задача B

$12.   НСД.

https://www.e-olymp.com/uk/problems/137

https://www.e-olymp.com/uk/problems/136

https://www.e-olymp.com/uk/problems/7239

https://www.e-olymp.com/uk/problems/4742

https://www.e-olymp.com/ru/problems/4283