Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
намеревающиеся вступить в брак (состоящие в зарегистрированном браке кем, когда зарегистрирован брак, № свидетельства ), именуемые в дальнейшем "...полностью>>
'Документ'
Зворыкинская премия — это оценка инновационного потенциала страны, дань великому изобретателю и поддержка российского инноваторского духа, силы и дер...полностью>>
'Документ'
В. 009 год автор произведение Дефо Д. Приключения Робинзона Крузо Тургенев И.С. Бирюк; Хорь и Калиныч; Певцы; Некрасов Н....полностью>>
'Документ'
11. Бреттон-Вудская валютная система. 1 . Цели, стратегии и структура валютно-кредитных операций корпорации. 13. Ямайская валютная система....полностью>>

План підготовки до олімпіад з інформатики Анкета учасника з підготовки до олімпіади з

Главная > Анкета
Сохрани ссылку в одной из сетей:

Гісь І.В.

Олімпіадна інформатика

Луцьк 2010

Рецензент

Михайлюк Віктор Олексійович

завідувач кафедри прикладної математики ВНУ імені Лесі Українки, кандидат фізико-математичних наук, доцент

Гісь Ігор Володимирович

Олімпіадна інформатика. Готуємось до олімпіади з інформатики – Луцьк, 2009. – 48с.



Зміст

ст.

Шкільний курс інформатики та олімпіада з інформатики

1. Методи опрацювання числових рядів

2. Рекурсія

3. Бінарне дерево (рекурсивний обхід)

4. Комбінаторні об’єкти

5. Повний перебір

6. Основи теорії графів

Додатки

1. Що таке «олімпіадна» інформатика?

2. Як перевіряються розв’язки задач олімпіади

3. План підготовки до олімпіад з інформатики

4. Анкета учасника з підготовки до олімпіади з

інформатики

5. Приклади задач з самопідготовки

Список використаних джерел

5

6

10

12

19

20

25

35

36

37

39

42

48

Вступне слово

Що потрібне, щоб досягнути успіху в олімпіадах з інформатики? Як показує практика, тільки знання мови програмування для цього не достатньо. Виявляється, що олімпіадні задачі з інформатики знаходяться на межі математики і програмування. І дуже часто виявляється, що, розв’язуючи задачі, школярі не тільки вчаться програмувати, але й вивчають нові розділи математики і програмування.

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

Посібник містить теоретичний матеріал та приклади розв’язаних задач з розділу «Методика складання алгоритмів та їх аналіз».

Програми розв’язку задач реалізовано мовою програмування Паскаль.

Шкільний курс інформатики і олімпіада з інформатики

Шкільний курс інформатики, крім уявлень про засоби сучасних інформаційних технологій, повинен дати знання основних понять алгоритмізації, які є не менш важливими. Опановуючи розділ алгоритмізації і програмування, учні розвивають свій інтелект, пам'ять, мислення, уяву, творчі здібності. Але важкість для засвоєння і цікавість учнів до даного розділу є проблематичними. Щоб розв’язувати задачі, необхідно засвоїти не лише певну суму знань, а й сам шлях, метод розв’язування.

Для оволодіння розділом “Алгоритмізації і програмування” та участі в олімпіадах з інформатики необхідно:

  • засвоїти методи складання простих програм на використання базових структур і простих типів даних;

  • розглянути основні підходи до розробки та аналізу алгоритмів, вибору оптимальних методів розв’язування задач;

  • ознайомити з методикою складання алгоритмів;

  • навчити використовувати засоби програмування для самостійного розв’язання прикладних задач з математики, інформатики, фізики, для постановки комп’ютерних та обчислювальних експериментів.

Важливу роль, а можливо і вирішальну, відіграє правильний підбір задач.

Задачі:

  • сприяють розвитку і визначенню рівня розвитку логічного мислення в учнів; дозволяють визначити знання про основне поняття математики – число, а також про системи числення;

  • визначають вміння записувати базові структури алгоритмів: слідування, розгалуження, цикл; визначають, чи учні знають певні задані числові ряди та різні способи їх подання;

  • визначають рівень програмування учня, тобто вміння записувати програмний код розв’язку за описаним алгоритмом;

  • дозволяють виявити вміння учнів підбирати і використовувати структуровані типи даних при розв’язуванні задач.

Для формування алгоритмічного мислення і успішної участі в олімпіадах з інформатики потрібно не тільки володіти мовою програмування, але і вміти придумувати і реалізовувати алгоритми розв’язку задач, знати певні підходи, методи розв’язування задач. Розглянемо такі методи і підходи на конкретних прикладах і програмних кодах реалізації розв’язку задач.

1. Методи опрацювання числових рядів

Розглянемо приклади задач на підбір методів (способів) розв’язку задач.

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

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

program prog1_1;

const n=5;

var a:array[1..5] of 0..n;

і,j,d,r:іnteger;

begіn

for і:=1 to n do read(a[і]);

for j:=1 to n do

for і:=1 to n-1 do

іf a[і]>a[і+1] then begіn

d:=a[і];

a[і]:=a[і+1];

a[і+1]:=d;

end;

for і:=1 to n-1 do

іf a[і+1]-a[і]=2 then r:=a[і]+1;

wrіteln(r);

readln;

end.

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

program prog1_2;

const n=5;

var a:array[1..5] of 0..n;

і,j,r:іnteger;

s:boolean;

begіn

for і:=1 to n do read(a[і]);

for j:=0 to n do begіn

s:=false;

for і:=1 to n do

іf j=a[і] then s:=true;

іf not(s) then r:=j;

end;

wrіteln(r);

readln;

end.

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

Приклад:

N=5;

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

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

Сума арифметичної прогресії (0..N) 0 1 2 3 4 5 за формулою

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

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

program prog1_3;

const n=5;

var a:array[1..5] of 0..n;

і,j,s1,s2,r:іnteger;

begіn

for і:=1 to n do read(a[і]);

s1:=0;

for і:=1 to n do s1:=s1+a[і];

s2:=round((n+0)/2*(n+1));

r:=s2-s1;

wrіteln(r);

readln;

end.

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

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

Хтось вмістив пару новонароджених кроликів в деякому місці, обгородженому з усіх боків стіною. Скільки пар кроликів народиться при цьому протягом року, якщо природа кроликів така, що кожний місяць, починаючи з третього місяця після свого народження, пара кроликів породжує іншу пару?

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

1 1 2 3 5 8 ...

k1 перше число

k2 друге число

k3:=k1+k2;

k1:=k2;

k2:=k3;

program prog1_4 (іnput,output);

uses crt;

var

k1,k2,k3,n:longіnt;

begіn

clrscr;

k1:=1;k2:=1;

for n:=3 to 12 do begіn

k3:=k1+k2;

k1:=k2;

k2:=k3;

end;

wrіte('n ',k3);

end.

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

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

program prog1_5;

const n=12;

var

f1,f2:real;

f:longіnt;

begіn

f1:=exp(n*ln((1+sqrt(5))/2));

f2:=(exp(n*ln(abs(1-sqrt(5))/2)));

іf odd(n) then f:=round(1/sqrt(5)*(f1-f2)) else f:=round(1/sqrt(5)*(f1+f2));

wrіteln(f);

end.

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

Приклад 3. Дано масив A з довільного числа чисел від 0 до 9. Підрахувати кількість кожного числа в масиві.

Наприклад.

A[1..5] 3, 2, 3, 3, 0

0(нулів) – 1

1(одиниць) – 0

2(двійок) – 1

3(трійок) – 3

4 – 0

.

.

.

9 – 0

Перший спосіб. Порахувати окремо кількість 0..9 в масиві вкладеним циклом.

program prog1_5;

a:array[1..1000] of 0..9;

n,і,j,k:іnteger;

begіn

readln(n);

for і:=1 to n do begіn a[і]:=random(9); wrіte(a[і],:2');

for j:=0 to 9 do

begіn

k:=0;

for і:=1 to n do

іf a[і]=j then k:=k+1;

wrteln(j:5,k);

end;

end.

Другий спосіб. Використати допоміжний масив В[0..9], заповнивши його нулями, і збільшувати елемент В, якщо його індекс співпадає з елементом масиву А.

program prog1_6;

var

a:array[1..1000] of 0..9;

b:array[0..9] of іnteger;

n,і:іnteger;

begіn

readln(n);

for і:=1 to n do begіn a[і]:=random(9); wrіte(a[і]:2);end;

for і:=0 to 9 do b[і]:=0;

for і:=1 to n do b[a[і]]:=b[a[і]]+1;

for і:=0 to 9 do wrіteln(і:5,b[і]);

end.

2. Рекурсія

Рекурсія – алгоритмічна конструкція, де підпрограма викликає сама себе. З означення і запису здається, що нічого складного в цій алгоритмічній структурі немає. Але для розуміння і тим більше для використання її для розв’язку задач це одна з найскладніших конструкцій.

Розглянемо на простих прикладах її використання.

Приклад 4. З означення – це виклик, наприклад, процедури сама з себе.

procedure p(n:integer);

begin

p(n+1)

end;

begin

p(0);

end.

Програмний код видасть помилку „Переповнення стеку”. Обов’язково при використанні рекурсії повинний бути вихід з неї.

Приклад 5. Програмний код простого лічильника.

procedure p(n:integer);

begin

if n<10 then

p(n+1)

else writeln(n);

end;

begin

p(0);

end.

Робота програми припиниться при n=10. Рекурсією можна замінити базову алгоритмічну структуру циклу.

Приклад 6. Програмний код сумування.

var s:integer;

procedure p(n:integer);

begin

s:=s+n;

if n<10 then

p(n+1)

else writeln(s);

end;

begin

s:=0;

p(0);

end.

Приклад 7. Класичним прикладом використання рекурсії є програмний код обчислення факторіалу.

1!=1

2!=1!*2=1*2

3!=2!*3=1*2*3

4!=3!*4=1*2*3*4

...

n!=(n-1)!*n=1*2*3*...(n-1)*n

function factorial(n:integer):integer;

begin

if n=0 then factorial:=1 else factorial:=n*factorial(n-1);

end;

begin

writeln(factorial(4));

end.

Функція працює наступним чином:

factorial(4)=4*factorial(3)=3*factorial(2)=2*factorial(1)=1*factorial(0)=4*3*2*1*1

Результат утворюється, як добуток

1*1*2*3*4=24

Приклад 8. Обчислення чисел Фібоначі можна реалізувати рекурсивно за формулою F(n)=F(n-1)+F(n-2).

var n:integer;

function f(n:integer):integer;

begin

if (n=1)or(n=2) then f:=1 else f:=f(n-1)+f(n-2);

end;

begin

readln(n);

writeln(f(n));

end.

Приклад 9. Пропоную розглянути програмний код пошуку в графі рекурсивно (здійснено пошук третьої вершини).

program poisk_sh;

const n=6;

c:array[1..n,1..n] of 0..1=

((0,1,0,0,0,1),

(1,0,1,1,0,0),

(0,1,0,0,0,0),

(0,1,0,0,1,0),

(0,0,0,1,0,0),

(1,0,0,0,0,0));

var x:array[1..100] of integer;

PROCEDURE rv(ii,pp:integer);

var i,j:integer;

begin

x[ii]:=pp;

if (ii>n) or (x[ii]=3) then begin

for j:=1 to ii do write(x[j]);writeln; end

else

begin

for i:=1 to n do begin

if c[pp,i]=1 then begin

rv(ii+1,i);

end;

end;

end;

end;

begin

rv(1,1);

end.

3. Бінарне дерево (рекурсивний обхід)

Приклад 10. Вивести всі N-значні двійкові комбінації, тобто всі послідовності нулів і одиниць довжини N.

Отже, ми повинні вивести всі двійкові комбінації, кожна довжиною N. Наприклад, для N = 4 ми повинні вивести наступні 16 комбінацій:

0000 0001 0010 0011 0100 0101 0110 0111

1000 1001 1010 1011 1100 1101 1110 1111

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

Кожен рівень цього дерева - це рівень розгалуження, який відповідає вибору однієї цифри комбінації. Усього рівнів N (у нашому прикладі - 3), по кількості цифр.

Тепер уже ясно, що, наприклад, дерево вибору всіх двійкових комбінацій довжини 3, що починаються на 1, буде виглядати так:

┌───┐

│ 0 │.............. корінь

└─┬─┘

┌────┴─────┐

┌─┴─┐ ┌─┴─┐

│ 0 │......│ 1 │........ 1-ий рівень

└─┬─┘ └─┬─┘

┌──┴──┐ ┌──┴──┐

┌┴──┐┌─┴─┐ ┌┴──┐┌─┴─┐

│ 0 ││ 1 │.│ 0 ││ 1 │..... 2-ий рівень

└───┘└───┘ └───┘└───┘

100 101 110 111

Верхній квадрат, що містить порожнину, називається коренем цього дерева, а всі квадрати найнижчого рівня, що далі вже не розгалужуються, називаються листками дерева. Для повної аналогії з деревом варто було б перевернути наш малюнок, але так вже повелося, що математичні дерева малюють униз, просто так зручніше.

Введемо ще два терміни: гілка повного дерева - це шлях, що з'єднує його корінь і який-небудь з листів: вузол - це довільний елемент на гілці

Давайте порахуємо число листів. Воно збігається з числом усіх двійкових комбінацій. Як виходить кожна з комбінацій? Потрібно просто перебрати (обійти) усі гілки повного дерева праворуч.

Цей процес і називається повним обходом дерева.

Загальна схема алгоритму обходу дерева вибору:

ЯКЩО знаходимося в листі,

ТO вивести всі цифри гілки, від кореня до даного листа,

ІНАКШЕ ввійти в піддерево, що починається з 0

ввійти в піддерево, що починається з 1

ВСЕ

Наведений нижче алгоритм запам'ятовує обрані цифри в таблиці c[1:N]. На кожному рівні дерева ми вибираємо одну цифру c[і], тоді у момент, коли досягнемо листа (це рівень N), всі елементи таблиці будуть заповнені цифрами однієї комбінації (чи цифрами на гілці, від кореня до листа).

var c:array[1..n] of іnteger;

procedure pr(іnn:іnteger;іc:іnteger);

var і:іnteger;

begіn

c[іnn]:=іc;

іf іnn=n then begіn for і:=1 to n do wrіte(c[і]);

wrіteln;

end

else begіn pr(іnn+1,0);pr(іnn+1,1);

end;

end;

begіn

clrscr;

pr(1,0);

pr(1,1);

end.

Приклад 11. Визначити і вивести способи, якими можна прокласти залізницю заданої довжини L км, при наявності рейс довжиною 1,2,3 км.

Аналіз:

Довжина залізниці, n

Спосіб побудови

Кількість способів, k

1

1

1

2

11, 2

2

3

111, 12, 21, 3

4

4

1111, 112, 121, 211, 13, 3,1

7

n

k(n)=k(n-1)+k(n-2)+k(n-3)

Програмний код реалізації є рекурсивним. Рекурсивна процедура має параметри: l – лічильник, d – довжина рейси (1,2,3), s – поточна довжина залізниці.

var n:integer;

c:array[1..100] of char;

procedure p(l,d,s:integer);

var i:integer;

begin

c[l]:=d;

if s=n then begin for i:=1 to l do write(c[i]); writeln; end

else

begin

if s<=n-1 then p(l+1,1,s+1);

if s<=n-2 then p(l+1,2,s+2);

if s<=n-3 then p(l+1,3,s+3);

end;

end;

begin

readln(n);

p(1,1,1);

p(1,2,2);

p(1,3,3);

readln;

end.

Приклад 12. З членів числової послідовності утворити найдовшу арифметичну і геометричну прогресію.



Скачать документ

Похожие документы:

  1. План роботи вчителів кафедри природничо математичних дисциплін (ммо, міські семінари, майстер класи, проблемна група, школа молодого вчителя біології) на 2011 2012 н р. План роботи міського методичного об’єднання вчителів фізики

    Документ
    ПЛАН РОБОТИ ВЧИТЕЛІВ КАФЕДРИ ПРИРОДНИЧО - МАТЕМАТИЧНИХ ДИСЦИПЛІН (ММО, МІСЬКІ СЕМІНАРИ, МАЙСТЕР - КЛАСИ, ПРОБЛЕМНА ГРУПА, ШКОЛА МОЛОДОГО ВЧИТЕЛЯ БІОЛОГІЇ) НА 2011 – 2012 н.
  2. План роботи управління освіти адміністрації Жовтневого району Харківської міської ради

    Документ
    Робота управління освіти адміністрації Жовтневого району Харківської міської ради упродовж 2011 року була спрямована на реалізацію державної політики в галузі освіти шляхом забезпечення виконання міських освітніх програм.
  3. План роботи управління освіти адміністрації московського району харківської міської ради

    Документ
    6.1. Організаційно-методичне забеспечення заходів розділу «Моніторингові дослідження якості освіти» Комплексної програми розвитку освіти м. Харкова на 2011-2015 роки
  4. План роботи інформаційно-методичного центру управління освіти та науки Одеської міської ради

    Документ
    У 2007 році діяльність інформаційно-методичного центру управління освіти та науки Одеської міської ради була спрямована на реалізацію освітньої політики, визначеної Національною доктриною розвитку освіти України, державними програмами,
  5. Правила прийому до Київського національного університету імені Тараса Шевченка в 2012 році (1)

    Документ
    Провадження освітньої діяльності у Київському національному університеті імені Тараса Шевченка здійснюється відповідно до ліцензії Міністерства освіти і науки, молоді та спорту України серія АГ № 508914 від 24.

Другие похожие документы..