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

програмування в С++

Школа олімпійського резерву з інформатики
Оголошення PDF Печать E-mail
Добавил(а) Administrator   
15.09.10 10:12

Реєструйтеся в школі

Заповнюйте анкету

Виконуйте вступну роботу

Відправляйте розв'язки

Успіхів у роботі!!!

 
Вступна робота 2010 PDF Печать E-mail
Добавил(а) Гісь ІВгор Володимирович   
10.09.10 13:24

Вступна робота

1. Як за допомогою скляних трилітрової і п’ятилітрової банок відміряти об’єм рідини що дорівнює 1) 7 л; 2)12 л; 3)14 л; 4) 1 л.

2. Початкове розташування чорних та білих шашок таке:

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

3.  Записати у вигляді схеми алгоритм вгадування задуманого
числа в проміжку:

1) від 0 до 7;      2) від 0 до 15;    3) від 0 до 31;    4) від 0 до 100.

Під час вгадування можна задавати лише одне із запитань типу: «Ваше число менше за ...?» або ж «Ваше число більше за ...?» Відповіддю на запитання може бути «Так» або «Ні». За яку найменшу кількість кроків можна це зробити? Визначити тин цього алгоритму.

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

1)   15 предметів;

2)   17 предметів;

3)  8 предметів.

Сформулювати виграшну стратегію для першого гравця за наявності будь-якої кількості предметів. Визначити тип Цього алгоритму.

5. Є 12 монет, серед яких одна фальшива. За 3 зважування на терезах без гирок визначити фальшиву монету і відповісти на запитання: «Фальшива монета легша чи важча?» Скласти схему алгоритму, визначити його тип.

6. Скількома способами хлопчик може піднятися по сходах на 5 сходинку, якщо він може підніматися на наступну сходинку, або переступати через одну чи дві сходинки? Сформулювати алгоритм визначення кількості способів сходження на N-ну сходинку.

7. З’ясувати, яка з двох дат передує іншій.

8. За координатами вершин опуклого чотирикутника встановити:

а) його вид (квадрат, ромб, прямокутник, паралелограм, трапеція);

б) чи є він вписаним;

в) описаним.

9. Написати алгоритм пошуку виходу в лабіринті.

10. Задача про вісім ферзів. На шаховій дошці розміром 8x8
розташувати вісім ферзів так, щоб вони не загрожували один
одному.

11. «Ханойські башти». Є три стержні А, В, С та п дисків різного розміру, перенумерованих від 1 до я в порядку зростання їх розмірів. Спочатку всі диски насаджені на стержень А таким чином, що на кожному диску зверху лежить менший за розміром диск. Необхідно перенести всі диски із стержня А на стержень С, враховуючи такі умови: диски можна переносити лише по одному і більший диск не можна ставити на менший. Для цієї операції необхідно скористатися стержнем В. Надрукувати послідовно в сі кроки, вказуючи пари стержнів, які в них використовуються (першим — стержень, з якого знімається диск, другим —  стержень, на який він перекладається). Напишіть для N=4.

 
Школа обдарованих учнів з інформатики PDF Печать E-mail
Добавил(а) Administrator   
09.09.10 15:31

На виконання Державної цільової програми роботи з обдарованою молоддю на 2007-2010 роки, затвердженої постановою Кабінету Міністрів України від 8 серпня 2007 року № 1016, з метою виявлення творчо обдарованих учнів, пропагування алгоритмізації та покращення роботи з підготовки учнів до олімпіади з інформатики на базі ВІППО продовжить роботу школа обдарованих дітей з інформатики. Заняття будуть проходити щоп’ятниці з 15.00 до 17.30 в лабораторії інформатики і заочно на сайті http://schoololymp.byethost32.com  для учнів 8-10 класів за програмою факультативного курсу «Школа олімпійського резерву з програмування» (Автор Лисенко Т.І.)[1]

Перше заняття відбудеться 10 вересня 2010 року о 15.00 в кабінеті інформатики №26 ВІППО.

Додаткову інформацію про роботу школи можна отримати на сайті http://schoololymp.byethost32.com і в методиста лабораторії інформатики Гіся Ігоря Володимировича (контактний телефон (0332) 242225, моб.0509163106, кабінет №26 ВІППО).



[1] 1. Інформатика. Програми для загальносвітніх навчальних закладів. – Запоріжжя: Прем'єр, 2003. – с. 277-283.

 

 
Школа обдарованих дітей з інформатики PDF Печать E-mail
Добавил(а) Гісь І.В.   
30.08.10 08:00

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

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

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

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

-                              ознайомити з розділами: теорія графів, обчислювальна геометрія, лінійне програмування і т.і.;

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

З метою пропагування алгоритмізації і підготовки учнів до олімпіад з інформатики на базі Волинського ІППО в лабораторії інформатики працює школа для обдарованих дітей. Заняття проводяться для учнів  8-11 класів за програмою факультативного курсу «Школа олімпійського резерву з програмування. 9-11 класи» (Автор Лисенко Т.І.)[1]

 

 

На заняттях розглядаються і опрацьовуються наступні теми:

1.     Поняття мови програмування, їх класифікація. Мова програмування Pascal .

2.     Середовище програмування Delphi. Можливості використання вбудованого редактора.

3.     Структура програми мовою Паскаль. Операції виведення.

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

5.     Оператори управління. Оператор розгалуження та безумовного переходу. Проста і складена умови. Оператор множинного вибору.

6.      Цикли. Організація циклів.

7.      Масиви. Одновимірний масив. Опрацювання елементів одновимірного масиву. Організація пошуку елементів із заданими властивостями в масивах.

8.     Найпростіші алгоритми сортування масивів: метод “бульбашки”, метод прямого вибору.

9.     Двовимірний масив. Опрацювання елементів двовимірного масиву.

10. Рядкові дані. Процедури та функції опрацювання рядкових величин.

11. Текстові файли. Опрацювання текстових файлів.

12. Підпрограми. Процедури в мові PASCAL. Структура процедури. Підпрограми-функцiї. Структура функції. Поняття рекурсії

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

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

1.      В мішку у Діда Мороза лежать цукерки трьох видів: шоколадні, іриски і льодяники. Дід Мороз знає, що якщо вийняти будь-які 100 цукерок з мішка, то серед них обов'язково знайдуться цукерки всіх трьох видів. Яка найбільша кількість цукерок може бути в мішку у Діда Мороза?

Розв’язок

Якщо цукерок одного виду буде 100 і більше, то можна взяти всі сто цукерок одного виду. Отже цукерок одного виду менше сто. Якщо цукерок одного і другого виду буде по 50, то можна взяти всі сто цукерок лише двох видів. Отже цукерок одного виду менше 50, а точніше 49 .

Загальна сума цукерок 148, тому що,

1 вид

2 вид

3 вид

Сума

49

49

2

100

1

49

50

100

49

1

50

100

 

2.     Маємо 8 монет однакової вартості, серед них одна фальшива. Відомо, що фальшива монета трохи легша за інші. Як визначити фальшиву монету двома зважуваннями на терезах з двома шальками без гирок?

Розв’язок

Здійснимо два зважування, взявши у перше зважування по 3 монети на кожну шальку  а, у друге зважування по 1-й монеті на шальку.

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

Якщо у результаті першого зважування  монети будуть однакові переходимо до наступного зважування.

Якщо у результаті другого зважування виявляємо легшу монету, тоді виводимо.

3.     Дано п'ять мішків, помічених літерами А, Б, В, Г та Д, у яких знаходиться дріб вагою 1г, 2г, 3г, 4г та 5г (у кожному мішку дріб однакової ва­ги). Маємо також терези, що можуть визначати точну вагу покладеного на них предмета. Потріб­но з кожного мішка витягти можливо меншу кількість дробин так, щоб за результатами одно­го зважування визначити, у якому мішку який дріб знаходиться.

Розв’язок

Десяткова система:

1,10,100,1000,1000 дробин.

12345, 21345, ....

Можна використати іншу систему числення, наприклад п’ятіркову.

4.     Переставити значення змінних місцями без використання допоміжної змінної.

Розв’язок

Кроки

Дія

x

y

 

 

2

3

1.

x:=x+y

2+3

3

2.

y:=x-y

5

5-3

3.

y:=x-y

5-2

2

 

 

3

2

5.     Задати два дійсних числа і замінити їх. Якщо перше менше,  то перше добутком, а друге сумою. Якщо друге менше рівне,  то навпаки, перше сумою, друге добутком.

Розв’язок

Оптимальним був би розв’язок без використання допоміжних змінних

якщо x

 

6.     Обчислити суму n елементів числового ряду: 1,2,4,7,11,…

Розв’язок

S:=0;

A:=1;

Для і:=1 до n пц

S:=S+A

A:=A+i

Кц.

7.     Обчислити суму n елементів числового ряду: 1,2,5,14,42,132,…

Розв’язок

Це числа Каталана, які обчислюються за формулою

n=9

1

2

5

14

42

132

429

1430

4862

 

8.     Вивести на екран ряд простих чисел на проміжку від 2 до N використовуючи решето Ератосфена.

Розв’язок

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

0

2

3

0

5

0

7

0

9

0

11

0

13

0

15

0

17

0

19

0

0

2

3

0

5

0

7

0

0

0

11

0

13

0

15

0

17

0

19

0

 

9.     Виконати операції з «довгими числами» (кількість цифр до 1000):

-                              зчитати «довге число» з текстового файлу, як послідовність цифр в масив;

-                              додати два «довгих числа» однакової довжини (однакова кількість цифр);

-                              додати два «довгих числа»  різної довжини;

-                              помножити «довге число» на одноцифрове число;

-                              перемножити два «довгих числа» одне на одне.

Такого типу задачі:

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

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

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

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

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

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

 

Література

1.       Інформатика. Програми для загальносвітніх навчальних закладів. – Запоріжжя: Прем'єр, 2003.

2.        Караванова Т.П. Основи алгоритмізації та програмування: 777 задач з рекомендаціями та прикладами: Навч. посіб. Доп. та випр. – К.: Генеза, 2006. – 288 с.: іл.

3.        Караванова Т.П. Методи побудови алгоритмів та їх аналіз: необчислювальні алгоритми: Навч. посіб. – К.: Генеза, 2006. – 224 с.: іл.

4.        Караванова Т.П. Методи побудови алгоритмів та їх аналіз: обчислювальні алгоритми: Навч. посіб. – К.: Генеза, 2008. – 334 с.: іл.

 



[1] 1. Інформатика. Програми для загальносвітніх навчальних закладів. – Запоріжжя: Прем'єр, 2003. – с. 277-283.

 
Зареєструйся і запропонуй задачу!!! PDF Печать E-mail
Добавил(а) Administrator   
28.05.10 15:47

Літо...

Багато вільного часу...

Розв'язуємо цікаві задачі...

Пропонуйте запитання, завдання...

Будем вирішувати і працювати разом...

 
Олімпіадна задача "Криза" PDF Печать E-mail
Добавил(а) Administrator   
14.05.10 13:21

Криза

(XXIII Всеукраїнська олімпіада з інформатики, другий тур)

«Знав би прикуп, жив би в Ялті»

Петро

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

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

Вхідні дані Перший рядок вхідного файлу CRISIS.DAT містить два цілих числа N (1N≤50 000) – довжина кризи у днях та (1S≤100 000) – сума початкових заощаджень Петра. Наступні N рядків містять по два натуральних числа, які не перевищують 1 000 000:

1.     Перше число – кількість олімпів, за які у цей день можна було придбати один галакт.

2.     Друге – кількість олімпів, які можна отримати, продавши один галакт цього дня. Друге число не перевищує перше.

Вихідні дані Єдиний рядок вихідного файлу CRISIS.SOL має містити одне ціле число – найбільшу суму грошей в олімпах, яку міг би мати Петро по закінченню останнього дня кризи. Гарантовано, що відповідь на кожен з тестів журі не буде перевищувати 1018.

Оцінювання Щонайменше у 25% тестів буде виконуватись додаткове обмеження N≤20.

Щонайменше у 75% тестів буде виконуватись додаткове обмеження N≤2000.

Приклад вхідних та вихідних даних

CRISIS.DAT

CRISIS.SOL

3 1000

100 99

110 105

90 80

1050

 

 
Список сайтів, пов’язаних с задачами і олімпіадами по програмуванню PDF Печать E-mail
Добавил(а) Administrator   
13.05.10 08:54

Література

1. Гісь І.В. Обчислювальна геометрія

2. Омелян П.П. Обчислювальна геометрія

Список сайтів, пов’язаних с задачами і олімпіадами по програмуванню:

  • http://vippo.lutsk.ua/vippo-olimp    – Волинська Інтернет-олімпіада з програмування
  • http://www.school-olymp.narod.ru    – школа олімпійського резерву при ВІППО
  •  http://www.olymp.vinnica.ua   – Всеукраїнські Інтернет-олімпіади з різних предметів (фізика, інформатика). На сайті розміщена цікава інформація про Всеукраїнські олімпіади по інформатиці, фізиці. Проводилася мережна олімпіада по інформатиці.
  • http://www.uoi.in.ua  – Всеукраїнська олімпіада з інформатики
  • http://www.e-olimp.com.ua E-Olimp система підготовки та проведення олімпіад зі спортивного програмування
  • http://www.qbit.org.ua/ -Молодёжное научное общество QBit - Кубит - г. Харьков
  • http://algolib.chat.ru  –алгоритми: методи розв’язання
  • http://algolist.manual.ru  –алгоритми: методи розв’язання
  • http://olympiads.win.true.nl/ioi  – Міжнародна олімпіада з інформатики
  • http://www.olympiads.ru  - Події, задачі, тести, рішення, коментарі. На сайті також можна викачати бібліотеку для написання "перевірялок" до задач - Testlib.
  •  http://neerc.ifmo.ru/School/  - На цьому сайті міститься інформація про олімпіади школярів по інформатиці, які проходять в Росії, в яких беруть участь  Петербурзькі школярі
  •  http://www.olympiada.km.ua/ - Задачі заочних і обласних олімпіад Хмельницької області. Архіви турнірів, конкурсів. Багато іншої корисної інформації.
  •  http://comp-science.narod.ru/ - Матеріали олімпіад школярів по програмуванню в Пермській області; підготовка до олімпіад по програмуванню; дидактичні матеріали по алгебрі і геометрії; технологія генерації дидактичних матеріалів по математиці; дидактичні матеріали по інформатиці (задачі, тести); методична скарбничка; посилання на освітні ресурси Internet.
  •  http://acm.timus.ru -  Тут ви можете знайти деяку кількість задач з різних змагань. Перевіряюча система дозволяє вам перевірити ваш розв’язок для кожної задачі.
  •  http://www.informatics.ru/ - Даний сайт присвячений російським олімпіадам школярів по інформатиці. Автори сайту - члени журі і наукового комітету Всеросійської олімпіади, а також тренери збірної команди Росії для міжнародної олімпіади. Тут викладаються матеріали Всеросійських олімпіад, учбово-тренувальних зборів по інформатиці, різні книги і статті, присвячені даній тематиці.
  •  http://g6prog.narod.ru - Сайт присвячений докладному розбору олімпіадних задач по інформатиці. Рівень задач від міської до міжнародної олімпіад. Програмні тексти до задач не додаються (представлений словесний опис рішення). До деяких задач додаються тести. Є багато корисних книг по олімпіадних задачах і велика кількість посилань на аналогічні ресурси.
  •  http://byoi.narod.ru - Архів республіканських, міських, районних олімпіад, зборів до IOI. Підбір рідкісних, ефективних алгоритмів.
  •  http://homepages.compuserve.de/chasluebeck - Дуже великий архів задач по інформатиці на російській мові.
  •  http://www.stream.newmail.ru/index.html - Тут можна отримати відповідь на питання про олімпіади, взнати останні новини, підготуватися до олімпіад. На сайті є бібліотека книг і докладний каталог ресурсів.
Последнее обновление 11.11.10 20:04
 
Школа обдарованих дітей з інформатики PDF Печать E-mail
Добавил(а) Administrator   
12.05.10 09:10

        На виконання Державної цільової програми роботи з обдарованою молоддю на 2007-2010 роки, затвердженої постановою Кабінету Міністрів України від 8 серпня 2007 року № 1016, з метою виявлення творчо обдарованих учнів, пропагування алгоритмізації та покращення роботи з підготовки учнів до олімпіади з інформатики на базі ВІППО в 2009-20010 н.р. продовжить роботу школа обдарованих дітей з інформатики. Заняття будуть проводись щоп’ятниці з 1500 до 1700 в лабораторії інформатики і заочно на сайті www.school-olymp.narod.ru для учнів 8-11 класів за програмою факультативного курсу «Школа олімпійського резерву з програмування» (Автор Лисенко Т.І.)  Додаткову інформацію про роботу школи можна отримати на сайті www.school-olymp.narod.ru і в методиста лабораторії інформатики Гіся Ігоря Володимировича (контактний телефон 4-22-25, моб.0509163106, кабінет №24 ВІППО).

Последнее обновление 21.06.10 11:34
 


Страница 26 из 26

Статистика

Пользователей : 152
Статей : 220
Просмотрено статей : 88159

Вход/Регистрация

Нет