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

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

Школа олімпійського резерву з інформатики
Мова програмування С, С++ » PDF Печать E-mail
Добавил(а) Administrator   
21.09.11 09:55

«Мова програмування С, С++ »

методист лабораторії інформатики ВІППО Гісь Ігор Володимирович

Мета спецкурсу:

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

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

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

№

Тема

План

Засоби

1.

Розділ «Алгоритмізація і програмування»

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

-                      «+» і «-» вивчення розділу

-                      тематика вивчення: 1) базові структури алгоритмів; 2)методика складання алгоритмів та їх аналіз; 3) об’єктно-орієнтоване програмування, візуальне програмування.

-                      принцип IPO (input procedure output): визначення місцезнаходження і введення даних; задання операцій над даними; виведення результуючих даних

-                      етапи розв’язування задач з використанням ЕОМ.

презентація «Алгоритмізація і програмування»

 

мозковий штурм

 

аналіз схеми «людина-задача-алгоритм-програма-комп’ютер»

 

додаток: Етапи розв’язування задач

2.

Мови програмування

-          структуровані мови програмування

-          С – Деніс Рітчі (1972)

-          C++ - 80-ті роки, Бьяртні страус труп (1979)

-          середовище Borland C++ 3.1

завантаження і робота в середовищі

3.

Лексеми мови програмування

-          алфавіт мови і ключові слова

-          директиви препроцесора (#include)

-          сталі (const назва=значення)

-          змінні і їх типи; (цілі: int спиок змінних; дійсні: float  змінна=значення; символьний char с1=’A’, c2=65; логічний bool false, true)

-          коментарі // ...

         /* ... */

-          перша програма (структура програми)

приклад структури програми

4.

Присвоєння, вирази, функції

-          = аналіз виразів

-          функції math.h

приклади виразів

5.

Введення і виведення даних

-          stdio.h: scanf (“%d”, &a) &змінна – адреса даних puts (“рядок”); %d –int %f – float %c –char %s – рядок символів

-          conio.h: cin >> змінна; cout << «текст»<< p

приклади рядків введення і виведення

6.

Базові структури

-          слідування

-          розгалуження (==, !=, ! – не, && - і, || - або, IF (логічний вираз) команда 1; else команда 2)

-          вибір (switch (вираз) {case ознака 1: команда 1; break; default: команда}

-          цикл: for ( ) {}, while (умова) {}, do команда while (вираз);

-          підпрограми

додаток з задачами:

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

 

7.

Типи даних

-          масиви

-          рядки

-          вказівники

-          файли

 

Єдиний спосіб вивчати нову мову програмування –

писати на ній програми.
Брайен Керніган

 

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

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

 

 

ЗАДАЧІ

Структура програми

#include <stdio.h>

void main()

{

puts("Okey");

}

 

#include <iostream.h>

void main()

{

cout <<"Okey";

}

Слідування

1. Два  резистори  R1  і  R2  з'єднані паралельно. Визначити сумарний  опір за формулою .

2.     Обчислити  відстань  між двома точками з координатами X1,Y1 і X2,Y2  за формулою L=

#include <stdio.h>

#include <math.h>

void main()

{

float x1,y1,x2,y2;

puts("Zadayte x1,y1,x2,y2\n");

scanf("%f%f%f%f",&x1,&y1,&x2,&y2);

float l=sqrt(pow((x1-x2),2)+pow(y1-y2,2));

printf("L=%f\n",l);

}

 

3.   В  рядку  S  символів,  на  сторінці  R рядків. Скільки символів в книжці, у якої N сторінок?

За скільки хвилин учень прочитає книгу, якщо він одну сторінку читає за T хвилин?

#include <stdio.h>

void main()

{

int s,r,n,t;

puts("Zadayte s,r,n, t\n");

scanf("%d%d%d%d",&s,&r,&n, &t);

int a=s*r*n;

printf("A=%d\n",a);

int b=a/t;

printf("B=%d\n",b);

int g,h;

g=b/60; h=b%60;

printf("%d:%d",g,h);

}

4. Скільки  лампочок потрібно, щоб освітити вулицю довжиною D км, як­­­ що стовпи з ліхтарями стоять на відстані V м?

5. Одна  серія фільму по телевізору триває F хв. Скільки часу в годи­­нах необхідно, щоб переглянути N серій?

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

6. Знайти максимальне значення серед двох чисел введених з клавіатури.

#include <stdio.h>

void main()

{

int a,b,max;

printf("a=");

scanf("%d",&a);

printf("b=");

scanf("%d",&b);

if (a>b) max=a; else max=b;

printf("max=%d",max);

}

 

7. Знайти максимальне значення серед трьох чисел введених з клавіатури.

#include <stdio.h>

void main()

{

int a,b,c,max;

printf("a=");

scanf("%d",&a);

printf("b=");

scanf("%d",&b);

printf("c=");

scanf("%d",&c);

 

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

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

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

printf("max=%d",max);

}

8. Введене число перевірити: додатне, від'ємне чи дорівнює нулю.

9. Напишіть програму перевірки знання додавання трьох введених чисел.

10. За трьома сторонами перевірити, чи трикутник прямокутний.

11.Введене число перевірити: менше, більше чи дорівнює воно 100.

12. Перевірити, чи існує трикутник із сторонами A, B, C.

 

 

 

 

 

Цикл

12.Скласти програму виведення на екран квадратiв всiх натуральних чисел менших за 20.

#include <stdio.h>

#include <conio.h>

 

void main()

{

clrscr();

for (int i=1;i<20;i++)printf("%2d*%2d=%4d\n",i,i,i*i);

}

 

13. Скласти програму знаходження суми всiх чисел кратних  трьом  з  вiдрiзка [n,50].

#include <stdio.h>

void main()

{

int n;

printf("n=");

scanf("%d",&n);

int i=48;

int s=0;

while (i>=n)

{

s+=i;

i-=3;

}

printf("S=%d",s);

}

14. Протабулювати функцію f(x)=cos(2x) на проміжку [a,b] розбитого на n проміжків.

#include <stdio.h>

#include <math.h>

void main()

{

const a=0, b=10, n=10;

float h=(b-a)/n;

float x=a;

float y;

while (x<=b)

{

y=cos(2*x);

printf("x=%f y=%f\n",x,y);

x=x+h;

}

}

15.  За заданою формулою члена ряду з номером  k  скласти  програму  обрахунку суми всix членiв ряду , не менших заданого числа  E.

                                      1

                                ───────

                                (2k-1)(2k+1)

16. Скласти програму обчислення добутку членів послідовності D=-1*(1/2)*(-1/3)*(1/4)*(-1/5)*...*(-1/2N-1)*(1/2N).

17. Написати таблицю переведення температури з градусів  по  шкалі Цельсія (С) в градуси шкали Фаренгейта (F) за формулою F=1.8*C+32  для значень від 10 до 20 градусів з кроком 2 градуси.

18. Написати таблицю переведення радіуса в площу круга для  значень  радіуса від 1 до 18 В кроком 2.

19. Написати таблицю відповідності між вагою в фунтах  і  вагою  в кг для значень від 1 до 30 фунтів з кроком 3 фунт (1 фунт = 0.4 кг.)

 

Підрограми

20. Знайти площу чотирикутника заданого сторонами і діагоналлю.

21. Знайти площу чотирикутника заданого координатами вершин.

#include <stdio.h>

#include <conio.h>

#include <math.h>

 

float l(int x0, int y0, int x, int y)

{return sqrt(pow((x-x0),2)+pow((y-y0),2));}

 

float geron(float a, float b, float c)

{ float p=(a+b+c)/2;

return sqrt(p*(p-a)*(p-b)+(p-c));}

 

void main()

{

clrscr();

int x1,y1,x2,y2,x3,y3,x4,y4;

scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);

float a,b,c,s;

a=l(x1,y1,x2,y2);

b=l(x2,y2,x3,y3);

c=l(x1,y1,x3,y3);

s=geron(a,b,c);

a=l(x3,y3,x4,y4);

b=l(x4,y4,x1,y1);

c=l(x1,y1,x3,y3);

s+=geron(a,b,c);

printf("s=%f\n",s);

}

22. Знайти площу многокутника заданого координатами вершин а) вершини задані по порядку; б) вершини задані в довільному порядку.

Площа трикутника: 1)Формула Герона; 2)S=1/2*|(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)|

23.Використовуючи функцію сумування двох чисел, обчислити суму трьох чисел.

#include <stdio.h>

#include <math.h>

 

float suma(int x, int y)

{return x+y;}

 

void main()

{

int a,b,c,s;

scanf("%d%d%d",&a,&b,&c);

s=suma(suma(a,b),c);

printf("%d+%d+%d=%d",a,b,c,s);

}

24.Використовуючи функцію максимального з двох, визначити максимальне з чотирьох чисел.

 

Масив

 

25. Дано лінійну таблицю  із  n  цілих  чисел.  Знайти  суму  S  всіх елементів.

#include <stdio.h>

void main()

{

int a[100];

int i,n,s;

printf("n=");

scanf("%d",&n);

for (i=1;i<=n;i++){printf("a[%d]=",i);scanf("%d",&a[i]);}

s=0;

for (i=1;i<=n;i++) s=s+a[i];

printf("s=%d",s);

}

26. З масиву стерти K-тий елемент.

#include <stdio.h>

void main()

{

int a[100];

int i,n,k,s;

printf("n=");

scanf("%d",&n);

for (i=1;i<=n;i++){printf("a[%d]=",i);scanf("%d",&a[i]);}

printf("k=");

scanf("%d",&k);

for (i=k;i<=n;i++) a[i]=a[i+1];

n--;

for (i=1;i<=n;i++) printf("a[%d]=%d\n",i,a[i]);

}

27. В масив вставити елемент на К-те місце

28. В таблиці а[1..100)]всі елементи рівні 2,3,4 або 5. Написати  програму, яка заміняє 2 на 5, 3 на 4, 4 на 3, 5 на 2.

29. Скласти програму підрахунку суми елементів з непарними номерами  масиву A[1..25].

30. Задано таблиця A[1..N]. Побудувати таблицю  B[1..N],  в  якій  першими розміщені всі від`ємні елементи таблиці A, а потім всі додатні.

31. Дано натуральна таблиця A[1..10]. В таблицю М записати тільки ті числа, остача від ділення яких на 3 рівна 1, а на 5 рівна 2.

32. Заданий одномірний числовий масив. Визначити суму добутків  всіх  пар  сусідніх чисел.

33. Дано масив A[1..M]. Скласти програму перестановки місцями елементів з  парними та непарними номерами.

34. Скласти програму запису в таблицю квадратів чисел від 1 до 100.

35. Скласти  програму  підрахунку  кількості  мінімальних  елементів  в масиві A[1..N].

36.В одномірному числовому масиві всі від`ємні елементи замініть  нуля ми.

37. Перевірити, чи є одномірний числовий масив упорядкованим по зростанню.

Рядки

 

38. Знайти подвійні пропуски і знищити їх.

39. Знайти найдовше слово, слова  заданої  довжини  N,  слова  які  містять літеру M.

40. В заданому тексті знищити частину тексту поміщену в дужках.

41. Із тексту вибрати а) цифри; б)числа і вивести їх по порядку.

 

Операції над адресами. Вказівники.

 

Задача 1.

Змінна - 25

Адреса – 0xfff4

 

#include <iostream.h>

void main()

{

int a=25;

cout <<”Zminna”<<a<<"\n";

cout <<”Adress”<<&a<<"\n";

 

}

 

Задача 2.

Порівння типів, стосовно використання пам’яті.

#include <iostream.h>

 

void main()

{

int *a;

float *b;

char *c;

cout <<"int    "<<sizeof(a)<<"\n";

cout <<"float  "<<sizeof(b)<<"\n";

cout <<"char   "<<sizeof(c)<<"\n";

 

 

int a1;

float b1;

char c1;

cout <<"int    "<<sizeof(a1)<<"\n";

cout <<"float  "<<sizeof(b1)<<"\n";

cout <<"char   "<<sizeof(c1)<<"\n";

}

 

Задача 3.

Введення і виведення змінної заданої вказівником.

#include <stdio.h>

void main()

{

float *a;

*a=3.14;

printf("a=%f\n",*a);

printf("a=%p\n",a);

scanf("%f",a);

printf("a=%f\n",*a);

}

Задача 4.

Виділення і вивільнення пам’яті.

#include <stdio.h>

void main()

{

int *a=new int;

*a=5;

int *b=new int(10);

printf("a=%d b=%d\n",*a,*b);

a=b;

printf("a=%d b=%d\n",*a,*b);

delete(b);

printf("a=%d \n",*a);

}

 

В С (tdlib.h, alloc.h ) malloc, calloc для надання динамічної пам’яті, free – вивільнення пам’яті.

 

Файли.

Задача  5. Обчислити суму.

#include <fstream.h>

void main()

{

ifstream inp;inp.open("input.dat");

int a,b,c;

inp>>a>>b;

inp.close();

c=a+b;

ofstream out;out.open("output.sol");

out<<c;

out.close();

}

Задача  6.

Рядок вивести в стовпчик і в зворотному порядку.

#include <fstream.h>

#include <string.h>

 

void main()

{

ifstream inp;inp.open("input.dat");

char a[100];

inp>>a;

inp.close();

strrev(a);

ofstream out;out.open("output.sol");

for (int i=1;i<=strlen(a);i++) out<<a[i]<<\n;

out.close();

}

 Задача  7. В таблиці NxM знайти суму кожного рядка і стовпця.

#include <stdio.h>

#include <fstream.h>

 

void main()

{

int n,m,i,j,s;

int a[100][100];

ifstream inp;inp.open("input.dat");

inp>>n>>m;

for (i=1;i<=n;i++)

for (j=1;j<=m;j++)

inp>>a[i][j];

inp.close();

 

 

for (i=1;i<=n;i++)

{

for (j=1;j<=m;j++)

printf("%d ",a[i][j]);

printf("\n");

}

Задача 4. Зчитати з файлу всі дані і вивести їх на екран.

#include <iostream.h>

 

void main()

{

ifstream inp;inp.open("input.dat");

while (!inp.eof())

{

char *a=new char[1000];

inp>>a;

cout <<a<<"\n";

delete [] a;

}

inp.close();

}

 
 
Вступна робота 2011 PDF Печать E-mail
Добавил(а) Administrator   
09.09.11 13:09

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

1. Хто сидить поруч з мамою Марії?

На лавці сидить Марія, її мама, бабуся і лялька. Бабуся сидить поруч з внучкою, але не поруч з лялькою. Лялька не сидить поруч з мамою. Хто сидить поруч з мамою Марії?

2. Що виросте у розгубленої господарки?

У розгубленої господарки є 3 ящики для розсади з надписами:” Огірки”, „Квіти”, „Ромашки”. Вона посадила насіння ромашки, огірків і дзвіночків в ці ящики так, що всі надписи на ящиках виявились невірними. Що виросте в ящику з надписом” Ромашки”?

3. Переможці олімпіад.

П’ятеро однокласників: Ірина, Тарас, Катя, Сергій і Микола стали переможцями олімпіад школярів з фізики, математики, інформатики, літератури та географії. Відомо, що:

- переможець олімпіади з інформатики вчить Іірину і Тараса працювати на комп’ютері;

- Катя і Сергій також зацікавились інформатикою;

- Тарас завжди побоювався фізики;

- Катя, Тарас і переможець олімпіади з літератури займаються плаванням;

- Тарас і Катя привітали переможця олімпіади з математики;

- Іра шкодує, що в неї залишається мало часу на літературу.

Переможцем якої олімпіади став кожен з учнів?

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

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

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


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

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

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

7. Серед трьох монет одна фальшива (вона легше, ніж дві інші однакової ваги). За допомогою одного зважування на терезах (без гир) знайти фальшиву монету.

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

9. Фальшива монета

З 60- ти однакових за виглядом монет одна відрізняється від інших за масою. За допомогою двох зважувань без гир визначити: важча вона чи легша від справжніх?

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

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

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

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

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

в) описаним.

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

14. Плитка шоколаду складається з 35 квадратиків (7 5). Ламають по прямих, які ділять квадратики до тих пір, поки не одержать окремі 35 квадратиків. Скільки разів потрібно поділити шоколадку?

14. Трьом учням в темній кімнаті одягли на голову по чорній шапці. Перед ними поставлено завдання відгадати, хто в якій шапці, якщо всього шапок 15, причому 2 з них - сірі, а 3 - чорні. Сірі шапки сховали перед тим, як у кімнаті запалили світло. Через деякий час один учень відгадав, що він стоїть в чорній шапці. Як він це зробив?

16. Яку найбільшу кількість слонів можна розташувати на шаховій дошці, щоб ані один із слонів не був під подвійною бійкою?

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

18. «Ханойські башти». Є три стержні А, В, С та п дисків різного розміру, перенумерованих від 1 до я в порядку зростання їх розмірів. Спочатку всі диски насаджені на стержень А таким чином, що на кожному диску зверху лежить менший за розміром диск. Необхідно перенести всі диски із стержня А на стержень С, враховуючи такі умови: диски можна переносити лише по одному і більший диск не можна ставити на менший. Для цієї операції необхідно скористатися стержнем В. Надрукувати послідовно в сі кроки, вказуючи пари стержнів, які в них використовуються (першим — стержень, з якого знімається диск, другим — стержень, на який він перекладається). Напишіть для N=4.
 
Задачі 09.09.2011 (заняття 1) PDF Печать E-mail
Добавил(а) Administrator   
09.09.11 13:04

Задача 1. Затори на дорогах (JAMMING)

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

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

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

Формат вхідних даних:

Вхідний файл містить єдине число S (1<=S<=10000) – задана відстань.

Формат вихідних даних:

Єдиний рядок вихідного файла повинен містити відповідь – кількість розстановок тур.

Достеменно відомо, що кількість цифр у відповіді не перевищує 700.

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

JAMMING.DAT

JAMMING.RES

2

4

 

 

 

Задача 2. Збирання мита (TALLAGE) -70 балів.

Король країни Аріїв завоював N міст на території сусідніх держав.

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

Вхідні дані:

Перший рядок вхідного файлу містить натуральне число N – кількість міст у країні, а також цілі числа X та Y – координати столиці.

Наступні N рядків містять через проміжок координати Xi , Yi завойованих міст.

Вихідні дані:

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

Наступні рядки мають містити у довільному порядку список побудованих доріг у форматі:

<номер міста> => <номер міста>

При цьому столицю позначте номером 0.

Якщо відповідей декілька, виведіть одну довільну з них.

Приклади:

TALLAGE.DAT

TALLAGE.SOL

6 0 0

1 1

-1 1

0 2

1 -1

-1 -1

0 -2

8.485

2 3

3 1

1 0

0 4

4 6

6 5
Последнее обновление 09.09.11 13:08
 
Інформаційний лист PDF Печать E-mail
Добавил(а) Administrator   
07.09.11 12:24

На виконання рішення обласної ради шостого скликання від 28.12.2010 р. №2/38 «Про внесення змін до обласної цільової Програми роботи з обдарованою молоддю на 2007-2010 роки» та з метою пошуку обдарованих дітей, підготовки їх до участі у Всеукраїнській олімпіаді з інформатики залучити учнів, переможців ІІІ етапу Всеукраїнської олімпіади з інформатики для навчання в школі обдарованих дітей з інформатики та додатково в школі обдарованих дітей з математики.

Заняття з інформатики проводяться в середу та п’ятницю з 15.00 до 17.00 в лабораторії інформатики Волинського ІППО і заочно на сайті http://schoololymp.byethost32.com.

Додаткову інформацію про роботу школи можна отримати в методиста лабораторії інформатики Гіся Ігоря Володимировича (контактний телефон (0332) 242225, моб.0509163106, кабінет №24 ВІППО).
Последнее обновление 07.09.11 13:06
 
Список сайтів PDF Печать E-mail
Добавил(а) Гісь   
16.08.11 12:03

1. Разбор олимпиадных задач по информатике от Михаила Густокашина
http://www.g6prog.narod.ru/

Этот сайт посвящен подробному разбору олимпиадных задач по информатике.
Здесь разобраны задачи школьных, городских, областных, Всероссийских,
международных, университетских, ACM олимпиад, а также задачи неопределенного
происхождения и собственного сочинения. Исходные тексты к задачам
не прилагаются. К некоторым задачам прилагаются тесты.
Кроме того имеется отличная подборка книг и статей,
великолепная коллекция ссылок и активно работающий форум.

 

2. http://kievoi.narod.ru/
Официальный сайт Киевских олимпиад по информатике. Содержит архив задач прошлых лет, обширный список материалов и ссылок, а также небольшой

подборку статей. Часть материала из этой подборки практически невозможно найти где-либо ещё в общеизвестных источниках.

 

3. http://acm.timus.ru
Сайт Уральских ACM-олимпиад. Обширный набор авторских задач на разные темы с системой тестирования плюс регулярные соревнования. Исходных

текстов, разборов, тестов – нет.

 

4. http://algolist.manual.ru/
Архив, посвящённый алгоритмам. Представляет собою тематический каталог статей об алгоритмах из разных областей знаний, зачастую с

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

статей переведено на русский язык, однако встречаются исключения. Функционирующий параллельно форум содержит ответы на те вопросы, которым

не нашлось места в статьях:)

 

5. http://alglib.sources.ru/
Проект, аналогичный описанному выше. Количество охваченных алгоритмов и тем слегка меньше, упор ставится на исходные тексты.

 

6. http://olympiads.ru
Сайт, посвящённый олимпиадной информатике. Более всего примечателен тем, что ведёт постоянное отслеживание всех крупных российских

информатических соревнований и предоставляет доступ к их материалам.

 

7. http://acm.mipt.ru
Олимпиады Московского физико-технологического института. Подборка алгоритмов, некоторые книги, небольшой архив задач, система тестирования

El Judge.

 

8. http://topcoder.com
Справедливость требует указать этот ресурс:)
Уникальный проект, посвящённый соревнованиям в компьтерным наукам как таковым, в разных категориях. Центральное направление всё же

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

пунктов, не имеющих аналогов (к примеру, ознакомление с исходными текстами соперников либо призовые баллы за удачно подобранный и внесённый

в основной набор тест и т.д.), несколько поддерживаемых языков (Паскаля на данный момент в списке нет). Каждый год проводится очный тур для

сильнейших.

 

9. http://www.olymp.vinnica.ua/
Всеукраинская ежегодная интернет-олимпиада по информатике

 

10. http://olympiada.km.ua/
Ежегодная интернет-олимпиада по информатике Хмельницкой области

 

11. http://sbs.km.ua/
Довольно часто проводяться турниры для подготовки и тренировки школьников различного уровня

Набор АСМ – сайтов: база задач + изредка проводимые онлайн – олимпиады

12. http://www.e-olimp.com.ua

13. http://acm.timus.ru/

14. http://icpcres.ecs.baylor.edu/onlinejudge/

15. http://acm.mipt.ru/

16. http://acm.lviv.ua/

17. http://acmp.ru/

 

18. http://www.topcoder.com/tc
Сайт, где регулярно (еженедельно) проводяться 75-минутные олимпиады, помогающие повысить как качество написание кода так и умение решать задачи. Также есть множество разобранных алгоритмов и методов программирования, раздел “только для школьников”, лучшие из которого ездят на ежегодную онсайт олимпиаду в США, матчи с более научными задачами и многое другое. Доступные языки: С++, С#, Vsiual Basic, Java, Python.

 

19. http://ace.delos.com/
Сайт команды США на международную олимпиаду. Раз в месяц проводяться олимпиады с разбором, есть большая база задач, разбитая на темы и

перемешанная с теорией, для каждой задачи после решения доступен разбор.

 

20. http://www.hsin.hr/coci/
Сайт подготовки к Всехорватской олимпиаде, ежемесячные олимпиады с разборами

 

21. http://olympiads.ru/
Сайт с задачами и разборами различных российских олимпиад. На нём проводиться Всероссийская интернет – олимпиада. Также есть несколько уроков с разборами алгоритмов, задачами на эти алгоритмы и разборами задач.

 

22. http://neerc.ifmo.ru/school/
Сайт с архивами Всероссийских, СПб олимпиад, регулярно проводяться командные и личные соревнования для подготовки к Всероссийской

 

23. http://code.google.com/codejam/
Ежегодное соревнование под эгидой гугла. Предполагает решение задач любым способом и предоставление верных ответов.

Сергей Могильный:

Только то, чего не указали ранее:

 

24. http://ceoi.inf.elte.hu/
Сайт Центрально-Европейской Олимпиады по Информатике, ежегодно проводится в июне-июле, каждый год есть онлайн трансляция. Там же ссылки на архив прошлых лет.

 

25. http://ioinformatics.org
Сайт IOI, имеются тесты практически ко всем задачам всех лет.

 

26. http://qbit.org.ua/
Архив Харьковских АСМ олимпиад, проверяющая система. Изредка проводятся онлайн трансляции различных чемпионатов.

 
 
Олімпіади з інформатики: корисні сайти PDF Печать E-mail
Добавил(а) Gis   
16.08.11 11:45

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

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

 

Перша адреса:

http://vippoolimp.byethost14.com - Волинська учнівська Інтернет-олімпіада з програмування
 
Задачі на повторення за рік PDF Печать E-mail
Добавил(а) Гісь   
23.05.11 09:22
v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} Normal 0 false false false MicrosoftInternetExplorer4 /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Обычная таблица"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman"; mso-ansi-language:#0400; mso-fareast-language:#0400; mso-bidi-language:#0400;}

Задачі (20.05.2011)

Завдання 1

Є 10 мішків з монетами. Відомо, що в одному з мішків всі монети фальшиві і

кожна з них на 1 грам легша від нефальшивої. За одне зважування на терезах з

гирями визначити, в якому з мішків знаходяться фальшиві монети.

Завдання 2

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

подорожній долає міст за різний час: першому потрібна 1 хвилина, другому – 2 хвилини, третьому – 5 хвилин, а четвертому – 10 хвилин. Якщо подорожні йдуть мостом вдвох, то вони пересуваються з швидкістю найповільнішого з них (наприклад, якщо йтимуть перший і четвертий, то вони здолають міст за 10 хвилин)

Завдання 3

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

Рішення
Ділим монетки на 3 купки по 4 монети
1 2 3 4 5 6 7 8 9 10 11 12
1. Перше зважування 1 2 3 4 і 5 6 7 8
(один варіант)
Якшо 1 2 3 4 = 5 6 7 8 Переходим на крок 2
Якшо 1 2 3 4 > 5 6 7 8 (якшо менше теж підходить але порядок ваги є важливий) переходим на крок 4
2. Друге зважування
(один варіант)
7 8 = 11 12 тобто фальшива є серед 9 і 10, бо 7 і 8 - справжні
7 8 11 12 то фальшива є серед 11 і 12
Переходим на крок 3
3. Третє зважування
(один варіант)
8 = 9 тоді фальшива 9
(8 = 11 тоді фальшива 12)
(другий варіант)
8 10 тоді фальшива 10
(8 11 тоді фальшива 11)
Переходим на крок 12

4. (другий варіант)
1 2 3 4 > 5 6 7 8 (якшо менше теж підходить але порядок ваги є важливий)
Переходим на крок 5
5. Друге зважування
Відкладєм 1 2 3
важим
(Варіант 1)
6. 4 5 6 7 > 8 9 10 11 оскільки монетки 1 2 3 не впливають на зміну ваги - вони справжні, І фальшива є
або 7 або 8. Переходи на крок 9
(Варіант 2)
7. 4 5 6 7 < 8 9 10 11 фальшива монета є серед 4 5 6 і фальшива монета є лекша Переходи на крок 10
(Варіант 3)
8. 4 5 6 7 = 8 9 10 11 фальшива монетка є серед 1 2 3 і фальшива монета є важча Переходи на крок 11
Важим
9. 7 і 12 якшо рівні то фальшива 8, якшо не рівні - фальшива 7-ма
10. 4 і 5 якшо рівні то фальшива 6, якшо 4 лекше за 5 то фальшива 4, якшо 4 важча за 5 то фальшива є 5
11. 1 і 2 якшо рівні то фальшива 3, якшо 1 важче за 2 то фальшива 1, якшо 1 лекша за 2 то вальшиває є 2
12. Кінець

Завдання 4

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

Завдання 5

В таблиці а[1..100)]всі елементи рівні 2,3,4 або 5. Написати програму, яка заміняє 2 на 5, 3 на 4, 4 на 3, 5 на 2.

Завдання 6

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

fibonachi

Завдання 7 DOMINO

Написати програму, яка буде підраховувати кількість варіантів покриття прямокутника 2хN прямокутниками 2х1. Покриття, які перетворюються одне в одне симетріями рахувати різними.

Вхідні дані. Вхідний файл DOMINO.DAT містить число N (0 < N < 65536).

Вихідні дані. Вихідний файл DOMINO.SOL повинен містити одне число: кількість варіантів.

Завдання 8

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

Проте для боротьби із спекулянтами касир продавала не більше 3-х квитків в одні руки, тому домовитися таким чином між собою могли лише 2 або 3 підряд вартих людини.

Відомо, що на продаж i-ій людині з черги одного квитка касир витрачає Ai секунд, на продаж двох квитків — Bi секунд, трьох квитків — Ci секунд. Напишіть програму, яка підрахує мінімальний час, за який могли бути продані квитки для всіх людей черги.

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

Формат вхідних даних

У вхідному файлі записано спочатку число N — кількість покупців в черзі (1<=N<=5000). Далі йде N трійок натуральних чисел Ai, Bi, Ci. Кожне з цих чисел не перевищує 3600. Люди в черзі нумеруються починаючи від каси.

Формат вихідних даних

У вихідний файл виведіть одне число — мінімальний час в секундах, за яке могли бути обслужені всі покупці.

Приклади

Bilet.dat

Bilet.sol

5

5 10 15

2 10 15

5 5 5

20 20 1

20 1 1

12

2

3 4 5

1 1 1

4


Завдання 9

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

Необхідно по заданій послідовності координат руху обчислити суму штрафу.

Вхідні дані: В першому рядку вхідного файлу VIOLATION.DAT записано N - кількість зафіксованих координат руху деякого автомобіля та М - величина штрафу, в наступних рядках координати автомобіля в процесі руху - (хi, уi), і=1,2,...,М, де (х1, у1) - точка початку руху, (хN,уN) - остання точка маршруту автомобіля.

Всі числа цілі та знаходяться в межах від -1000 до 1000.

Вихідні дані: Єдиний рядок вихідного файлу VIOLATION.SOL має містити суму штрафу.

Приклад:

VIOLATION.DAT

VIOLATION.SOL

5 50

0 0

2 0

1 1

5 1

5 -1

50

Завдання 10

Міжнародна конференція

Вас найняли для того, щоб визначити мiсця дипломатiв за столом обговорень мiжнародної конференцiї. На конференцiю запрошенi по одному дипломату з N рiзних країн свiту. Кожен дипломат знає вiд однiєї до М мов. Дипломати, якi не знають спiльної мови, не можуть розмовляти один з одним. До того ж, деякi країни проголосили, що не будуть пiдтримувати дипломатичних стосункiв з деякими iншими, тобто представники цих країн не будуть розмовляти один з одним. Ваше завдання полягає в розробцi програми DIPLOMAT.*, що визначає мiсця за столом для дипломатiв таким чином, щоб кожен мiг розмовляти з обома своїми сусiдами, якi сидять лiворуч та праворуч вiд нього.

Стiл, що використовується, круглий i розрахований на N персон. Дипломат може спiлкуватись з дипломатом, який сидить лiворуч однiєю мовою, а з дипломатом, що сидить праворуч, – iншою.

Вхiднi данi:

В першому рядку текстового файлу DIPLOMAT.DAT – число N. Далi – N рядкiв, по одному рядку на дипломата. Кожен рядок – послiдовнiсть слiв. Сусiднi слова вiдокремленi пропуском. Кожне слово – це послiдовнiсть великих латинських лiтер. Перше слово – код країни – складається з 3 лiтер. Друге слово має довжину вiд 1 до 5 лiтер i представляє перелiк мов, на яких може спiлкуватись дипломат. Кожна мова позначена однiєю лiтерою. Далi iде список з не бiльш як N трилiтерних слiв – кодiв країн, з якими уряд дипломата пiдтримує стосунки.

Вихiднi данi:

До файлу DIPLOMAT.SOL треба вивести список дипломатiв в порядку розмiщення за столом (по одному дипломату в рядку). Кожен рядок складається з 3 слiв: перше – код мови, якою дипломат може спiлкуватись з сусiдом лiворуч, друге – код країни дипломата, третє – код мови для спiлкування з сусiдом праворуч. Можливе iснування декiлькох розв'язкiв. Вам потрiбно знайти один. Якщо розв'язку не iснує, Ваша програма повинна видати таке повiдомлення: NO SOLUTION EXISTS.

Приклад вхiдних даних

Приклад вихiдних даних

10

USA EF CHN GBR USR FRA FRG JPN ISR POR KOR

CHN CFE USA GBR FRA FRG

GBR ER USA CHN USR FRA FRG JPN ISR POR KOR

USR RF USA GBR FRA FRG

FRA F USA CHN GBR USR FRG JPN ISR POR

FRG ERG USA CHN GBR USR FRA JPN ISR POR

JPN JHG USA GBR FRA FRG JPN ISR POR KOR

ISR YER USA GBR FRA FRG JPN KOR

POR PGE USA GBR FRA FRG JPN

KOR KEC USA GBR USR JPN ISR

E USA E

E KOR E

E ISR H

H JPN G

G FRG G

G POR E

E GBR E

E USR F

F FRA F

F CHN E

Завдання 11 GoTo.

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

В синтаксично вірній програмі ключове слово оператора переходу GOTO може стояти або на початку рядка або після пропуску або після одного з символів — ‘;’, ‘:’, ‘}’, а після нього може стояти або пропуск або переклад рядка або символ ‘{‘ (табуляцію як роздільник розглядати не будемо).

Нагадаємо, що окрім позначення дійсно оператора переходу, слово GOTO може зустрічатися в тексті програми в рядкових константах, укладених в апострофи, або в коментарях, причому для простоти вважатимемо, що коментар завжди починається з символу ‘{‘, а закінчується першим що зустрівся після цього символом ‘}’, при цьому символ ‘{‘ повинен знаходитися не усередині рядкової константи. В цих випадках слово GOTO підраховувати не потрібно. Рядкові і прописні букви в Pascal не помітні.

У вхідному файлі goto.in знаходиться текст програми без синтаксичних помилок на мові Pascal. Розмір програми не перевершує 64К. У вихідному файлі goto.out повинне виявитися одне число – кількість операторів GOTO в цій програмі.

Приклад вхідного файлу:

label 1,2;

var I:byte;

begin

1: I:=I+1;

if I>10 then goto 2 else

writeln(¢ goto ¢); GoTo 1;

2: if I<10 then goto 1 {else { goto 2;}

end.

Вихідний файл для наведеного приклад

3

Завдання 12 «Циліндр»

Із аркушу паперу ножицями Ви можете вирізати дві поверхні, з яких можна скласти циліндр наступним чином:

1. Розрізати папір горизонтально (паралельно короткій стороні), отримавши дві прямокутні частини.

2. З першої частини вирізати круг максимального радіуса. Він буде лежати в основі циліндра.

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

За заданими розмірами паперу необхідно побудувати подібним чином циліндр максимального об'єму.

Технічні умови

Вхідні дані

Вхідні дані містять декілька тестів. Кожен тест містить два числа w і h (1 ≤ w ≤ h ≤ 100), які позначають ширину та висоту аркуша паперу. Останні тест містить два нулі і не опрацьовується.

Вихідні дані

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

Приклад

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

10 10
10 50
10 30
0 0

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

54.247
785.398
412.095

 
Синтаксичний розбір виразів PDF Печать E-mail
Добавил(а) Administrator   
22.04.11 14:09

Тема: Синтаксичний розбір виразів

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

              Нагадаємо, що існує цілий ряд  методів  синтаксичного  розбору і обчислення виразів. Нехай вирази є рекурсивними  структурними  даними, які визначаються в термінах самих себе.  Якщо ви обмежитеся використанням у виразах тільки операторів +,  -  * / і дужок,  то зможете сказати, що всі вирази можуть бути визначеними в термінах наступних правил:
              выраз=>терм[+терм][-терм]
              терм=>множник[*множник][/множник]
              множник=>змінна, число або (вираз) де будь-яка частина може бути порожньою.  Квадратні дужки  позначають  необов'язковість,  а => - утворення. Фактично правила є правилами утворення виразів. 
              Вираз             10+5*В складається з двох термів: 10 і 5*В. Проте, включає три множники:  10,  5 і В.  Цими множниками є два числа і одна змінна.
              З другого боку вираз          14*(7-С)   має два  терми 10 і (7-С),  один з яких є числом,  а інша дочірнім виразом. Дочірній вираз розпадається на одне число і одну змінну.
              Даний процес формує основу для рекурсивного низхідного  синтаксичного  розбору,  який є набором загальних  рекурсивних процедур,  що носять характер ланцюжка. На кожному відповідному кроці  синтаксичний розбір може виконувати задані операції в алгебра правильній послідовності. Наприклад розглянемо синтаксичний розбір вхідного виразу 9/3-(100 +56) і виконання операцій по кроках.

      Крок 1. Узяти першу лексему: 9/3

      Крок 2. Узяти обидва множники і виконати операцію поділу.

                     В результаті виходить 3.

      Крок 3. Узяти другу лексему: (100+56). В даній точці ви повинні рекурсивно  проаналізувати другий вираз.

      Крок 4. Узяти обидва числа і скласти. В результаті виходить                      156.

      Крок 5. Повернутися з рекурсивного виклику і відняти 156 з 3, що дає відповідь - 153.

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

 

 

 

 

Рядкові величини

- операція + (з’єднання)                        ‘місто’+’ ’+’Луцьк’

 

Функції роботи з рядками:

 

№

Назва функції

Призначення

Приклад

Результат

1.

Length(S)

визначає кількість символів у заданому рядку

Length (‘місто Луцьк’)

11

2.

Сору(S,n,m)

виділяє m символів рядка S, починаючи від символу з номером n

Copy (‘місто Луцьк’, 6, 5)

‘Луцьк’

3.

Pos(S1, S2)

визначає номер символу, з якого починається входження рядка (тексту) S1 у рядок S2

Pos (‘ ‘,‘місто Луцьк’)

6

4.

Concat(S1, S2,...)

з'єднує рядки в один рядок

Concat('20', '01')

‘2001’

 

Процедури роботи з рядками:

 

№

Назва функції

Призначення

Приклад

Результат

1.

Insert (A:string, var В: string, n:integer)

вставляє рядок А у рядок В, починаючи від позиції з номером n

S1:=’місто’;

S2:=’Луцьк’;

Insert(S1,S2,1);

’містоЛуцьк’;

 

2.

Delete (var S:string, n:integer, m:integer)

вилучає m символів з рядка S, починаючи від позиції n

S:=’містоЛуцьк’;

delete(S,1,5);

’Луцьк’;

 

3.

Str (A:integer, var S:string)

переводить числове дане A у дане типу рядок

A:=2001;

Str(A,S);

‘2001’

4.

Val (S: string, var A, KOD: integer)

засилає у числову змінну A числовий образ рядка S, повертаючи код помилки KOD

S:=’2001’;

Val(S,A,Kod);

2001

 
 
Другие статьи...


Страница 23 из 27

Главное меню

Статистика

Пользователей : 261
Статей : 225
Просмотрено статей : 105532

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

Нет